![:(](./images/smilies/icon_frown.gif)
10993 - Ignoring Digits
Moderator: Board moderators
10993 - Ignoring Digits
Can anyone tell me how to solve this problem? I haven't any idea ![:(](./images/smilies/icon_frown.gif)
![:(](./images/smilies/icon_frown.gif)
Last edited by frankhuhu on Mon Feb 13, 2006 9:38 am, edited 1 time in total.
-
- Guru
- Posts: 584
- Joined: Thu Jun 19, 2003 3:48 am
- Location: Sanok, Poland
- Contact:
-
- Guru
- Posts: 584
- Joined: Thu Jun 19, 2003 3:48 am
- Location: Sanok, Poland
- Contact:
-
- 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.
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...
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..
Sorry For My Poor English.. ![:)](./images/smilies/icon_smile.gif)
![:)](./images/smilies/icon_smile.gif)
-
- 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 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.
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)
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,
![:)](./images/smilies/icon_smile.gif)
the format my source code used was correct, but during posting here I saw things
![:P](./images/smilies/icon_razz.gif)
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.. ![:)](./images/smilies/icon_smile.gif)
![:)](./images/smilies/icon_smile.gif)
-
- Guru
- Posts: 1080
- Joined: Thu Dec 19, 2002 7:37 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.
The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.
AC but a query
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
Practice Makes a man perfect
-
- Guru
- Posts: 584
- Joined: Thu Jun 19, 2003 3:48 am
- Location: Sanok, Poland
- Contact: