Yet another substring problem
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
The problem is completely unrelated to its problem code :).
Let us build an infinite string D that is simply a concatenation of the decimal representations of all positive integers without leading zeros. In other words, D = 12345678910111213141...
You are given a string S. Find the position of the first occurrence of S in D that satisfies one additional constraint: at least one integer that was concatenated to form D occurs entirely within S.
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a string of digits S.
It is guaranteed that S will occur satisfying the given condition somewhere in D.
For each test case, output a single line containing the minimal position number where S occurs in D under the given condition, modulo 109+7. Consider the string to be 1-indexed: '1' is in position 1.
- 1 ≤ T ≤ 10
- 1 ≤ |S| ≤ 300
- Subtask 1 (17 points): the answer won't exceed 107
- Subtask 2 (23 points): the answer will fit in a signed 64-bit integer (before taking modulo).
- Subtask 3 (60 points): no additional constraints.
Input: 2 78910 9930 Output: 7 2679
Please pay attention that in the second test case the answer is not 788, as it may seem at first glance. This is because the part 298299300301 doesn't contain any integer completely in it - neither 299, nor 300. But the part 928929930931932 contains the integer 930 completely.
|Tags||biginteger, bruteforce, handling, ltime18, simple, xcwgf666|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.