A - Weak Beats

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 100 点

問題文

0 と 1 からなる長さ 16 の文字列 S が与えられます。

2 以上 16 以下のすべての偶数 i について S の i 文字目が 0 ならば Yes を、 そうでないならば No を出力してください。

制約

  • S は 0 と 1 からなる長さ 16 の文字列

入力

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

S

出力

2 以上 16 以下のすべての偶数 i について S の i 文字目が 0 ならば Yes を、 そうでないならば No を出力せよ。

入力例 1

1001000000001010

出力例 1

No

S= 1001000000001010 の 4 文字目が 1 であるため、No を出力します。

入力例 2

1010100000101000

出力例 2

Yes

S= 1010100000101000 の偶数番目の文字はすべて 0 であるため、Yes を出力します。

入力例 3

1111111111111111

出力例 3

No

S の偶数文字目はすべて 1 となっています。 特に「すべて 0 」ではないため、No を出力します。

Score : 100 points

Problem Statement

You are given a string S of length 16 consisting of 0 and 1.

If the i-th character of S is 0 for every even number i from 2 through 16, print Yes; otherwise, print No.

Constraints

  • S is a string of length 16 consisting of 0 and 1.

Input

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

S

Output

If the i-th character of S is 0 for every even number i from 2 through 16, print Yes; otherwise, print No.

Sample Input 1

1001000000001010

Sample Output 1

No

The 4-th character of S= 1001000000001010 is 1, so you should print No.

Sample Input 2

1010100000101000

Sample Output 2

Yes

Every even-positioned character in S= 1010100000101000 is 0, so you should print Yes.

Sample Input 3

1111111111111111

Sample Output 3

No

Every even-positioned character in S is 1. Particularly, they are not all 0, so you should print No.
B - ASCII code

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 100 点

問題文

英小文字 a, b, \ldots, z の ASCII 文字コードはこの順に 97,98,\ldots,122 です。

97 以上 122 以下の整数 N が与えられるので、ASCII 文字コードが N であるような英小文字を出力してください。

制約

  • N は 97 以上 122 以下の整数

入力

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

N

出力

答えを出力せよ。

入力例 1

97

出力例 1

a

ASCII 文字コードが 97 である英小文字は a です。

入力例 2

122

出力例 2

z

Score : 100 points

Problem Statement

The ASCII values of the lowercase English letters a, b, \ldots, z are 97,98,\ldots,122 in this order.

Given an integer N between 97 and 122, print the letter whose ASCII value is N.

Constraints

  • N is an integer between 97 and 122 (inclusive).

Input

Input is given from Standard Input in the following format:

N

Output

Print the answer.

Sample Input 1

97

Sample Output 1

a

97 is the ASCII value of a.

Sample Input 2

122

Sample Output 2

z
C - cat 2

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 200 点

問題文

N 種類の文字列 S _ 1,S _ 2,\ldots,S _ N が与えられます。

あなたは、次の操作を 1 度だけ行います。

  • 相異なる整数 i,j\ (1\le i\le N,1\le j\le N) を選び、S _ i と S _ j をこの順で連結する。

この操作で連結した結果の文字列としてありえるものは何通りあるか求めてください。

選んだ (i,j) が異なっても、連結した文字列が同じ場合は 1 通りと数えることに注意してください。

制約

  • 2\le N\le100
  • N は整数
  • S _ i は英小文字からなる長さ 1 以上 10 以下の文字列
  • S _ i\ne S _ j\ (1\le i\lt j\le N)

入力

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

N
S _ 1
S _ 2
\vdots
S _ N

出力

操作の結果できる文字列が何通りあるかを出力せよ。

入力例 1

4
at
atco
coder
der

出力例 1

11

できる文字列は、atatco, atcoat, atcoder, atcocoder, atder, coderat, coderatco, coderder, derat, deratco, dercoder の 11 通りです。

よって、11 を出力してください。

入力例 2

5
a
aa
aaa
aaaa
aaaaa

出力例 2

7

できる文字列は、aaa, aaaa, aaaaa, aaaaaa, aaaaaaa, aaaaaaaa, aaaaaaaaa の 7 通りです。

よって、7 を出力してください。

入力例 3

10
armiearggc
ukupaunpiy
cogzmjmiob
rtwbvmtruq
qapfzsitbl
vhkihnipny
ybonzypnsn
esxvgoudra
usngxmaqpt
yfseonwhgp

出力例 3

90

Score : 200 points

Problem Statement

You are given N types of strings S_1,S_2,\ldots,S_N.

You perform the following operation once:

  • Choose distinct integers i and j\ (1\le i\le N,1\le j\le N) and concatenate S_i and S_j in this order.

How many different strings can be obtained as a result of this operation?

If different choices of (i,j) result in the same concatenated string, it is counted as one string.

Constraints

  • 2\le N\le100
  • N is an integer.
  • S_i is a string of length between 1 and 10, inclusive, consisting of lowercase English letters.
  • S_i\ne S_j\ (1\le i\lt j\le N)

Input

The input is given from standard input in the following format:

N
S_1
S_2
\vdots
S_N

Output

Print the number of different strings that can be obtained from the operation.

Sample Input 1

4
at
atco
coder
der

Sample Output 1

11

The possible strings are atatco, atcoat, atcoder, atcocoder, atder, coderat, coderatco, coderder, derat, deratco, dercoder, which are 11 strings.

Thus, print 11.

Sample Input 2

5
a
aa
aaa
aaaa
aaaaa

Sample Output 2

7

The possible strings are aaa, aaaa, aaaaa, aaaaaa, aaaaaaa, aaaaaaaa, aaaaaaaaa, which are 7 strings.

Thus, print 7.

Sample Input 3

10
armiearggc
ukupaunpiy
cogzmjmiob
rtwbvmtruq
qapfzsitbl
vhkihnipny
ybonzypnsn
esxvgoudra
usngxmaqpt
yfseonwhgp

Sample Output 3

90
D - Decrease 2 max elements

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 200 点

問題文

長さ N の正整数列 A = (A_1, A_2, \dots ,A_N) が与えられます。高橋くんは、以下の操作を A に含まれる正の要素の個数が 1 つ以下になるまで繰り返します。

  • A を要素の降順に並び替える。それから、 A_1, A_2 を 1 減らす。

高橋くんが操作をする回数を求めてください。

制約

  • 2 \leq N \leq 100
  • 1 \leq A_i \leq 100
  • 入力はすべて整数

入力

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

N
A_1 A_2 \cdots A_N

出力

答えを出力せよ。

入力例 1

4
1 2 3 3

出力例 1

4

操作は以下のように進みます。

  • 1 回目の操作で A = (2, 2, 2, 1) となる。
  • 2 回目の操作で A = (1, 1, 2, 1) となる。
  • 3 回目の操作で A = (1, 0, 1, 1) となる。
  • 4 回目の操作で A = (0, 0, 1, 0) となる。A に含まれる正の要素の個数が 1 つ以下になったので、ここで操作を終了する。

入力例 2

3
1 1 100

出力例 2

2

Score : 200 points

Problem Statement

You are given a sequence of N positive integers A = (A_1, A_2, \dots ,A_N). Takahashi repeats the following operation until A contains one or fewer positive elements:

  • Sort A in descending order. Then, decrease both A_1 and A_2 by 1.

Find the number of times he performs this operation.

Constraints

  • 2 \leq N \leq 100
  • 1 \leq A_i \leq 100
  • All input values are integers.

Input

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

N
A_1 A_2 \cdots A_N

Output

Print the answer.

Sample Input 1

4
1 2 3 3

Sample Output 1

4

The process goes as follows:

  • After the 1st operation, A is (2, 2, 2, 1).
  • After the 2nd operation, A is (1, 1, 2, 1).
  • After the 3rd operation, A is (1, 0, 1, 1).
  • After the 4th operation, A is (0, 0, 1, 0). A no longer contains more than one positive elements, so the process ends here.

Sample Input 2

3
1 1 100

Sample Output 2

2
E - Dango

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

正の整数 L に対して、 レベル L のダンゴ文字列とは、以下の条件を満たす文字列です。

  • o と - からなる長さ L+1 の文字列である。
  • 先頭の文字と末尾の文字のうちちょうど一方が - であり、そのほかの L 文字はすべて o である。

例えば、ooo- はレベル 3 のダンゴ文字列ですが、-ooo- や oo や o-oo- などはダンゴ文字列ではありません（より正確には、どのような正の整数 L に対してもレベル L のダンゴ文字列ではありません）。

2 種類の文字 o - からなる、長さ N の文字列 S が与えられます。 次の条件を満たすような正整数 X のうち、最大のものを求めてください。

  • S の連続する部分文字列であって、レベル X のダンゴ文字列であるものが存在する。

ただし、そのような整数が存在しない場合、-1 と出力してください。

制約

  • 1\leq N\leq 2\times10^5
  • S は o - からなる長さ N の文字列

入力

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

N
S

出力

S にレベル X のダンゴ文字列が含まれるような最大の X の値を 1 行で出力せよ。 そのような値が存在しない場合、-1 を出力せよ。

入力例 1

10
o-oooo---o

出力例 1

4

たとえば、S の 3 文字目から 7 文字目までに対応する部分文字列 oooo- は、レベル 4 のダンゴ文字列です。 S の部分文字列であってレベル 5 以上のダンゴ文字列であるようなものは存在しないため、4 と出力してください。

入力例 2

1
-

出力例 2

-1

S の連続する部分文字列は空文字列と - の 2 種類だけです。 これらはダンゴ文字列ではないため、-1 と出力してください。

入力例 3

30
-o-o-oooo-oo-o-ooooooo--oooo-o

出力例 3

7

Score : 300 points

Problem Statement

For a positive integer L, a level-L dango string is a string that satisfies the following conditions.

  • It is a string of length L+1 consisting of o and -.
  • Exactly one of the first character and the last character is -, and the other L characters are o.

For instance, ooo- is a level-3 dango string, but none of -ooo-, oo, and o-oo- is a dango string (more precisely, none of them is a level-L dango string for any positive integer L).

You are given a string S of length N consisting of the two characters o and -. Find the greatest positive integer X that satisfies the following condition.

  • There is a contiguous substring of S that is a level-X dango string.

If there is no such integer, print -1.

Constraints

  • 1\leq N\leq 2\times10^5
  • S is a string of length N consisting of o and -.

Input

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

N
S

Output

Print the greatest positive integer X such that S contains a level-X dango string, or -1 if there is no such integer.

Sample Input 1

10
o-oooo---o

Sample Output 1

4

For instance, the substring oooo- corresponding to the 3-rd through 7-th characters of S is a level-4 dango string. No substring of S is a level-5 dango string or above, so you should print 4.

Sample Input 2

1
-

Sample Output 2

-1

Only the empty string and - are the substrings of S. They are not dango strings, so you should print -1.

Sample Input 3

30
-o-o-oooo-oo-o-ooooooo--oooo-o

Sample Output 3

7