A - DDCC型文字列

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 100 点

問題文

長さ 4 の文字列がDDCC型文字列であるのは、文字列の 1 文字目と 2 文字目が等しく、 2 文字目と 3 文字目が異なり、 3 文字目と 4 文字目が等しいときです。

4 文字の文字列 S が与えられるので、DDCC型文字列ならば Yes 、そうでなければ No を出力してください。

制約

  • |S|＝4
  • 入力は英大文字からなる

入力

入力は以下の形式で標準入力から与えられる。

S

出力

S がDDCC型文字列ならば Yes 、そうでなければ No を出力せよ。

入力例 1

DDCC

出力例 1

Yes

S の 1 文字目と 2 文字目は等しく、 2 文字目と 3 文字目は異なり、 3 文字目と 4 文字目は等しいので、 S はDDCC型文字列です。

入力例 2

AAAA

出力例 2

No

S の 2 文字目と 3 文字目が等しいため、 S はDDCC型文字列ではありません。

入力例 3

ABCD

出力例 3

No
B - 鉛筆

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 200 点

問題文

鉛筆 1 ダースは 12 本、 1 グロスは 144 本、 1 グレートグロスは 1728 本です。

A グレートグロスの鉛筆と、 B グロスの鉛筆と、 C ダースの鉛筆と、 D 本の鉛筆があるとき、合計で鉛筆は何本あるか答えてください。

制約

  • 0≦A,B,C,D≦11
  • 入力は整数からなる

入力

入力は以下の形式で標準入力から与えられる。

A B C D

出力

合計で鉛筆が x 本あるとき、 x を出力せよ。

入力例 1

1 2 4 0

出力例 1

2064

1 グレートグロスは 1728 本であり、2 グロスは 288本、 4 ダースは 48 本なので、合計で 2064 本の鉛筆があります。

入力例 2

0 0 0 0

出力例 2

0

鉛筆が一本もないこともあります。

入力例 3

8 11 5 4

出力例 3

15472
C - 収納

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 300 点

問題文

N 本の棒があり、 i(1≦i≦N) 本目の棒の長さは L_i です。

これらを長さ C のケースに収納していきます。

ケースには 1 本か 2 本の棒を収納できますが、棒を収納できる条件は

  • 1 本の棒を収納するには、棒の長さが a のとき、 a≦C
  • 2 本の棒を収納するには、棒の長さが a,b のとき、 a+b+1≦C

です。

全ての棒を収納するのに、ケースは最小でいくつ必要か答えてください。

制約

  • 1≦N≦100000
  • 1≦C≦10^9
  • 1≦L_i≦C
  • 入力は整数からなる

入力

入力は以下の形式で標準入力から与えられる。

N C
L_1
:
L_N

出力

ケースが最小で x 個必要な時、 x を出力せよ。

入力例 1

4 10
2
8
4
5

出力例 1

3

3 番目の棒と 4 番目の棒を同じケースに収納し、 1 番目の棒と 2 番目の棒をそれぞれ別のケースに収納すると、 3 個のケースに収納することができます。

入力例 2

3 10
1
1
1

出力例 2

2

1 つのケースには 2 本までの棒しか収納できないことに注意して下さい。

入力例 3

9 30
22
5
2
18
6
21
29
11
18

出力例 3

5
D - 石

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 600 点

問題文

南北方向に H 、東西方向に W のグリッド状の庭があり、北から i(1≦i≦H) 番目、西から j(1≦j≦W) 番目のマスを (i,j) とします。

ただし、 H と W は偶数とします。

各マスには石が高々 1 つ置かれており、また、 1 つ以上のマスに石が置かれています。

なお、最初の庭の状態は、文字列 m_{i,j} を用いて、 (i,j) に石があるなら m_{i,j} = S、石がないなら m_{i,j} = . として与えられます。

これらの石を 1 つずつ取り除いていきます。

石を取り除いた直後に、庭の石の配置が南北方向に対称なら A の幸福度、東西方向に対称なら B の幸福度が得られます。

ただし、南北方向にも東西方向にも対称のときは A+B の幸福度が得られることとします。

全ての石を自由な順番で取り除くとき、得られる最大の幸福度を求めてください。

なお、南北方向に対称とは、以下のことが成り立つ場合です。

  • すべての i,j(1≦i≦H,1≦j≦W) において (i,j) に石があるなら (H+1-i,j) にも石があり、 (i,j) に石がなければ (H+1-i,j) に石がない。

また、東西方向に対称とは、以下のことが成り立つ場合です。

  • すべての i,j(1≦i≦H,1≦j≦W) において (i,j) に石があるなら (i,W+1-j) にも石があり、 (i,j) に石がなければ (i,W+1-j) に石がない。

制約

  • 2≦H,W≦200
  • H,W は偶数
  • 1≦A,B≦10000
  • m_{i,j} は S か .
  • 石が置かれているマスは 1 つ以上存在する
  • H,W,A,B は整数で与えられる

入力

入力は以下の形式で標準入力から与えられる。

H W
A B
m_{1,1}...m_{1,W}
:
m_{H,1}...m_{H,W}

出力

得られる最大の幸福度が x のとき、 x を出力せよ。

入力例 1

4 4
2 5
....
.SS.
..S.
....

出力例 1

12

たとえば、 (3,3),(2,2),(2,3) の順に石を取り除くと、(3,3) の石を取り除いた時に東西方向に対称になり、 (2,3) の石を取り除いたときに東西方向と南北方向に対称になり、得られる幸福度は 12 となる。

入力例 2

2 2
4 7
.S
S.

出力例 2

11

石をどの順番で取り除いても、最後の石を取り除いたとき以外に幸福度を得られない。

入力例 3

4 8
9 13
.SS.....
.SS.....
.SS.....
.SS.....

出力例 3

49