A - カレンダー
配点: $250$ 点
ある日, E869120はそのカレンダーに以下の規則性があることを発見した。
そこで、以下の条件を満たす正方形の置き方を数え上げしてみることにした。
この場合、以下の表のようなカレンダーになっている。
ここでは, $(i, j)$ を上から $i$ 番目, 左から $j$ 番目のマスとする。
問題文担当者:square1001
実行時間制限: 1 sec / メモリ制限: 256 MB
問題文
E869120は, 縦に長いカレンダーらしいものを持っていた。ある日, E869120はそのカレンダーに以下の規則性があることを発見した。
- 上から $i$ 番目, 左から $j$ 番目に書かれている整数は $7i+j-7$ である。
そこで、以下の条件を満たす正方形の置き方を数え上げしてみることにした。
- 正方形の枠内に入っている $9$ 個の数字の和を $11$ で割った余りは $k$ である。
入力
入力は以下の形式で標準入力から与えられる。$n \quad k$
- 1行目には、カレンダーの段数 $n$ と, 正方形を置く時の条件となる数 $k$ が空白区切りで与えられる。
出力
- 条件を満たす $3 \times 3$ の正方形の置き方の通り数を1行に出力しなさい。
- ただし, 1つも条件を満たすような置き方ができない場合, $0$ と出力しなさい。
制約
- $1 \le n \le 10^9$
- $0 \le k \le 10$
小課題
小課題1 [ $150$点 ]
- $1 \le n \le 100$ を満たす。
小課題2 [ $100$ 点 ]
- 追加の制約はない。
入力例1
7 7
出力例1
2
1列目 | 2列目 | 3列目 | 4列目 | 5列目 | 6列目 | 7列目 | |
1行目 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
2行目 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
3行目 | 15 | 16 | 17 | 18 | 19 | 20 | 21 |
4行目 | 22 | 23 | 24 | 25 | 26 | 27 | 28 |
5行目 | 29 | 30 | 31 | 32 | 33 | 34 | 35 |
6行目 | 36 | 37 | 38 | 39 | 40 | 41 | 42 |
7行目 | 43 | 44 | 45 | 46 | 47 | 48 | 49 |
ここでは, $(i, j)$ を上から $i$ 番目, 左から $j$ 番目のマスとする。
- 左上が $(1, 5)$ のとき, $5+6+7+12+13+14+19+20+21=117$ となり, $11$ で割った余りは $7$ となる。
- 左上が $(3, 2)$ のとき, $16+17+18+23+24+25+30+31+32=216$ となり, $11$ で割った余りは $7$ となる。
入力例2
6 0
出力例2
2左上が $(1, 3)$ または $(4, 4)$ のときのみ条件を満たす。
入力例3
18 10
出力例3
7左上のマスが $(2,2), (5,3), (8,4), (10,1), (11,5), (13,2), (16,3)$ のとき, 条件を満たす。
入力例4
100 8
出力例4
45この入力例は小課題1を満たす。
B - 石落としゲーム
よって, $7+16=23$ 点となる。
また, 場所 $(4,3)$ を消すのが最適である。
問題作成者:E869120
実行時間制限: 1 sec / メモリ制限: 256 MB
配点: $300$ 点
この試験の内容は、以下のようなものであります。
square1001氏を助けるために、最大の点数を出力しなさい。
問題文
square1001氏は、パソコン部に入るために試験を受けました。この試験の内容は、以下のようなものであります。
- $H \times W$ の盤面が与えられる。
- その盤面の各マスは、 $1 \sim 9$ の数字が書かれている。また、1行目が一番上である。
- あなたは、セルのうち1つのマスを消すことができる。消した上のマスは落ちてくる。
- 1:$K$ 個以上の水平に隣り合うセルに同じ数字を彫った石があれば,これらの石は消滅する.こうした石群の消滅はすべて同時に起きる。
- 2:石が消滅したセルの上方のセルに石があれば,空きを埋めるように石が落下する。
- 3:すべての石の落下完了後に,消滅の条件を満たすようになった石群があれば,ステップ1に戻って繰り返す。
- 4:スコアは, $2^i \times \left(i \text{回目の消滅で消えた数字の値の和}\right)$ の合計である。ただし、最初の消滅を0回目とする。
square1001氏を助けるために、最大の点数を出力しなさい。
入力
入力は以下の形式で標準入力から与えられる。$H \ W \ K$ $c_{1, 1} \ c_{1, 2} \ \cdots \ c_{1, W}$ $c_{2, 1} \ c_{2, 2} \ \cdots \ c_{2, W}$ $\vdots \ \ \ \ \ \ \ \ \ \ \vdots \ \ \ \ \ \ \ \ \ \ \vdots$ $c_{H, 1} \ c_{H, 2} \ \cdots \ c_{H, W}$
- 1行目に, 盤面の縦、横の大きさ$H$, $W$と、何個横に並ぶと消滅するかを表す数 $K$ が与えられる。
- 2行目から, $H$行にわたって盤面の状況が与えられる。
1
~9
はそれぞれの数字があることを示す。
出力
出力は以下の形式で標準出力に従うこと。- 最大の点数を1行に出力しなさい。
制約
- $2 \le H, W \le 30$
- 点数は $1,000,000,000$ 点を超えない
- 最初の盤面では, すべての横に隣り合うマス同士は同じ数が書かれていることはない。
小課題
小課題1 [ $120$ 点 ]- $H, W \le 10$
- $W=K$
- 追加の制約はない。
入力例1
4 4 2 3413 4121 1424 2312
出力例1
23場所 $(4, 3)$ を押すと以下のようになります。
よって, $7+16=23$ 点となる。
また, 場所 $(4,3)$ を消すのが最適である。
入力例2
4 4 2 1212 2121 1212 2121
出力例2
54この入力例は小課題1の制約を満たさない。
入力例3
7 7 2 8989898 9898989 8989898 9898989 8989898 9898989 8989898
出力例3
2520この入力例は小課題1の制約を満たさない。
入力例4
17 17 2 12345678912345678 23456789123456789 34567891234567891 45678912345678912 56789123456789123 67891234567891234 78912345678912345 89123456789123456 91234567891234567 12345678912345678 23456789123456789 34567891234567891 45678912345678912 56789123456789123 67891234567891234 78912345678912345 89123456789123456
出力例4
2354638連鎖数が非常に大きくなることもある。
C - XORパズル
問題作成者:E869120
実行時間制限: 1 sec / メモリ制限: 256 MB
配点: $400$ 点
彼は, 数列 $b$ を作りましたが, この数列を覚えていません。しかし, 次のことは覚えています。
しかし, 彼は全探索をしようとしていて, これに気付いたあなたは, 彼の代わりに求めてあげようとしました。
そのとき, square'1001'が作った数列 $b$ として考えられるものは, 何通りあるでしょうか?
ただし, 答えが非常に大きくなることがあるので, $1,000,000,007$で割った余りを求めてください。
問題文
サンプルケース3に不備があったので、リジャッジをしました。申し訳ございません。(21:01)
square1001は, Atcoder社から長さ $n$ の数列 $a$ をもらいました。$a$ の要素はすべて異なります。彼は, 数列 $b$ を作りましたが, この数列を覚えていません。しかし, 次のことは覚えています。
- $b$ の要素はすべて異なる。
- $b$ の要素はすべて $a$ にも入っている。
- square'1001' は, 2進数が好きなため, $b_1 \oplus b_2 \oplus \cdots \oplus b_r = k$ ($r$ は数列 $b$ の長さ) であることも覚えている。[$\oplus$ は XOR]
しかし, 彼は全探索をしようとしていて, これに気付いたあなたは, 彼の代わりに求めてあげようとしました。
そのとき, square'1001'が作った数列 $b$ として考えられるものは, 何通りあるでしょうか?
ただし, 答えが非常に大きくなることがあるので, $1,000,000,007$で割った余りを求めてください。
入力
入力は以下の形式で標準入力から与えられる。
$n \ k$ $a_1 \ a_2 \ \cdots \ a_n$
- 1 行目には、数列aの長さnと、数列bのXORした値kが空白区切りで与えられる。
- 2 行目には、数列aの要素が空白区切りで与えられる。
出力
出力は以下の形式で標準出力に従うこと。
- square'1001'が作った数列として考えられるものの通り数を1行に出力せよ。
- ただし, $1,000,000,007$ で割った余りを出力すること。
制約
- $1 \le n \le 100$
- $1 \le a_i, k \le 255$
- $i \neq j \Rightarrow a_i \neq a_j$
小課題
小課題1 [ $50$ 点 ]- $1 \le n \le 4$ を満たす。
- $1 \le n \le 20$ を満たす。
- $1 \le n \le 100$ を満たす。
入力例1
3 1 1 2 3
出力例1
3数列 $b$ として考えられるのは, $b = \{ 1 \}, \{ 2, 3 \}, \{ 3, 2 \}$ の3つである。
入力例2
3 10 8 7 5
出力例2
6数列 $b$ として考えられるのは, $b = \{ 5, 7, 8 \}, \{ 5, 8, 7 \}, \{ 7, 5, 8 \}, \{ 7, 8, 5 \}, \{ 8, 5, 7 \}, \{ 8, 7, 5 \}$ の6つである。
入力例4
25 127 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 100 105 110 115 120 125
出力例4
235924722
$1,000,000,007$ で割った余りを求めること。
D - お土産購入計画2
そのとき, 次のような進み方が最適です。
問題文担当者:square1001
実行時間制限: 2 sec / メモリ制限: 256 MB
配点: $600$ 点
左上のマスがスタート地点, 右下のマスがゴール地点です。
上から$i$番目, 左から$j$番目には, $a_{i, j}$ 個のお土産が売られています。
そこで, 2人で協力してお土産をできるだけ多く集めることにしました。
しかし, 2人は最短経路で行かなければなりません。そうしないとTLEします。
そのとき, 買うことができるお土産の個数の最大値を求めなさい。
問題文
E869120とsquare1001は, $H \times W$ のマス目を移動して, お土産を買うことにしました。左上のマスがスタート地点, 右下のマスがゴール地点です。
上から$i$番目, 左から$j$番目には, $a_{i, j}$ 個のお土産が売られています。
そこで, 2人で協力してお土産をできるだけ多く集めることにしました。
しかし, 2人は最短経路で行かなければなりません。そうしないとTLEします。
そのとき, 買うことができるお土産の個数の最大値を求めなさい。
入力
入力は以下の形式で標準入力から与えられる。$H \ W$ $a_{1, 1} \ a_{1, 2} \ \cdots \ a_{1, W}$ $a_{2, 1} \ a_{2, 2} \ \cdots \ a_{2, W}$ $\vdots \ \ \ \ \ \ \ \ \ \ \vdots \ \ \ \ \ \ \ \ \ \ \vdots$ $a_{H, 1} \ a_{H, 2} \ \cdots \ a_{H, W}$
- $1$行目に, 整数$H$と$W$が与えられる。
- $2$行目から$H+1$行目には, $W$個の整数が空白区切りで与えられる。
出力
出力は以下の形式で標準出力に従うこと。
- 買うことのできるお土産の個数の最大値を1行に出力しなさい。
制約
- $1 \le H, W \le 200$
- $0 \le a_{i, j} \le 10^5$
小課題
小課題1 [50点]- $1 \le H \le 2$ を満たす。
- $1 \le H \le 3$ を満たす。
- $1 \le H, W \le 7$ を満たす。
- $1 \le H, W \le 30$ を満たす。
- 追加の制約はない。
入力例1
3 3 1 0 5 2 2 3 4 2 4
出力例1
21ここでは, 上から $i$ 番目, 左から $j$ 番目を $(i, j)$ とします。
そのとき, 次のような進み方が最適です。
- E869120は, $(1, 1) -> (1, 2) -> (1, 3) -> (2, 3) -> (3, 3)$ と進む。
- square1001は, $(1, 1) -> (2, 1) -> (3, 1) -> (3, 2) -> (3, 3)$ と進む。
入力例2
6 6 1 2 3 4 5 6 8 6 9 1 2 0 3 1 4 1 5 9 2 6 5 3 5 8 1 4 1 4 2 1 2 7 1 8 2 8
出力例2
97
E - 円と三角形
よって, $K = 9$ 番目の三角形の面積は $\frac{\sqrt{3}}{2}$ となります。
この中で面積が一番大きいのは正三角形となるときなので, $K = 220$ 番目の三角形の面積は $\frac{3 \sqrt{3}}{4}$ となります。
問題作成者:E869120
実行時間制限: 2 sec / メモリ制限: 256 MB
配点: $850$ 点
頂点は, 円周を $N$ 等分しています。
square1001は, $3$ つの頂点を選んで三角形を作ろうとしています。
$\frac{N(N-1)(N-2)}{6}$ 通りの作り方のうち, 面積が小さい順に数えて $K$ 番目となる三角形の面積を出力してください。
ただし, 面積が同じ場合は、面積だけを出力すればいいので順番は適当で構いません。
例えば, $N = 4, K = 3$ のとき, 次のようになります。
問題文
半径が $1$ の円があり、頂点 $1$ ~ $N$ が時計回りに並んでいます。頂点は, 円周を $N$ 等分しています。
square1001は, $3$ つの頂点を選んで三角形を作ろうとしています。
$\frac{N(N-1)(N-2)}{6}$ 通りの作り方のうち, 面積が小さい順に数えて $K$ 番目となる三角形の面積を出力してください。
ただし, 面積が同じ場合は、面積だけを出力すればいいので順番は適当で構いません。
例えば, $N = 4, K = 3$ のとき, 次のようになります。
- 3頂点の番号が $(1,2,3)$ のとき, 面積 $= 1$
- 3頂点の番号が $(1,2,4)$ のとき, 面積 $= 1$
- 3頂点の番号が $(1,3,4)$ のとき, 面積 $= 1$
- 3頂点の番号が $(2,3,4)$ のとき, 面積 $= 1$
入力
入力は以下の形式で標準入力から与えられる。$N \ K$
- 1行目に, 円周上にある点の数 $N$ と, 何番目の三角形かを表す整数 $K$ が, 空白区切りで与えられる。
出力
- 面積が小さい順から数えて $K$ 番目となる三角形の面積を出力しなさい。
- ただし, 絶対誤差または相対誤差が $10^{-9}$ 以下であれば正解とみなされる。
制約
- $3 \le N \le 200,000$
- $1 \le K \le \frac{N(N - 1)(N - 2)}{6}$
小課題
小課題1 [ $160$ 点 ]- $N \le 100$
- $N \le 1000$
- 追加の制約はない。
入力例1
4 3
出力例1
1.000000000000000000この入力例は問題文で説明したとおりです。
入力例2
6 9
出力例2
0.86602540378$N = 6$ のとき, 面積が $\frac{\sqrt{3}}{4}$ となるような頂点の選び方は $6$ 通り, 面積が $\frac{\sqrt{3}}{2}$ となるような頂点の選び方は $12$ 通り, 面積が $\frac{3 \sqrt{3}}{4}$ となるような頂点の選び方は $2$ 通りあります。
よって, $K = 9$ 番目の三角形の面積は $\frac{\sqrt{3}}{2}$ となります。
入力例3
12 220
出力例3
1.29903810568$N = 12$ のとき, 三角形の作り方は $\frac{12 \times 11 \times 10}{6} = 220$ 通りあります。
この中で面積が一番大きいのは正三角形となるときなので, $K = 220$ 番目の三角形の面積は $\frac{3 \sqrt{3}}{4}$ となります。
F - 寿司
問題作成者 : E869120
実行時間制限: 3 sec / メモリ制限: 256 MB
配点: $1200$ 点
板前は, 次の操作を $Q$ 回します。
$i$ 回目の操作では, 次のことをします。
$Q$ 回すべての操作が終わったあと, それぞれの人が食べた寿司の皿数を計算してください。
問題文
$N$人の客が寿司屋にいます。それぞれの客には番号が付けられており, $1,2,3,…,N$ となっています。板前は, 次の操作を $Q$ 回します。
$i$ 回目の操作では, 次のことをします。
- 板前は, 客 $1, 2, 3, \dots, a_i$ の中で食べた寿司の皿数が最も少ない人を選びます。そのような人が複数いる場合は, その中で番号が最も少ない人を選びます。
- 板前が選んだ人に寿司を渡します。
- 2. で選ばれた人は, 寿司を食べます。
- 1. ~ 3. のを $b_i$ 回繰り返します。
$Q$ 回すべての操作が終わったあと, それぞれの人が食べた寿司の皿数を計算してください。
入力
入力は以下の形式で標準入力から与えられる。$N \ Q$ $a_1 \ b_1$ $a_2 \ b_2$ $ : \ : $ $a_Q \ b_Q$
- 1行目に, 客の数 $N$ と, 操作の回数 $Q$ が空白区切りで与えられる。
- 2行目から $N$ 行にわたって, 整数 $a_i$, $b_i$ が空白区切りで与えられる。
出力
出力は以下の形式で標準出力に従うこと。- $N$ 行にわたって出力する。
- $i$ 行目には, 客 $i$ が食べた寿司の皿数を出力しなさい。
制約
- $3 \le N, Q \le 100,000$
- $1 \le a_i \le N$
- $1 \le b_i \le 10^{12}$
- 最終的な値は, どれも $2 \times 10^{13}$ を超えない。
小課題
小課題1 [ $60$ 点 ]- $N, Q \le 100$
- $b_i = 1$
- $N, Q \le 100$
- $b_i \le 10^{12}$
- $N, Q \le 100,000$
- $b_i = 1$
- 追加の制約はない。
入力例1
9 3 5 11 8 4 4 7
出力例1
4 4 4 4 2 2 1 1 0客が食べた寿司の皿数の変化は以下の通りです。
客1 | 客2 | 客3 | 客4 | 客5 | 客6 | 客7 | 客8 | 客9 | |
1回目の操作 | 3 | 2 | 2 | 2 | 2 | 0 | 0 | 0 | 0 |
2回目の操作 | 3 | 2 | 2 | 2 | 2 | 2 | 1 | 1 | 0 |
3回目の操作 | 4 | 4 | 4 | 4 | 2 | 2 | 1 | 1 | 0 |
入力例2
6 6 3 5 6 11 1 6 4 7 5 2 2 5
出力例2
10 10 5 5 4 2
入力例3
5 6 1 1 2 1 3 1 1 1 5 1 3 1
出力例3
2 2 1 1 0
入力例4
10 10 10 10 9 20 8 30 7 40 6 50 5 60 4 70 3 80 2 90 1 100
出力例4
223 123 77 50 33 21 12 7 3 1
G - フィボナッチ数の総和
よって, $d_{4, 7} = 176$ となり, これが答えとなります。
問題文担当者:square1001
実行時間制限: 2 sec / メモリ制限: 256 MB
配点: $1400$ 点
E869120は, この数列を使って次のように数列 $d_1, d_2, d_3, \dots , d_n$ を定義することにしました。
整数 $n, m$ が与えられます。そのとき, $d_{n, m}$ の値を求めてください。
ただし, 答えが非常に大きくなることがあるので, $998,244,353$ で割った余りを求めてください。
あなたはこの問題が解けますか???
問題文
次のような数列があります。- $a_1=a_2=1$, $a_{k+2}=a_{k+1}+a_k \ (k \ge 1)$
E869120は, この数列を使って次のように数列 $d_1, d_2, d_3, \dots , d_n$ を定義することにしました。
- $d_{1, j} = a_j$
- $d_{i, j} = \sum_{k = 1}^j d_{i - 1, k} \ (i \ge 2)$
整数 $n, m$ が与えられます。そのとき, $d_{n, m}$ の値を求めてください。
ただし, 答えが非常に大きくなることがあるので, $998,244,353$ で割った余りを求めてください。
あなたはこの問題が解けますか???
入力
入力は以下の形式で標準入力から与えられる。$n \quad m$
- 1行目には, 整数 $n, m$ が空白区切りで与えられる。
出力
- $d_{n, m}$ を $998,244,353$ で割った余りを求めなさい。
制約
- $1 \le n \le 200,000$
- $1 \le m \le 10^{18}$
小課題
小課題1 [ $100$ 点 ]- $1 \le n, m \le 3,000$ を満たす。
- $1 \le m \le 200,000$ を満たす。
- $1 \le n \le 3$ を満たす。
- $1 \le n \le 1000$ を満たす。
- 追加の制約はない。
入力例1
4 7
出力例1
176以下のような数列になっています。
$d_{i, 1}$ | $d_{i, 2}$ | $d_{i, 3}$ | $d_{i, 4}$ | $d_{i, 5}$ | $d_{i, 6}$ | $d_{i, 7}$ | |
$d_1$ | 1 | 1 | 2 | 3 | 5 | 8 | 13 |
$d_2$ | 1 | 2 | 4 | 7 | 12 | 20 | 33 |
$d_3$ | 1 | 3 | 7 | 14 | 26 | 46 | 79 |
$d_4$ | 1 | 4 | 11 | 25 | 51 | 97 | 176 |
よって, $d_{4, 7} = 176$ となり, これが答えとなります。
入力例2
12 20
出力例2
174174144
入力例3
16 30
出力例3
102292850$d_{16, 30} = 1,193,004,294,685$ なので, これを $998,244,353$ で割った余りは $102,292,850$ です。
H - 爆弾ゲーム
質問は以下のような形式で出力することによってできる。
また, 質問の返答は, 以下のような出力で行われる。
また, 答えが分かった時に, 以下のような出力をしなければならない。
ただし, この場合 $H = W = 4, N = 4$ なので, 実際のテストケースには存在しない。
ただし, 必ずしも意味のある質問をしているとは限りません。
また, これらの情報で必ずしも盤面が把握できるとは限らず, エスパーをすることも許されはします。
問題作成者: E869120
実行時間制限: 1 sec / メモリ制限: 256 MB
配点: $1500$ 点
square1001氏は, 最終兵器として, あるダンジョンに爆弾を仕掛けた。
そのダンジョンは, 左上のマスが $(0,0)$, 右下のマスが $(49,49)$ の $50 \times 50$ の大きさである。
その中には, 250個の爆弾が仕掛けられている。位置はすべて違うマスである。
あなたは, 全ての爆弾の位置を知ることで, そのダンジョンから脱出できる。
「そんなん、どうやって知ればいいんだよ! 全く分かんねぇじゃないか!助けてぇぇぇぇぇ!」
しかし、あなたは以下の質問を何回かできる。
しかし, 質問回数が多くなればなるほど, 爆弾の爆発する確率が高くなり, すなわち生存確率が下がる。
そのため, できるだけ少ない質問回数で爆弾250個の配置を当ててほしい。(その方が得点が高い)
あなたの挑戦を待っている。
問題文
さて, このsquare869120Contest #3も, 最終問題となってしまった。square1001氏は, 最終兵器として, あるダンジョンに爆弾を仕掛けた。
そのダンジョンは, 左上のマスが $(0,0)$, 右下のマスが $(49,49)$ の $50 \times 50$ の大きさである。
その中には, 250個の爆弾が仕掛けられている。位置はすべて違うマスである。
あなたは, 全ての爆弾の位置を知ることで, そのダンジョンから脱出できる。
「そんなん、どうやって知ればいいんだよ! 全く分かんねぇじゃないか!助けてぇぇぇぇぇ!」
しかし、あなたは以下の質問を何回かできる。
- 左上のマス $(a, b)$, 右下のマス $(c, d)$ の区間に何個爆弾があるかを聞くことができる。
しかし, 質問回数が多くなればなるほど, 爆弾の爆発する確率が高くなり, すなわち生存確率が下がる。
そのため, できるだけ少ない質問回数で爆弾250個の配置を当ててほしい。(その方が得点が高い)
あなたの挑戦を待っている。
入出力
最初, 以下のように入力される。$H \ W \ N \ K$
- $H, W$ はダンジョンの大きさである。この問題では, $H, W = 50$ である。
- $N$ はダンジョンの中に含まれる爆弾の数である。この問題では, $N = 250$ である。
- $K$ は最終的な盤面の状態を出力するために使う整数である。
質問は以下のような形式で出力することによってできる。
$? \ a \ b \ c \ d$これは, 左上のマス $(a, b)$, 右下のマス $(c, d)$ の区間に存在する爆弾の数を聞くことである。
また, 質問の返答は, 以下のような出力で行われる。
$p$$p$ は, 質問で聞いた区間に存在する爆弾の総数である。
また, 答えが分かった時に, 以下のような出力をしなければならない。
$! \ ans$ただし, $ans$ は以下の値であり, $r_{i, j}$ は, マス $(i, j)$ にある爆弾の個数である。
- $ans = \sum_{i=0}^{H-1} \sum_{j=0}^{W-1} r_{i, j} 2^{iW + j}$ mod $K$
制約
- $H, W = 50$
- $N = 250$
- $1,000,000,000 \le K \le 1,000,01,000$ ($K$はランダムに与えられる)
得点
5つのテストケースがある。各テストケースに対する得点は, 以下のように計算される。- 質問回数を $Q$ とする。
- $Q > 2500$ のとき, $0$ 点 (Wrong Answer) となる。
- $930 \le Q \le 2500$ のとき, $score = max(\lfloor 125 - 3.2\sqrt{Q - 920} \rfloor, 40)$ となる。
- $880 \le Q < 930$ のとき, $score = \lfloor 288 - 22\sqrt{Q - 870} \rfloor$ となる。
- $Q < 880$ のとき, $score = min(2860 - 3Q, 300)$ となる。
入出力例1
例えば, 以下のような配置の場合、以下のような入出力が考えられる。ただし, この場合 $H = W = 4, N = 4$ なので, 実際のテストケースには存在しない。
H=4, W=4, N=4 1001 0000 0010 0100入出力として考えられる例
プログラムへの入力 | プログラムの出力 |
---|---|
4 4 4 1000000007 | |
? 0 0 0 1 | |
1 | |
? 0 1 0 2 | |
0 | |
? 0 3 1 3 | |
1 | |
? 2 1 3 2 | |
2 | |
? 2 2 2 2 | |
1 | |
! 9225 |
また, これらの情報で必ずしも盤面が把握できるとは限らず, エスパーをすることも許されはします。