Chef and The String of Digits
All submissions for this problem are available.
The Chef has written all the numbers from 1 to 109 consecutively on a board. Let P be the long string
obtained by concatenating the numbers written on the board consecutively. Given below are the first few digits of the long string P.
Given another string Q, he is wondering whether Q is a substring of the string P.
For example, Q="02122" is a substring of P, and has been marked in bold above.
The first line of the input contains T denoting the number of test cases. Each of the following T lines contain a string Q.
For each test case, print "YES" if the given string is contained in the string P, otherwise print "NO".
- 1 ≤ T ≤ 10
- 1 ≤ length of Q ≤ 100000 (105)
- Q consists of only digits(0-9)
Input: 3 23456789101 3216546546546546545 02122
Output: YES NO YES
|Tags||ad-hoc, cook37, easy-medium, implementation, rustinpiece|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, 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, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.