Ramesh And Suresh
All submissions for this problem are available.
Ramesh and Suresh are playing a game. Ramesh will give Suresh a question to solve and vice versa. So, Ramesh gave Suresh a string consisting of digits from (1 to 9). He also gave him two integers A and B and told him to cut the string S minimum number of times such that every part lies in the range [A,B]. Since, Suresh is weak in programming, he has asked for your help in finding the answer.
First line consists of an integer T denoting the number of test cases. Next T lines consists of a string S and two integers A and B.
A single integer denoting the minimum number of cuts of string S such that every part lies in [A,B].
Print "-1" without the quotes if Suresh is not able to cut the string according to the given conditions.
- 1 ≤ T ≤ 10
- 1 ≤ |S| ≤ 105
- 1 ≤ A ≤ B ≤ 109
Input: 3 1236 1 6 12315 1 15 5423 1 4 Output: 3 2 -1
Test case 1: The string can be divided into minimum 4 parts - "1","2","3","6". So 3 cuts are required.
Test case 2: The string can be divided into minimum 3 parts - "12","3","15". So 2 cuts are required.
Test case 3: The string cannot be divided into parts which lies in [1,4], hence answer is -1.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, 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, SCM chicken, CLOJ, FS|
Fetching successful submissions