TWINS

Time limit0.5sMemory limit1024 MB

Summary

Find the one or two Reni pictures among N by asking group queries that check whether a set contains any Reni picture, using few groups and questions.

Level: Medium6 of 10
Topics: Binary search, Bit manipulation, Implementation
Solved: No attempts yet

Problem

The twins Reni and Nora fooled everyone again by switching places. Alex was sure he had found a way to tell them apart, but he was wrong. Knowing that Alex is hopelessly confused, Reni and Nora decided to play a newly invented game.

Reni and Nora choose $N$ different pictures of themselves, numbered from $1$ to $N$ . One or two of the pictures show Reni, and the rest show Nora.

Alex may ask questions of the form: "Among the pictures with numbers $p_1, p_2, \ldots, p_K$ ( $1 \leq K \leq N$ ), is there at least one picture of Reni?" He can submit several such questions together as one question group and receives all the answers at the same time.

Alex's goal is to determine, after some finite number of questions, which pictures are Reni's and which are Nora's. He must also minimize both the number of question groups and the total number of questions. Write a program twins that finds the one or two pictures of Reni. The program must contain the function play, which is compiled together with the jury's program.

Constraints

$15 \leq N \leq 50\,000$
$1 \leq T \leq 2$

Examples1

Example 1
Input
```
15
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
```
Expected output
```
1
```