Alice and Bob are engaging in quantum communication. Their language of
communication is a dictionary of size . In the dictionary, a word
may be represented by a 256-bit binary string. In
this problem, may be generated by calling function gen
. The
contestants may refer to gen.cpp,
and the parameters n,a1,a2
will be specified by the test cases.
Alice and Bob will communicate for rounds next. In each round, Alice will send bob exactly one word in the dictionary. However, their communication channel is not reliable and may be disturbed by noise. More formally, for the -th round of communication, suppose the word Alice wants to send is , then at most bits of the binary string will flip. In other words, suppose the binary string Bob receives is , then is different from for at most positions. does not have to be in dictionary .
At the same time, Bob knows Eve has invaded the communication channel and is going to manipulate the communication between Alice and Bob. Eve will replace the binary string Bob is going into receive with an arbitrary 256-bit binary string, and the arbitrary 256-bit binary string does not have to be in the dictionary. Eve does not have to manipulate all rounds of communication.
Now Bob asks you for help, and you need to determine whether it is possible that a round of communication is not manipulated by Eve given the string Bob received and the threshold for noise disturbance . In other words, you need to check whether the binary string Bob received can be obtained by flipping at most bits of a word in the dictionary. If it is possible that the round of communication is not manipulated by Eve, output 1. Otherwise, output 0. Bob trusts your ability, so you need to answer the queries online. For the specifics, see the input section.
To save the time spent on I/O, the strings Bob received are given by
64-bit hexadecimal strings. The hexadecimal strings contain numerals 0-9
and upper-case English letters A-F. A-F represents 10-15 in that order.
A hexadecimal string may be converted to a binary string bit by bit. For
example, 5
will correspond to 0101
, A
will correspond to 1010
,
and C
will correspond to 1100
.
Input Specification
The first line of the input contains four nonnegative integers
denoting the size of the dictionary, the number of rounds
of communication, and the initial values of parameters a1
and a2
for
the function gen
. Contestants need to generate the dictionary using
the gen
function mentioned in the problem statement. Contestants may
copy and use the code in gen.cpp
. The Boolean array s[N+1][256]
is
just the list of all words.
For the next lines, each line contains a hexadecimal string of length 64 and a nonnegative integer denoting the final binary string Bob received in round and the threshold for noise disturbance.
To make sure contestants are answering the queries online, after the
contestants recover the 256-bit binary string based on the hexadecimal
string, contestants need to perform XOR operation with lastans
bitwise
to recover the real binary string Bob received in the round. lastans
denotes the answer to the query last round. Before the
first round, the initial value of lastans
is 0.
Notice: when reading or writing unsigned long long
variables using
scanf
or printf
, use llu
.
Output Specification
The output consists of lines. Each line contains an integer 0 or 1 denoting the answer to the query.
Sample
For convenience, we will give the words in the dictionary explicitly, reduce the word length to 4, and allow offline answers to the queries.
Suppose the dictionary size is . The words are 1010 and 0111.
For query B = 1011
and , the output shall be 1 since B
may
be obtained by flipping the 4-th bit of 1010.
For query B = 0001
and , the output shall be 1 since 0001 may
be obtained by flipping the second and the third bit of 0111.
For query B = 0001
and , the output shall be 0.
The remaining samples can be found here.
Constraints
For all test cases, , , , and are uniformly random among .
Test case | Additional Constraints | |||
---|---|---|---|---|
1 | None. | |||
2 | ||||
3 | ||||
4 | ||||
5 | ||||
6 | ||||
7 | ||||
8 | ||||
9 | ||||
10 | ||||
11 | ||||
12 | ||||
13 | ||||
14 | ||||
15 | ||||
16 | The query strings are generated randomly. | |||
17 | ||||
18 | ||||
19 | None. | |||
20 | ||||
21 | ||||
22 | ||||
23 | ||||
24 | ||||
25 |
Comments