SPOJ.com - Problem PONY10

PONY10 - When Does The World End

There is a recently discovered ancient temple, and Daring Do is already exploring it. She's come across an old Artifact of Power, which just seems to be spouting meaningless numbers. "...82980644837721883829806448..."

Reading the inscription on the wall, it gives an explanation to the artifact:

WE HAVE TAPPED INTO THE UNIVERSAL LIFE FORCE.

WE HEAR THE CLOCK TICKING TOWARD THE END.

CAN YOU HEAR IT?

WHEN THE PROPHESIED NUMBERS ARE SAID THE FORETOLD NUMBER OF TIMES

IT ENDS.

Daring Do doesn't know the prophesied numbers or foretold count, so she moves on with exploring.

She gets more clues while exploring:

The artifact began counting at the beginning of time, starting from 0 and going up 1 step at a time, saying each digit individually. So when it first began, it went "0123456789101112131415...". Each second, it says the next digit. This means at time t=0, it said "0", at time t=1, it said "1", etc.
The universe will end not on the tick after the prophesied number is said for the final time, it ends on the tick that the prophesied number begins. For instance, if the prophesied numbers were "01", and the foretold number of times were "2", then the universe would end at time t = 11. See below for more examples.
She's found different things which could be the prophesied numbers, or the foretold number of times, but she's not sure.

Please help her figure out the life time of the universe, if the given pair of a 'foretold count' and 'prophesied numbers' were the true ones. But, if you take too long, the world might end before you figure it out!

Input Description

The first line is an integer T, indicating the number of test cases to follow. The following T lines will contain 2 things: a number K, the foretold count, and a string composed of digits, TARGET.

Output Description

For each test case, please determine S, the number of seconds until the prophesied number would be said for the final time. For test case i, please output "Case #i: S" on an individual line.

Example

Input:
6
1 0
1 00
9 1
2 01
100 25
5555 178

Output:
Case #1: 0
Case #2: 191
Case #3: 22
Case #4: 11
Case #5: 9018
Case #6: 5104196

Explanation of Case #3

The artifact starts "01234567891011121314151617..." We see that '1' occurs for the 9th time at time t = 22.

Limits

For one test file, T ~= 100000. For the other five files, T ~= 10000

Of the possibilities found by Daring Do, they all seem to follow this limit:

LEN(K) + LEN(TARGET) <= 17.

In other words, if TARGET = "1", then K could potentially be "9999999999999999", but no larger.

whereas if TARGET = "1234567890123456", then K could potentially be "9", but no larger.

Submit solution!

Added by:	Alex Anderson
Date:	2015-10-25
Time limit:	6s-26s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ASM64 GOSU JS-MONKEY
Resource:	My own problem

hide comments



2017-07-01 02:36:11 Alex Anderson @Krueger Well, you could always solve it both ways to see :) But to answer your question, it would be t=13.
2017-06-23 03:43:27 Krueger I've read through the description a few times, but I still may be missing something. How is the case of overlap handled? If the prophesied numbers were "11", and the foretold number of times were "2", would the universe end at time t = 13 or t = 195?
2017-01-02 11:23:17 Alex Anderson @Kaio You're getting the first test file correct. But RE/TLE on second test file. I took a look at your solution in more detail, you're having issues with the really large test cases, or even only moderately large ones, since it seems like your solution is brute force. Try inputs like 9999999999999999 1 9 1234567890123456
2016-12-17 08:27:18 Alex Anderson @Kaio You're failing the first test file, which is 111100 test cases, K in [1,10], TARGET every string up to length 4. I don't have python set up on my machine so I couldn't find the specific case that you fail. But from some spot checks, you're passing them, so I'll try to get Python set up to run your code against the full test case and compare the output. Maybe the judge is not comparing correctly. EDIT: Found one you are getting incorrect. Good luck! 2 1111 Last edit: 2016-12-17 08:31:25
2016-12-11 19:59:40 Kaio César Nascimento Peixoto People do you have any other input cases we could test? My program pass in all the inputs in the exemplo but when I submit i get wrong answer in the running(6). I would like some edge test cases to test. if that matters I'm using python 3.4 Last edit: 2016-12-11 20:02:19
2016-08-19 08:54:59 Alex Anderson @People trying to solve this. Good luck. I take a look here every once in awhile to see new attempts.
2016-03-26 18:50:15 Alex Anderson @ash_hacker For your first question, this is the second condition given: The universe will end not on the tick after the prophesied number is said for the final time, it ends on the tick that the prophesied number begins. For instance, if the prophesied numbers were "01", and the foretold number of times were "2", then the universe would end at time t = 11. See below for more examples. It means that you want to find the index of the first character in the Nth occurrence of the target string. It doesn't mean "subtract 1 from the last index of the Nth occurrence of the target string". For your second question, this is the first condition given: The artifact began counting at the beginning of time, starting from 0 and going up 1 step at a time, saying each digit individually. So when it first began, it went "0123456789101112131415...". Each second, it says the next digit. This means at time t=0, it said "0", at time t=1, it said "1", etc. Your confusion here seems to derive from your earlier confusion. As explained here and in the explicit example explanation, the digits of each number are said on separate ticks. To further elaborate, at t=9, it says "9", at t=10, it says "1", at t=11, it says "0".
2016-03-22 18:13:26 Your examples are contradictory, or less explanation is provided. example given in quesiton, when Target="01", then it says "01" 2nd time at t=12, 9 at t=9; for 10, 1 at t=10, 0 at t=11, then for 11, 1 at t=12; so you see at t=12, "01" is said twice. but if consider the time just before 1 is said in 11, i.e. t=11, then in your 3rd test case, target="1", is said 9 times, at t=21, because t=22, it is 1 to be counted, which if is counted, then previous example answer would be 12. Another confusion, do we have to count each digit in number separately, as then 1st example ans would t=11, as both digits "0" and "1" is counted twice at t=11, when 10 is to be said. but then what would be the significance of 2nd test case target="00", k=1, that means, two 0's counted once, which is at t=11, when counter hits 10, or whole string "00" is counted continuously, which occurs first time when counter hits 100, which is at t=191. Last edit: 2016-03-22 18:22:55
2016-02-01 09:32:21 Alex Anderson long long should be sufficient, given the limits. There shouldn't be any unreachable solutions. Do you have an example input which wouldn't fit into long long?
2016-01-20 01:34:45 Antonio Roberto Paoli @cricycle Do I need to use big numbers or long long is enough to solve this problem? For the test cases provided, would like to know if all answers fit in an unsigned 64 bits number? Because within 16 digits Target there are unreachable solutions, Thanks. Last edit: 2016-01-22 01:53:53