## 10993 - Ignoring Digits

Moderator: Board moderators

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

### 10993 - Ignoring Digits

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.

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:
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:
Sorry Krzysztof Duleba,I post the wrong problem id and I need help on p10993 Ignoring Digits.

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:
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:
hmm...
Can you explain it in details,I don't quite understand how to use BFS.

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:
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
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..

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
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
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
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.
Sorry For My Poor English..

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 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
Contact:
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
Contact:

### AC but a query

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

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:
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