## DMOPC '17 Contest 5 P2 - Mimi and Binary

View as PDF

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 , consisting of only 0s and 1s. Her little sister comes along and being very curious, asks questions about the binary string:

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

Help Mimi write a program to answer these queries.

#### Constraints

Let denote the length of string .

For all subtasks, , and .

#### Input Specification

The first line will contain the string .
The next line of input will contain a single integer, .
The next lines will each contain three space-separated integers: , , and , the th query.

#### Output Specification

The output should contain integers, each on a newline. The th integer should be either the leftmost index such that there are occurrences of the digit , 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

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

Could someone explain the sample input and output?

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

For the first query the substring is the first to have occurrences of so the answer is , the second query the substring is the first to have occurrences of hence the answer is and for the last there is no substring containing ones starting from first char.

• 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?"

• commented on Jan. 27, 2020, 9:45 a.m.

relatable