Xmas Contest 2016 昼の部

A - Array Sum

実行時間制限: 2 sec / メモリ制限: 256 MB

配点 : 100 点

問題文

うさぎは，長さ N の整数列 a = \{a_0,a_1,...,a_{N-1}\} を用意した．

あなたは，うさぎに以下のような質問をすることができる．

r-l が 2 冪数 (1,2,4,8,...) であるような l,r (0 \leq l \lt r \leq N) の組を 1 つ選び，数列 a の区間 [l,r) の和，すなわち (a_l+a_{l+1}+...+a_{r-1}) を質問する．

できるだけ少ない質問回数で，数列 a に含まれる数の総和を当てよ．

制約

1 \leq N \leq 10^5．
0 \leq a_i \leq 10^4．

採点

すべてのテストケースのうち最も質問クエリの回数が多かったものの回数を x としたとき，900/max(x,9) の小数点以下を切り捨てた値が得点となる．
ただし，不正解のケースが 1 つでもあった場合は 0 点となる．

入出力

まず，数列の長さを表す整数 N が標準入力に与えられる．
続いて，あなたのプログラムは質問を実行時間制限を超えない限り何回でも行うことができる．
1. 各質問では，文字 ? と 2 つの整数 l,r を空白区切りで標準出力に出力する．
  - l,r は問題文中の条件を満たしていなければならない．
2. すると，数列 a の区間 [l,r) の和が標準入力に与えられる．
最後に，文字 ! と，数列 a に含まれる数の総和を空白区切りで出力する．

入出力例も参考にせよ．

注意点

答えを出力した後，あなたのプログラムは直ちに終了しなければならない． 終了しなかった場合のジャッジ結果は不定である．また，正しくない出力をした場合の結果も不定である（必ずしも WA になるとは限らない）．

あなたのプログラムが正しい答えを出力して終了した場合，正答とみなされる．

出力した後に，出力をflushしなければならないことに注意せよ．flushしなかった場合，TLEとなることがある．

各言語での入出力の方法は過去の AtCoder で出題されている問題 (リンク: ABC 019 D: 高橋くんと木の直径) を参考にするとよい．

入出力例

N=7,\ a = \{1,2,3,4,5,6,7\} ときの入出力例を示す．

入力	出力	説明
`7`		数列の長さ `N` が与えられている．
	`?` `0` `1`	区間 `[0,1)` の和を質問している．
`1`		質問の回答が与えられている．
	`?` `0` `4`	区間 `[0,4)` の和を質問している．
`10`		質問の回答が与えられている．
	`?` `1` `3`	区間 `[1,3)` の和を質問している．
`5`		質問の回答が与えられている．
	`?` `3` `7`	区間 `[3,7)` の和を質問している．
`22`		質問の回答が与えられている．
	`!` `28`	答えを出力している．

B - Binary Tree

実行時間制限: 2 sec / メモリ制限: 256 MB

配点 : 100 点

問題文

うさぎは完全二分木を持っている．この完全二分木の深さは 11 であり，つまり頂点数は 4095 である．

うさぎはこの完全二分木を以下のように二次元平面に埋め込もうとしている．

各頂点をそれぞれ異なる格子点に埋め込む．
辺は頂点が埋め込まれた格子点どうしを結ぶ線分となる．
辺どうしは端点以外で交差しない．
辺上には端点以外の格子点を含まない．

入力

この問題では入力は与えられない．

出力

頂点の埋め込む格子点の座標を，通りがけ順（in-order）で出力せよ．ただし，座標を表す整数は 0 以上 10^9 以下の整数でなければならない．

採点

想定解の座標の最大値を x，提出された解答の座標の最大値を y としたとき，\sqrt{10000*x/y} の小数点以下を切り捨てた値が得点となる．
ただし，問題文中の条件を満たしていない場合は 0 点となる．

出力例

以下は，深さが 11 ではなく 2 であった場合の出力例である．

この出力例の場合，完全二分木は下図のように埋め込まれており，座標の最大値は 3 となる．

C - Cutting Swiss Roll

実行時間制限: 2 sec / メモリ制限: 256 MB

配点 : 100 点

問題文

白うさと黒うさはクリスマスケーキとして長さ N cm のロールケーキを購入した．このロールケーキは場所によって甘さが異なり，各 i (1 \leq i \leq N) に対し，ケーキの左端から i-1 cm の場所から i cm の場所までの甘さは整数 A_i で表される．

白うさと黒うさは，このケーキのうちちょうど 1 cm を 2 羽で一緒に食べ，残りの部分は冷蔵庫にしまおうと考えている．ケーキのどの部分を食べるかは以下のようにして決める．

まず白うさが，左端から k cm のところでケーキを 2 つに切り分ける．ここで k は 1 以上かつケーキの長さ未満の整数であればなんでもよい．
切り分けられた 2 つのケーキのうち，黒うさが好きな方をひとつを選んで冷蔵庫にしまう．

この手順 1, 2 を終えたあとでケーキがまだ 2 cm 以上残っている場合，次は黒うさがケーキを切り分けて白うさが片方を冷蔵庫にしまう．こうして長さ 1 cm のケーキが残るまで，白うさと黒うさは交代しながら手順 1, 2 を繰り返し行う．

白うさはとにかく甘いケーキが好きなので，最終的に残るケーキの甘さが最大になるように行動したいと考えている．一方，黒うさはビターな味付けのほうが好きなので，最終的に残るケーキの甘さが最小になるように行動したいと考えている．

双方が最適な行動をとったとき，最終的に残るケーキの甘さを X とする．白うさの最適な行動，すなわち黒うさがどのように行動しても最終的に甘さ X 以上のケーキを必ず残せるような戦略を実装したプログラムを作成せよ (X は明示的に与えられないことに注意せよ)．

制約

2 \leq N \leq 5,000．
1 \leq A_i \leq 10^9．
A_i は整数．

採点

あなたのプログラムが以下に示す入出力のフォーマットに従った上で，最終的に残ったケーキの甘さが X 以上である場合，正答と見なされる．

すべてのテストケースに正答すれば 100 点が与えられる．

入出力

まず，ケーキの長さを表す整数 N が標準入力に与えられる．続いて，ケーキの甘さを表す N 個の整数 A_1, A_2, ..., A_N が順に標準入力に与えられる．

その後，ケーキの切り分けが開始され，以下の入出力 1〜4 が繰り返される．

あなたのプログラムは，白うさがケーキを切る場所を表す整数 k を標準出力に出力する．これはケーキの左端から k cm の地点を切ることを意味する．
- k は 1 以上かつ現在のケーキの長さ未満でなければならない．
文字 L または R が標準入力に与えられる．L, R はそれぞれ黒うさが切れ目より左・右の部分を冷蔵庫にしまったことを表す．
- 黒うさのこの行動により残ったケーキが 1 cm になった場合，以降入力は与えられず，あなたのプログラムも直ちに終了せねばならない．
黒うさがケーキを切る場所を表す整数 k' が標準入力に与えられる．これはケーキの左端から k' cm の地点を切ることを意味する．
- k' は 1 以上かつ現在のケーキの長さ未満である．
あなたのプログラムは，文字 L または R を標準出力に出力する．L, R はそれぞれ白うさが切れ目より左・右の部分を冷蔵庫にしまうことを表す．
- 白うさのこの行動により残ったケーキが 1 cm になった場合，以降入力は与えられず，あなたのプログラムも直ちに終了せねばならない．

入出力例も参考にせよ．

注意点

ケーキの長さが 1 cm になった後，あなたのプログラムは直ちに終了しなければならない． 終了しなかった場合のジャッジ結果は不定である．また，正しくない出力をした場合の結果も不定である（必ずしも WA になるとは限らない）．

出力した後に，出力をflushしなければならないことに注意せよ．flushしなかった場合，TLEとなることがある．

各言語での入出力の方法は過去の AtCoder で出題されている問題 (リンク: ABC 019 D: 高橋くんと木の直径) を参考にするとよい．

入出力例

N=5,\ A = \{1,2,3,4,5\} ときの入出力例を示す．

入力	出力	説明
`5` `1` `2` `3` `4` `5`		ケーキの長さ `N` と甘さ `A` が与えられている．
	`4`	白うさがケーキを左から `4` cm の点で切る．
R		黒うさが右の部分を冷蔵庫にしまう．
`1`		黒うさがケーキを左から `1` cm の点で切る．
	L	白うさが左の部分を冷蔵庫にしまう．
	`2`	白うさがケーキを左から `2` cm の点で切る．
R		黒うさが右の部分を冷蔵庫にしまう．
`1`		黒うさがケーキを左から `1` cm の点で切る．
	L	白うさが左の部分を冷蔵庫にしまう．この時点でケーキが `1` cm となるので応答は終了する．

上記の応答例では最終的に甘さ 3 のケーキが残っている．このケースでは X = 3 (白うさと黒うさが双方ともに最適に行動したときに残るケーキの甘さが 3) であるため，上記の応答例は正答と見なされる．

D - Distributed Sorting

実行時間制限: 2 sec / メモリ制限: 256 MB

配点 : 100 点

問題文

時は 20XX 年，世界は Distributed AtC◯der 社の支配によるディストピアである．現在，人々の娯楽は分散・並列処理を題材としたプログラミングコンテストに限られている．例えば，週末に家族でスーパーコンピュータを (ssh で) 訪れるというのはとてもよく見られる光景である．（問題文参考: UTPC 2011 問題 A）

（実際のところ以下で述べる問題設定は分散というより並列処理で Distributed Sorting というより Parallel Sorting っぽいのだが，頭文字が D の方が都合がいいし，ここで言い訳もしていることだし，とにかく今日はクリスマスなので我々は細かいことは気にしない．）

分散・並列処理においては，基礎的と思える処理でも多種多様な工夫が考えられることが多くある．たとえば，N 個の相異なる整数からなる整数列 X_1, X_2, ..., X_N を昇順にソートする処理を考えよう．

ソートには，以下の 1 種類の操作が可能なマシンを用いるとする．

操作: 2k 個の相異なるインデックス A_1, A_2, ..., A_{2k} を入力として与えると，各 i (1 \leq i \leq k) に対し X_{A_{2i-1}} と X_{A_{2i}} (X の A_{2i-1} 番目と A_{2i} 番目) の値を交換する．ただし，各 j (1 \leq j \leq 2k) に対し 1 \leq A_j \leq N でなければならない．

たとえば X = (5, 3, 1, 2, 4) のとき k=2，(A_1, A_2, A_3, A_4) = (1, 3), (2, 4) として操作を行うと，X = (1, 2, 5, 3, 4) になる．

この操作だけを使って X を昇順にソートするために必要な操作の最小回数を求め，実際にその最小回数の操作で X をソートする手順をひとつ出力するようなプログラムを作成せよ．

制約

1 \leq N \leq 10^5．
1 \leq X_i \leq 10^9．
X_i は相異なる整数．

入力

入力は以下の形式で標準入力から与えられる．

N
X_1 X_2 ... X_N

出力

1 行目に X を昇順にソートするために必要な操作の最小回数を出力し，それに続いて，各操作の内容を 1 操作につき 1 行で出力せよ．

操作を表す行の最初には，値の交換を行うペア数 k を出力せよ．その後，空白に続いて 2k 個の整数 A_1, A_2, ..., A_{2k} を空白区切りで出力せよ．

入力例 1

3
2 3 1

出力例 1

2
1 1 3
1 2 3

操作の回数が最小であり，正しく昇順にソートできるような手順であれば，これ以外の出力でも正解と見なされる．たとえばこの入力例に対しては

2
1 1 2
1 3 1

のような出力も正解と見なす．

入力例 2

3
1 2 3

出力例 2

入力例 3

5
5 4 3 2 1

出力例 3

1
2 1 5 2 4

E - Examination, Estimation

実行時間制限: 2 sec / メモリ制限: 256 MB

配点 : 100 点

問題文

うさぎは 50 問の問題からなる試験を受けようとしている．各問題は四択問題であり，0, 1, 2, 3 の四つの選択肢のうちいずれかひとつが正答で，他は誤答である．

うさぎが試験を受けるより前に，30 匹のうなぎが全く同じ試験を受けた．それぞれのうなぎの試験への回答方法は以下の 3 つのタイプのうちいずれかであり，どのタイプのうなぎも 10 匹ずついることが分かっている．

各問題に対し独立に，2/3 の確率で正答を選び，1/3 の確率で誤答をひとつ選ぶ．誤答を選ぶ際は，どの誤答も同じ確率で選ぶ．
各問題に対し独立に，1/3 の確率で正答を選び，2/3 の確率で誤答をひとつ選ぶ．誤答を選ぶ際は，どの誤答も同じ確率で選ぶ．
各問題に対し独立に，4 つの選択肢の中から同じ確率でひとつを選ぶ．

問題はうなぎ語で書かれており，うさぎは自力で問題を解くことはできない．そこでうさぎは超能力カンニングにより，すべてのうなぎの答案を手に入れた．ただし，どのうなぎが上記 3 タイプのどれに属するかは分かっていない．手に入れた情報だけをもとに，できるだけ多く正答を当てよ．

採点

1 つの入力データにつきちょうど 200 個のテストケースが与えられる．1 つのテストケースが一回の試験に対応している．

各試験について，出力された回答のうち誤答が 3 個以下であれば合格とし，そうでなければ不合格とする．

その上で，1 つの入力データに含まれる 200 個の試験のうち 90% 以上に合格 (すなわち 180 個以上の試験に合格) すれば，そのデータについては正解と見なされる．

入力データは 10 個あり，すべての入力データに正解できれば 100 点が与えられる．

各試験の入力データは，正答を一様ランダムに選んだあと，うなぎのタイプ分けも一様ランダムに選んで生成している．更に具体的な生成方法についてはページ下部を参照せよ．ただし，具体的な生成方法には依存しない解法で 100 点を得ることが可能であるため，必ずしもページ下部の情報を読む必要はなく，また読んでもこの問題を解くために有用な情報が得られるとは限らない．

入力

入力は以下の形式で標準入力から与えられる．

A_{1,1} A_{1,2} ... A_{1,50}
A_{2,1} A_{2,2} ... A_{2,50}
:
A_{30,1} A_{30,2} ... A_{30,50}
(ここまでが 1 個の試験に対応しており，以下同様の形式の入力がさらに 199 個与えられる)

ここで A_{i,j} は i 匹目のうなぎの j 問目の問題への回答であり，0, 1, 2, 3 のいずれかである．

出力

200 行出力せよ．i (1 \leq i \leq 200) 行目には i 個目の試験の回答を出力せよ．

各試験の回答は空白で区切られた 50 個の整数 (0, 1, 2, 3 のいずれか) として出力せよ．j (1 \leq j \leq 50) 個目の整数が j 問目の問題への回答に対応する．

入力例 1

0 2 2 0 0 0 2 1 1 3 1 1 3 3 1 2 2 1 3 0 1 0 1 2 1 3 3 0 0 1 1 1 3 2 1 2 0 2 2 1 2 3 2 0 2 2 2 0 3 3
0 3 3 1 2 3 0 0 2 0 0 2 3 1 2 0 3 2 0 2 2 1 1 2 3 0 1 2 2 0 3 3 0 2 0 3 1 2 2 1 0 3 1 1 1 0 2 1 3 1
3 2 1 0 1 1 2 0 1 1 0 3 0 2 0 0 2 3 2 2 3 1 2 1 0 2 3 0 1 0 1 0 2 3 2 1 1 0 0 0 3 3 3 0 2 2 2 2 2 3
2 0 2 2 0 1 1 1 0 3 1 0 1 1 3 3 0 0 3 1 0 3 0 2 2 0 1 3 3 1 3 3 3 0 2 2 3 2 0 3 0 3 1 1 0 2 3 0 3 1
1 3 0 1 1 1 1 3 2 2 0 2 0 1 0 3 2 3 3 0 1 3 2 1 1 3 1 0 1 2 0 0 3 2 0 3 0 2 1 1 0 1 0 1 2 0 0 3 0 0
2 1 0 1 3 2 1 1 2 3 0 2 3 2 2 1 1 2 1 2 1 3 3 2 1 1 2 3 0 0 3 0 2 3 3 3 1 3 1 1 2 0 3 3 3 2 1 1 3 0
3 0 2 0 0 0 2 0 3 3 0 3 0 1 2 2 1 1 2 0 2 0 2 3 2 2 0 3 2 2 2 3 0 2 0 3 1 0 2 0 3 3 0 2 2 0 2 3 2 3
3 0 1 0 0 0 2 3 2 3 3 3 1 1 3 1 2 2 1 0 0 0 0 1 1 1 0 0 3 3 2 2 3 2 0 3 2 3 1 0 1 0 3 3 2 0 2 3 2 3
1 1 2 0 0 0 2 0 2 3 0 2 0 1 2 2 1 2 3 0 2 0 0 0 0 3 2 1 2 0 0 3 3 3 1 3 0 0 1 0 2 2 3 0 2 0 2 0 2 3
2 0 2 0 0 0 2 0 0 3 0 2 0 1 0 3 1 2 2 0 2 1 0 3 2 2 2 2 2 0 2 3 3 3 1 3 0 0 1 0 3 3 3 0 2 3 0 3 3 3
0 2 3 2 3 2 2 0 1 1 1 3 0 1 2 1 1 1 1 0 2 2 2 2 2 1 2 2 2 0 1 0 2 2 0 0 1 0 2 3 3 2 3 0 2 0 1 0 1 3
1 1 0 0 0 3 2 0 2 0 1 0 3 1 2 3 1 2 2 2 3 1 2 0 3 2 1 1 3 0 3 3 2 1 0 2 1 1 3 0 3 2 2 2 3 3 0 2 2 1
3 1 1 0 1 2 3 2 1 2 3 0 2 1 0 2 0 1 2 0 2 0 3 2 2 1 0 2 0 3 1 2 3 0 1 0 2 2 1 0 2 1 1 1 3 0 3 3 0 2
0 0 2 1 1 3 3 0 3 3 3 2 1 2 1 3 3 2 2 2 3 0 2 3 2 3 0 0 0 0 3 3 2 0 3 0 2 3 1 1 1 0 3 1 1 2 2 1 2 0
3 1 2 3 1 0 0 2 2 2 0 3 0 1 1 2 1 2 3 0 2 0 0 1 1 2 2 1 2 1 2 1 3 0 1 3 0 0 0 3 3 0 3 0 2 0 2 3 0 3
3 3 2 0 2 0 2 0 1 3 0 2 0 0 0 1 3 1 2 1 2 2 0 1 3 2 2 1 2 0 3 3 3 1 1 3 2 2 1 0 3 3 3 0 2 3 2 3 2 3
2 1 1 3 3 0 3 3 0 1 1 0 0 1 3 0 2 2 1 3 2 3 2 3 3 0 3 0 1 1 0 1 0 2 1 1 2 3 2 2 0 1 1 0 3 2 0 0 0 3
3 1 2 3 0 3 2 2 3 1 1 1 1 1 3 1 0 3 0 1 2 2 3 0 3 2 0 1 3 0 2 1 3 2 1 3 0 3 1 3 3 3 1 2 2 2 1 2 1 0
3 2 1 2 0 3 2 0 2 0 2 3 0 1 2 3 2 1 0 0 2 1 1 2 1 2 3 1 0 3 2 3 0 2 2 2 3 2 1 1 2 0 2 1 1 3 0 0 1 3
3 2 2 2 0 2 2 3 2 3 0 2 0 2 0 2 3 2 0 2 0 3 0 1 0 1 2 3 2 0 0 3 3 3 3 3 2 0 3 0 1 3 3 2 2 0 2 3 2 3
3 2 2 2 1 1 2 3 2 3 0 1 0 1 0 2 1 0 2 0 2 0 0 1 1 2 2 3 1 2 3 3 3 3 1 3 2 0 1 3 3 1 3 0 2 2 0 3 2 3
2 0 3 1 0 0 0 1 1 0 0 2 3 1 1 0 0 1 2 0 3 0 0 2 0 0 2 2 1 0 1 3 3 2 2 1 0 2 1 1 1 2 2 2 1 1 1 0 1 2
2 1 3 0 2 0 3 2 2 3 1 2 0 0 0 2 0 2 2 0 2 0 0 1 1 0 3 1 3 1 2 3 3 3 2 3 3 2 2 3 3 0 1 0 3 0 0 3 1 2
3 1 2 3 0 0 2 1 2 3 0 2 2 1 0 2 1 2 2 0 2 2 1 1 1 2 0 1 2 3 2 3 3 1 1 3 2 0 1 0 0 0 1 1 2 0 2 3 2 3
1 1 0 0 1 2 0 2 2 3 0 2 1 1 3 1 0 2 3 0 3 0 1 2 1 1 0 0 2 3 2 2 2 2 1 0 0 0 1 0 0 2 2 0 2 0 1 0 2 3
2 1 0 3 1 2 2 0 3 2 0 0 0 1 2 2 0 1 3 2 1 0 3 3 1 2 3 2 2 1 2 3 1 0 1 2 0 3 3 3 0 0 3 1 0 3 3 3 2 0
1 2 1 2 0 2 2 0 1 1 3 2 3 2 1 1 3 2 3 1 3 2 0 0 3 2 1 0 2 2 2 1 3 0 0 2 2 0 1 3 3 0 0 0 1 3 0 0 3 0
2 2 3 0 0 0 3 1 2 3 0 1 1 1 3 2 3 2 2 3 2 0 1 1 3 2 1 1 1 0 3 3 1 1 0 2 1 0 3 2 2 3 0 2 0 3 1 0 2 0
2 3 0 0 0 3 2 0 2 1 1 2 0 1 3 0 1 1 2 0 1 2 2 2 1 1 1 3 3 1 2 1 1 2 2 3 2 2 3 0 0 1 1 0 3 2 0 3 3 1
1 1 2 2 1 0 3 2 0 2 3 2 1 0 3 1 1 0 1 0 1 3 0 3 1 2 1 2 2 0 2 0 0 3 1 2 1 3 0 2 3 0 3 2 2 1 0 2 3 3

本来の入力データはこの後さらに試験 199 個分のデータが続くが，この例ではそれを省略し，最初の 1 回の試験に対応するデータのみを載せていることに注意せよ．

出力例 1

3 2 2 0 0 0 2 0 2 3 0 2 0 1 0 2 1 2 2 0 2 0 0 1 1 2 2 1 2 0 2 3 3 3 1 3 2 0 1 0 3 0 3 0 2 0 2 3 2 3

出力についても，本来はこの後さらに試験 199 個分のデータを出力せねばならないことに注意せよ．

なお，この入力例は本来のデータと同様の方法で生成したあとに最初の 1 個の試験だけを抜き出したものであり，出力例の回答は誤答を含まない (自分のプログラムを手元でテストする際などに使ってもよい)．

入力データについて

この問題の入力データは以下に示す C++ プログラムによって生成されている．

このプログラムは標準入力から乱数の種となる整数 w を入力し，この問題の入力データを出力する．入力例 1 のデータは w = 0 とした場合の最初の 1 個の試験である．

ジャッジに使用される入力データは w の値を 1 以上 10^9 以下の整数から 10 個選び生成されたものである．

なお，この具体的な生成方法に依存しない解法が存在することの根拠のひとつとして，以下の生成プログラムに依存しないこの問題の解答プログラムで，0≦w≦1,000 の 1,001 個の入力データすべてに正解できるものが存在する．

生成プログラム:

#include <iostream>
#include <cstdint>

using namespace std;

uint32_t x = 123456789, y = 362436069, z = 521288629, w = 88675123;

uint32_t xor128() {
  uint32_t t = x ^ (x << 11);
  x = y; y = z; z = w;
  return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
}

int randint(int lo, int hi) {
  uint64_t v = ((uint64_t)xor128() << 32) | xor128();
  return v % (hi - lo + 1) + lo;
}

void generate() {
  const int N = 30, Q = 50;

  int correct_answer[Q];
  for (int i = 0; i < Q; ++i) {
    correct_answer[i] = randint(0, 3);
  }

  int eel_type[N];
  for (int i = 0; i < N; ++i) {
    eel_type[i] = i / (N / 3);
  }
  for (int i = N - 1; i >= 1; --i) {
    swap(eel_type[i], eel_type[randint(0, i)]);
  }

  for (int i = 0; i < N; ++i) {
    int eel_answer[Q];
    for (int j = 0; j < Q; ++j) {
      bool correct = false;
      if (eel_type[i] == 0) correct = randint(0, 2) != 0;
      if (eel_type[i] == 1) correct = randint(0, 2) == 0;
      if (eel_type[i] == 2) correct = randint(0, 3) == 0;
      if (correct) {
        eel_answer[j] = correct_answer[j];
      } else {
        eel_answer[j] = (correct_answer[j] + randint(1, 3)) % 4;
      }
    }
    for (int j = 0; j < Q; ++j) {
      printf("%d%c", eel_answer[j], j+1 == Q ? '\n' : ' ');
    }
  }
}

int main() {
  cin >> w;
  for (int i = 0; i < 10000; ++i) {
    xor128();
  }
  for (int t = 0; t < 200; ++t) {
    generate();
  }
  return 0;
}

F - Fifty-Fifty?

実行時間制限: 2 sec / メモリ制限: 256 MB

配点 : 100 点

問題文

うさぎは，A を A 個，B を B 個持っている．うさぎはこれらから N 文字を選んで並べて作ることの出来る K 次回文の個数の偶奇が気になっている．

ただし，K 次回文とは，以下のような操作をちょうど K 回行うことで回文にすることの出来る文字列のことを指すものとする．

追加：文字列の末尾に文字を 1 つ追加する．
削除：文字列の末尾の文字を 1 つ削除する．
置換：文字列の末尾の文字を 1 つ，別の文字に置き換える．

例えば ABB は，追加を 1 回行うことで ABBA に出来るため，1 次回文である．また，削除を 1 回行ってから置換を 1 回行うことで AA に出来るため，2 次回文でもある．

この問題では 1 つの入力データに複数のテストケースが含まれている．テストケースの個数は T 個であり，i\ (1 \leq i \leq T) 番目のテストケースでは N_i,\ A_i,\ B_i,\ K_i の組が与えられる．

制約

1 \leq T \leq 100．
0 \leq A_i,\ B_i \leq 100．
1 \leq N_i \leq A_i+B_i．
0 \leq K_i \leq N_i．

入力

入力は以下の形式で標準入力から与えられる．

T
N_1 A_1 B_1 K_1
N_2 A_2 B_2 K_2
:
N_T A_T B_T K_T

出力

それぞれのテストケースに対し，作ることの出来る K 次回文の個数を 2 で割った余りを 1 行ずつ出力せよ．

入力例 1

2
3 3 1 0
3 1 2 2

出力例 1

0
1

1 つ目のテストケースで作ることの出来る 0 次回文は AAA と ABA の 2 つである．0 次回文は回文そのものである点に注意せよ．

2 つ目のテストケースで作ることの出来る 2 次回文は ABB と BAB と BBA の 3 つである．

G - Guide Passengers

実行時間制限: 2 sec / メモリ制限: 256 MB

配点 : 100 点

問題文

うさ鉄道は，うさぎのための鉄道である．うさ鉄道には東西に伸びる 1 本の長い線路と N 個の駅がある．駅には西から順に 1～N の番号が付けられている．各駅には capacity があり，駅 i\ (1 \leq i \leq N) には同時に C_i 羽までしか居ることができない．

うさ鉄道では M 本の列車を運行する予定で，列車 i\ (1 \leq i \leq M) は時刻 S_i に駅 A_i を出発して時刻 T_i に駅 A_i+1 に到着する列車であり，B_i 羽までうさぎを乗せることができる．うさ鉄道には線路は 1 本しかないため，追い越しが発生しないように列車の発着時刻を決めている．また，同時刻に同じ駅を出発する列車の組や，同時刻に同じ駅に到着する列車の組は存在しない．ただし，ある時刻にある駅を出発する列車と同時刻に同じ駅を到着する列車が存在することはある．この場合，駅の capacity によらず，列車が発車するまでは乗り降りを何羽でも自由に行うことが出来る．

今，駅 1 に C_1 羽のうさぎがおり，全員が駅 N に向かおうとしている．各駅の capacity を超えないようにうまくうさぎを運んだとき，最大で何羽のうさぎを駅 N に運ぶことが出来るだろうか？

制約

2 \leq N \leq 500,000．
0 \leq M \leq 500,000．
1 \leq C_i,\ B_i \leq 10^9．
1 \leq S_i \lt T_i \leq 10^9．
1 \leq A_i \leq N-1．
A_i = A_j を満たすような i,\ j\ (i \neq j) であって，S_i \leq S_j かつ T_i \geq T_j を満たすようなものは存在しない．
- つまり，追い越しは発生せず，同時刻に同じ駅を出発する列車の組や，同時刻に同じ駅に到着する列車の組は存在しない．

入力

入力は以下の形式で標準入力から与えられる．

N M
C_1 C_2 ... C_N
S_1 T_1 A_1 B_1
S_2 T_2 A_2 B_2
:
S_M T_M A_M B_M

出力

駅 N に運ぶことの出来るうさぎの羽数の最大値を出力せよ．

入力例 1

出力例 1

以下のように 5 羽のうさぎを運ぶことが出来る．

列車 1 に 3 羽乗る．
- 駅 2 で列車 2 に全員が乗り換える．
- 駅 3 で全員降りる．
列車 4 に 2 羽乗る．
- 駅 2 で全員降りて列車 3 を待つ．
- 列車 3 に全員乗る．
- 駅 3 で全員降りる．

入力例 2

出力例 2

入力例 3

2 1
1000000000 2016
999999999 1000000000 1 1000000000

出力例 3

入力例 4

2 0
12 24

出力例 4

入力例 5

出力例 5

H - High-powered Illuminations

実行時間制限: 3 sec / メモリ制限: 256 MB

配点 : 100 点

問題文

うさぎはクリスマスに向けてクリスマスツリーを用意した．

賢明なる参加者諸氏はお気づきかもしれないが，クリスマスツリーとはもちろんグラフ理論における木構造のことである．ツリーは N 個の頂点 (頂点 1,\ 2,\ ...,\ N) からなり，N-1 本の辺を持つ．i (1 \leq i \leq N-1) 本目の辺は頂点 A_i と頂点 B_i を結ぶ長さ C_i の辺である．

うさぎは K 個の電球を持っており，それぞれの電球をツリーの頂点に置いて飾りつけようとしている．しかし，うさぎの持っている電球は非常に光量が大きいため，あまり電球どうしが近くなるとツリーが眩しくなりすぎてしまう．そこでうさぎは，電球どうしの距離をできるだけ遠ざけて電球を配置することにした．ここで，電球どうしの距離とは，電球が設置された頂点どうしの距離である．2 つの頂点間の距離は，片方の頂点からもう一方の頂点へツリーの辺を辿って行くときに，辿る辺の長さの和の最小値である．

N 個の頂点のうち K 個に電球を置いて光らせるとき，電球どうしの距離の最小値 d を考える．d として考えられる値のの最大値を求めよ．

制約

2 \leq K \leq N \leq 200,000．
1 \leq A_i, B_i \leq N．
1 \leq C_i \leq 5,000．
A_i \neq B_i．
入力は木構造を表していることが保証される．

部分点

N \leq 40,000 であるようなデータセットに正解した場合は，50 点が与えられる．
追加制約のないデータセットに正解した場合は，上記とは別に 50 点が与えられる．

入力

入力は以下の形式で標準入力から与えられる．

N K
A_1 B_1 C_1
A_2 B_2 C_2
:
A_{N-1} B_{N-1} C_{N-1}

出力

電球どうしの距離の最小値 d として考えられる値の最大値を 1 行に出力せよ．

入力例 1

出力例 1

頂点 1,\ 3,\ 4 に飾れば良い．

入力例 2

出力例 2

頂点 2,\ 4,\ 6,\ 9 に飾れば良い．

入力例 3

出力例 3

入力例 4

出力例 4

I - ISOLT

実行時間制限: 2 sec / メモリ制限: 256 MB

配点 : 100 点

問題文

テトロミノには下図のように I, S, O, L, T の 5 種類がある．

うさぎは，テトロミノをいくつか持っている．うさぎはそれらのテトロミノを回転させたり裏返したりして，縦 H 行，横 W 列のマス目に沿って互いに重ならないようにすべて並べてアートを作った．このとき，テトロミノによって覆われたマスの情報は文字列の列 C によって以下のように表された．

C_{i,j} が o であるとき，i 行目 j 列目のマスは覆われていたことを表す．
C_{i,j} が . であるとき，i 行目 j 列目のマスは覆われていなかったことを表す．

その後，うさぎはこのアートを壁に飾ろうと持ち上げたが，その拍子にアートを崩してしまった．うさぎは慌てて散らばったテトロミノをかき集めたが，どうしても 1 つだけ見つからなかった．

現在，うさぎの手元には I テトロミノが I 個，S テトロミノが S 個，O テトロミノが O 個残っている．L テトロミノと T テトロミノは 1 つも残っていない．うさぎは，テトロミノによって覆われたマスの情報 C も覚えている．うさぎは，これらの情報から，無くしたテトロミノがどの種類であったかを推察することにした．

制約

1 \leq H,\ W \leq 100．
0 \leq I,\ S,\ O．
C_{i,j} は o または .．
問題文の条件をみたすようなテトロミノの並べ方が 1 通り以上存在する．
答えは一意に定まる．

部分点

答えが L または T であるようなデータセットに正解した場合は，15 点が与えられる．
追加制約のないデータセットに正解した場合は，上記とは別に 85 点が与えられる．

入力

入力は以下の形式で標準入力から与えられる．

H W
I S O
C_{1,1}C_{1,2}...C_{1,W}
C_{2,1}C_{2,2}...C_{2,W}
:
C_{H,1}C_{H,2}...C_{H,W}

出力

うさぎが無くしたテトロミノの種類を表す文字（I, S, O, L, T のうちのいずれか）を出力せよ．

入力例 1

4 5
1 1 1
o.ooo
ooooo
.o.oo
.oooo

出力例 1

うさぎの作ったアートは，例えば下図の様なものであったと考えられる．

入力例 2

5 9
1 4 2
.o.......
oooo.ooo.
oooo.oooo
ooo.ooooo
oooo.oooo

出力例 2

うさぎの作ったアートは，例えば下図の様なものであったと考えられる．

入力例 3

1 4
0 0 0
oooo

出力例 3

入力例 4

8 7
4 4 4
oooooo.
ooooooo
ooooooo
o.ooooo
ooooo.o
ooooooo
ooooooo
.oooooo

出力例 4

J - Just a Single Testcase

実行時間制限: 2 sec / メモリ制限: 256 MB

配点 : 100 点

問題文

うなぎは Xmas Contest 2016 の準備をしていたが，入力データを作るのが面倒になってしまった．

そこでうなぎは，多くの問題の入力データとして使えるような便利な整数列が存在するかが気になった．

以下では，問題の入力を整数列で簡単に表すことが難しい A, C 問題 (リアクティブ形式)・B 問題 (入力なし)・I 問題 (入力が文字列) を除いた Xmas Contest 2016 の問題 (すなわち D, E, F, G, H, J 問題) について考える．

ある整数列 Z が問題 X の入力データとして使えるとは，問題 X の条件を満たす入力データであって，そのデータに現れる整数を順に並べた整数列が Z の接頭辞になるようなものが存在することを言う．簡単に言えば，Z のある接頭辞 (先頭から連続する要素をいくつか持ってきたもの) が，改行等のフォーマットを除いて問題 X の正当な入力データになっていればよい．

この問題の入力として整数 t (t=1,2) が与えられる．以下の全ての条件を満たす整数列 Z をひとつ求めよ．

Z の要素数は 1 以上 500,000 以下である．
Z のすべての要素は 0 以上 10^9 以下の整数である．
t=1 のとき，Z は最も多くの問題の入力データとして使える．すなわち，「Z が問題 X の入力データとして使える」ような X (ここで X は D, E, F, G, H, J のいずれか) の個数が最大となる．個数さえ最大であれば，どの問題に対して使えるデータであるかは問わない．
t=2 のとき，Z は少なくとも問題 D, F, H の入力データとして使えるような整数列のうち，辞書順で最大のものである．すなわち，条件を満たす整数列のうち 1 個目の要素が最も大きく，さらにそのようなものの中では 2 番目の要素が最も大きく，……となるものである (つまり整数列としての辞書順であり，出力した際の文字列としての辞書順ではない)．

制約

t=1,2．

部分点

t = 1 を満たすデータセットに正解した場合は，50 点が与えられる．
t = 2 を満たすデータセットに正解した場合は，上記とは別に 50 点が与えられる．

入力

入力は以下の形式で標準入力から与えられる．

出力

問題文の条件を満たす整数列 Z の長さを 1 行目に出力せよ．

2 行目に Z の要素を順に空白区切りで出力せよ．

条件を満たす整数列 Z が複数考えられる場合はどれを出力しても構わない．

入力例 1

出力例 1

3
100 200 300

この出力例は出力形式の確認のためのものであり，実際には間違いである．