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

hi,i used range from -10 to +10 ,but got TLE,i am so confused,why??
[cpp]
AC now
[/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
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
thank you very much,i got ac now

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

### 10633 -- Rare easy problem WA

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
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:
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
Experienced poster
Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela
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

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.

UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:
10^18 doesn't work.

Antonio Ocampo
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per
Thanks for replying UFP2161. But, one more question

Why my program doesn

UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:
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
Thanks Guru, bye.

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

### unsigned long long !

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)

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
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
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.