Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
予選を勝ち抜いてきた N 人の参加者が 1 つの部屋で M 問の問題が出題されるコンテストに参加しています。
このコンテストでは全ての問題を正解した参加者から部屋の出口に歩いて行き、部屋の外に出ることができます。
i 番目の参加者 (1\le i\le N) の予選の順位は i 位であり、問題を 1 問解くのに S_i 秒かかり、出口まで歩くのに E_i 秒かかります。
複数の参加者が同時に出口にたどり着いた場合、予選順位が高い方の参加者から順に部屋から出ます。
部屋から出る順番に参加者の番号を出力してください。
制約
- 2\le N\le 100
- 1\le M\le 10^9
- 1\le S_i,E_i\le 10^9
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M S_1 E_1 S_2 E_2 \vdots S_N E_N
出力
i 番目に部屋から出る参加者の番号を P_i として、以下の形式で出力せよ。
P_1 P_2 \ldots P_N
入力例 1
3 6 3 10 4 2 10 100
出力例 1
2 1 3
- 1 番目の参加者はコンテスト開始から出口にたどり着くまでに 3\times 6 + 10 = 28 秒かかります。
- 2 番目の参加者はコンテスト開始から出口にたどり着くまでに 4\times 6 + 2 = 26 秒かかります。
- 3 番目の参加者はコンテスト開始から出口にたどり着くまでに 10\times 6 + 100 = 160 秒かかります。
したがって、2 番目の参加者、1 番目の参加者、3 番目の参加者の順に部屋から出ていきます。
入力例 2
4 100 1 1000000000 100 100 100 100 100 100
出力例 2
2 3 4 1
複数の参加者が同時に出口にたどり着いた場合、予選順位が高い方の参加者から順に部屋から出ることに注意してください。
入力例 3
6 5 1 9 1 3 7 9 10 9 7 3 4 8
出力例 3
2 1 6 5 3 4
Time Limit: 2 sec / Memory Limit: 1024 MiB
問題文
正整数 M が与えられます。x = 0, 1, \dots, M - 1 について次の問題を解いてください。
- y ^ 3 \equiv x \pmod{M} を満たす M 未満の非負整数 y を 1 個出力してください。ただし、そのような y が存在しない場合は -1 を出力してください。
制約
- M は 1 以上 10^6 以下の整数
入力
入力は以下の形式で標準入力から与えられる。
M
出力
M 行出力せよ。i 行目には x = i - 1 の時の答えを出力せよ。
なお、答えが複数存在する場合はどれを出力しても良い。
入力例 1
4
出力例 1
2 1 -1 3
各 x に対する答えは次の通りです。
- x = 0 のとき、y = 2 とすると 2^3 = 8 \equiv 0 \pmod{4} が成り立ちます。よって y = 2 を出力します。
- x = 1 のとき、y = 1 とすると 1^3 = 1 \equiv 1 \pmod{4} が成り立ちます。よって y = 1 を出力します。
- x = 2 のとき、条件を満たす y は存在しません。よって -1 を出力します。
- x = 3 のとき、y = 3 とすると 3^3 = 27 \equiv 3 \pmod{4} が成り立ちます。よって y = 3 を出力します。
入力例 2
7
出力例 2
0 4 -1 -1 -1 -1 6
入力例 3
10
出力例 3
0 1 8 7 4 5 6 3 2 9
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
2 以上の整数 N が与えられます。
N 行 N 列のマス目に 1 以上 N^2 以下の整数を 1 つずつ書き込む方法であって、以下の条件を満たすものを一つ求めてください。
- 各行の和と各列の和を全て書き出したとき、その 2N 個の整数の値が相異なる。
ただし、制約下で条件を満たす書き込み方が必ず存在することが証明できます。
制約
- 2\le N\le 50
- 入力される値は整数
入力
入力は以下の形式で標準入力から与えられる。
N
出力
マス目の i 行 j 列に書き込む整数を A_{i,j} として、以下の形式で出力せよ。
A_{1,1} A_{1,2} \ldots A_{1,N}
A_{2,1} A_{2,2} \ldots A_{2,N}
\vdots
A_{N,1} A_{N,2} \ldots A_{N,N}
条件を満たす書き込み方が複数ある場合、どれを出力しても正答となる。
入力例 1
3
出力例 1
8 9 3 6 5 1 4 2 7
- 1 行目に書かれた整数の総和は 8+9+3=20 です。
- 2 行目に書かれた整数の総和は 6+5+1=12 です。
- 3 行目に書かれた整数の総和は 4+2+7=13 です。
- 1 列目に書かれた整数の総和は 8+6+4=18 です。
- 2 列目に書かれた整数の総和は 9+5+2=16 です。
- 3 列目に書かれた整数の総和は 3+1+7=11 です。
20,12,13,18,16,11 は相異なる整数なので、この書き込み方は条件を満たします。
入力例 2
2
出力例 2
4 2 3 1
入力例 3
5
出力例 3
20 6 23 3 5 19 21 16 11 14 18 4 9 2 10 22 17 12 15 13 8 1 24 7 25
Time Limit: 2 sec / Memory Limit: 1024 MiB
問題文
この問題は インタラクティブな問題（あなたの作成したプログラムとジャッジプログラムが標準入出力を介して対話を行う形式の問題）です。
整数 N が与えられます。
N 個のみかんがあります。
あなたとダックスフンドのルンルンは交互に以下の行動を行います。
- みかんを 1 個または 2 個食べる。
最後のみかんを食べた者の勝ちです。 先攻か後攻かを選び、実際に行動の選択を行って勝ってください。
制約
- 1\le N\le 100
入出力
この問題はインタラクティブな問題（あなたの作成したプログラムとジャッジプログラムが標準入出力を介して対話を行う形式の問題）です。
最初に、整数 N が与えられるのでこれを受け取ってください。
N
まず、あなたは一方の手番を選びます。そして、選んだ手番が先攻ならば First を、後攻ならば Second を出力してください。
その後、あなたは出力した方の手番で、ルンルンがそうでない方の手番でゲームが直ちに開始されます。あなたはゲームが終了するまで入出力を利用してジャッジシステムと対話をして、ゲームに勝利してください。
あなたは手番が回ってきたら、操作で食べるみかんの数 x を次の形式で出力してください。ただし、選ぶことのできる x が存在しない場合は x=0 を出力してください。
x
ルンルンの手番では、ジャッジシステムが以下の形式で整数 a を出力します。
a
ここで a は次の 4 種類のいずれかであることが保証されます。
- a=0 の場合：ルンルンは操作を行えなくなったことを意味します。つまり、あなたはゲームに勝利しました。
- a=-1 の場合：あなたは 1 つ前に x=1,2 以外を出力したか、残ったみかんより大きい x を出力したことを意味します。つまり、あなたはゲームに敗北しました。
- それ以外の場合：ルンルンはみかんを a 個食べる操作を行ったことを意味します。ここでルンルンが選んだ操作は a=1,2 かつ残った a は残ったみかんの数以下であることが保証されます。
ジャッジが a=0 または a=-1 を返した場合、ゲームはすでに終了しています。この場合、プログラムをただちに終了してください。
注意点
- 出力を行うたびに、末尾に改行を入れて標準出力を flush してください。そうしなかった場合、ジャッジ結果が TLE となる可能性があります。
- 対話の途中で不正な出力を行った、あるいはプログラムが途中で終了した場合のジャッジ結果は不定です。 特に、プログラムの実行中に実行時エラーが起こった場合に、ジャッジ結果が ではなく や TLE になる可能性があることに注意してください。
- ゲームが終了したらただちにプログラムを終了してください。そうしない場合、ジャッジ結果は不定です。
入出力例
以下は、N = 4 の場合の入出力例です。
| 入力 | 出力 | 説明 |
|---|---|---|
4 |
まず整数 N が与えられます。 | |
First |
先攻を選び、ゲームを開始します。 | |
1 |
みかんを 1 個食べます。残ったみかんは 3 個になります。 | |
2 |
みかんを 2 個食べます。残ったみかんは 1 個になります。 | |
1 |
みかんを 1 個食べます。残ったみかんは 0 個になります。 | |
0 |
ルンルンは操作を行うことができなくなったので、あなたの勝ちです。 |
Time Limit: 5 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
H \times W のグリッドで表される会場があります。上から i 行目、左から j 列目のマスをマス (i,j) と表します。マス (i,j) には S_{i,j} が # ならば壁があり、 . ならば空であり通行可能です。
あなたはこの会場の空のマスを 3 マス選んでブースを設置します。以下の条件を満たすようなブースの設置方法は何通りあるか求めてください。ただし、ブース同士は区別しないものとします。
- 以下を両方満たすようなマス (r,c) が存在する。
- マス (r,c) には壁もブースもない。
- 全てのブースについて、マス (r,c) から上下左右に隣接する壁もブースもないマスに移動する操作を 0 回以上繰り返すことでそのブースに上下左右に隣接するマスに到達することができる。
制約
- 2\le H,W\le 8
- H,W は整数
- S_{i,j} は
#または. - S_{i,j}=
.を満たす (i,j) が 3 つ以上存在する
入力
入力は以下の形式で標準入力から与えられる。
H W
S_{1,1}S_{1,2}\ldots S_{1,W}
S_{2,1}S_{2,2}\ldots S_{2,W}
\vdots
S_{H,1}S_{H,2}\ldots S_{H,W}
出力
答えを出力せよ。
入力例 1
3 3 #.. ..# #.#
出力例 1
2
以下の 2 つの配置が条件を満たします。ただし、ブースがあるマスは B で表しています。
#B. #.B B.# B.# #B# #B#
どちらの配置もマス (2,2) から全てのブースに到達可能です。
入力例 2
3 5 ..... .###. .....
出力例 2
0
条件を満たすブースの配置方法は存在しません。したがって、 0 を出力してください。
入力例 3
8 8 ........ ........ ........ ........ ........ ........ ........ ........
出力例 3
41660