### 10993 - Ignoring Digits

Posted:

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

Page **1** of **2**

Posted: **Mon Feb 13, 2006 8:14 am**

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

Posted: **Mon Feb 13, 2006 9:25 am**

I solved it with BFS.

Posted: **Mon Feb 13, 2006 9:39 am**

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

Posted: **Mon Feb 13, 2006 9:40 am**

I know and this is what I meant.

Posted: **Mon Feb 13, 2006 9:45 am**

hmm...

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

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

Posted: **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.

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

for input
output
Is it right?

However, the length of output seems to be very large..

Code: Select all

```
3
2 38
52 17725
2 29999
```

Code: Select all

```
222222222222222222
55222255225
222222222222222222222........(approximately 30000 digits)......22
```

However, the length of output seems to be very large..

Posted: **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 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**

Agreed. There is no number of test cases, the input is terminated by two zeroes.little joey wrote:Please read the input specification again, yours is not a valid input.

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

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

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

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.

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.

Posted: **Mon Feb 13, 2006 12:47 pm**

Duh, you're absolutely right. I shouldn't be posting when I just woke up and caffeine/nicotine levels are still too low...misof wrote: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.)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.

Posted: **Mon Feb 13, 2006 9:41 pm**

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

Posted: **Thu Feb 16, 2006 11:19 am**

Why My accepted code terminated for the following input in VC++
I am wonder why I should get Accepted. It should be WA.

Code: Select all

```
3 99991
2 29999
```

Posted: **Thu Feb 16, 2006 12:05 pm**

This is possible if you use recurrence.

Posted: **Fri Feb 17, 2006 4:51 am**

Krzysztof Duleba,

Thank you

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.This is possible if you use recurrence.

Thank you