10633 - Rare Easy Problem

All about problems in Volume 106. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

shuniu
New poster
Posts: 34
Joined: Thu Oct 16, 2003 6:15 pm

Post by shuniu » Mon May 17, 2004 10:53 pm

Here is a proof that finds the answers mathematically,

N = original number
M = N with last digit chopped off
B = the chopped off digit

So that,
N = 10M + B where (0<=B<=9)
N-M = (10M+B)-M = 9M+B

We can calculate
(N-M)%9 = (9M+B)%9 = (9M)%9 + (B)%9 = B%9

If B%9==0, then B can be either 0 or 9,
B=0 implies N-M = 9M, so M = (N-M)/9, and
N = M + (N-M) = (N-M)/9 + (N-M) = (N-M)/9*10 (<-- answer 1)
B=9 implies N-M = 9M+9, N = (N-M)/9 - 1, and
N = M + (N-M) = (N-M)/9 - 1 + (N-M) = (N-M)/9*10 - 1 (<-- answer 2)

If B%9!=0, since 0<=B<=9, it must be that B<9, so B/9 = 0.
So N-M = 9M+B and (N-M)/9 = M + B/9 = M, hence
N = M + (N-M) = (N-M)/9 + (N-M) = (N-M)/9*10 (<-- answer 1)

oulongbin
Learning poster
Posts: 53
Joined: Sat Jul 10, 2004 5:57 pm
Location: Shanghai China

10633 help!

Post by oulongbin » Tue Oct 05, 2004 4:44 am

hi,i used range from -10 to +10 ,but got TLE,i am so confused,why??
[cpp]
AC now :D
[/cpp]
Last edited by oulongbin on Mon Oct 11, 2004 1:32 pm, edited 1 time in total.

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Tue Oct 05, 2004 7:01 am

for(i=obvious_n-10;i<=obvious_n+10;i++)

you get overflow here, since i is declared as int
so this is getting you the TLE.

oulongbin
Learning poster
Posts: 53
Joined: Sat Jul 10, 2004 5:57 pm
Location: Shanghai China

Post by oulongbin » Mon Oct 11, 2004 1:31 pm

thank you very much,i got ac now :D

User avatar
Ghust_omega
Experienced poster
Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela

10633 -- Rare easy problem WA

Post by Ghust_omega » Sat Dec 18, 2004 3:23 am

Hi !! to all , I thinks this problem is easy just I can not find the error,
I use long double in C for read the number %Lf as the same for print
just is %.0Lf is this ok??? :-? , in my solution only I have to ways to
say is this with multiple answers or not

Code: Select all

if (N-m%9==0)
  have two answers
else 
   only one 
this is some I/O please help me
in:

Code: Select all

18
19
20
27
36
345
345
234
23
10000
1000000000000000000
10
80
90
6756756756
3423452353452
53252353225345243
465756865455532
5475665432

56765432478

900
7888
5677
34777
2390
45690
56790
out:

Code: Select all

19 20
21
22
29 30
39 40
383
383
259 260
26
11111
1111111111111111111
11
89
99 100
7507507507
3803835948279 3803835948280
59169281361494714
517507628283924
6084072702
63072702753
999 1000
8764
6308
38641
2656
50767
63099 63100
Thanks in advance
Keep posting !!

User avatar
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 » Sat Dec 18, 2004 4:42 am

Floating point is inaccurate:
19 20
21
22
29 30
39 40
383
383
259 260
25
11111
1111111111111111111
11
88
99 100
7507507506
3803835948279 3803835948280
59169281361494714
517507628283924
6084072702
63072702753
999 1000
8764
6307
38641
2655
50766
63099 63100

User avatar
Ghust_omega
Experienced poster
Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela

Post by Ghust_omega » Sat Dec 18, 2004 5:55 am

Hi !! Thanks for your quick answer I change to unsigned long long and I got AC
Thanks in advance
Keep posting !!

Antonio Ocampo
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per

10633 Rare Easy Problem

Post by Antonio Ocampo » Sun Dec 19, 2004 4:57 am

I got WA. Please what's wrong in my code??

Code: Select all


Cut after AC   :D 

Last edited by Antonio Ocampo on Sun Dec 19, 2004 8:18 pm, edited 1 time in total.

User avatar
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 » Sun Dec 19, 2004 5:04 am

10^18 doesn't work.

Antonio Ocampo
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per

Post by Antonio Ocampo » Sun Dec 19, 2004 8:17 pm

Thanks for replying UFP2161. But, one more question :lol:

Why my program doesn

User avatar
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 » Sun Dec 19, 2004 8:31 pm

Yes, the input is fine with a long long. But some of the intermediate calculations probably went over 2^63-1.

Antonio Ocampo
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per

Post by Antonio Ocampo » Mon Dec 20, 2004 6:35 am

Thanks Guru, bye. :D

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

unsigned long long !

Post by Sedefcho » Thu Feb 10, 2005 6:21 pm

Yes, use unsigned long long.
This is the most natural choice and
the first built-in C++ type I chose to try for this problem.

It works for even bigger numbers in input
( bigger than 10^18 ).

murkho
New poster
Posts: 33
Joined: Mon Mar 28, 2005 6:41 pm

10633 (Rare Easy problem)

Post by murkho » Sat Apr 16, 2005 11:19 am

Hi, here is my code , i don't know why i am given TLE. Pls help me.

Code: Select all

#include<stdio.h>
int main()
{
  unsigned long long int a,b,c,d,n,f,count;
	while(scanf("%llu",&n) && n) 
	{
	a = n;
	b = n/10;
	count = 0;
		while(1)
		{		
		c = a+b;
		d = c - (c/10);
		if(d == n)
		{
			if(!count)
			{
			printf("%llu",c);
			count ++;
			}
			else 
			printf(" %llu",c);

		}
		else if(d>n) break;
		b++;	
		}
	printf("\n");
	}

return 0;
}

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Mon May 02, 2005 7:47 am

Your code takes few seconds to produce results for input like:
4545544554
The output is:
5050605059 5050605060
The right algorithm is use a mathematical formual ( which you seem to be using) to trace one of the solution, the rest lie within (+/-)10 of this.

Post Reply

Return to “Volume 106 (10600-10699)”