Lv.1 だいがくぐらし！
リソース制限
| C / C++ | Java | Python2 / Python3 | |
|---|---|---|---|
| 時間制限 | 1秒 | 1秒 | 5秒 |
| メモリ制限 | 256MB | 256MB | 256MB |
問題文
K君の朝は遅い。
K君のその日最初の講義への出席状況は芳しくなく、
一週間前の段階では、あと1回遅刻をすればその講義の単位を落としてしまう状態だった。
K君は、家を出て大学に着くまで
K君の最近の一週間の「家を出た時刻」と、「その日最初の講義が始まる時刻」の履歴が与えられるとき、
各講義について、単位取得の可能性があるかどうかを判定せよ。
なお、K君は大学に着いた瞬間に教室に着席できるため、
大学に着いた時刻 > 講義が始まる時刻のときのみ、遅刻と判定されるものとする。
入力
A LH_1 LM_1 AH_1 AM_1 LH_2 LM_2 AH_2 AM_2 LH_3 LM_3 AH_3 AM_3 LH_4 LM_4 AH_4 AM_4 LH_5 LM_5 AH_5 AM_5 LH_6 LM_6 AH_6 AM_6 LH_7 LM_7 AH_7 AM_7
Aは、K君が家を出て、大学に着くまでにかかる時間(単位：分)である。
出力
全ての曜日の最初の講義について、単位取得の可能性があるなら
SAFE
単位取得の可能性が無いなら
DEAD
と各行に出力せよ。
出力は7行からなるはずである。
末尾に改行を出力すること。
制約
$1≦A≦180$ $0≦LH_i, AH_i≦20$ $0≦LM_i, AM_i≦59$
入力は全て整数である。
サンプル
入力1
60 9 0 10 30 9 20 10 30 9 30 10 30 9 31 10 30 10 30 8 50 15 5 16 10 20 59 0 0
出力1
SAFE SAFE SAFE DEAD DEAD SAFE DEAD
1番目、2番目の曜日に関しては、講義開始時刻前に出席できています。
3番目に関しては、講義開始時刻と同時に到着しているため、SAFEです。
4番目は、到着時刻が講義開始時刻を1分超過しているため無慈悲にもDEADです。
5番目は、家を出た時刻には、恐らく講義が終わっている(少なくとも、始まってはいる)のでもちろんDEADです。
6番目は、講義開始時刻が遅いため、SAFEです。
7番目は、徹夜して大学に居なければならなかったので、家を出発している時点でDEADです。
Lv.2 ディジタル信号処理
問題文
あるアナログ信号
そのうちの
基本周期が存在しなければ、代わりに
なお、ここでは基本周期は、
ある正の整数
が成り立つような
また、
サンプリング、量子化については、各自調べて欲しい。
入力
N f[0] f[1] … f[N-1]
出力
基本周期を一行に出力せよ。
基本周期が存在しない場合、代わりに
末尾に改行を出力すること。
制約
$1≦N≦1000$ $-1000≦f[i]≦1000$
入力は全て整数である。
サンプル
入力1
14 1 2 3 1 2 3 4 1 2 3 1 2 3 4
出力1
7
入力2
14 1 2 1 2 1 2 3 4 1 2 1 2 1 2
出力2
14
Lv.3 巡回レポートマン問題
問題文
K君の昼は忙しい。
K君は苦心の末、今日の昼休みの終わりが締め切りである
しかし、これらのレポートを提出しなければ単位を落としてしまう。
地図と現在地点、それぞれのレポートの提出場所と提出順序が与えられるので、
全てのレポートを提出するのに最短何分かかるかを計算して欲しい。
地図はマス目状になっており、K君は1分間に、上下左右のうちいずれかの方向へ1マス分動くことができるものとする。
ただし、移動しようとした先のマスの地形が.である場合のみ、そのマスに進むことができる。
地形が#となっているマスや、枠外のマスには足を踏み入れることが出来ない。
地図の地形等により、一部のレポートを提出できない場合がある。この場合、-1を出力せよ。
また、K君は新聞配達アルバイトで鍛えたポスト投函テクニックを用いるので、
レポートの提出自体にかかる時間は0分とする。
入力
N H W M(11)M(12)…M(1W) M(21)M(22)…M(2W) … M(H1)M(H2)…M(HW) R_0 C_0 R_1 C_1 R_2 C_2 … R_N C_N
マップの地形は.か#のいずれかである。
.である。
出力
全てのレポートを提出するのかかる最短時間(分)を1行に出力せよ。
一部のレポートを提出することが出来ない場合は-1を1行に出力せよ。
末尾に改行を出力すること。
制約
$1≦N≦10000$ $1≦W, H≦10$ $1≦R_i≦H, 1≦C_i≦W$
入力は全て整数である。
サンプル
入力1
3 5 5 ..#.. ..#.. ..#.. ..#.. ..... 1 1 1 5 1 1 1 5
出力1
36
1行1列目と1行5列目間を3回移動します。
1行1列目と1行5列目間を移動するために必要な最短時間は12分なので、
12 * 3 = 36を出力します。
2番目のレポートを最初に出せばもっと早く提出し終えることができますが、
K君は提出順を律儀に守るため、最低36分かかります。
入力2
12 10 10 .......... #########. ........#. .######.#. .#....#.#. .#.#..#.#. .#.####.#. .#......#. .########. .......... 1 1 6 6 6 6 6 6 6 6 6 6 1 1 6 6 6 6 6 6 6 6 6 6 6 6
出力2
174
昼休み中の提出は絶望的ですね。
入力3
1 1 3 .#. 1 1 1 3
出力3
-1
提出は絶望的です。
Lv.4 物理実験
問題文
K君の午後の授業は物理実験である。
K君はモデル化された物質「物質K」について実験している。
実験の内容は以下の通りである。
ここに物質Kが
空間Bにある場合、全体エネルギーが
さらに、
$C_j$ 個目の物質Kと$D_j$ 個目の物質Kがそれぞれ別の空間にある場合、
それぞれが引き合うので、全体のエネルギーが更に$E_j$ 増える。
物質Kたちは、全体エネルギーができるだけ少なくなるように自ら空間Aまたは空間Bに移動する。
全体エネルギーが最小になる時の全体エネルギーを推測せよ。
K君は優秀なプログラマーであるあなたに、この答えを出力するプログラムの作成を依頼した。
彼の代わりにプログラムを作って欲しい。
入力
N M A_1 B_1 A_2 B_2 … A_N B_N C_1 D_1 E_1 C_2 D_2 E_2 … C_M D_M E_M
各条件は
全体エネルギーが更に
出力
1行目に全体エネルギーが最小になる時の全体エネルギーを出力せよ。
末尾に改行を出力すること。
制約
$1≦N≦100$ $0≦M≦N(N-1)/2$ かつ$0≦M≦1000$ を満たす。$0≦A_i, B_i≦1000$ $1≦C_j<D_j≦N$ - 内容が同じ条件、及び矛盾する条件は含まれない。(条件
$j$ と条件$k(j≠k)$ に対して、$C_j=C_k$ かつ$D_j=D_k$ となることはない。) $0≦E_j≦1000$
入力される変数は全て整数である
部分点制約
この問題には部分点が設定されている。
- 部分点1: 全体の配点の10%分のテストケースは、
$1≦N≦16$ かつ$M=0$ を満たす。 - 部分点2: 全体の配点の20%分のテストケースは、
$1≦N≦16$ かつ$M≦1$ を満たす。 - 部分点3: 全体の配点の40%分のテストケースは、
$1≦N≦16$ を満たす。 - 部分点4: 全体の配点の20%分のテストケースは、
$17≦N≦100$ かつ 全ての$1≦j≦N$ について、$D_j - C_j = 1$ を満たす。 - 部分点5: 全体の配点の80%分のテストケースは、全ての
$1≦j≦N$ について、$1≦D_j - C_j≦16$ を満たす。
例えば、「
リソース制限を満たし正しい答えを出力するプログラムを提出すれば、20%分の得点が保証される。(部分点2)
また、部分点3と部分点4は排反であるから、2つのテストケース両方に対応するプログラムを作ることで、60%分の得点を得ることができる。
1つのアルゴリズムを使うのではなく、テストケースによって使うアルゴリズムを切り替えるのも良い方法である。
サンプル
入力1
3 1 1 2 4 2 5 5 1 2 3
出力1
9
1個目の物質Kが空間B、
2個目の物質Kが空間B、
3個目の物質Kが空間Aまたは空間B
にあるとき全体エネルギーが最小の状態となり、その時の全体エネルギーは
入力2
3 2 1 5 9 2 5 5 1 2 3 1 3 1
出力2
11
1個目の物質Kが空間A、
2個目の物質Kが空間B、
3個目の物質Kが空間A
にあるとき全体エネルギーが最小の状態となり、その時の全体エネルギーは