## 10633 - Rare Easy Problem

Moderator: Board moderators

### 10633 - Rare Easy Problem

I thought it is an easy problem.
But get WA all the time.
What's wrong with my input/output
input
Code: Select all
`9119999941107774`

output
Code: Select all
`1012111109 11111045668637`

Or someone could give some tricky input/output, thx
windows2k
Experienced poster

Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

### Re: 10633 rare easy problem

Check trailing spaces in output.
You should use unsigned long long instead of signed long long.

Input:
1000000000000000000

Output:
1111111111111111111
rotoZOOM
Learning poster

Posts: 63
Joined: Mon Dec 22, 2003 5:05 am
Location: Russia, Chelyabinsk

i don't think that u should use unsigned long long. i used only long long.
if n=9 output 10
and if u use 10*n/9 then u will face overflow problem if n is 18 digit
Hope, it will help u
prince56k
New poster

Posts: 33
Joined: Fri Dec 12, 2003 10:32 pm

Maybe 10^18 is not so big,but i use big numbers and got AC at one's.
I don't know how in C++ may be long long is bigger than 10^18 but in Pascal i don't think that INT64 is bigger than 10^18.That why i use big numbers.
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650
Eduard
Experienced poster

Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

With some care no overflow will ever ocur in a 64 bit signed integer.
PdR
New poster

Posts: 24
Joined: Mon Dec 30, 2002 4:27 am

In Pascal INT64 type can store integers, less than 2^63-1>10^18. So you could fill free to use int64.

10*a/9 = a + a/9.
if you write this way you won't meet any overflowing.

P.S. This is realy very easy problem.

mlvahe
New poster

Posts: 23
Joined: Wed Jul 30, 2003 6:54 am
Location: Yerevan, Armenia

(we can find out a number easily by the formula)
Sajid Online: www.sajidonline.com
Sajid
Learning poster

Posts: 94
Joined: Sat Oct 05, 2002 5:34 pm
Location: CS - AIUB, Dhaka, Bangladesh.

The other answers lie (+-) 10 of the number calculated using formula.

shamim
A great helper

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

hmm, I guess, I did simple mistake in the contest. I checked only previous ten number of the calculated number....
anyway, got AC now
Sajid Online: www.sajidonline.com
Sajid
Learning poster

Posts: 94
Joined: Sat Oct 05, 2002 5:34 pm
Location: CS - AIUB, Dhaka, Bangladesh.

Actually, there's an easier way to check if a number is capable of multiple numbers..
Larry
Guru

Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City

Larry,
Can you explain the ways?
Sajid Online: www.sajidonline.com
Sajid
Learning poster

Posts: 94
Joined: Sat Oct 05, 2002 5:34 pm
Location: CS - AIUB, Dhaka, Bangladesh.

I'm not a good math prover, but either prove to yourself or believe that the most number of ways is 2.

Knowing this, most numbers will have only one solution. Try to find that special case where there are two.

Hope it helps without giving too much away.. =)
Larry
Guru

Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City

Just I'm so curious that why maximum answers are only two.
Of course, I think it's very natural, but I want to know the reason.
Last edited by soyoja on Tue May 04, 2004 10:12 am, edited 2 times in total.
soyoja
Experienced poster

Posts: 106
Joined: Sun Feb 17, 2002 2:00 am
Location: Seoul, South Korea

Here is general idea of this problem ^^

A = original number
B = Sample input

A - A/10 = B ( by problem description )
therefore , (10A - A)/10 = B, 9A = 10B, A = 10/9 * B
So we can find one answer.
And minus value is always made by ( A/10 ),
so another answer's range is - 10 ~ + 10 at original answer.
You can find that number by small range searching.
soyoja
Experienced poster

Posts: 106
Joined: Sun Feb 17, 2002 2:00 am
Location: Seoul, South Korea

soyoja:

sorry, as I said, I'm not a good math prover, and it was just an intuition (that worked), so I don't know why this is the case.
Larry
Guru

Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City

Next