Time Limit: 2 sec / Memory Limit: 64 MB
問題文
センター試験の各々の問題は 1 から 4 までの選択肢があります。高橋君はあまり勉強をしていなかったので、全ての問題で同じ選択肢を選びました。
試験終了後、センター試験の解答が与えられましたが、高橋君は何番を選んだのかを忘れてしまいました。しかし、高橋君は自分の点数が気になります。
そこで、高橋君のため、高橋君が正解する問題の数として考えられる最大と最小の数を求めなさい。
入力
N c_1c_2c_3…c_N
- 1 行目は、センター試験の問題の数を表す整数 N (1 ≦ N ≦ 100) が与えられる。
- 2 行目は、センター試験の解答を表す N 文字の文字列が与えられる。この文字列の i 文字目 (1 ≦ i ≦ N) の文字 c_i (c_i は
1
、2
、3
、4
のいずれかである) は、i 番目の問題の正解が c_i であったことを表す。
出力
入力例 1
9 131142143
出力例 1
4 1
- 選択肢 1 を選ぶ時、高橋君が正解する問題の数は 4 問となり、これが最大の正解数です。
- 選択肢 2 を選ぶ時、高橋君が正解する問題の数は 1 問となり、これが最小の正解数です。
入力例 2
20 12341234123412341234
出力例 2
5 5
- 1,2,3,4 のいずれの選択肢を選んだ場合も、正答数は 5 問であり、高橋君が正解する問題の数の最小と最大の数はいずれも 5 となります。
入力例 3
4 1111
出力例 3
4 0
Source Name
ARC 001Time Limit: 2 sec / Memory Limit: 64 MB
問題文
壊れたキーは押しても文字が出力されません。
力が強いことで有名な高橋君なので、キーを強く叩きすぎたのでしょう。
しかし、高橋君は小さいことは気にしない性格なので、そのキーボードを壊れたまま使うことにしました。
高橋君がタイピングする文字列が与えられるので、壊れたキーボードを用いてタイピングした場合の出力結果を答えなさい。
入力
X s
- 入力は 2 行ある。
- 1 行目には、壊れたキーを表す文字 X が与えられる。
- X は英字の小文字(
a-z
)のいずれかである。
- X は英字の小文字(
- 2 行目にはタイピングする文字列を表す 1 文字以上 50 文字以下の文字列が与えられる。
- 文字列は英語の小文字(
a-z
)のみで成り立っている。
- 文字列は英語の小文字(
出力
なお、最後には改行を出力せよ。
もし何も出力されない場合は改行のみを出力せよ。
入力例 1
a abcdefgabcdefg
出力例 1
bcdefgbcdefg
- 1 文字目と 8 文字目に含まれる
a
の文字が出力されないので、bcdefgbcdefgが答えになります。
入力例 2
g aassddffgg
出力例 2
aassddff
- 最後の
g
が 2 文字出力されません。
入力例 3
a aaaaa
出力例 3
- 何も表示されない場合は改行のみ出力します。
入力例 4
l qwertyuiopasdfghjklzxcvbnm
出力例 4
qwertyuiopasdfghjkzxcvbnm
入力例 5
d qwsdtgcszddddsdfgvbbnj
出力例 5
qwstgcszsfgvbbnj
Source Name
ARC 007Time Limit: 2 sec / Memory Limit: 64 MB
問題文
しかし、私達が普段使用する数字は大小関係が 0<1<2<3<4<5<6<7<8<9 の順になっているのに対して、 AtCoder国の数字ではその大小関係が異なっています。
例えば、AtCoder国の数字では 0<9<8<7<6<5<4<3<2<1 の順になっている場合、AtCoder国では 9 よりも 8 の方が大きいことになります。また、97 よりも 72 の方が大きいことになります。
AtCoder国の数字の大小関係といくつかの数が与えられるので、AtCoder国の数字の大小関係で昇順に並び替えてください。
なお、私達が普段使用する数字同様、AtCoder国で最も小さい数字は 0 であることは決まっています。
入力
b_0 b_1 ‥‥ b_9 N a_0 a_1 : : a_{N-1}
- 入力は N+2 行ある。
- 1 行目には、AtCoder国での 1 桁の数字の大小関係が与えられる。
- AtCoder国では b_0 < b_1 < ... < b_9 であることを表している。
- b_0 は必ず 0 である。
- 重複する数字は存在せず、0 から 9 までの数字が 1 度ずつ現れる。
- 2 行目には並び替える数の個数を表す整数 N(1≦N≦777) が与えられる。
- 3 行目からの N 行には、j+3 行目に並び替える数を表す整数 a_j(1≦a_j≦777,777,777) が与えられる。
出力
なお、最後には改行を出力せよ。
入力例 1
0 8 1 3 5 4 9 7 6 2 10 1 2 3 4 5 6 7 8 9 10
出力例 1
8 1 3 5 4 9 7 6 2 10
- AtCoder国ではこの大小関係の場合、0, 8, 1, 3, 5, 4, 9, 7, 6, 2, 80, 88, 81, 83, ..., 86, 82, 10, 18, 11, ... の順に大きくなるので、答えは上記の順になります。
入力例 2
0 9 8 7 6 5 4 3 2 1 3 13467932 98738462 74392
出力例 2
74392 98738462 13467932
- 5 桁の数は 8 桁の数よりも小さいので、1 番は 74392 になります。
- 98738462 と 13467932 では最上位の 9 は1 より小さいので、98738462 が 2 番目、13467932 が 3 番目になります。
入力例 3
0 1 2 3 4 5 6 7 8 9 4 643 1234 43 909
出力例 3
43 643 909 1234
- 私達の普段使用する数と同じ大小関係に昇順に並べます。
入力例 4
0 7 4 3 9 5 6 2 1 8 2 333 333
出力例 4
333 333
入力例 5
0 2 4 6 8 1 3 5 7 9 1 10
出力例 5
10
Source Name
ARC 009Time 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連休が最長です。
Source Name
ARC 010Time Limit: 2 sec / Memory Limit: 64 MB
問題文
しかし、1 から N までの正整数を合計するときに、ある正整数 M(M は N 以下の正整数)だけ足し忘れてしまい、間違った平均値を算出してしまいました。
さらに、太郎君は正整数 N の値も忘れてしまいました。
今、間違った平均値だけがわかっています。元の数 N と M の組み合わせとして考えられるものを全て答えてください。
入力
X/Y
- 入力は 1 行のみからなり、間違った平均値が分数の形で与えられる。
- 分数は整数 X(1≦X≦10^{18})、
/
、整数 Y(1≦Y≦10^9) の順で与えられ、間違った平均値が X/Y であることを表す(0 < X/Y≦10^9)。 - ただし、入力は既約分数とは限らない。
出力
ただし、考えられる答えが複数ある場合は 1 行に N と M を 1 組ずつ出力し、考えられる答えが無い場合は
Impossible
と答えること。なお、最後には改行を出力せよ。
入力例 1
4/3
出力例 1
3 2
- N=3、M=2 の時、間違った平均値は (1+3)/3 = 4/3 となり、入力を満たします。
- したがって、この組み合わせが答えとなります。
入力例 2
4/6
出力例 2
Impossible
- 入力値を満たすような解は存在しません。
入力例 3
49995/10
出力例 3
10000 10000
- N=10,000、M=10,000 の時、間違った平均値は (1+2+...+9999)/10000 = 4995000/10000 = 49995/10 となり、入力を満たします。
入力例 4
1/400
出力例 4
Impossible
Source Name
ARC 004Time Limit: 2 sec / Memory Limit: 64 MB
問題文
たこ焼き屋の開店にあたって、たこ焼きの味を皆に分かってもらうために試食イベントを行うことにしました。
しかし、高橋社長はたこ焼きをより多くの人に食べてもらいたいので、試食イベントを兼ねたお祭り『THE☆たこ焼き祭り2012』をすることを提案してきました。高橋社長が提案してきた『THE☆たこ焼き祭り2012』の試食イベント内容は以下のようになっています。
会場にはあなたと参加者を足して N 人の人がいます。あなたはたこ焼きを N 個持っており、それを全員に 1 人 1 個ずつ行き渡るようにします。
会場は広いのであなたはたこ焼きを投げて配らないといけません。
あなただけで全員に配ることは大変なので、参加者にも協力してもらうことにし、参加者は受け取ったたこ焼きを別の参加者へと投げることもできます。
あなたと参加者はつまようじを1 人につき 1 本しか持っていないので同じタイミングで複数のたこ焼きを投げることはできず、たこ焼きを投げてから 1 秒間は次のたこ焼きを投げることができません。受け取る側はいつでも何個でも受け取ることができます。
さらに、あなたと参加者は立っている位置から動いてはいけません。
参加者は大人から子供までいるのでそれぞれにはたこ焼きをキャッチできる速度の上限があり、たこ焼きを投げる側にも投げられる速度の上限があります。投げられたたこ焼きの速度は減衰することなく受け取り手に届きます。
たこ焼きはなるべく出来立てを食べて欲しいので、たこ焼きを全員に配り切るために必要な時間の最小値を答えなさい。
入力
N x_{0} y_{0} t_{0} r_{0} x_{1} y_{1} t_{1} r_{1} : : x_{N-1} y_{N-1} t_{N-1} r_{N-1}
- 入力は N+1 行ある。
- 1 行目には、たこ焼き祭りの参加者数とあなたを足した数を表す整数 N\ (1≦N≦1,000) が与えられる。
- 2 行目には、あなたが立っている位置の x 座標を表す整数 x_0\ (-10,000≦x_0≦10,000)、y 座標を表す整数 y_0\ (-10,000≦y_0≦10,000)、たこ焼きを投げる速度の上限を表す整数 t_0\ (3≦t_0≦340) とたこ焼きを受け取る速度の上限を表す整数 r_0\ (3≦r_0≦340) が空白で区切られて与えられる。
- 3 行目から N-1 行のうち i+2\ (1≦i≦N-1) 行目には i 番目の参加者が立っている位置の x 座標を表す整数 x_i\ (-10,000≦x_i≦10,000)、y 座標を表す整数 y_i\ (-10,000≦y_i≦10,000)、たこ焼きを投げる速度の上限を表す整数 t_i\ (3≦t_i≦340) とたこ焼きを受け取る速度の上限を表す整数 r_i\ (3≦r_i≦340) が空白で区切られて与えられる。
- 与えられる速度は 1 秒辺りの速度である。
- 複数の人が同じ位置に立つことはない。
出力
出力は整数および小数のみとし、誤差は絶対誤差あるいは相対誤差の少なくとも片方が 10^{−6} 以下であれば許容する。
なお、最後には改行を出力せよ。
入力例 1
4 0 0 300 10 0 100 10 100 0 200 10 200 0 300 10 300
出力例 1
3
- 0 秒目 :
- あなた : 1 番目の参加者に速度 100 でたこ焼きを投げる。
- 1 秒目 :
- あなた : 2 番目の参加者に速度 200 でたこ焼きを投げる。
- 1 番目の参加者 : あなたが 0 秒目に投げたたこ焼きをキャッチする。
- 2 秒目 :
- あなた : 3 番目の参加者に速度 300 でたこ焼きを投げる。
- 2 番目の参加者 : あなたが 1 秒目に投げたたこ焼きをキャッチする。
- 3 秒目 :
- 3 番目の参加者 : あなたが 2 秒目に投げたたこ焼きをキャッチする。
入力例 2
4 0 0 100 10 0 90 10 10 0 100 30 100 -20 100 10 10
出力例 2
3
- 0 秒目 :
- あなた : 2 番目の参加者に速度 100 でたこ焼きを投げる。
- 1 秒目 :
- あなた : 2 番目の参加者に速度 100 でたこ焼きを投げる。
- 2 番目の参加者 : あなたが 0 秒目に投げたたこ焼きをキャッチし、3 番目の参加者に速度 10 で投げる。
- 2 秒目 :
- あなた : 2 番目の参加者に速度 100 でたこ焼きを投げる。
- 2 番目の参加者 : あなたが 1 秒目に投げたたこ焼きをキャッチし、2 番目の参加者に速度 10 で投げる。
- 3 秒目 :
- 1 番目の参加者 : 2 番目の参加者が 2 秒目に投げたたこ焼きをキャッチする。
- 2 番目の参加者 : あなたが 2 秒目に投げたたこ焼きをキャッチする。
- 3 番目の参加者 : 2 番目の参加者が 1 秒目に投げたたこ焼きをキャッチする。
入力例 3
1 0 0 3 3
出力例 3
0
- 参加者があなただけなので配る必要がありません。
入力例 4
4 58 -49 38 109 45 -29 200 56 -32 123 103 98 49 -234 289 43
出力例 4
4.874179
入力例 5
8 100 100 30 50 100 50 93 123 100 0 89 111 50 100 13 18 50 0 155 86 0 100 30 58 0 50 58 49 0 0 98 153
出力例 5
7.666667
Source Name
ARC 008Time Limit: 2 sec / Memory Limit: 64 MB
問題文
まず、図 1 のような縦 7 マス・横 7 マスの 49 マスの白黒で作られた A,B,C の図形が与えられます。
与えられる図の中に、先程の A,B,C の形がそれぞれいくつあるかを答えます。与えられる図に存在する黒マスは全て A,B,C のいずれかの一部であり、A,B,C 以外の図形は存在しません。 しかし、A,B,C は任意の正の整数倍に拡大した形も、同じ形とみなされます。そのため、図 2(a) の 3 つの A は全て A として数えられます。 加えて、図 2(b) のように、形が 90 度きざみで回転しているものも同じ形とみなされます。
なお、A,B,C の図形はまわりにある白マスの部分も含めてそのアルファベットと判断され、図 3 のように A を構成する縦 7 マス・横 7 マスと、別の図形である B を構成する縦 7 マス・横 7 マスが重なるような入力は与えられません。
与えられる図の中から、A,B,C の図形がそれぞれいくつずつあるか答えなさい。
入力
H W c_{(0,0)}c_{(0,1)} ‥‥ c_{(0,W-1)} c_{(1,0)}c_{(1,1)} ‥‥ c_{(1,W-1)} : : c_{(H-1,0)}c_{(H-1,1)} ‥‥ c_{(H-1,W-1)}
- 入力は H+1 行ある。
- 1 行目には、与えられる図の縦の長さを表す整数 H(1≦H≦1,000) と横の長さを表す整数 W(1≦W≦1,000) が空白を区切りとして与えられる。
- 2 行目からの H 行には、図の形を表す状態 c_{(i,j)}(0≦i≦H-1, 0≦j≦W-1) が与えられる。
- i-2 行目 j-1 番目の文字 c_{(i,j)} はそれぞれ
.
またはo
で与えられ、縦 i+1番目、横 j+1 番目のマスの状態が以下であることを表す。.
:そのマスが白色であることを表す。o
:そのマスが黒色であることを表す。
- 図には A,B,C 以外の図形は出てこない。
- A,B,C の図形は重ならない。
- i-2 行目 j-1 番目の文字 c_{(i,j)} はそれぞれ
出力
ただし、任意の正整数に等倍拡大した形や 90 度きざみで回転した形も含まれる。
なお、最後には改行を出力せよ。
入力例 1
7 7 ....... ...o... ..o.o.. .o...o. .ooooo. .o...o. .......
出力例 1
1 0 0
- A が 1 つあり、B と C はありません。
入力例 2
7 14 .............. .oooo....oooo. .o...o..o...o. .oooo....oooo. .o...o..o...o. .oooo....oooo. ..............
出力例 2
0 2 0
- 通常の向きの B が 1 つと、180 度回転している B が 1 つあるので、B が 2 つという答えになります。
入力例 3
14 42 .......................................... .................o...o........o.o......... ....oooooo.......ooooo.......o.o.o........ ....oooooo.......o...o.......o.o.o........ ..oo......oo......o.o........o.o.o........ ..oo......oo.......o.........ooooo........ ..oo...................................... ..oo...................................... ..oo......oo............ooo............... ..oo......oo...........o...o.............. ....oooooo.............o...o.............. ....oooooo.............o...o.............. ........................o.o............... ..........................................
出力例 3
1 1 2
- 180 度回転した A、反時計回りに 90 度回転した B、時計回りに 90 度回転した C、2 倍に拡大した C が存在する。
入力例 4
6 8 ........ ........ ........ ........ ........ ........
出力例 4
0 0 0
- A,B,C が 1 つも存在しません。
入力例 5
40 40 ........................................ ..ooo.....o.................ooo......... .o...o...o.o....oooo.......o.o....o.o... .o......o...o..o...o......o..o...o...o.. .o...o..ooooo...oooo.......o.o...o...o.. ..ooo...o...o..o...o........ooo..o...o.. ................oooo..............ooo... ........................................ ...........................o.o.......... ..........................o.o.o......... .........ooo..............o.o.o......... ........o...o.............o.o.o......... ..ooo...o...o..ooooo......ooooo......... .o...o..o...o..o.o.o.................... .....o...o.o...o.o.o..............o.o... .o...o.........o.o.o.............o.o.o.. ..ooo...........o.o..............o.o.o.. .................................o.o.o.. .................................ooooo.. ...........................oooo......... ..........................o...o......... ...........................oooo......... .................ooo......o...o......... ................o...o......oooo......... ..oooooo........o....................... ..oooooo........o...o................... ....oo..oo.......ooo...............oooo. ....oo..oo........................o...o. ....oo....oo.......................oooo. ....oo....oo......................o...o. ....oo..oo.........................oooo. ....oo..oo.............................. ..oooooo................................ ..oooooo................ooo............. .................ooo.....o.o......o.o... ................o...o....o..o....o.o.o.. ................o........o.o.....o.o.o.. ................o...o...ooo......o.o.o.. .................ooo.............ooooo.. ........................................
出力例 5
4 7 6