10993 - Ignoring Digits

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

Moderator: Board moderators

frankhuhu
New poster
Posts: 30
Joined: Tue Jul 20, 2004 5:22 am
Contact:

10993 - Ignoring Digits

Post by frankhuhu » Mon Feb 13, 2006 8:14 am

Can anyone tell me how to solve this problem? I haven't any idea :(
Last edited by frankhuhu on Mon Feb 13, 2006 9:38 am, edited 1 time in total.

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Mon Feb 13, 2006 9:25 am

I solved it with BFS.
For millions of years, mankind lived just like the animals. Then something happened which unleashed the power of our imagination. We learned to talk and we learned to listen...

frankhuhu
New poster
Posts: 30
Joined: Tue Jul 20, 2004 5:22 am
Contact:

Post by frankhuhu » Mon Feb 13, 2006 9:39 am

Sorry Krzysztof Duleba,I post the wrong problem id and I need help on p10993 Ignoring Digits. :P

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Mon Feb 13, 2006 9:40 am

I know and this is what I meant.
For millions of years, mankind lived just like the animals. Then something happened which unleashed the power of our imagination. We learned to talk and we learned to listen...

frankhuhu
New poster
Posts: 30
Joined: Tue Jul 20, 2004 5:22 am
Contact:

Post by frankhuhu » Mon Feb 13, 2006 9:45 am

hmm...
Can you explain it in details,I don't quite understand how to use BFS. :oops:

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Mon Feb 13, 2006 9:58 am

It's hard to give a hint and not to give the whole fun away, but I'll try.

N is not so big here, so building a graph with N nodes is ok (each node corresponds to a remainder modulo N). In fact, you don't even have to build it.

There is an edge from u to v if you can transform number u to v with one allowed digit.

If you can find a path to 0, you've found the solution.

There are some important details that I've left out, but they are a part of the fun part.
For millions of years, mankind lived just like the animals. Then something happened which unleashed the power of our imagination. We learned to talk and we learned to listen...

wook
Learning poster
Posts: 76
Joined: Fri Oct 01, 2004 11:34 am
Location: Korea, Republic Of

Post by wook » Mon Feb 13, 2006 10:47 am

for input

Code: Select all

3
2 38
52 17725
2 29999
output

Code: Select all

222222222222222222
55222255225
222222222222222222222........(approximately 30000 digits)......22
Is it right?

However, the length of output seems to be very large..
Sorry For My Poor English.. :)

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Mon Feb 13, 2006 10:58 am

Please read the input specification again, yours is not a valid input.
The third answer has just under 15000 digits. It can not have more than that because the odd remainders are not reachable using even digits only.
The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof » Mon Feb 13, 2006 11:43 am

little joey wrote:Please read the input specification again, yours is not a valid input.
Agreed. There is no number of test cases, the input is terminated by two zeroes.
little joey wrote:The third answer has just under 15000 digits. It can not have more than that because the odd remainders are not reachable using even digits only.
I disagree with this one. They are reachable, if the modulus is odd. E.g., 22 mod 7 = 1. (But still you are right that in this case there will be only 14820 '2's in the output.)

Here is some I/O:

input:

Code: Select all

86421 2
86421 4
86421 7
210 5
2 38
9751 99982
52 17725
2 47
98764321 45
63 99991
3 99991
0 0
correct output:

Code: Select all

2
4
14
10
222222222222222222
impossible
55222255225
2222222222222222222222222222222222222222222222
impossible
363633363336333633666663
333.......333 (this line has length 49995)

wook
Learning poster
Posts: 76
Joined: Fri Oct 01, 2004 11:34 am
Location: Korea, Republic Of

Post by wook » Mon Feb 13, 2006 12:06 pm

Now I got accepted.
my basic approach wasn't wrong, but I had made a simple mistake.

Invalid input format above was another mistake, :)
the format my source code used was correct, but during posting here I saw things :P


BTW, the correct output for "2 29999" is the string whose length is less than 15000.

And, Thanks to misof, and to little joey.
Sorry For My Poor English.. :)

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Mon Feb 13, 2006 12:47 pm

misof wrote:
little joey wrote:The third answer has just under 15000 digits. It can not have more than that because the odd remainders are not reachable using even digits only.
I disagree with this one. They are reachable, if the modulus is odd. E.g., 22 mod 7 = 1. (But still you are right that in this case there will be only 14820 '2's in the output.)
Duh, you're absolutely right. I shouldn't be posting when I just woke up and caffeine/nicotine levels are still too low...
The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Mon Feb 13, 2006 9:41 pm

Now I got AC, turns out that my initialization was incorrect. Misof, thanks for your i/o.

mrahman
New poster
Posts: 25
Joined: Mon Oct 24, 2005 9:45 am
Location: Bangladesh
Contact:

AC but a query

Post by mrahman » Thu Feb 16, 2006 11:19 am

Why My accepted code terminated for the following input in VC++

Code: Select all

3 99991
2 29999
I am wonder why I should get Accepted. It should be WA.
Practice Makes a man perfect

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Thu Feb 16, 2006 12:05 pm

This is possible if you use recurrence.
For millions of years, mankind lived just like the animals. Then something happened which unleashed the power of our imagination. We learned to talk and we learned to listen...

mrahman
New poster
Posts: 25
Joined: Mon Oct 24, 2005 9:45 am
Location: Bangladesh
Contact:

Post by mrahman » Fri Feb 17, 2006 4:51 am

Krzysztof Duleba,
This is possible if you use recurrence.
Do you want to say that the code will run under the environment of Judge(gcc compiler) successfully. I don't know whether gcc compiler have more stack memory than VC++. Please Clarify me.
Thank you
Practice Makes a man perfect

Post Reply

Return to “Volume 109 (10900-10999)”