## 10633 - Rare Easy Problem

Moderator: Board moderators

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)
shuniu
New poster

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

### 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.
oulongbin
Learning poster

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

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.
Guru

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

thank you very much,i got ac now
oulongbin
Learning poster

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

### 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 answerselse    only one `

in:

Code: Select all
`1819202736345345234231000010000000000000000001080906756756756342345235345253252353225345243465756865455532547566543256765432478900788856773477723904569056790`

out:
Code: Select all
`19 20212229 3039 40383383259 26026111111111111111111111111118999 10075075075073803835948279 380383594828059169281361494714517507628283924608407270263072702753999 1000876463083864126565076763099 63100`

Keep posting !!

Ghust_omega
Experienced poster

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

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

UFP2161
A great helper

Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm

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

Ghust_omega
Experienced poster

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

### 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.
Antonio Ocampo
Experienced poster

Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per

10^18 doesn't work.

UFP2161
A great helper

Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm

Thanks for replying UFP2161. But, one more question

Why my program doesn
Antonio Ocampo
Experienced poster

Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per

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

UFP2161
A great helper

Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm

Thanks Guru, bye.
Antonio Ocampo
Experienced poster

Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per

### 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 ).

Sedefcho
A great helper

Posts: 375
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

### 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;}`
murkho
New poster

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

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.

shamim
A great helper

Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Dhaka

PreviousNext