SINGLEL - Attack A Single Test File!

no tags 

Background

The purpose of this problem is to simulate attacking a problem with limited input/output data. Suppose a problem has only N bits (0/1) as input, 1 bit 0/1 as output. Obviously, it has 2N mutually distinct test files. Only with infomation given above, one can successfully get all the input/output data by submitting attacking programs and extracting judge's responses!

Interactive Protocol

You should communicate with Judge using standard input and output.

Attention: the program should clear the output buffer after printing each line. It can be done using fflush(stdout) command or by setting the proper type of buffering at the beginning of the execution - setlinebuf(stdout).

Each input contains exactly 26 = 64 games. The very first line of the input contains number N. After reading this data your program should play 64 games with judge.

At the beginning of each game, the judge will generate a permutation P of 0..2N-1 and a 0/1 string S of length 2N. These two parameters won't change during the whole game.

Each time you should send to the judge a line with a 0/1 string S' of length 2N.

If S' is purely coincident with judges string S, judge will send to you number "-1" as response. Your program should terminate the processing of this game immediately after getting this response.

Otherwise, judge's response will be a number T (0 <= T <= 2N-1), which means that, for each 0 <= i < T, S'[P[i]] == S[P[i]], while S'[P[T]] != S[P[T]]. All the indices are 0-based.

For each game you should not make more than 6666 queries, otherwise you will get Wrong Answer verdict.

Scoring

For each game, if you use w queries before you get "-1" response, your score will be w2. The score for each test file will be the sum of scores of the 64 games. The final score will be the average score of all test files. Smaller score is better.

Constraints

1 <= N <= 8.

Time limit for each test file is 33 seconds.

Example

The example of communication. J=Judge, P=Player.

J: 1

P: 00
J: 1
P: 01
J: 0
P: 10
J: -1

P: 00
J: 0
P: 10
J: 1
P: 01
J: 0
P: 11
J: -1

[and 62 games more]

Explanation

In the first example, judge's permutation is (1,0), while in the second example, judge's permutation is (0,1). The score of these two games will be 22 + 32 = 17.


hide comments
studyfather: 2017-07-19 13:15:07

The example may have some problems...
edit:I'm so stupid...I forgot something important...

Last edit: 2017-07-20 12:09:36

Added by:Fudan University Problem Setters
Date:2008-05-24
Time limit:33s
Source limit:10240B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: C99 ERL GOSU JS-RHINO NODEJS PERL6 VB.NET
Resource:Noob is a fool!