実行時間制限: 1 sec / メモリ制限: 1024 MB
配点: 100 点
問題文
ギガ高校には A 個の教室があり,すべての教室は一辺が B メートルの正方形の形をしています.
この高校の教室の合計面積を求めてください.
制約
- 1 \leq A \leq 100
- 1 \leq B \leq 100
- 入力はすべて整数
部分点
この問題には部分点は存在せず,すべてのテストケースに正解すると 100 点が与えられます.
入力
入力は以下の形式で標準入力から与えられます.
A B
出力
ギガ高校の教室面積の合計が何平方メートルか,整数で出力してください.
入力例 1
4 3
出力例 1
36
教室の 1 個当たりの面積は 3×3=9 平方メートルです.
また,ギガ高校には教室が 4 個あるため,合計面積は 9×4=36 平方メートルとなります.
入力例 2
24 15
出力例 2
5400
教室の 1 個当たりの面積は 15×15=225 平方メートルです.
また,ギガ高校には教室が 24 個あるため,合計面積は 225×24=5400 平方メートルとなります.
入力例 3
100 100
出力例 3
1000000
実行時間制限: 1 sec / メモリ制限: 1024 MB
配点: 100 点
問題文
GigaCode 社は毎年採用面接を行っています.
この会社では,採用において「技術力」「社会性」の 2 つの観点を重要視しています.採用に当たっては「技術力」「社会性」それぞれ 100 点満点で点数をつけ,それらに応じて以下の 2 つの条件を両方満たす人のみ合格とします.
- 技術力が X 点以上かつ社会性が Y 点以上である.
- 技術力と社会性の合計点が Z 点以上である.
さて,今年は N 人の大学生が応募しました.i 人目の応募者は,技術力の点数が A_i 点,社会性の点数が B_i 点でした.何人の応募者が採用面接に合格するか,求めてください.
制約
- 1 \leq N \leq 100
- 0 \leq A_i \leq 100
- 0 \leq B_i \leq 100
- 0 \leq X \leq 100
- 0 \leq Y \leq 100
- 0 \leq Z \leq 200
- 入力はすべて整数
部分点
この問題はいくつかの小課題に分けられ,その小課題のすべてのテストケースに正解した場合に「この小課題に正解した」とみなされます.
提出したソースコードの得点は,正解した小課題の点数の合計となります.
- (30 点) N = 1 を満たす.
- (30 点) N 人全員が採用面接に合格する.
- (40 点) 追加の制約はない.
入力
入力は以下の形式で標準入力から与えられます.
N X Y Z A_1 B_1 A_2 B_2 A_3 B_3 ... A_N B_N
出力
N 人のうち何人の応募者が採用面接に合格するか,整数で出力してください.
小課題 1 のヒント
小課題 1 では,すべてのテストケースが N = 1 です.つまり,以下の形式で入力が与えられます.
N X Y Z A_1 B_1
そのとき,X \leq A_1, Y \leq B_1, Z \leq A_1 + B_1 のすべての条件を満たせば,1 人目の応募者が合格するので 1 と出力し,そうでない場合は 0 と出力するのが,小課題 1 の本質です.
なお,この小課題は,繰り返し処理等を使わなくても解くことができます.
小課題 2 のヒント
小課題 2 では,答えは必ず N になります.
小課題 3 のヒント
for 文などの繰り返し処理と,if 文などの条件分岐を使うと,解くことができます.
入力例 1
1 60 20 100 72 28
出力例 1
1
1 人目の応募者は,以下の条件を満たすため,合格となります.
- 技術力の点数が 72 点となり,合格基準である 60 点以上となる.
- 社会性の点数が 28 点となり,合格基準である 20 点以上となる.
- 技術力と社会性の合計点数が 72+28=100 点となり,合格基準である 100 点以上となる.
よって,合格人数は 1 人です.
なお,この入出力例は 1 つ目の小課題(小課題 1)の制約を満たします.また,2 つ目の小課題(小課題 2)の制約も満たします.
入力例 2
5 70 70 150 72 77 70 90 65 88 75 75 97 84
出力例 2
3
2 人目・4 人目・5 人目の応募者のみ合格となります.
この入出力例は N=1 ではないので,小課題 1 の制約を満たしません.
入力例 3
15 80 60 150 20 24 33 17 29 36 40 18 15 27 10 41 53 77 42 15 12 17 32 10 19 28 37 27 91 2 13 25 40 40
出力例 3
0
とても難しい採用試験です.
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点: 100 点
問題文
ギガ君は,「GigaCode 20XX」というイベントに参加するために,小遣いからパソコンを購入することになりました.今日を 1 日目とすると,彼は D 日目までにパソコンを購入しなければなりません.
1 日目の朝の段階で,彼が持っている小遣いの金額は 0 円です.また,i 日目の正午には小遣い a_i 円が彼に渡されます.
さて,パソコンの価格は毎日変動します.i 日目のパソコンの価格は b_i 円であり,この価格はその日の 0 時から 24 時まで変わりません.
D 日間分の小遣いの情報・パソコンの価格の情報が与えられたとき,彼が買うことのできるパソコンの価格としてあり得る最小値を求めてください.ただし,彼がパソコンを D 日目までに購入することができない場合は -1
と出力してください.なお,与えられた小遣い以外の金は使うことができないものとします.
制約
- 1 \leq D \leq 200 \ 000
- 1 \leq a_1, a_2, a_3, \dots, a_D \leq 200 \ 000
- 1 \leq b_1, b_2, b_3, \dots, b_D \leq 2 \ 000 \ 000 \ 000
- 入力はすべて整数
部分点
この問題はいくつかの小課題に分けられ,その小課題のすべてのテストケースに正解した場合に「この小課題に正解した」とみなされます.
提出したソースコードの得点は,正解した小課題の点数の合計となります.
- (20 点) D = 1 を満たす.
- (40 点) D \leq 365 を満たす.
- (40 点) 追加の制約はない.
入力
入力は以下の形式で標準入力から与えられます.
D a_1 a_2 a_3 ... a_D b_1 b_2 b_3 ... b_D
出力
ギガ君が買うことのできるパソコンの価格としてあり得る最小値を出力してください.
ただし,彼がパソコンを D 日目までに購入することができない場合は -1
と出力してください.
入力例 1
1 120000 100000
出力例 1
100000
彼は 1 日目の夜の時点で 120 \ 000 円持っているため,1 日目の夜に 100 \ 000 円のパソコンを購入することができます.
よって,100000
と出力するのが正解です.
なお,この入出力例は,小課題 1 の制約,小課題 2 の制約を満たします.
入力例 2
1 70000 100000
出力例 2
-1
彼は 1 日目の夜の時点で 70 \ 000 円持っていますが,パソコンを購入するのに 100 \ 000 円かかるため,彼はパソコンを購入することができません.
よって,-1
と出力するのが正解となります.
入力例 3
5 10000 10000 10000 10000 10000 41210 27556 29018 42919 33762
出力例 3
29018
彼が 1 日目の夜にパソコンを購入しようとした場合:
- 所持金:10 \ 000 円
- パソコンの価格:41 \ 210 円 → 購入できない
彼が 3 日目の夜にパソコンを購入しようとした場合:
- 所持金:10 \ 000 + 10 \ 000 + 10 \ 000 = 30 \ 000 円
- パソコンの価格:29 \ 018 円 → 購入できる
彼が 5 日目の夜にパソコンを購入しようとした場合:
- 所持金:10 \ 000 + 10 \ 000 + 10 \ 000 + 10 \ 000 + 10 \ 000 = 50 \ 000 円
- パソコンの価格:33 \ 762 円 → 購入できる
また,彼は 2, 4 日目の夜にパソコンを購入することはできません.よって答えは 29 \ 018 円となります.
なお,この入出力例は,小課題 2 の制約を満たします.
入力例 4
5 10000 10000 10000 10000 10000 30000 29999 29998 29997 29996
出力例 4
29996
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点: 100 点
問題文
ギガ君は,パソコンを買い,プログラミングの勉強をし,会社に入り,金を儲け,そしてついに家を建設することとなりました!
彼の住むテラ市は H 行 W 列のマス目で表されます.上から i 行目,左から j 列目のマスは (i, j) で表されます.また,マス (i, j) の地価は A_{i, j} 円です.
さて,家は以下のように建設することができます.
- テラ市の中のいくつかのマス(土地)を選び,購入することができる.マス (i, j) を購入するのに A_{i, j} 円かかる.なお,購入するマスの領域は 1 つの長方形で表されなければならない.
- 購入した土地全体に家を建設する.S 個のマスを購入した場合,家を建設するのに S×K 円かかる.
例えば,K = 5 であるとき,(図1) のような建設を行う場合は (1+4)+(2 \times 5)=15 円,(図2) のような建設を行う場合は (6+3+4+1)+(4 \times 5)=34 円かかります.ただし図中の数は各マスの地価とします.
また,以下の (図3) や (図4) の灰色の部分の土地を購入することはできません.なぜなら,購入した土地の領域が 1 つの長方形で表されないからです.
彼は現在 V 円持っており,全財産を豪邸の購入に使うことができます.彼はできるだけ面積の大きい家を買いたいです.
現在彼が買うことのできる家として考えられる,最大の面積を求めてください.また,家を購入できない場合は 0
と出力してください.ただし,家の面積と購入した長方形領域の面積は同じものとします.
制約
- 1 \leq H, W \leq 125
- 1 \leq A_{i, j}, K \leq 1 \ 000 \ 000 \ 000
- 1 \leq V \leq 1 \ 000 \ 000 \ 000 \ 000 \ 000 (=10^{15})
- 入力はすべて整数
部分点
この問題はいくつかの小課題に分けられ,その小課題のすべてのテストケースに正解した場合に「この小課題に正解した」とみなされます.
提出したソースコードの得点は,正解した小課題の点数の合計となります.
- (11 点) H = 1, W = 1
- (17 点) H = 1, W \leq 20
- (28 点) H \leq 20, W \leq 20
- (27 点) H \leq 75, W \leq 75
- (17 点) 追加の制約はない.
入力
入力は以下の形式で標準入力から与えられます.
H W K V A_{1, 1} A_{1, 2} A_{1, 3} ... A_{1, W} A_{2, 1} A_{2, 2} A_{2, 3} ... A_{2, W} A_{3, 1} A_{3, 2} A_{3, 3} ... A_{3, W} : A_{H, 1} A_{H, 2} A_{H, 3} ... A_{H, W}
出力
彼が買うことのできる家として考えられる,最大の面積を求めてください.
ただし,家を購入できない場合は 0
と出力してください.
入力例 1
1 1 200 500 300
出力例 1
1
彼は唯一のマスを購入し,家を建設すると,200 + 300 = 500 円かかり,ギリギリ足ります.
この入力例は,小課題 1 の制約を満たします.
入力例 2
1 8 10 200 30 40 10 20 30 40 10 20
出力例 2
6
例えば,彼が以下のように土地を購入したとしましょう.
その場合,土地を購入するのに 10 + 20 + 30 + 40 + 10 + 20 = 130 円,家を建設するのに 6 × 10 = 60 円かかるため,合計で 130 + 60 = 190 円必要ですが,200 円以下なので面積 6 の家が建設可能です.
なお,面積 7 以上の家を購入できるような方法はありません.
この入力例は,小課題 2 の制約を満たします.
入力例 3
5 5 10 17 12 19 25 13 25 14 16 18 11 10 19 17 24 26 12 23 11 16 19 14 18 23 27 11 16
出力例 3
0
この入力例では,家を購入することができません.そのため,0
と出力してください.
入力例 4
4 7 10 240 17 12 15 18 19 15 23 22 12 41 16 27 10 10 15 69 18 11 10 23 15 12 20 13 12 17 18 15
出力例 4
9
例えば,以下のように土地を買い,面積 9 の家を購入すると,235 円が必要となり,ギリギリ足ります.
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点: 100 点
問題文
ギガ通りは西から東へ一直線に走る,長さ L メートルの道路です.
E869120 君は最初ギガ通りの西端におり,分速 V_S メートルで残り D_S メートル走れる車に乗っています.
この通りにはこれ以外にも N 個の車があります.i 個目の車は西端から X_i メートルの位置にあり,分速 V_i メートルで残り D_i メートル走れます.
あなたは,車を 西から東の向きに 運転し,ギガ通りの東端にたどり着きたいです.
彼は,途中で車が停まっている場所まで運転してその車に乗り換えることもできます.乗り継ぎにかかる時間は 0 分として良いです.
さて,彼はギガ通りの東端にたどり着けるでしょうか?たどり着けない場合このことを報告し,たどり着ける場合は東端にたどり着くのに必要な最短時間 (分) を報告してください.
制約
- 0 \leq N \leq 2 \ 019
- 1 \leq L \leq 40 \ 075 \ 017
- 1 \leq X_1, X_2, \dots, X_N \leq L-1
- X_1, X_2, \dots, X_N はすべて異なる
- 1 \leq V_S, V_1, V_2, \dots, V_N \leq 100 \ 000
- 1 \leq D_S, D_1, D_2, \dots, D_N \leq L
- 入力はすべて整数
部分点
この問題はいくつかの小課題に分けられ,その小課題のすべてのテストケースに正解した場合に「この小課題に正解した」とみなされます.
提出したソースコードの得点は,正解した小課題の点数の合計となります.
- (9 点) N = 0
- (6 点) N = 0 または N = 1
- (22 点) N \leq 10
- (30 点) V_S = 1 であり、すべての i に対して V_i = 1
- (33 点) 追加の制約はない.
小課題 4 のヒント
この小課題は,「東端にたどり着けるかどうか」を判定する問題です.なぜなら,すべての場所で分速 1 メートルで進むので,たどり着ける場合は最短時間が絶対 L 分になるからです.小課題 4 に取り掛かる人は,このヒントも踏まえて考えてみるのも良いでしょう.
入力
入力は以下の形式で標準入力から与えられます.
N L V_S D_S X_1 V_1 D_1 X_2 V_2 D_2 : : : X_N V_N D_N
出力
ギガ通りの東端に何をやってもたどり着けないならば impossible
と出力してください.
たどり着ける場合は,その際にかかる最短時間 (分) を出力してください.これは小数点以下何桁でも出力して良いですが,答えとの誤差(絶対誤差または相対誤差)が 10^{-5} 以内であったときのみ正解とみなされます.
入力例 1
3 10 1 5 3 5 8 6 10 5 7 2 7
出力例 1
4.000000000000000000000
次のような移動をすると 4 分でギガ通りの東端にたどり着くことができ、これが最短です。
- まず、最初に乗る車で西端から 3 メートルのところまで進む。これに 3/1 = 3 分かかる。
- 次に、1 個目の車で西端から 6 メートルのところまで進む。これに 3/5 = 0.6 分かかる。
- 最後に、2 個目の車で東端 (西端から 10 メートルのところ) まで進む。これに 4/10 = 0.4 分かかる。
- 合計 3 + 0.6 + 0.4 = 4 分で、東端にたどり着くことができた。
入力例 2
3 10 1 5 3 5 8 6 1 5 7 2 7
出力例 2
4.400000000000000355271
次のような移動をすると 4.4 分でギガ通りの東端にたどり着くことができ、これが最短です。
- まず、最初に乗る車で西端から 3 メートルのところまで進む。これに 3/1 = 3 分かかる。
- そして、1 個目の車で東端 (西端から 10 メートルのところ) まで進む。これに 7/5 = 1.4 分かかる。
- 合計 3 + 1.4 = 4.4 分で、東端にたどり着くことができた。
入力例 3
2 10 1 4 3 1 2 6 1 10
出力例 3
impossible
この場合、どうやってもギガ通りの東端にたどり着くことはできません。
また、入出力例 3 は小課題 4「V_S = 1、V_i = 1」の制約を満たします。
入力例 4
0 1 99991 1
出力例 4
0.000010000900081007291
答えは 1.00009e-05
のような形式ではなく、0.00001000090008
のような形式で出力する必要があることに注意してください。
また、入出力例 4 は小課題 1「N = 0」の制約を満たします。
入力例 5
1 100 5 60 50 7 90
出力例 5
17.142857142857142349612
この場合、西端から 50 メートルのところで乗り継ぐのが最適となります。
また、入出力例 5 は小課題 2「N = 0 または N = 1」の制約を満たします。
入力例 6
4 1000 37 426 725 16 612 237 19 458 516 13 509 408 17 400
出力例 6
46.861585850556437549130
絶対誤差または相対誤差が 10^{-5} 以内ならば正解とみなされますので、46.861585
や 46.86159
などと出力しても正解となります。
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点: 100 点
問題文
ギガコード君は家を買いました.この家は,左右に H 分割,前後に W 分割された合計 H \times W 個の区画に分かれています.そのうち左から i 番目,前から j 番目のマスを (i, j) で表します.
そのうち N 個の区画には物が置かれています.i 個目の物は,区画 (r_i, c_i) 全体を占めています.また,これらの物が動くことはありません.
ギガコード君は,この家にクローゼットを 1 つ設置することにしました.クローゼットは家の外壁に平行な長方形でなければならず,クローゼットのある区画に物が置かれていてはなりません.しかし,地震が起きた時にクローゼットが動くと良くないので,次の条件を満たす置き方のうち 1 つを選ぶことにしました.
- クローゼットを向きを変えずにどんな方向に動かそうとしても,物や家の外壁に当たって動かせない.
例えば,次のようなクローゼットの配置ができます.
しかし,条件を満たさないクローゼットの配置はできません.
条件を満たすようなクローゼットの配置はいくつあるか求めてください.
制約
- 1 \leq H \leq 5 \ 000
- 1 \leq W \leq 5 \ 000
- 0 \leq N \leq 201 \ 900
- 1 \leq r_i \leq H
- 1 \leq c_i \leq W
- N 個の物はすべて異なる区画に置かれている
- 入力はすべて整数
部分点
この問題はいくつかの小課題に分けられ,その小課題のすべてのテストケースに正解した場合に「この小課題に正解した」とみなされます.
提出したソースコードの得点は,正解した小課題の点数の合計となります.
- (2 点) H = 1, W = 1
- (11 点) H = 1, W \leq 25
- (11 点) H \leq 25, W \leq 25
- (19 点) N \leq 10
- (16 点) H \leq 100, W \leq 100
- (17 点) H \leq 350, W \leq 350
- (19 点) H \leq 1500, W \leq 1500
- (5 点) 追加の制約はない.
入力
入力は以下の形式で標準入力から与えられます.
H W N r_1 c_1 r_2 c_2 : : r_N c_N
出力
地震が起きても動かないようなクローゼットの配置の数を出力してください.
注意
入力のサイズが大きいので、高速な入出力(C++ の場合 scanf/printf など)を使うことが推奨されています.
入力例 1
3 3 2 1 1 3 2
出力例 1
4
この入出力例では,クローゼットを配置する方法は下図のように 4 個ありますので,「4」と出力してください.
入力例 2
1 10 3 1 1 1 5 1 8
出力例 2
3
この入力例は H = 1 なので小課題 2 の制約を満たします.
クローゼットを配置する方法は下図のように 3 個あります.
入力例 3
4 6 6 1 3 4 2 2 1 2 4 3 6 4 5
出力例 3
11
クローゼットを配置する方法は 11 個あります.自分でも数えてみましょう!
入力例 4
4802 5000 10 254 3330 1713 3331 1712 989 256 988 4192 3521 3602 4991 255 987 3603 3520 256 987 4191 4992
出力例 4
32
この入力例は N = 10 なので小課題 4 の制約を満たします.
小課題 4 には,H, W が大きい場合もあることに注意してください.
実行時間制限: 3 sec / メモリ制限: 1024 MB
配点: 100 点
問題文
ギガ国には N 個の都市があり,それぞれ 1, 2, 3, \dots, N と番号が付けられています.
いくつかの都市は道路でつながれています.具体的には,M 本の道路があり,i 本目の道路は都市 a_i と b_i を双方向に結んでいます.また,いくつかの道路だけを通ることによって,どの都市からどの都市へも行けるようになっています.
ここで,d(i, j) を,「都市 i と j の距離」,つまり「都市 i から都市 j に道路だけを使って行くときに使う,最小の道路の本数」とします.
そのとき,すべての異なる 2 都市の組 (x, y) に対しての距離 d(x, y) の合計を求めて下さい.
制約
- 1 \leq N \leq 100 \ 000
- 1 \leq M \leq 100 \ 000
- N - 1 \leq M \leq N + 777
- 1 \leq a_i, b_i \leq N
- a_i \neq b_i
- どのような (u, v) の組においても,都市 u と都市 v を直接結ぶ道路は高々 1 つしか存在しない.
- どの都市からどの都市へも,道路を辿って行くことができる.
- 入力はすべて整数
部分点
この問題はいくつかの小課題に分けられ,その小課題のすべてのテストケースに正解した場合に「この小課題に正解した」とみなされます.
提出したソースコードの得点は,正解した小課題の点数の合計となります.
- (9 点) N \leq 100, M \leq 100
- (7 点) N \leq 3 \ 000, M \leq 3 \ 000
- (12 点) M - N = -1 を満たす.
- (13 点) M - N = 0 を満たす.
- (28 点) M - N \leq 7 を満たす.また,1 \leq i \leq N-1 について,a_i = i, b_i = i+1 を満たす.
- (22 点) M - N \leq 77 を満たす.
- (9 点) 追加の制約はない.
入力
入力は以下の形式で標準入力から与えられます.
N M a_1 b_1 a_2 b_2 : : a_M b_M
出力
全ての都市 x, y 間の距離 d(x, y) の合計を出力してください.
注意
この問題は入出力のサイズがやや大きいため,高速な入出力(C++ の場合 scanf/printf など)を用いることが推奨されます.
入力例 1
4 3 1 2 2 3 3 4
出力例 1
10
ギガ国は,以下のような道路網を持ちます.
この道路網において,d(1, 2) = 1, d(1, 3) = 2, d(1, 4) = 3, d(2, 3) = 1, d(2, 4) = 2, d(3, 4) = 1 より,答えは 1+2+3+1+2+1=10 となります.
入力例 2
4 6 1 2 1 3 1 4 2 3 2 4 3 4
出力例 2
6
ギガ国は,以下のような道路網を持ちます.
この道路網において,すべての都市間を距離 1 で移動できるので,答えは 6 となります.
入力例 3
9 12 1 2 2 3 4 5 5 6 7 8 8 9 1 4 4 7 2 5 5 8 3 6 6 9
出力例 3
72
実行時間制限: 1 sec / メモリ制限: 1024 MB
配点: 100 点
問題文
N 個のスイッチがあり,それぞれスイッチ 1, 2, 3, ..., N と番号付けられています.各スイッチは,0 か 1 のいずれか二通りの状態を持ちます.
さて,あなたは番号 N+1, N+2, ..., N+M がついた M 個のメモリを使って,回路を作ることができます.(M の値は自由に決められます.)
メモリには,以下の 4 種類があります.以下の説明では,該当するメモリの番号を x としています.
① AND メモリ
2 つのスイッチ/メモリから繋がっており,これらを番号 u, v (u < x, v < x) とします.番号 x のメモリの値は,番号 u がついたスイッチ/メモリの値・番号 v がついたスイッチ/メモリの値が両方 1 であれば 1 となり,そうでなければ 0 となります.
② OR メモリ
2 つのスイッチ/メモリから繋がっており,これらを番号 u, v (u < x, v < x) とします.番号 x のメモリの値は,番号 u がついたスイッチ/メモリの値・番号 v がついたスイッチ/メモリの値のうち片方でも 1 であれば 1 となり,そうでなければ 0 となります.
③ XOR メモリ
2 つのスイッチ/メモリから繋がっており,これらを番号 u, v (u < x, v < x) とします.番号 x のメモリの値は,番号 u がついたスイッチ/メモリの値・番号 v がついたスイッチ/メモリの値のうち一つだけが 1 であれば 1 となり,そうでなければ 0 となります.
④ NOT メモリ
1 つのスイッチ/メモリから繋がっており,これを番号 u (u < x) とします.番号 x のメモリの値は,番号 u がついたスイッチ/メモリの値が 0 であれば 1 となり,そうでなければ 0 となります.
例えば,以下の図のような回路を考えます.
この回路の場合,それぞれのスイッチの状態について各メモリの状態は,以下の表のようになります.
スイッチ1 | スイッチ2 | スイッチ3 | メモリ4 | メモリ5 | メモリ6 |
---|---|---|---|---|---|
0 | 0 | 0 | 0 | 1 | 0 |
0 | 0 | 1 | 0 | 0 | 0 |
0 | 1 | 0 | 1 | 1 | 1 |
0 | 1 | 1 | 1 | 0 | 0 |
1 | 0 | 0 | 1 | 1 | 1 |
1 | 0 | 1 | 1 | 0 | 0 |
1 | 1 | 0 | 0 | 1 | 0 |
1 | 1 | 1 | 0 | 0 | 0 |
そのため,{スイッチ1, スイッチ2, スイッチ3} の状態が {0, 1, 0}, {1, 0, 0} の 2 通りに限り,メモリ6 の値が 1 となります.
それについて,以下の 2 つの問題を解いてください.
T=1 のとき
スイッチの状態は 2^N 通りありますが,そのうちちょうど K 通りについて,番号 N+M のメモリ(M=0 の場合はスイッチ)の値が 1 となるような回路を一つ構成してください.
ただし,2^{N}×4N 個を超えるメモリを使ってはいけません.
T = 2 のとき
スイッチの状態が S_1, S_2, S_3, ..., S_K であるときに限り,番号 N+M のメモリ(M=0 の場合はスイッチ)の値が 1 となるような回路を一つ構成してください.
ただし,50 \ 000 個を超えるメモリを使ってはいけません.
制約
- 1 \leq T \leq 2
- 2 \leq N \leq 10
- 1 \leq K \leq 2^{N}-1
- T, N, K は整数
小課題・得点
この問題には,2 つの小課題があります.
- (30 点) T = 1.
- (70 点) T = 2.
小課題 1 において,各テストケースに対して以下のように得点が定められます.この小課題の全部のテストケースに対する最低得点がこの小課題の得点となります.
- 2^{N}×4N < M のとき,0 点.
- 2^{N}×2 < M \leq 2^{N}×4N のとき,10 点.
- N^2 < M \leq 2^{N}×2 のとき,16 点.
- N-1 < M \leq N^2 のとき,23 点.
- M \leq N-1 のとき,30 点満点.
次に,小課題 2 において,すべてのテストケースにおける M の最大値を L_2 としたとき,この小課題の得点は以下のようになります.
- 50 \ 001 \leq L_2 のとき,0 点.
- 4 \ 201 \leq L_2 \leq 50 \ 000 のとき,15 点.
- 3 \ 101 \leq L_2 \leq 4 \ 200 のとき,18 点.
- 2 \ 101 \leq L_2 \leq 3 \ 100 のとき,21 点.
- 1 \ 601 \leq L_2 \leq 2 \ 100 のとき,25 点.
- 1 \ 201 \leq L_2 \leq 1 \ 600 のとき,29 点.
- 751 \leq L_2 \leq 1 \ 200 のとき,35 点.
- 501 \leq L_2 \leq 750 のとき,floor(70 - \frac{L_2 - 500}{8}) 点.
- L_2 \leq 500 のとき,70 点満点.
入力
入力は以下の形式で標準入力から与えられます.
(☆) T = 1 のとき
1 N K
ただし,N はスイッチの個数,K は番号 N+M のスイッチ(M=0 の場合メモリ)の値が 1 であるべき状態の通り数を意味します.
(★) T = 2 のとき
2 N K S_1 S_2 S_3 : S_K
ここでは,S_i は番号 N+M のスイッチ (M=0 の場合メモリ) の値が 1 であるべき状態のうち,i 番目のものです.
S_i は N 文字の文字列で表され,i 文字目が 0
である場合は i 番目のスイッチの状態が 0 である,i 文字目が 1
である場合は i 番目のスイッチの状態が 1 であることを意味します.
例えば,N = 4 で S_i = 0101
の場合,スイッチ 2, 4 が 1 であり,スイッチ 1, 3 が 0 であるような状態のことを表します.
出力
以下のように,論理回路の構成方法を出力してください.
M (番号 N+1 のメモリの情報) (番号 N+2 のメモリの情報) (番号 N+3 のメモリの情報) : (番号 N+M のメモリの情報)
番号 x のメモリの情報は,以下のように出力してください.
AND メモリの場合
AND u v
これは,番号 u と v のスイッチ/メモリから,番号 x のメモリに繋がっていることを表します.u < x, v < x を満たさなければなりません.(ただし u = v でも構わない)
OR メモリの場合
OR u v
これは,番号 u と v のスイッチ/メモリから,番号 x のメモリに繋がっていることを表します.u < x, v < x を満たさなければなりません.(ただし u = v でも構わない)
XOR メモリの場合
XOR u v
これは,番号 u と v のスイッチ/メモリから,番号 x のメモリに繋がっていることを表します.u < x, v < x を満たさなければなりません.(ただし u = v でも構わない)
NOT メモリの場合
NOT u
これは,番号 u のスイッチ/メモリから,番号 x のメモリに繋がっていることを表します.u < x を満たさなければなりません.
入力例 1
1 3 2
出力例 1
3 XOR 1 2 NOT 3 AND 4 5
この出力の場合,N = 2 に対して M = 3 であり,N 以上 N^2 以下なので 23 点となります.
入力例 2
2 3 2 010 100
出力例 2
3 XOR 1 2 NOT 3 AND 4 5
入力例 3
1 5 24
出力例 3
1 OR 1 2
入力例 4
2 3 4 001 101 011 111
出力例 4
0