10993 - Ignoring Digits

[frankhuhu]

Can anyone tell me how to solve this problem? I haven't any idea

[Krzysztof Duleba]

I solved it with BFS.

[frankhuhu]

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

[Krzysztof Duleba]

I know and this is what I meant.

[frankhuhu]

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

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

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

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

[misof]

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.

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]

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


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

And, Thanks to misof, and to little joey.

[little joey]

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

[sclo]

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

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

[Krzysztof Duleba]

This is possible if you use recurrence.

[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