A - 名刺交換
青木君は就職活動をおこなっている大学生で、名刺を N 枚持っています。
これから M 日間の就職活動を予定しており、 i 日目には名刺を c_{i} 枚消費することがわかっています。
就職活動を行うにあたり、名刺が足りなくなると非常に困ります。
そこで、青木君はそれぞれの日のはじめに名刺の所持枚数を確認し、A 枚以下ならば B 枚名刺を補充することにしました。
B 枚補充しても A 枚以下にしかならないような場合でも、それ以上の補充はできません。
最初から持っている N 枚とこのような補充で、就職活動の最後の日まで乗りきれるかどうか判定してください。
もし、足りなくなる場合は、その日付を青木君に教えてあげてください。
入力は以下の形式で標準入力から与えられる。
就職活動の最後の日まで乗り切ることができれば
もし、名刺を配りきってしまった場合は、足りなくなった日の日付を出力すること。
出力は標準出力におこない、末尾には改行をいれること。
Time Limit: 2 sec / Memory Limit: 64 MB
問題文
これから M 日間の就職活動を予定しており、 i 日目には名刺を c_{i} 枚消費することがわかっています。
就職活動を行うにあたり、名刺が足りなくなると非常に困ります。
そこで、青木君はそれぞれの日のはじめに名刺の所持枚数を確認し、A 枚以下ならば B 枚名刺を補充することにしました。
B 枚補充しても A 枚以下にしかならないような場合でも、それ以上の補充はできません。
最初から持っている N 枚とこのような補充で、就職活動の最後の日まで乗りきれるかどうか判定してください。
もし、足りなくなる場合は、その日付を青木君に教えてあげてください。
入力
N M A B
c_{1}
c_{2}
:
:
c_{M}
- 1 行目に N , M , A , B が半角スペースで区切られて与えられる。
- N は持っている名刺の枚数で 1≦N≦1,000 を満たす。
- M は就職活動の日数で 0≦M≦100 を満たす。
- A は名刺を補充するタイミングの枚数を示す数で 0≦A≦1,000 を満たす。
- B は補充する名刺の枚数で 0≦B≦1,000 を満たす。
- N , M , A , B は全て整数である。
- 2 行目から M+1 行目までの M 行間で、名刺を配る枚数がそれぞれ与えられる。
- c_{i} は i(1≦i≦M) 日目に配る名刺の枚数を表す整数で 0≦c_{i}≦1,000 を満たす。
出力
completeと出力すること。もし、名刺を配りきってしまった場合は、足りなくなった日の日付を出力すること。
出力は標準出力におこない、末尾には改行をいれること。
入力例 1
100 3 0 100 10 20 30
出力例 1
complete
- 就職活動を通して 60 枚しか使わないので名刺は余ります。
入力例 2
100 4 0 100 10 20 30 40
出力例 2
complete
- 就職活動最終日にちょうど名刺を配りきります。
入力例 3
100 4 0 100 50 40 30 20
出力例 3
3
- 2 日目終了時点で残り 10 枚で、補充ができないので 3 日目は足りなくなります。
入力例 4
100 4 10 100 50 40 30 20
出力例 4
complete
- 2 日目が終了した時点で残り 10 枚で、3 日目の始めに 100 枚補充するので、最終日を終えても名刺は余っています。
入力例 5
5 3 20 10 15 5 20
出力例 5
3
- 1 日目が始まる時点で、残り枚数が 20 枚を下回っているので名刺を補充して、15 枚にすることでその日は無事に配ることができます。
- 2 日目が始まる時に名刺が足りないのでまた補充し、その日は 5 枚余って終了することができます。
- しかし、3 日目では補充しても枚数が 15 枚にしかならず、名刺不足になります。
B - 超大型連休
2011 年、AtCoder 国の高橋首相はある重大な決定を行った。
その決定とは...法改正である。国民の祝日に関する法律を変更し、休日を増やすことにした!!
国民の創造性を尊重するその決定が、霞が関を魔境へと変えたッ！
あなたは霞が関の国土交通省に勤務する職員であり、この法改正により上司から新たな任務を与えられた。
その任務とは、2012 年の「連休の最大日数」を計算することである。
連休の大きさを事前に計算することで国民の行動を予想し、高速道路の部分的な値下げを行い、経済を活性させるためだ。
したがって、あなたに失敗することは許されない。国民の行動を正確に予想できなくなるからだ。
以下に、「連休」の定義と諸注意を記す。
入力は以下の形式で標準入力から与えられる。
法改正後における 2012 年の連休の最大日数を出力せよ。
出力は標準出力におこない、末尾には改行をいれること。
Time Limit: 2 sec / Memory Limit: 64 MB
問題文
その決定とは...法改正である。国民の祝日に関する法律を変更し、休日を増やすことにした!!
国民の創造性を尊重するその決定が、霞が関を魔境へと変えたッ！
あなたは霞が関の国土交通省に勤務する職員であり、この法改正により上司から新たな任務を与えられた。
その任務とは、2012 年の「連休の最大日数」を計算することである。
連休の大きさを事前に計算することで国民の行動を予想し、高速道路の部分的な値下げを行い、経済を活性させるためだ。
したがって、あなたに失敗することは許されない。国民の行動を正確に予想できなくなるからだ。
以下に、「連休」の定義と諸注意を記す。
- AtCoder 国が使用する暦はグレゴリオ暦に従う。
- 「連休」とは、「休日」が連続して続くことである。
- 「土曜日」「日曜日」「祝日」「振替休日」が「休日」に相当する。
- 「祝日」が他の休日と同じ日に指定されていた場合、「振替休日」を必ず設置する。
- 「振替休日」は祝日の時系列順に決定していき、その祝日以降最も近い平日（休日を除いた日）となる。
- 2012 年 1 月 1 日は日曜日である。
入力
N
m_{1}/d_{1}
m_{2}/d_{2}
:
:
m_{n}/d_{n}
- 1 行目には祝日の日数を表す整数 N が与えられ、 0≦N≦366 を満たす。
- 2 行目から N+1 行目までの N 行で祝日の日付が与えられる。
- m_{i} は i(1≦i≦366) 番目に与えられる祝日の月で、 1≦m_{i}≦12 を満たす。
- d_{i} は i(1≦i≦366) 番目に与えられる祝日の日で、
- m_{i} = 2 のとき、 1≦d_{i}≦29 を満たす。
- m_{i} = (4, 6, 9, 11) のとき、 1≦d_{i}≦30 を満たす。
- m_{i} = (1, 3, 5, 7, 8, 10, 12) のとき、 1≦d_{i}≦31 を満たす。
- m_{i} と d_{i} はともに整数である。
- m_{i} と d_{i} は必ず
/で区切られて与えられる。 - 祝日は時系列順に与えられるとは限らないことに注意せよ。ただし、同じ日付が複数与えられないことは保証されている。
出力
出力は標準出力におこない、末尾には改行をいれること。
入力例 1
1 1/9
出力例 1
3
- 1/7(土),1/8(日),1/9(月)の 3 連休が最長です。
入力例 2
1 1/10
出力例 2
2
- 1/10(火)が祝日となり、1/7(土),1/8(日)などの 2 連休が最長です。
入力例 3
1 1/7
出力例 3
3
- 1/7は土曜日なので、以降で最も近い平日である1/9が振替休日になります。
- よって、1/7(土)、1/8(日)、1/9(月)の3連休が最長です。
入力例 4
2 1/7 1/9
出力例 4
4
- 1/7は土曜日なので振替休日を以降に設定したく、1/9が祝日なので1/10が振替休日になります。
- よって、1/7(土)、1/8(日)、1/9(月)、1/10(火)の4連休が最長です。
C - 積み上げパズル
高橋君はある日、以下のようなゲームで遊ぶことにしました。
m 色のブロックが n 個、1 つずつ順番に落ちてきます。
1 つ落ちてくるたびに、高橋君は落ちてきたそのブロックを取って山に積むか、積まずに捨てるか選べます。
ブロックを積む山は 1 つで、ブロックは必ず山の一番上に積まないといけません。
全てのブロックが落ちきった後、出来た山は以下のように評価されます。
入力は以下の形式で標準入力から与えられる。
評価で得ることのできる得点の最大値を標準出力に 1 行で出力せよ。
なお、最後には改行を出力せよ。
Time Limit: 2 sec / Memory Limit: 64 MB
問題文
m 色のブロックが n 個、1 つずつ順番に落ちてきます。
1 つ落ちてくるたびに、高橋君は落ちてきたそのブロックを取って山に積むか、積まずに捨てるか選べます。
ブロックを積む山は 1 つで、ブロックは必ず山の一番上に積まないといけません。
全てのブロックが落ちきった後、出来た山は以下のように評価されます。
- 色ボーナス：色ごとに決められた得点が、山に含まれている個数分与えられます。
- コンボボーナス：同じ色のブロックが x 個続いて積まれている場合、コンボボーナス配点 Y に応じて Y×(x-1) 点が与えられます。
- 全色ボーナス：山の中に m 色のブロックがそれぞれ 1 個以上含まれていると Z 点が与えられます。
入力
n m Y Z c_1 p_1 c_2 p_2 : : c_m p_m b_1b_2 ‥‥ b_n
- 1 行目に n, m, Y, Z が半角スペースで区切られて与えられる。
- n はブロックの個数で 1≦n≦5,000 を満たす。
- m はブロックの色の総数で 1≦m≦10 を満たす。
- Y はコンボボーナス配点で -100≦Y≦100 を満たす。
- Z は全色ボーナス配点で -10,000≦Z≦10,000 を満たす。
- n, m, Y, Z は全て整数である。
- 2 行目からの m+1 行目までの m 行で色ボーナスの配点がそれぞれ与えられる。
- c_i は i(1≦i≦m) 番目に与えられるブロックの色である。
- p_i は c_i に対する色ボーナスの配点である。
- c_i は英大文字(
A-Z)、p_i は -100≦p_i≦100 を満たす。 - 配点は重複して与えられない（x≠y ならば c_x≠c_y)
- m+2 行目には落ちてくるブロックの順序を表す長さ n の文字列が与えられる。
- b_j は j(1≦j≦n) 番目に落ちてくるブロックの色を表している。
- b_j は c_1,c_2,...,c_m のいずれかである。
出力
なお、最後には改行を出力せよ。
入力例 1
5 3 3 5 R 1 G 1 B 1 RGBRR
出力例 1
13
- 全てのブロックを山に積むと、
- 色ボーナス：どの色も配点が 1 点なので、1 点 × 5 個 = 5点
- コンボボ−ナス：Rが 2 個連続しているので、3×(2-1)=3 点
- 全色ボーナス：全ての色が 1 つ以上山に積まれているので、5 点
- いずれかのブロックを捨てるとこの点数よりも低くなるので、答えは 13 点です。
入力例 2
3 3 3 5 R 1 G 3 B 2 RBR
出力例 2
5
- 全てのブロックを山に積むと、
- 色ボーナス：1 点 ×2 個 +2 点 ×1 個 =4 点
- 連続していないのでコンボボーナス、Gが含まれていないので全色ボーナスはそれぞれ 0 点
- しかし、Bを捨ててRRを山に積むと、
- 色ボーナス：1 点 ×2 個 =2 点
- コンボボーナス：3×(2-1)=3 点
入力例 3
8 3 5 3 R 1 G 1 B 1 RRGRRBRR
出力例 3
31
- 図 (a) のように順に 8 個のブロックが落ちてきます。
- ブロックを全部山に積むと、図 (b) のように、2 個のコンボが 3 組できます。
- また、全色ボーナスもつくので、1 点 × 8 個 + 5 点 × (2-1) × 3 組 + 3 点 = 26 点です。
- しかし、図 (c) のようにRのみを山に積むと、1 点 × 6 個 + 5 点 × (6-1) + 0 点 = 31 点になります。
- Rだけ山に積むとき最高得点となり、31 が答えです。
入力例 4
8 3 5 3 R 1 G 100 B 1 RRGRRBRR
出力例 4
126
- 全部積んだ場合(図 (a))：107 点 + 5 点 × (2-1) × 3 組 + 3 点 = 125 点
- Rのみを積んだ場合(図 (b))：6 点 + 5 点 × (6-1) + 0 点 = 31 点
- B以外を積んだ場合(図 (c))：106 点 + 5 点 × \{(2-1) + (4-1)\} + 0 点 = 126 点
- したがって、最高得点は 126 点です。
D - 情報伝播
AtCoder 国の秘密情報部に就職した青木くんは諜報活動に勤しむ青年です。
今回、青木くんに与えられたミッションは以下の様なものです。
このミッションを達成するために、青木くんは全ての仲間の場所に赴いて
この 3 つを行えば良いのですが、残念ながら全ての仲間の場所へ赴くような時間はありません。
そこで、青木くんは仲間がスピーカーで情報を拡散してしまう性質を利用して、効率良く機密情報を伝えてもらうことにしました。
スパイに機密情報が漏れることなく、全ての仲間に機密情報を伝えるとき、青木くんが機密情報を伝えなければならない仲間の最小の人数はいくらでしょうか。
入力は以下の形式で標準入力から与えられる。
情報を伝える必要がある最小の人数を出力せよ。
出力は標準出力におこない、末尾には改行をいれること。
Time Limit: 8 sec / Memory Limit: 256 MB
問題文
今回、青木くんに与えられたミッションは以下の様なものです。
- 青木くんは 2 次元座標上に散らばる全ての仲間に AtCoder 国の機密情報を伝えなければならない。
- ただし、その 2 次元座標上には仲間だけでなく、敵国のスパイが紛れ込んでいる。
- 青木くんが仲間に機密情報を伝えると、情報を受け取った仲間はスピーカーで情報を拡散する（機密情報だというのに！）
- スピーカーで情報を拡散するとは、自分を中心とする同心円状内（スピーカーの音量は調節できるので、半径は任意である）にいる全ての「人間」に情報を伝えることである。
- 情報を受け取った仲間もスピーカーで情報を拡散し、連鎖的に情報を伝えていく。
- 当然のことながらスパイに機密情報が伝わってはいけない。
このミッションを達成するために、青木くんは全ての仲間の場所に赴いて
- 機密情報を伝える
- 持っているスピーカーを叩き潰す
- 「機密情報を漏らすな」と念を押す
この 3 つを行えば良いのですが、残念ながら全ての仲間の場所へ赴くような時間はありません。
そこで、青木くんは仲間がスピーカーで情報を拡散してしまう性質を利用して、効率良く機密情報を伝えてもらうことにしました。
スパイに機密情報が漏れることなく、全ての仲間に機密情報を伝えるとき、青木くんが機密情報を伝えなければならない仲間の最小の人数はいくらでしょうか。
入力
N
f_{x1} f_{y1}
f_{x2} f_{y2}
:
:
f_{xN} f_{yN}
M
s_{x1} s_{y1}
s_{x2} s_{y2}
:
:
s_{xM} s_{yM}
- 1 行目には仲間の数を表す整数 N が与えられ、 1≦N≦5,000 を満たす。
- 2 行目から N+1 行目までの N 行で仲間の位置情報が与えられる。
- f_{xi} は i 番目に与えられる仲間の X 座標である。
- f_{yi} は i 番目に与えられる仲間の Y 座標である。
- i は 1≦i≦N を満たし、 f_{xi} と f_{yi} はそれぞれ -10^9≦f_{xi} , f_{yi}≦10^9 を満たす整数である。
- N+2 行目にはスパイの数を表す整数 M が与えられ、 0≦M≦100,000 を満たす。
- N+2 行目から N+M+2 行目までの M 行でスパイの位置情報が与えられる。
- s_{xj} は j 番目に与えられるスパイの X 座標である。
- s_{yj} は j 番目に与えられるスパイの Y 座標である。
- j は 1≦j≦M を満たし、 s_{xj} と s_{yj} はそれぞれ -10^9≦s_{xj} , s_{yj}≦10^9 を満たす整数である。
- 同じ座標に複数の人間が重なることはない。
- M>1,000 のとき、スパイはランダムに分布することが保証される。
部分点
- 0≦N≦10 を満たす入力にのみ正解した場合、部分点として 10 点が与えられる。
- 0≦N≦30 を満たす入力にのみ正解した場合、部分点として 50 点が与えられる。
出力
出力は標準出力におこない、末尾には改行をいれること。
入力例 1
3 1 1 1 2 2 1 0
出力例 1
1
- 座標 (1, 1) にいる仲間に伝えることができれば、 3 人の仲間全員に伝えることができます。
入力例 2
2 1 1 1 2 1 2 1
出力例 2
1
- 座標 (1, 2) にいる仲間に伝えることができれば、 2 人の仲間全員に伝えることができます。
- 座標 (1, 1) にいる仲間から 座標 (1, 2) にいる仲間に伝えようとすると、必ずスパイに見つかってしまいます。
入力例 3
5 1 1 1 2 2 3 3 3 5 3 2 2 1 4 4
出力例 3
2
- 座標 (2, 3) にいる仲間に伝えることができれば、座標 (1, 2) にいる仲間と、座標 (3, 3) にいる仲間へ情報を伝えることができます。
- その後、座標 (1, 2) にいる仲間から座標 (1, 1) にいる仲間へ情報が伝搬されます。
- 座標 (5, 3) にいる仲間へは、別途情報を伝える必要があります。
入力例 4
10 -10 5 2 9 -4 4 10 -9 8 3 5 6 4 -5 6 8 -8 10 -4 -2 10 -1 2 -2 -7 9 -3 -5 5 6 -10 -10 9 7 4 2 1 -10 1 -5 2
出力例 4
8