Page 1 of 2

10993 - Ignoring Digits

Posted: Mon Feb 13, 2006 8:14 am
by frankhuhu
Can anyone tell me how to solve this problem? I haven't any idea :(

Posted: Mon Feb 13, 2006 9:25 am
by Krzysztof Duleba
I solved it with BFS.

Posted: Mon Feb 13, 2006 9:39 am
by frankhuhu
Sorry Krzysztof Duleba,I post the wrong problem id and I need help on p10993 Ignoring Digits. :P

Posted: Mon Feb 13, 2006 9:40 am
by Krzysztof Duleba
I know and this is what I meant.

Posted: Mon Feb 13, 2006 9:45 am
by frankhuhu
hmm...
Can you explain it in details,I don't quite understand how to use BFS. :oops:

Posted: Mon Feb 13, 2006 9:58 am
by Krzysztof Duleba
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.

Posted: Mon Feb 13, 2006 10:47 am
by wook
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..

Posted: Mon Feb 13, 2006 10:58 am
by little joey
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.

Posted: Mon Feb 13, 2006 11:43 am
by misof
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)

Posted: Mon Feb 13, 2006 12:06 pm
by wook
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.

Posted: Mon Feb 13, 2006 12:47 pm
by little joey
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...

Posted: Mon Feb 13, 2006 9:41 pm
by sclo
Now I got AC, turns out that my initialization was incorrect. Misof, thanks for your i/o.

AC but a query

Posted: Thu Feb 16, 2006 11:19 am
by mrahman
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.

Posted: Thu Feb 16, 2006 12:05 pm
by Krzysztof Duleba
This is possible if you use recurrence.

Posted: Fri Feb 17, 2006 4:51 am
by mrahman
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