AT_rco_contest_2019_final_a めくってそろえる

Description

[problemUrl]: https://atcoder.jp/contests/rco-contest-2019-final/tasks/rco_contest_2019_final_a **この問題はインタラクティブ形式です。** Xは[神経衰弱](https://ja.wikipedia.org/wiki/%E7%A5%9E%E7%B5%8C%E8%A1%B0%E5%BC%B1_(%E3%83%88%E3%83%A9%E3%83%B3%E3%83%97%E3%82%B2%E3%83%BC%E3%83%A0))で遊ぶこととマラソンをすることが大好きです。ある日、Xは神経衰弱と長距離走を組み合わせた新たなゲームで遊ぶことにしました。 \$1\$ 以上 \$ \\lfloor N/2 \\rfloor \$ 以下の整数がひとつ書かれているカードを大量に用意し、シャッフル後に裏向きに積んで作られた山札が \$N\$ 個あります。山札は横一列に等間隔で並んでいて、左から順に山札 \$0, 1, \\cdots, N-1\$ とします。 Xは山札の上を動き回り、二連続で同じ値のカードを見たらそれらのカードをペアで取り除いてスコアを獲得します。ゲーム開始時、Xは山札 \$0\$ の上にいて、初期スコアは \$0\$ です。 Xは、移動可能な総距離 \$T\$ を超えない範囲で以下の一連の操作を繰り返し行うことができます。 - 操作開始時にXがいる山札の番号を \$p\$ とします。 - 山札 \$p\$ の一番上のカードが表向きであれば、その整数を \$a\_p\$ とします。（一番最初の操作時、および、後述のペアで取り除いた直後の移動時は、山札 \$p\$ の一番上のカードは裏向きです。） - 山札 \$q ( 0 \\leq q \\leq N-1) \$ をひとつ選び、山札 \$p\$ から山札 \$q\$ の上に移動します。（ \$q = p\$ でもかまいません。）この時の移動距離は \$|p - q|\$ です。 - 山札 \$q\$ の一番上のカードを表向きにし、そのカードに書かれている整数を \$a\_q\$ とします。 - 表向きで存在する二枚のカードの値が等しい場合は、そのカードをペアで取り除いてカードに書かれた整数分のスコアを得ます。つまり、\$p \\neq q\$ かつ\$ a\_p = a\_q \$ の場合、山札 \$p, q\$ の一番上からカードを1枚ずつ取り除き、スコアが \$a\_p\$ だけ加点されます。カードを取り除いた後のそれぞれの山札の一番上には、必ず新たなカードが裏向きで存在します。 - ペアで取り除けなかった場合、表向きで存在するカードが二枚あれば、先に表向きにしたカードが裏向きに戻ります。つまり、 \$p \\neq q\$の時に、山札 \$p\$ の一番上のカードが裏向きになります。 Xが得るスコアがなるべく大きくなるようにXを動かしてください。各テストケースの得点およびこの問題の得点は、次のように計算されます。 - 1つのテストケースでは、Xが得たスコアの合計がそのまま得点になります。 - テストケースは全部で $ 50 $ 個あります。各テストケースの得点の合計が、この問題の得点になります。 ### Input & Output Format 最初に、以下の形式で標準入力から入力が与えられます。 ``` $N$ $T$ ``` - $ N $ は山札の個数を表す整数で、$ N\ =\ 50 $ を満たします。 - $ T $ は移動可能な総距離を表す整数で、$ T\ =\ 10000 $ を満たします。 - **ジャッジプログラムの都合上、標準入力の内容を必ず読み込んでください。** 以降、次のやり取りをジャッジプログラムと繰り返し行ってください。 1. 標準出力に整数をひとつ出力してください。 ``` $q$ ``` - Xを移動させる場合、Xが移動する先の山札の番号を表す整数 \$(0 \\leq q \\leq N-1)\$ を出力してください。 - ゲームを終了する場合は`-1`を出力してプログラムを終了してください。 - **移動可能な総距離を超える移動をした場合はWrong Answerとなります。** - **出力の後には必ず改行し、flush してください。** 2. \$q \\neq -1\$ の場合、標準入力から整数がひとつ与えられます。 ``` $a_q$ ``` - $ a_q $ は、山札 \$q\$ の一番上のカードに書かれている整数 \$(1 \\leq a\_q \\leq N/2)\$ を表します。 - **ジャッジプログラムの都合上、標準入力の内容を必ず読み込んでください。**

Input Format

N/A

Output Format

N/A

Explanation/Hint

### テストケースの生成について各カードに書かれた整数は一様乱数にしたがって生成されます。 ### 入出力例プログラムへの入力プログラムの出力説明山札の情報移動総距離スコア ``` 4 6 ``` 山札が4個あり、移動可能な総距離が6であることを表します。このサンプルは制約 \$N=50\$ および \$T=10000\$ を満たしていません。 `? ? ? ?` 0 0 ``` 0 ``` 山札0に移動して一番上のカードを表向きにします。最初にXは山札0の上にいるので、移動距離は0です。 `? ? ? ?` 0 0 ``` 1 ``` 山札0の一番上には`1`と書かれたカードがあります。 `1 ? ? ?` 0 0 ``` 2 ``` 山札2に移動します。山札0から山札2への移動距離は2です。 `1 ? ? ?` 2 0 ``` 2 ``` 山札2の一番上には`2`と書かれたカードがあります。 \$a\_0 \\neq a\_2\$ なので、先に表向きにした山札0の一番上のカードは裏向きになります。 `1 ? 2 ?` ↓ `? ? 2 ?` 2 0 ``` 1 ``` 山札1に移動します。山札2から山札1への移動距離は1です。 `? ? 2 ?` 3 0 ``` 2 ``` 山札1の一番上には2と書かれたカードがあります。 \$a\_1 = a\_2 = 2\$ なので、山札1,2からカードを取り除き、スコアを2点獲得します。山札1, 2からカードを取り除いたことで、それぞれの山札の一番上にあるカードは再度表向きにしないと分かりません。 `? 2 2 ?` ↓ `? ? ? ?` 3 2 ``` 1 ``` 今いる山札1の一番上のカードを表向きにします。 `? ? ? ?` 3 2 ``` 2 ``` 山札1の一番上には2と書かれたカードがあります。先ほどと同じ整数が出ることもあります。 `? 2 ? ?` 3 2 ``` 2 ``` 山札1から山札2へ移動します。 `? 2 ? ?` 4 2 ``` 1 ``` 山札2の一番上には1と書かれたカードがあります。 `? 2 1 ?` ↓ `? ? 1 ?` 4 2 ``` 0 ``` 山札2から山札0へ移動します。 `? ? 1 ?` 6 2 ``` 1 ``` 山札0の一番上には（一度表向きにしたことからすでに判明しているように）1と書かれたカードがあり、条件を満たすのでペアで取り除いてスコアを1点獲得します。 `1 ? 1 ?` ↓ `? ? ? ?` 6 3 ``` -1 ``` ゲームを終了します。さらに移動しようとすると、移動可能な総距離を超えてしまいWrong Answer扱いとなります。 `? ? ? ?` 6 3### テスター次のリンクから提供しています。 [テスター](https://github.com/recruit-communications/rco-contest-2019/tree/master/final_A/tester)