시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 256 MB443100.000%

문제

Casino "Three Devices for Lumbering" has come up with a new gambling game which has immediately received much attention.

The rules of this game are very easy. Two players alternate their turns in the game: a visitor and a croupier. At the start of the round, the croupier has a whole chocolate bar, and the visitor goes first.

In his turn, each player takes any of the pieces of chocolate which belong to the opponent, cuts it into two pieces so that the bigger piece is at most twice as large as the smaller. After that, he takes one of these two pieces for himself and leaves the other one.

The casino decides not to investigate any optimal strategies in this game. Instead, the croupier in his turn chooses one of the visitor's pieces with equal probability, and takes as much as possible: $\frac{2}{3}$ of this piece. The randomness of the croupier's turns should convince the players that the croupier will make random and wrong turns.

The game lasts for a fixed odd number of turns: as the visitor starts without any chocolate at all, and croupier has a whole chocolate bar, it is guaranteed by the rules that the visitor makes the first and the last turns.

The cost of participation in one round is rather high: the player must pay 0.55 chocolate units, or c.u., which will not be refunded after the game. Despite this fact, analysts of a rival company have found a vulnerability in the rules which can guarantee making profit from each round of the game: get at least 0.55 of the chocolate piece in total in each round.

You have to develop such a strategy which gains at least 0.55 of the chocolate piece in total in each round, before the casino closes this vulnerability.

프로토콜

In the first line, you are given two integers $t$ and $n$: the number of rounds in which you must win and the number of turns that will be made in each round ($1 \le t \le 1000$; $1 \le n \le 30$; $n$ is odd).

After that, you must win $t$ rounds of the game. At the start of each round, the croupier has a whole chocolate bar which is labeled by $0$. Each next piece of chocolate is labeled with the number of the turn when a player cuts this piece from the opponent's piece and takes it for himself. There will be $n$ turns, the first and the last will be made by your program.

In your turn, you choose a piece of chocolate with some label $i$ ($i$ should be even because all the croupier's pieces have even numbers, and do not exceed the number of the current turn), which belongs to the croupier, and the percentage $x$ ($\frac{1}{3} \le x \le \frac{2}{3}$) of this piece which you take for yourself. When you choose $i$ and $x$, you should print these two numbers. The number $x$ should be printed with at least ten digits after the decimal point (the more the better). If your $x$ is less than $\frac{1}{3}$, it will be considered as $\frac{1}{3}$, and if it is bigger than $\frac{2}{3}$, it will be considered as $\frac{2}{3}$.

In his turn, the croupier randomly chooses one of your pieces, a uniformly distributed random odd $i$ not exceeding the number of the current turn, takes $\frac{2}{3}$ of this piece for himself, and prints these numbers. The fraction $\frac{2}{3}$ is always printed as "$0.6666666667$".

After your last turn, the interactor checks if you have at least $0.55 - 10^{-9}$ of the initial chocolate. If not, the interactor prints $0$, and your program should terminate: you don't pass the test and get "Wrong Answer" on this test. Otherwise, the interactor prints $1$, and a new round starts immediately, where the interactor is waiting for your first turn again.

예제 입력 1

2 5

1 0.6666666667

3 0.6666666667

1

1 0.6666666667

3 0.6666666667

0

예제 출력 1


0 0.5

2 0.6666666667

0 0.6666666667

0 0.6666666667

2 0.6666666667

0 0.6666666667

힌트

Let's take a look at what happens in the first sample. The participant must win in two rounds.

The first round:

  • Before the first turn, the participant doesn't have any pieces of chocolate, and the jury has one piece of size $1$.
  • After the first turn, the participant has one piece of size $\frac{1}{2}$, and the jury has one piece of size $\frac{1}{2}$.
  • After the second turn, the participant has one piece of size $\frac{1}{6}$, and the jury has pieces of sizes $\frac{1}{2}$ and $\frac{1}{3}$.
  • After the third turn, the participant has pieces of sizes $\frac{1}{6}$ and $\frac{2}{9}$, and the jury has pieces of sizes $\frac{1}{2}$ and $\frac{1}{9}$.
  • After the fourth turn, the participant has pieces of sizes $\frac{1}{6}$ and $\frac{2}{27}$, and the jury has pieces of sizes $\frac{1}{2}$, $\frac{1}{9}$ and $\frac{4}{27}$.
  • After the fifth turn, the participant has pieces of sizes $\frac{1}{6}$, $\frac{2}{27}$ and $\frac{1}{3}$, and the jury has pieces of sizes $\frac{1}{6}$, $\frac{1}{9}$ and $\frac{4}{27}$.

At the end, the participant has $\frac{1}{6} + \frac{2}{27} + \frac{1}{3} \approx 0.574$ which is bigger than $0.55$: the participant wins the round.

The second round:

  • Before the first turn, the participant doesn't have any pieces of chocolate, and the jury has one piece of size $1$.
  • After the first turn, the participant has one piece of size $\frac{2}{3}$, and the jury has one piece of size $\frac{1}{3}$.
  • After the second turn, the participant has one piece of size $\frac{2}{9}$, and the jury has pieces of sizes $\frac{1}{3}$ and $\frac{4}{9}$.
  • After the third turn, the participant has pieces of sizes $\frac{2}{9}$ and $\frac{8}{27}$, and the jury has pieces of sizes $\frac{1}{3}$ and $\frac{2}{27}$.
  • After the fourth turn, the participant has pieces of sizes $\frac{2}{9}$ and $\frac{8}{81}$, and the jury has pieces of sizes $\frac{1}{3}$, $\frac{2}{27}$ and $\frac{16}{81}$.
  • After the fifth turn, the participant has pieces of sizes $\frac{2}{9}$, $\frac{8}{81}$ and $\frac{2}{9}$, and the jury has pieces of sizes $\frac{1}{9}$, $\frac{2}{27}$ and $\frac{16}{81}$.

At the end, the participant has $\frac{2}{9} + \frac{8}{81} + \frac{2}{9} \approx 0.543$ which is less than $0.55$: the participant loses the round, and the interactor prints $0$, which means that solution got "Wrong Answer" on this test.

채점 및 기타 정보

  • 예제는 채점하지 않는다.