printРабочее место участника


1472. Bit by bit

Ограничения: время – 3s/6s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Some applications (such as compression algorithms) require searching a memory area for arbitrary bit strings.
Your program must find the first occurrence of the given bit string in the sequence of numbers generated by an arithmetic progression: `a,\ a\ +\ b,\ a\ +\ 2*b,\ …,\ a\ +\ N*b`. Numbers are stored in a continuous memory area as 32-bit unsigned integers in the little-endian byte order. Bits in byte are counted from the least significant to the most significant one.
For example, number 123456 will be stored as a sequence of four bytes with hexadecimal values "40 E2 01 00", interpreted as bit string "00000010 01000111 10000000 00000000" (spaces inserted for readability only). So the occurrence of the bit substring "1001" would be at position 7.
Note that the occurrence can cross boundaries between numbers.
Input file format
First line of input file contains integers `a\ b\ N`. Second line of input file contains a string of '0' and '1' characters, each character representing one bit of the string to search for.
Output file format
Output file must contain a single integer – the position of the bit string in the memory area, starting from 1. If the bit string is not found, output file must contain 0 (zero).
`0\ ≤\ a,\ b,\ N,\ a\ +\ N\ *\ b\ ≤\ 2^32\ -\ 1`, `0\ ≤\ N\ ≤\ 5\ *\ 10^6`
Bit string consists of 1 to 32 bits.

Sample Input 1

1 1 1

Sample Output 1


Sample Input 2

0 1 1

Sample Output 2


Sample Input 3

1 2 11

Sample Output 3

Source: NEERC ICPC, Far Eastern subregion, 2008