A - 宝くじ
高橋君は夏の宝くじをこっそり買っていました。今日はその宝くじの当選発表日です。購入者は、0 から 9 までの 10 個の数字から重複せずに 6 つの数字を選び購入します。発表日には 6 つの本数字と 1 つのボーナス数字が発表され、購入した宝くじとその数字がいくつ一致しているかで以下のように当選の等級が決まります。
高橋君が購入した宝くじの等級を求めなさい。 なお、与えられる当選番号とボーナス数字の 7 つの数字は互いに異なります。
入力は以下の形式で標準入力から与えられる。
高橋君が購入した宝くじの等級数 (1 等の場合は
また、はずれの場合は
なお、最後には改行を出力せよ。
Time Limit: 2 sec / Memory Limit: 64 MB
問題文
- 1 等 : 6 つ数字が一致
- 2 等 : 5 つ数字が一致し、残りの 1 つの数字がボーナス数字と一致
- 3 等 : 5 つ数字が一致
- 4 等 : 4 つ数字が一致
- 5 等 : 3 つ数字が一致
高橋君が購入した宝くじの等級を求めなさい。 なお、与えられる当選番号とボーナス数字の 7 つの数字は互いに異なります。
入力
E_0E_1E_2E_3E_4E_5 B L_0L_1L_2L_3L_4L_5
- 入力は 3 行ある。
- 1 行目には、当選番号を表す 6 つの整数 E_i(0≦i≦5, 0≦E_i≦9) が与えられる。
- E_i は昇順に並んでいる。
- 2 行目には、ボーナス数字を表す整数 B(0≦B≦9) が与えられる。
- 3 行目には、高橋君が購入した宝くじの 6 つの数字を表す整数 L_j(0≦j≦5, 0≦L_j≦9) が与えられる。
- L_i は昇順に並んでいる。
- L_i の 6 つの数字は互いに異なります。
- E_i と B を合わせた 7 つの数字は互いに異なります。
出力
1、2 等の場合は 2、のように) を標準出力に 1 行で出力せよ。また、はずれの場合は
0 を出力せよ。なお、最後には改行を出力せよ。
入力例 1
1 2 3 4 5 6 7 1 2 3 4 5 6
出力例 1
1
- 6 つの数字全てが当選番号と購入宝くじとで一致しているので、1 等にになります。
入力例 2
0 1 3 5 7 9 4 0 2 4 6 8 9
出力例 2
0
- 一致している数字が 0 と 9 の 2 つのみなので、当選の条件を満たさず、はずれです。
入力例 3
0 2 6 7 8 9 4 0 5 6 7 8 9
出力例 3
3
- 0, 6, 7, 8, 9 の 5 つが一致していますが、ボーナス数字の 4 は購入した宝くじの数字の中にないので 3 等になります。
入力例 4
1 3 5 6 7 8 9 3 5 6 7 8 9
出力例 4
2
- 3, 5, 6, 7, 8 の 5 つが一致しており、ボーナス数字の 9 も購入した宝くじの数字の中にあるので 2 等になります。
入力例 5
0 1 3 4 5 7 8 2 3 5 7 8 9
出力例 5
5
- 3, 5, 7 の 3 つの数字が一致しているので 5 等になります。
Source Name
ARC 006
B - あみだくじ
高橋君は学校で班のリーダーを決めなければいけなくなったので、あみだくじを用いて決めることにしました。
あみだくじとは、複数の縦線から 1 本を選び、その上端から下端へと辿っていき、途中で横線があれば、その横線を通り繋がっている隣接する縦線へと移動し、また下へと進みます。
今日はたまたま手元に紙がなかったので、パソコン上で
実は高橋君はリーダーになりたかったので、どの縦線を選べば
左から何番目の縦線を選べばリーダーになれるのかを求めなさい。
入力は以下の形式で標準入力から与えられる。
あみだくじを辿って
なお、最後には改行を出力せよ。
Time Limit: 2 sec / Memory Limit: 64 MB
問題文
あみだくじとは、複数の縦線から 1 本を選び、その上端から下端へと辿っていき、途中で横線があれば、その横線を通り繋がっている隣接する縦線へと移動し、また下へと進みます。
今日はたまたま手元に紙がなかったので、パソコン上で
|、-、o を用いて以下のようなあみだくじを作りました。
| | | | | | | | |
|-| | |-| | |-| |
| | |-| | |-| | |
| |-| | | | | |-|
| | | |-| | | |-|
| | |-| |-| | | |
|-| | |-| | |-| |
| | | | | |-| | |
o
o がある位置に到達した人がリーダーになります。実は高橋君はリーダーになりたかったので、どの縦線を選べば
o に辿り着くのか知りたいです。左から何番目の縦線を選べばリーダーになれるのかを求めなさい。
入力
N L |x|x|‥‥| |x|x|‥‥| |x|x|‥‥| : : : : : : : : | | |‥‥| y y y‥‥y
- 入力は L+2 行ある。
- 1 行目には、あみだくじの縦線の本数を表す整数 N(1≦N≦10) とあみたくじの長さを表す整数 L(1≦L≦20)が与えられる。
- 2 行目からの L 行には、あみたくじの形が与えられる。
- i 行目 (2≦i≦L+1) には 2N-1 文字の記号が与えられる。
- 各行の j 番目の記号は、以下のようになっている。
- j が奇数の時：
| - j が偶数の時(上記のxの位置)：
-または
- j が奇数の時：
|はあみだくじの縦線を表し、-はその両端の縦線を繋ぐ横線であることを表す。また、空白はその位置に横線が無いことを表す。|を 1 つ挟んで左右に隣り合ったxの位置の両方が-という入力は存在しない。- L+2 行目には 2N-1 文字の記号が与えられる。
- 各行の j 番目の記号は、以下のようになっている。
- j が奇数の時(上記のyの位置)：
oまたは - j が偶数の時：
- j が奇数の時(上記のyの位置)：
oは L+2 行目にただ 1 つのみ与えられる。
出力
o に到達するために選ぶべき縦線は左から何番目か 1 行で出力せよ。なお、最後には改行を出力せよ。
入力例 1
3 2 | |-| |-| | o
出力例 1
3
- 一番右の縦線を選ぶと、再左端に到達する。つまり、左から 3 番目を選択すると、
oのある位置に到達できる。
入力例 2
10 2
| |-| |-| |-| |-| |
|-| |-| |-| |-| |-|
o
出力例 2
9
- 左から 9 番目の縦線から辿ると、
oの位置に到達できる。 - したがって、答えは 9 になる。
入力例 3
1 5 | | | | | o
出力例 3
1
- 縦線が 1 本なので、左から 1 番目の縦線が答えとなる。
入力例 4
4 2
| | | |
| | | |
o
出力例 4
4
- 横線が 1 本も存在しないので、
oのある縦線を選べば良い。 - したがって左から 4 番目の縦線が答えとなる。
入力例 5
9 8
| | | | | | | | |
|-| | |-| | |-| |
| | |-| | |-| | |
| |-| | | | | |-|
| | | |-| | | |-|
| | |-| |-| | | |
|-| | |-| | |-| |
| | | | | |-| | |
o
出力例 5
3
Source Name
ARC 006
C - 積み重ね
高橋君はもう大人なので、親元を離れて一人暮らしをすることにしました。トラックから引越し先の部屋へと荷物のダンボールを運びたいのですが、部屋の床がダンボールで埋まってしまうと、今日高橋君が寝るための布団がひけません。
そこで、1 箱ずつ広げて置くのではなく、ある程度ダンボールを積み重ねた山を作ることにしました。しかし、ダンボールには重さが決まっており、下にあるダンボールよりも重いダンボールを上に積み重ねると下のダンボールが潰れてしまいます。
トラックから運ぶ順にダンボールの重さが与えられるので、ダンボールを潰さないような積み重ね方を考えなさい。そして、その積み重ねた山の個数が最小となる場合の山の個数を求めなさい。
入力は以下の形式で標準入力から与えられる。
ダンボールを順番に運び、上のダンボールが下のダンボールと同じ重さまたはそれよりも軽くなるように積み重ねたときに、できるダンボールの山の数の最小値を標準出力に 1 行で出力せよ。
なお、最後には改行を出力せよ。
Time Limit: 2 sec / Memory Limit: 64 MB
問題文
そこで、1 箱ずつ広げて置くのではなく、ある程度ダンボールを積み重ねた山を作ることにしました。しかし、ダンボールには重さが決まっており、下にあるダンボールよりも重いダンボールを上に積み重ねると下のダンボールが潰れてしまいます。
図：下にあるダンボールは上にあるダンボール以上の重さでなければならない
トラックから運ぶ順にダンボールの重さが与えられるので、ダンボールを潰さないような積み重ね方を考えなさい。そして、その積み重ねた山の個数が最小となる場合の山の個数を求めなさい。
入力
N w_1 w_2 : : w_N
- 入力は N+1 行ある。
- 1 行目には、ダンボールの個数を表す整数 N(1≦N≦50) が与えられる。
- 2 行目からの N 行には、i+1(1≦i≦N) 行目に i 番目に運ぶダンボールの重さを表す整数 w_i(1≦w_i≦100,000) が与えられる。
出力
なお、最後には改行を出力せよ。
入力例 1
5 4 3 1 2 1
出力例 1
2
- 下図の例の順に積み重ねると、2 つのダンボールの山ができる。
- 3 番目のダンボールの次に重さ 2 のダンボールをその上に重ねることはできないので 1 つの山にすることはできず、最小は 2 となる。
入力例 2
7 93 249 150 958 442 391 25
出力例 2
3
- 下図の形に積み重ねると、山の数は 3 となる。
訂正：下図の225のダンボールは25の誤りです。申し訳ありません。
入力例 3
4 100 100 100 100
出力例 3
1
- 同じ重さのダンボールは積み重ねられるので、1 つの山にすることができる。
入力例 4
6 5 10 15 20 25 30
出力例 4
6
- どのダンボールも前に運んだダンボールの上に重ねられないので、1 つも積み重ねることができない。
- したがって、6 つの山が最小となる。
入力例 5
15 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9
出力例 5
6
- 下図のように積み重ねると最小となる。
Source Name
ARC 006
D - アルファベット探し
高橋君は友人にこのようなパズルを出題されました。
まず、図 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 の図形がそれぞれいくつずつあるか答えなさい。
入力は以下の形式で標準入力から与えられる。
与えられた図の中に存在する A の個数、B の個数、C の個数を、A,B,C の順に空白を区切りとして標準出力に 1 行で出力せよ。
ただし、任意の正整数に等倍拡大した形や 90 度きざみで回転した形も含まれる。
なお、最後には改行を出力せよ。
Time Limit: 2 sec / Memory Limit: 64 MB
訂正：任意の整数に拡大した形も同じ形である→任意の正の整数に拡大した形も同じ形である に訂正させて頂きました。
問題文
まず、図 1 のような縦 7 マス・横 7 マスの 49 マスの白黒で作られた A,B,C の図形が与えられます。
図 1：与えられる A,B,C の形
図 2(a)：2 倍、3 倍に拡大された A の例 図 2(b)：回転した A の例
図 3：入力として与えられない他の図形が重なっている例
入力
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