10633 - Rare Easy Problem

[shuniu]

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]

hi,i used range from -10 to +10 ,but got TLE,i am so confused,why??
[cpp]
AC now
[/cpp]

[Adrian Kuegel]

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]

thank you very much,i got ac now

[Ghust_omega]

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 !!

[UFP2161]

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

[Ghust_omega]

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

[Antonio Ocampo]

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

Code: Select all

Cut after AC   :D 

[UFP2161]

10^18 doesn't work.

[Antonio Ocampo]

Thanks for replying UFP2161. But, one more question

Why my program doesn

[UFP2161]

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

[Antonio Ocampo]

Thanks Guru, bye.

[Sedefcho]

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]

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;
}

[shamim]

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.