A - Five Integers

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

与えられる 5 つの整数 A, B, C, D, E の中に何種類の整数があるかを出力してください。

制約

  • 0 \leq A, B, C, D, E \leq 100
  • 入力はすべて整数

入力

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

A B C D E

出力

答えを出力せよ。

入力例 1

31 9 24 31 24

出力例 1

3

与えられる 5 つの整数 31, 9, 24, 31, 24 の中には、9, 24, 31 という 3 種類の整数があります。 よって、3 を出力します。

入力例 2

0 0 0 0 0

出力例 2

1

Score : 100 points

Problem Statement

Print how many distinct integers there are in given five integers A, B, C, D, and E.

Constraints

  • 0 \leq A, B, C, D, E \leq 100
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

A B C D E

Output

Print the answer.

Sample Input 1

31 9 24 31 24

Sample Output 1

3

In the given five integers 31, 9, 24, 31, and 24, there are three distinct integers 9, 24, and 31. Thus, 3 should be printed.

Sample Input 2

0 0 0 0 0

Sample Output 2

1
B - Welcome to AtCoder Land 2

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

AtCoder Land は、 10 時ちょうど、 15 時ちょうど、 17 時ちょうどの 3 つのタイミングでしか入場できません。

高橋君は X 時ちょうどに AtCoder Land に到着しました。最短で何時ちょうどに入園できますか？
但し、高橋君の到着と同じタイミングに AtCoder Land に入場できる場合も、高橋君は AtCoder Land に入場できるものとします。

制約

  • X は 6 \le X \le 17 を満たす整数

入力

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

X

出力

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

入力例 1

14

出力例 1

15

高橋君は 14 時ちょうどに AtCoder Land に到着しました。高橋君は 15 時ちょうどに入園できます。

入力例 2

17

出力例 2

17

高橋君は 17 時ちょうどに AtCoder Land に到着しました。高橋君は 17 時ちょうどに入園できます。
この入力は、高橋君の到着と同じタイミングに AtCoder Land に入場できる場合に対応します。

入力例 3

6

出力例 3

10
C - qwerty

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

1 以上 26 以下の整数からなる長さ 26 の数列 P=(P_1,P_2, \ldots ,P_{26}) が与えられます。ここで、P の要素は相異なることが保証されます。

以下の条件を満たす長さ 26 の文字列 S を出力してください。

  • 任意の i\, (1 \leq i \leq 26) について、S の i 文字目は辞書順で小さい方から P_i 番目の英小文字である。

制約

  • 1 \leq P_i \leq 26
  • P_i \neq P_j (i \neq j)
  • 入力は全て整数である。

入力

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

P_1 P_2 \ldots P_{26}

出力

文字列 S を出力せよ。

入力例 1

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

出力例 1

abcdefghijklmnopqrstuvwxyz

入力例 2

2 1 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

出力例 2

bacdefghijklmnopqrstuvwxyz

入力例 3

5 11 12 16 25 17 18 1 7 10 4 23 20 3 2 24 26 19 14 9 6 22 8 13 15 21

出力例 3

eklpyqragjdwtcbxzsnifvhmou

Score : 200 points

Problem Statement

You are given a sequence of 26 integers P=(P_1,P_2, \ldots ,P_{26}) consisting of integers from 1 through 26. It is guaranteed that all elements in P are distinct.

Print a string S of length 26 that satisfies the following condition.

  • For every i (1 \leq i \leq 26), the i-th character of S is the lowercase English letter that comes P_i-th in alphabetical order.

Constraints

  • 1 \leq P_i \leq 26
  • P_i \neq P_j (i \neq j)
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

P_1 P_2 \ldots P_{26}

Output

Print the string S.

Sample Input 1

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

Sample Output 1

abcdefghijklmnopqrstuvwxyz

Sample Input 2

2 1 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

Sample Output 2

bacdefghijklmnopqrstuvwxyz

Sample Input 3

5 11 12 16 25 17 18 1 7 10 4 23 20 3 2 24 26 19 14 9 6 22 8 13 15 21

Sample Output 3

eklpyqragjdwtcbxzsnifvhmou
D - 3^A

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

正整数 M が与えられます。 以下の条件を全て満たす正整数 N と非負整数列 A=(A_1,A_2,\ldots,A_N) を一つ求めてください。

  • 1\le N\le 20
  • 0\le A_i\le 10 (1\le i\le N)
  • \displaystyle \sum_{i=1}^N 3^{A_i}=M

ただし、制約下では条件を満たす N と A の組が必ず存在することが証明できます。

制約

  • 1\le M\le 10^5

入力

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

M

出力

以下の形式で条件を満たす N と A を出力せよ。

N
A_1 A_2 \ldots A_N

なお、条件を満たす N と A の組が複数存在する場合は、どれを出力しても正答となる。

入力例 1

6

出力例 1

2
1 1

N=2 、A=(1,1) とすると \displaystyle \sum_{i=1}^N 3^{A_i}=3+3=6 より全ての条件を満たします。

他に N=4 、 A=(0,0,1,0) なども条件を満たします。

入力例 2

100

出力例 2

4
2 0 2 4

入力例 3

59048

出力例 3

20
0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9

1\le N\le 20 という制約に注意してください。

Score : 200 points

Problem Statement

You are given a positive integer M. Find a positive integer N and a sequence of non-negative integers A = (A_1, A_2, \ldots, A_N) that satisfy all of the following conditions:

  • 1 \le N \le 20
  • 0 \le A_i \le 10 (1 \le i \le N)
  • \displaystyle \sum_{i=1}^N 3^{A_i} = M

It can be proved that under the constraints, there always exists at least one such pair of N and A satisfying the conditions.

Constraints

  • 1 \le M \le 10^5

Input

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

M

Output

Print N and A satisfying the conditions in the following format:

N
A_1 A_2 \ldots A_N

If there are multiple valid pairs of N and A, any of them is acceptable.

Sample Input 1

6

Sample Output 1

2
1 1

For example, with N=2 and A=(1,1), we have \displaystyle \sum_{i=1}^N 3^{A_i} = 3+3=6, satisfying all conditions.

Another example is N=4 and A=(0,0,1,0), which also satisfies the conditions.

Sample Input 2

100

Sample Output 2

4
2 0 2 4

Sample Input 3

59048

Sample Output 3

20
0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9

Note the condition 1 \le N \le 20.
E - Reversible

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

ボールがいくつか刺さった棒が N 本あり、各ボールには英小文字が 1 個書かれています。

i = 1, 2, \ldots, N について、i 番目の棒に刺さった各ボールの英小文字は、文字列 S_i によって表されます。 具体的には、i 番目の棒には文字列 S_i の長さ |S_i| に等しい個数のボールが刺さっており、 刺さっているボールの英小文字を、棒のある端から順に並べたものは文字列 S_i と等しいです。

2 つの棒は、一方の棒に刺さっているボールの英小文字をどちらかの端から並べた列と、もう一方の棒に刺さっているボールの英小文字をどちらかの端から並べた列が一致するとき、同じ棒とみなされます。 より形式的には、1 以上 N 以下の整数 i, j について、i 本目の棒と j 本目の棒は、S_i が S_j と一致するか、S_i が S_j を前後反転したものと一致するとき、かつそのときに限り、同じとみなされます。

N 本の棒の中に、何種類の異なる棒があるかを出力してください。

制約

  • N は整数
  • 2 \leq N \leq 2 \times 10^5
  • S_i は英小文字のみからなる文字列
  • |S_i| \geq 1
  • \sum_{i = 1}^N |S_i| \leq 2 \times 10^5

入力

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

N
S_1
S_2
\vdots
S_N

出力

答えを出力せよ。

入力例 1

6
a
abc
de
cba
de
abc

出力例 1

3
  • S_2 = abc が S_4 = cba を前後反転したものと一致するため、2 番目の棒と 4 番目の棒は同じとみなされます。
  • S_2 = abc が S_6 = abc と一致するため、2 番目の棒と 6 番目の棒は同じとみなされます。
  • S_3 = de が S_5 = de と一致するため、3 番目の棒と 5 番目の棒は同じとみなされます。

よって、6 本の棒の中に、1 本目の棒、2 本目の棒（ 4, 6 本目の棒と同じ）、3 本目の棒（ 5 本目の棒と同じ）の 3 種類の異なる棒があります。

Score : 300 points

Problem Statement

There are N sticks with several balls stuck onto them. Each ball has a lowercase English letter written on it.

For each i = 1, 2, \ldots, N, the letters written on the balls stuck onto the i-th stick are represented by a string S_i. Specifically, the number of balls stuck onto the i-th stick is the length |S_i| of the string S_i, and S_i is the sequence of letters on the balls starting from one end of the stick.

Two sticks are considered the same when the sequence of letters on the balls starting from one end of one stick is equal to the sequence of letters starting from one end of the other stick. More formally, for integers i and j between 1 and N, inclusive, the i-th and j-th sticks are considered the same if and only if S_i equals S_j or its reversal.

Print the number of different sticks among the N sticks.

Constraints

  • N is an integer.
  • 2 \leq N \leq 2 \times 10^5
  • S_i is a string consisting of lowercase English letters.
  • |S_i| \geq 1
  • \sum_{i = 1}^N |S_i| \leq 2 \times 10^5

Input

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

N
S_1
S_2
\vdots
S_N

Output

Print the answer.

Sample Input 1

6
a
abc
de
cba
de
abc

Sample Output 1

3
  • S_2 = abc equals the reversal of S_4 = cba, so the second and fourth sticks are considered the same.
  • S_2 = abc equals S_6 = abc, so the second and sixth sticks are considered the same.
  • S_3 = de equals S_5 = de, so the third and fifth sticks are considered the same.

Therefore, there are three different sticks among the six: the first, second (same as the fourth and sixth), and third (same as the fifth).