問題文

以下の画像を 4 色で塗り分けよ．ただし，隣り合う領域は同じ色で塗ってはならない．

なお，枠の外の余白は塗らなくてよい．

問題文

以下の条件を満たす 1 以上 20181224 以下の整数 n をすべて求めよ．

条件：ある正の整数 k および正の整数 a_1, b_1, a_2, b_2, \ldots, a_k, b_k, c に対して，n = a_1^{b_1} \times a_2^{b_2} \times \cdots \times a_k^{b_k} \times c であり，a_1, b_1, a_2, b_2, \ldots, a_k, b_k, c を (先頭の 0 のない) 十進表記で書いてこの順に繋げると n になる．

問題文

かつて，うさぎはパスカルの三角形を N 段書こうとした．上から i 段目 (0 \le i < N) で左から j 番目 (0 \le j \le i) に書かれる値を C[i][j] とする．うさぎは以下の手続きによって各 C[i][j] の値を計算しようとした

for i = 0 to N - 1:
    C[i][0] = C[i][i] = 1
    for j = 1 to i - 1:
        C[i][j] = C[i - 1][j - 1] + C[i - 1][j]

が，(上記擬似コード中 4 行目の) 足し算をちょうど 1 回だけ間違えて，正しい和より大きい整数にしてしまった．

さらに，年月を経てうさぎが書いたいくつかの整数が消えてしまった．

うさぎの書いた三角形の情報を表す整数 A_{i,j} (0 \le i < N，0 \le j \le i) が与えられる．

• A_{i,j} = 0 のとき，三角形の上から i 段目で左から j 番目に書かれた整数は消えてしまってわからない．
• A_{i,j} \ne 0 のとき，三角形の上から i 段目で左から j 番目に書かれた整数は A_{i,j} である．

うさぎがどの (i, j) で (どの C[i][j] を計算するときに) 足し算を間違えたかを特定せよ．ただし，そのような (i, j) としてありうるものが複数ある場合や，何かが間違っていてそのような (i, j) としてありうるものがひとつも存在しない場合は，その旨を報告すること．

制約

• 1 \le N \le 500．
• 0 \le A_{i,j} \le 10^9．
• i = 0, 1, \ldots, N - 1 に対し A_{i,0} = A_{i,i} = 1．

部分点

• N \le 50 を満たすデータセットに正解した場合は，20 点が与えられる．
• 追加制約のないデータセットに正解した場合は，上記とは別に 80 点が与えられる．

入力例 1

6
1
1 1
1 0 1
1 3 0 1
1 0 7 0 1
1 0 11 0 6 1

出力例 1

3 2

この場合，整数が消える前のうさぎが書いた三角形は以下のようであったと考えられる．C[3][2] を計算するときに 2 + 1 を誤って 4 としてしまっているので，(i, j) = (3, 2) を出力する．　

1
1 1
1 2 1
1 3 4 1
1 4 7 5 1
1 5 11 12 6 1

入力例 2

4
1
1 1
1 0 1
1 0 0 1

出力例 2

AMBIGUOUS

足し算をした箇所がすべて消えてしまっているので，いずれの場所でも間違えた可能性がありうる．

入力例 3

4
1
1 1
1 0 1
1 4 5 1

出力例 3

IMPOSSIBLE

問題文

N 個の真っ白な K 面さいころがある．くろうさとしろうさが次のゲームを行う．

1. くろうさがさいころの各面に 0 以上 10^9 以下の整数を 1 個ずつ書き込む．
2. さいころの中から，しろうさが 1 個を選ぶ．
3. 残ったさいころの中から，くろうさが 1 個を選ぶ．
4. くろうさとしろうさが選んださいころを同時に振り，出た目が大きいほうが勝ちとなる．値が同じ場合はしろうさの勝ちとする．

さいころは，K 個の面がそれぞれ確率 \frac{1}{K} で出るとする．しろうさとくろうさが共に自身の勝率を最大化するようにさいころを選ぶとき，くろうさの勝率が最大になるような整数の書き込み方を 1 つ答えよ．

制約

• 2 \le N \le 100．
• 1 \le K \le 10．

部分点

• N \le 4，K \le 6 を満たすデータセットに正解した場合は，20 点が与えられる．
• 追加制約のないデータセットに正解した場合は，上記とは別に 80 点が与えられる．

入力例 1

2 6

出力例 1

0 0 0 2 2 2
1 1 1 1 1 1

しろうさがどちらのさいころを選んでも，勝つ確率は \frac{1}{2} である．

ストーリー

くろうさ「XOR は甘え」

しろうさ「まーた始まった」

くろうさ「AND と OR は許してあげる」

しろうさ「えっとえっと」

くろうさ「否定はよくないよね〜うんうん」

しろうさ「否定ってもしかして NOT のこｔ

くろうさ「というわけで今年もがんばってねっ」

問題文

整数 N が与えられたとき，以下の仕様を満たすプログラムのうち，プログラム中での NOT の使用回数が最小のものを 1 つ出力せよ (NOT の使用回数が最小でないときも，後述のように部分点が与えられる場合がある)．

プログラムの入力は N 個のブール変数 b_0, b_1, \ldots, b_{N-1} であり，これらから 2 個を選んで XOR をとった値 b_i \operatorname{XOR} b_j をすべて求めたい．

プログラムは以下の N + N^2 + 10^5 個のブール変数 (true または false の値をとる) を扱うことができる：

• \mathrm{in}[i]   (i = 0, 1, \ldots, N - 1)
• \mathrm{out}[i][j]   (i = 0, 1, \ldots, N - 1，j = 0, 1, \ldots, N - 1)
• \mathrm{a}[k]   (k = 0, 1, \ldots, 10^5 - 1)

プログラムは 0 行以上 10^5 行以下からなり，上から下へと実行される．各行は

• 変数 = 変数 AND 変数
• 変数 = 変数 OR 変数
• 変数 = NOT 変数

のいずれかの形であり，右辺の計算結果を左辺の変数に代入することを表す．

実行開始時に，各 \mathrm{in}[i] は入力 b_i で，各 \mathrm{out}[i][j] および各 \mathrm{a}[k] は false で初期化される．実行終了時に，各 \mathrm{out}[i][j] の値は b_i \operatorname{XOR} b_j でなければならない．

制約

• 1 \le N \le 16

部分点

• N \le 2 を満たすデータセットに正解した場合は，10 点が与えられる．
• N \le 3 を満たすデータセットに正解した場合は，上記とは別に 10 点が与えられる．
• N \le 4 を満たすデータセットに正解した場合は，上記とは別に 20 点が与えられる．
• N \le 8 を満たすデータセットに正解した場合は，上記とは別に 20 点が与えられる．
• 追加制約のないデータセットに正解した場合は，上記とは別に 40 点が与えられる．
• 各データセットについて，正解ではないが，すべての入力について NOT の使用回数が N - 1 以下の正しいプログラムを出力した場合，そのデータセットの配点の 20 % が与えられる．

入力例 1

3

出力例 1

a[0] = NOT in[0]
a[1] = NOT in[1]
a[2] = NOT in[2]
a[901] = in[0] AND a[1]
a[902] = in[0] AND a[2]
a[910] = in[1] AND a[0]
a[912] = in[1] AND a[2]
a[920] = in[2] AND a[0]
a[921] = in[2] AND a[1]
out[0][1] = a[901] OR a[910]
out[0][2] = a[902] OR a[920]
out[1][0] = a[910] OR a[901]
out[1][2] = a[912] OR a[921]
out[2][0] = a[920] OR a[902]
out[2][1] = a[921] OR a[912]

このプログラムは，3 回の NOT の使用によって XOR をすべて計算している．ただし，NOT の使用回数はこれが最小ではない．

N = 3 の場合はこちらで手で遊べる． 表示/非表示

問題文

xy 座標平面上の相異なる 5 つの格子点 (A, B, C, D, E) によって定まる 4 つの線分 (AB, BC, CD, DE) が /\/\ であるとは，\overrightarrow{AB} = \overrightarrow{CD} かつ \overrightarrow{BC} = \overrightarrow{DE} を満たすこととする．ここで，4 点 P(x_P, y_P), Q(x_Q, y_Q), R(x_R, y_R), S(x_S, y_S) に対し \overrightarrow{PQ} = \overrightarrow{RS} とは x_Q-x_P = x_S-x_R かつ y_Q-y_P = y_S-y_R が成り立つことを表す．

平面上に N 個の /\/\ を置き，2 本以上の線分 (端点を除く) の交点となっている点の個数を最大化せよ．このとき，以下の条件を満たす必要がある．

• 各 /\/\ を構成する 5 つの点は，すべてその x 座標および y 座標の絶対値が 10^9 以下の整数でなければならない．
• 各 /\/\ を構成する 5 つの点は，他の /\/\ を構成する点のいずれとも一致してはならない．
• 各 /\/\ によって定まる線分たちは，他のどの線分とも重なってはならない (すなわち，線分どうしが 0 より大きい長さの共通部分を持ってはならない)．

制約

• 2 \le N \le 100．

入力例 1

2

出力例 1

1 1 2 6 3 1 4 6 5 1
7 1 1 2 6 3 0 4 5 5

この出力例を図示すると以下のようになる．2 本以上の線分 (端点を除く) の交点となっている 16 個の点は黄色で表されており，これが最大個数である．

問題文

くろうさとしろうさは以下のようなゲームをしようとしている．

• H 行 W 列のマス目に，くろうさは黒石を，しろうさは白石を置いていく．
• 最初しろうさは先手か後手かを選び，その後交互に 1 つずつ石を置いていく．
• 既に石が置いてあるマスに石を置くことはできない．
• 自分の色の石が 2 \times 2 のブロックになってはならない．すなわち，ある格子点を共有する 4 つのマス全てに自分の石が置かれているという状態になってはならない．
• 先に石を置けなくなった方の負け．

しろうさの代わりにこのゲームをプレーし勝利するプログラムを作成せよ．

なお，ゲームは T 回連続で行われるので，その全てに勝利しなければならない．

制約

• 1 \leq T \leq 25
• 1 \leq H,W \leq 40

部分点

• H, W が共に偶数である全てのテストケースに正解した場合は，25 点が与えられる．
• 全てのテストケースに正解した場合は，上記とは別に 75 点が与えられる．

入出力

1. 整数 T が標準入力に与えられる．
2. 以下が T 回繰り返される．
   1. 整数 H, W が空白区切りで標準入力に与えられる．
   2. あなたのプログラムは First または Second と出力しなければならない．それぞれ先手・後手を選択することを表す．
   3. 勝敗が決まるまで以下を繰り返す．
      • 自分の手番の場合：2 つの整数 r, c (0 \leq r \leq H-1, 0 \leq c \leq W-1) を空白区切りで出力する．これは r 行目 c 列目のマスに白石を置くことを表す．
      • 相手の手番の場合：2 つの整数 r, c (0 \leq r \leq H-1, 0 \leq c \leq W-1) が空白区切りで標準入力に与えられる．これは r 行目 c 列目のマスに黒石が置かれたことを表す．ただし，黒石を置くことのできるマスが存在しなかった場合は代わりに -1 -1 が標準入力に与えられる．この場合はしろうさの勝利となり，ゲームは終了する．

入出力例も参考にせよ．

注意点

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

あなたのプログラムが全てのゲームに勝利したのちに終了した場合，正答とみなされる．

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

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

入出力例

問題文

うさぎが Xmas Contest 2018 に向けて看板を作ろうとしている．看板はマス目が長方形のグリッド状に並んだもので，それぞれのマスには 1 文字だけ文字を書くことができる．文字を書かないマスがあっても構わない．

うさぎが書ける文字の種類は，英大文字 (A-Z)，飾りの星マーク (*) のいずれかである．

うなぎが看板を読むときには，以下のようにして看板から文字列を読みとる:

• 上の行から順に 1 行ずつ見ていく．
• それぞれの行に対し，その行のいずれのマスにも文字が書かれていなければ，その行は無視する．
• その行に文字の書かれているマスがあれば，そのうち最も左のマスに書かれている文字を読みとる．

うさぎは，うなぎが看板を読んだときに読みとる文字列から星マーク (*) を除いたものがちょうど文字列 S となるように看板を作ろうとしている．

それだけでなく，もし看板の行と列を反転させたとしたときに，うなぎが看板を読んだときに読みとる文字列から星マーク (*) を除いたものがちょうど文字列 T となるようにしたいと考えている．

うさぎは，文字を書くインクが節約できるとうれしいので，上記の条件を満たすような看板を作るときに文字を書く必要があるマスの個数の最小値を求めることにした．

制約

• 1 \le |S| \le 50．
• 1 \le |T| \le 50．
• S, T は英アルファベット大文字のみからなる．

入力例 1

USAGI
UNAGI

出力例 1

6

例えば以下のように文字を書けばよい．

入力例 2

WA
AC

出力例 2

4

例えば以下のように文字を書けばよい．

マス目のサイズに制限はないという点に注意せよ．

問題文

実数 X が与えられるので，以下の条件を満たす整数 a, b, c, d を 1 組求めよ：

• \lvert a \rvert \le 10^5，
• \lvert b \rvert \le 10^5，
• \lvert c \rvert \le 10^5，
• \lvert a X^3 + b X^2 + c X + d \rvert \le 10^{-10}，
• a, b, c, d のうち少なくとも 1 個は 0 ではない．

制約

• 0 \le X \lt 10．
• X は十進表記で小数点以下 12 桁までからなる．
• 以下の条件を満たす整数 a, b, c, d が存在する：
  • \lvert a \rvert \le 10^4，
  • \lvert b \rvert \le 10^4，
  • \lvert c \rvert \le 10^4，
  • \lvert a X^3 + b X^2 + c X + d \rvert \le 10^{-12}，
  • a, b, c, d のうち少なくとも 1 個は 0 ではない．

入力例 1

2.018000000000

出力例 1

0 0 1000 -2018

入力例 2

1.414213562373

出力例 2

0 1 0 -2

入力例 3

3.141592653589

出力例 3

5103 -2893 -4197 -116487

問題文

漢数字で表される非負整数に対する，演算「a の b 乗」のみからなる式 S が与えられるので，その値を十億九で割った余りを漢数字で出力せよ．

非負整数は漢数字によって，標準的な日本語で表記する．以下の点に注意せよ．

• 本問で用いられる文字は 〇, 一, 二, 三, 四, 五, 六, 七, 八, 九, 十, 百, 千, 万, 億 である．
• 0 は「〇」である．正の整数には文字 〇 は用いない．
• 10^3 は「千」である (「一千」ではない)．同様に，10^7 は「千万」，10^{11} は「千億」である．
• 10^4 は「一万」である (「万」ではない)．同様に，10^8 は「一億」である．

また，「〇の〇乗」は一であると約束する．

制約

• S に含まれる文字の個数は一以上十万以下である．
• S の各文字は 〇, 一, 二, 三, 四, 五, 六, 七, 八, 九, 十, 百, 千, 万, 億, の, 乗 のいずれかである．
• S は問題文の仕様を満たす正しい式である．

部分点

• S に含まれる文字の個数が千以下であるデータセットに正解した場合は，二十点が与えられる．
• 追加制約のないデータセットに正解した場合は，上記とは別に八十点が与えられる．

入力例 1

四の三の二乗乗

出力例 1

二十六万二千百四十四

入力例 2

四の三乗の二乗

出力例 2

四千九十六

入力例 3

十億十

出力例 3

一

入力例 4

一億二千三百四十五万六千七百八十九の二の〇の〇乗乗乗

出力例 4

六億千三百一万六千三百十九

サンプル入出力ファイルはこちらからダウンロードできる．