GUESSN5 - Guess The Number With Lies v5
GUESSN5
Judge has chosen an integer x in the range [1, n]. Your task is to find x, using at most m queries as described below. But be careful, because there are 2 important things:
1. The Judge can lie. Judge is allowed to lie w times in single game and only in reply for query.
2. You must prepare all queries at once and send all of them to the Judge before You got any reply.
Query
Single query should contains string s1s2s3...sn, where si is '0' or '1'. The reply for query is "YES", if sx = '1', or "NO" otherwise.
For example, when n=8, x=5 and query is "00101011", the Judge will reply "YES" (if telling the truth) or "NO" (if lying), because the 5th character in query is '1'.
Real task and scoring
The real task is not to find the number x chosen by Judge, but only to prepare queries, which allow You to guess the x value for every possible Judge's reply. The Judge won't give You reply for Your queries.
If the Judge will find such reply for Your queries, that there will be more than one x value possible, You will fail the test case (see example for detail explanation). Otherwise You succeed.
If You succeed, Your score is q2, where q is the number of queries, that You use. If You fail, You got penalty score equal to 4m2. Total score is the sum of scores of single games. The smaller score is the better score.
Input
The first line of input contains one integer T - the number of test cases. Then T test cases follow.
Each test case contains one line with three single-space separated integers n, w and m, where n is the size of the game, w is the maximal number of lies and m is the maximal number of queries, that You can use.
Output
For each test case print a line with one integer q - the number of queries that You want to ask.
Then print q lines with Your queries. Each query should be string of length n, with all characters '0' or '1'.
Constraints
1 ≤ T ≤ 27
2 ≤ w ≤ 24
2 ≤ n ≤ 212
(2w+1) * ⌈log2 n⌉ ≤ m
0 ≤ q ≤ m
Example
Input: 4 2 2 6 2 3 8 2 16 34 5 2 18 One of possible output is: 6 01 01 01 01 01 01 6 01 01 01 01 01 01 0 15 00011 00011 00011 00011 00011 01010 01010 01010 01010 01010 00100 00101 00110 01100 01111
Explanation:
Notation: reply "YYN..." means, that Judge replied "YES" for first and second query, "NO" for third query, and so on...
In 1st test case there are only two numbers. Judge can reply "YYYYYY", "NNNNNN" (without lie), "YYYYYN", "YYYYNY", "YYYNYY", "YYNYYY", "YNYYYY", "NYYYYY", "NNNNNY", "NNNNYN", "NNNYNN", "NNYNNN", "NYNNNN", "YNNNNN", (with one lie) or "NNNNYY", "NNNYNY", "NNNYYN", "NNYNNY", "NNYNYN", "NNYYNN", "NYNNNY", "NYNNYN", "NYNYNN", "NYYNNN", "YNNNNY", "YNNNYN", "YNNYNN", "YNYNNN", "YYNNNN", "NNYYYY", "NYNYYY", "NYYNYY", "NYYYNY", "NYYYYN", "YNNYYY", "YNYNYY", "YNYYNY", "YNYYYN", "YYNNYY", "YYNYNY", "YYNYYN", "YYYNNY", "YYYNYN", "YYYYNN" (with 2 lies). The other replies ("NNNYYY", "NNYNYY", "NNYYNY", "NNYYYN", "NYNNYY", "NYNYNY", "NYNYYN", "NYYNNY", "NYYNYN", "NYYYNN", "YNNNYY", "YNNYNY", "YNNYYN", "YNYNNY", "YNYNYN", "YNYYNN", "YYNNNY", "YYNNYN", "YYNYNN", "YYYNNN") are not ok, because for every of them and for every possible x value, the Judge lies more than two times. For each good reply, there is only one integer from range [1, 2], that match this replies ("match" means match all except at most two of queries). The score is 62 = 36. Notice, that You can use the same query more than once.
In 2nd test case player tried to give the solution, but the solution is wrong. The Judge can reply for example "YYYNNN" and then for both possible values of x the judge lied 3 times. Player needs more queries in this case. The score is penalty score 4 * 82 = 256.
In 3rd test case player decided to skip. Player got the penalty score 4 * 342 = 4624.
In 4th test case the nubmer of queries given by player is smaller than the maximal possible number. For every possible Judge's reply there is only one possible value of x, so test succeeded. The score is 152 = 225.
Total score is 36 + 256 + 4624 + 225 = 5141.
Similar problems
There is a family of similar problems. Here is the table with them:
Code | Number of lies | Query format | Type | Section | Difficulty |
---|---|---|---|---|---|
GUESSN1 | 1 | subset | interactive | challenge | easy |
GUESSN2 | 2-16 | subset | interactive | challenge | medium/hard |
GUESSN3 | 1 | range | interactive | classical | medium |
GUESSN4 | 1 | subset | non-interactive | challenge | medium |
GUESSN5 | 2-16 | subset | non-interactive | challenge | hard |
subset - the query is about any subset of {1,2,...,n}
range - the query is about any range [a,b]
interactive - the Judge replies after every query
non-interactive - all queries have to be asked at once, before any reply
Added by: | miodziu |
Date: | 2013-12-29 |
Time limit: | 20s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |