A - Leftrightarrow

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

<, =, > のみからなる文字列 S が与えられます。
S が 双方向矢印型 の文字列であるか判定してください。
ただし、文字列 S が双方向矢印型の文字列であるとは、 ある正整数 k が存在して、
S が 1 個の < 、k 個の = 、1 個の > をこの順に連結した長さ (k+2) の文字列であることをいいます。

制約

  • S は <, =, > のみからなる長さ 3 以上 100 以下の文字列

入力

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

S

出力

S が 双方向矢印型 の文字列ならば Yes を、そうでないならば No を出力せよ。


入力例 1

<====>

出力例 1

Yes

<====> は、1 個の < 、4 個の = 、1 個の > をこの順に連結した文字列であり、双方向矢印型の文字列です。
よって、Yes を出力します。


入力例 2

==>

出力例 2

No

==> は双方向矢印型の文字列の条件をみたしていません。 よって、No を出力します。


入力例 3

<>>

出力例 3

No

Scoring: 100 points

Problem Statement

You are given a string S consisting of <, =, and >.
Determine whether S is a bidirectional arrow string.
A string S is a bidirectional arrow string if and only if there is a positive integer k such that S is a concatenation of one <, k =s, and one >, in this order, with a length of (k+2).

Constraints

  • S is a string of length between 3 and 100, inclusive, consisting of <, =, and >.

Input

The input is given from Standard Input in the following format:

S

Output

If S is a bidirectional arrow string, print Yes; otherwise, print No.


Sample Input 1

<====>

Sample Output 1

Yes

<====> is a concatenation of one <, four =s, and one >, in this order, so it is a bidirectional arrow string.
Hence, print Yes.


Sample Input 2

==>

Sample Output 2

No

==> does not meet the condition for a bidirectional arrow string.
Hence, print No.


Sample Input 3

<>>

Sample Output 3

No
B - 2^N

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

N が与えられます。2^N を出力してください。

制約

  • 0 \leq N \leq 30
  • N は整数である

入力

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

N

出力

答えを出力せよ。


入力例 1

3

出力例 1

8

2^3=8 です。


入力例 2

30

出力例 2

1073741824

Score : 100 points

Problem Statement

Given N, print 2^N.

Constraints

  • 0 \leq N \leq 30
  • N is an integer.

Input

Input is given from Standard Input in the following format:

N

Output

Print the answer.


Sample Input 1

3

Sample Output 1

8

We have 2^3=8.


Sample Input 2

30

Sample Output 2

1073741824
C - Default Price

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

高橋くんは回転寿司で N 皿の料理を食べました。 i 皿目の色は文字列 C_i で表されます。

また、料理の価格は皿の色と対応し、 i=1,\ldots,M のそれぞれについて、色が文字列 D_i の皿の料理は一皿 P_i 円です。また、D_1,\ldots,D_M のいずれとも異なる色の皿の料理は一皿 P_0 円です。

高橋くんが食べた料理の価格の合計を求めてください。

制約

  • 1\leq N,M\leq 100
  • C_i,D_i は英小文字からなる長さ 1 以上 20 以下の文字列
  • D_1,\ldots,D_M はすべて異なる
  • 1\leq P_i\leq 10000
  • N,M,P_i は整数

入力

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

N M
C_1 \ldots C_N
D_1 \ldots D_M
P_0 P_1 \ldots P_M

出力

答えを整数として出力せよ。


入力例 1

3 2
red green blue
blue red
800 1600 2800

出力例 1

5200

blue の皿は P_1 = 1600 円、red の皿は P_2 = 2800 円、green の皿は P_0 = 800 円です。

高橋くんが食べた料理の価格の合計は、2800+800+1600=5200 円です。


入力例 2

3 2
code queen atcoder
king queen
10 1 1

出力例 2

21

Score : 200 points

Problem Statement

Takahashi ate N plates of sushi at a sushi restaurant. The color of the i-th plate is represented by a string C_i.

The price of a sushi corresponds to the color of the plate. For each i=1,\ldots,M, the sushi on a plate whose color is represented by a string D_i is worth P_i yen a plate (yen is the currency of Japan). If the color does not coincide with any of D_1,\ldots, and D_M, it is worth P_0 yen a plate.

Find the total amount of the prices of sushi that Takahashi ate.

Constraints

  • 1\leq N,M\leq 100
  • C_i and D_i are strings of length between 1 and 20, inclusive, consisting of lowercase English letters.
  • D_1,\ldots, and D_M are distinct.
  • 1\leq P_i\leq 10000
  • N, M, and P_i are integers.

Input

The input is given from Standard Input in the following format:

N M
C_1 \ldots C_N
D_1 \ldots D_M
P_0 P_1 \ldots P_M

Output

Print the answer as an integer.


Sample Input 1

3 2
red green blue
blue red
800 1600 2800

Sample Output 1

5200

A blue plate, red plate, and green plate are worth P_1 = 1600, P_2 = 2800, and P_0 = 800 yen, respectively.

The total amount of the prices of the sushi that he ate is 2800+800+1600=5200 yen.


Sample Input 2

3 2
code queen atcoder
king queen
10 1 1

Sample Output 2

21
D - Let's Get a Perfect Score

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

1 から N までの番号がついた N 人の参加者が、1 から M までの番号がついた M 問からなるコンテストに参加します。

1 以上 N 以下の整数 i 、1 以上 M 以下の整数 j について、S_i の j 番目の文字が o のとき参加者 i は問題 j を解くことが可能で、S_i の j 番目の文字が x のとき参加者 i は問題 j を解くことが不可能です。

このコンテストは、二人の参加者でペアを組んで参加します。二人が協力することで M 問全てを解くことが可能であるようなペアの個数を答えてください。

より厳密には、1\leq x < y\leq N を満たす整数の組 (x,y) であって、 1 以上 M 以下の任意の整数 j について、参加者 x か参加者 y の少なくとも一方は問題 j を解くことが可能であるという条件を満たすものの個数を答えてください。

制約

  • N は 2 以上 30 以下の整数
  • M は 1 以上 30 以下の整数
  • S_i は o, x からなる長さ M の文字列

入力

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

N M
S_1
S_2
\vdots
S_N

出力

答えを出力せよ。


入力例 1

5 5
ooooo
oooxx
xxooo
oxoxo
xxxxx

出力例 1

5

参加者 1 と 2 のペア、参加者 1 と 3 のペア、参加者 1 と 4 のペア、参加者 1 と 5 のペア、参加者 2 と 3 のペアの 5 個のペアが条件を満たします。

例えば参加者 2 と 4 のペアは、問題 4 が解けないので条件を満たしません。


入力例 2

3 2
ox
xo
xx

出力例 2

1

入力例 3

2 4
xxxx
oxox

出力例 3

0

Score : 200 points

Problem Statement

N participants, numbered 1 to N, will participate in a contest with M problems, numbered 1 to M.

For an integer i between 1 and N and an integer j between 1 and M, participant i can solve problem j if the j-th character of S_i is o, and cannot solve it if that character is x.

The participants must be in pairs. Print the number of ways to form a pair of participants who can collectively solve all the M problems.

More formally, print the number of pairs (x,y) of integers satisfying 1\leq x < y\leq N such that for any integer j between 1 and M, at least one of participant x and participant y can solve problem j.

Constraints

  • N is an integer between 2 and 30, inclusive.
  • M is an integer between 1 and 30, inclusive.
  • S_i is a string of length M consisting of o and x.

Input

The input is given from Standard Input in the following format:

N M
S_1
S_2
\vdots
S_N

Output

Print the answer.


Sample Input 1

5 5
ooooo
oooxx
xxooo
oxoxo
xxxxx

Sample Output 1

5

The following five pairs satisfy the condition: participants 1 and 2, participants 1 and 3, participants 1 and 4, participants 1 and 5, and participants 2 and 3.

On the other hand, the pair of participants 2 and 4, for instance, does not satisfy the condition because they cannot solve problem 4.


Sample Input 2

3 2
ox
xo
xx

Sample Output 2

1

Sample Input 3

2 4
xxxx
oxox

Sample Output 3

0
E - PC on the Table

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

高橋君は部屋に PC を沢山置こうとしています。そこで最大何台の PC を部屋に置けるか調べるプログラムを書くことにしました。

H 個の長さ W の ., T からなる文字列 S_1,S_2,\ldots,S_H が与えられます。

高橋君は以下の操作を 0 回以上何回でも行うことができます。

  • 1\leq i \leq H, 1 \leq j \leq W-1 を満たす整数であって、 S_i の j 番目の文字も j+1 番目の文字も T であるようなものを選ぶ。 S_i の j 番目の文字を P で置き換え、S_i の j+1 番目の文字を C で置き換える。

高橋君が操作回数の最大化を目指すとき、操作終了後の S_1,S_2,\ldots,S_H としてあり得るものの一例を出力してください。

制約

  • 1\leq H \leq 100
  • 2\leq W \leq 100
  • H と W は整数である
  • S_i は ., T からなる長さ W の文字列

入力

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

H W 
S_1
S_2
\vdots
S_H

出力

高橋君が操作回数の最大化を目指すとき、操作終了後の S_1,S_2,\ldots,S_H としてあり得るものの一例を改行区切りで出力せよ。

解が複数存在する場合、どれを出力しても正答とみなされる。


入力例 1

2 3
TTT
T.T

出力例 1

PCT
T.T

可能な操作回数の最大値は 1 です。

例えば、 (i,j)=(1,1) として操作を行うと、S_1 が PCT に変化します。


入力例 2

3 5
TTT..
.TTT.
TTTTT

出力例 2

PCT..
.PCT.
PCTPC

Score : 300 points

Problem Statement

Planning to place many PCs in his room, Takahashi has decided to write a code that finds how many PCs he can place in his room.

You are given H strings S_1,S_2,\ldots,S_H, each of length W, consisting of . and T.

Takahashi may perform the following operation any number of times (possibly zero):

  • Choose integers satisfying 1\leq i \leq H and 1 \leq j \leq W-1 such that the j-th and (j+1)-th characters of S_i are both T. Replace the j-th character of S_i with P, and (j+1)-th with C.

He tries to maximize the number of times he performs the operation. Find possible resulting S_1,S_2,\ldots,S_H.

Constraints

  • 1\leq H \leq 100
  • 2\leq W \leq 100
  • H and W are integers.
  • S_i is a string of length W consisting of . and T.

Input

The input is given from Standard Input in the following format:

H W 
S_1
S_2
\vdots
S_H

Output

Print a sequence of strings, S_1,S_2,\ldots,S_H, separated by newlines, possibly resulting from maximizing the number of times he performs the operation.

If multiple solutions exist, print any of them.


Sample Input 1

2 3
TTT
T.T

Sample Output 1

PCT
T.T

He can perform the operation at most once.

For example, an operation with (i,j)=(1,1) makes S_1 PCT.


Sample Input 2

3 5
TTT..
.TTT.
TTTTT

Sample Output 2

PCT..
.PCT.
PCTPC