DMOPC '17 Contest 5 P2 - Mimi and Binary

View as PDF

Submit solution


Points: 5 (partial)
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Mimi is playing with a string S, consisting of only 0s and 1s. Her little sister comes along and being very curious, asks Q questions about the binary string:

If we consider the substring starting from the x_ith index, what is the leftmost index such that there are y_i occurrences of the digit z_i?

Help Mimi write a program to answer these queries.

Constraints

Let |S| denote the length of string S.

For all subtasks, 1 \le x_i, y_i \le |S|, and 0 \le z_i \le 1.

Subtask 1 [20%]

1 \le |S| \le 1\,000
1 \le Q \le 1\,000

Subtask 2 [80%]

1 \le |S| \le 200\,000
1 \le Q \le 200\,000

Input Specification

The first line will contain the string S.
The next line of input will contain a single integer, Q.
The next Q lines will each contain three space-separated integers: x_i, y_i, and z_i, the ith query.

Output Specification

The output should contain Q integers, each on a newline. The ith integer should be either the leftmost index such that there are y_i occurrences of the digit z_i, or -1 if no such index exists.

Sample Input

010100
3
1 2 0
1 2 1
1 3 1

Sample Output

3
4
-1

Comments


  • 4
    Medi  commented on Nov. 14, 2018, 1:51 a.m.

    Could someone explain the sample input and output?


    • 5
      kingW3  commented on Nov. 14, 2018, 8:20 a.m.

      For the first query the substring 010 is the first to have 2 occurrences of 0 so the answer is , the second query the substring 0101 is the first to have 2 occurrences of 1 hence the answer is 4 and for the last there is no substring containing 3 ones starting from first char.


  • 44
    echofox  commented on March 27, 2018, 8:28 p.m.

    don't you just hate it when you're doing something and your younger sibling comes over and asks "if we consider the substring starting from the xith index, what is the leftmost index such that there are yi occurrences of the digit zi?"