A - Chord

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

英大文字からなる長さ 3 の文字列 S が与えられます。S が ACE、BDF、CEG、DFA、EGB、FAC、GBD のいずれかと等しいとき Yes を、そうでないとき No を出力してください。

制約

  • S は英大文字からなる長さ 3 の文字列

入力

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

S

出力

S が ACE、BDF、CEG、DFA、EGB、FAC、GBD のいずれかと等しいとき Yes を、そうでないとき No を出力せよ。

入力例 1

ABC

出力例 1

No

S = ABC のとき、S は ACE、BDF、CEG、DFA、EGB、FAC、GBD のいずれとも等しくないので No を出力します。

入力例 2

FAC

出力例 2

Yes

入力例 3

XYX

出力例 3

No

Score : 100 points

Problem Statement

Given a length-3 string S consisting of uppercase English letters, print Yes if S equals one of ACE, BDF, CEG, DFA, EGB, FAC, and GBD; print No otherwise.

Constraints

  • S is a length-3 string consisting of uppercase English letters.

Input

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

S

Output

Print Yes if S equals one of ACE, BDF, CEG, DFA, EGB, FAC, and GBD; print No otherwise.

Sample Input 1

ABC

Sample Output 1

No

When S = ABC, S does not equal any of ACE, BDF, CEG, DFA, EGB, FAC, and GBD, so No should be printed.

Sample Input 2

FAC

Sample Output 2

Yes

Sample Input 3

XYX

Sample Output 3

No
B - Doors in the Center

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

以下の条件を全て満たす長さ N の文字列を求めてください。

  • 各文字は - または = である
  • 回文である
  • 文字列中に = は 1 個または 2 個含まれる。 2 個含まれる場合、それらの = は隣接している

なお、そのような文字列はちょうど 1 つ存在します。

制約

  • 1 \leq N \leq 100
  • N は整数である

入力

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

N

出力

答えを出力せよ。

入力例 1

4

出力例 1

-==-

入力例 2

7

出力例 2

---=---

Score : 100 points

Problem Statement

Find a length-N string that satisfies all of the following conditions:

  • Each character is - or =.
  • It is a palindrome.
  • It contains exactly one or exactly two =s. If it contains two =s, they are adjacent.

Such a string is unique.

Constraints

  • 1 \leq N \leq 100
  • N is an integer.

Input

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

N

Output

Print the answer.

Sample Input 1

4

Sample Output 1

-==-

Sample Input 2

7

Sample Output 2

---=---
C - Compression

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 150 点

問題文

長さ N の整数列 A=(A_1,A_2,\ldots,A_N) が与えられます。

A に含まれる数を重複を除いて小さい順に出力してください。

制約

  • 1\le N\le 100
  • 1\le A_i\le 100
  • 入力される値は全て整数

入力

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

N
A_1 A_2 \ldots A_N

出力

A に含まれる数を小さい順に C_1,C_2,\ldots , C_M として、以下の形式で出力せよ。

M
C_1 C_2 \ldots C_M

入力例 1

4
3 1 4 1

出力例 1

3
1 3 4

A=(3,1,4,1) に含まれる数は小さい順に 1,3,4 の 3 つです。したがって、上記のように出力してください。

入力例 2

3
7 7 7

出力例 2

1
7

入力例 3

8
19 5 5 19 5 19 4 19

出力例 3

3
4 5 19

Score : 150 points

Problem Statement

An integer sequence A=(A_1,A_2,\ldots,A_N) of length N is given.

Output the numbers contained in A in ascending order, removing duplicates.

Constraints

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

Input

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

N
A_1 A_2 \ldots A_N

Output

Let C_1,C_2,\ldots , C_M be the numbers contained in A in ascending order. Output in the following format:

M
C_1 C_2 \ldots C_M

Sample Input 1

4
3 1 4 1

Sample Output 1

3
1 3 4

The numbers contained in A=(3,1,4,1) are 1,3,4 in ascending order, totalling 3 distinct numbers. Therefore, output as shown above.

Sample Input 2

3
7 7 7

Sample Output 2

1
7

Sample Input 3

8
19 5 5 19 5 19 4 19

Sample Output 3

3
4 5 19
D - You're a teapot

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

I begin with T and end with T, and I am full of T. What am I?

文字列 t について、充填率を以下のように定義します。

  • t の先頭と末尾の文字がともに t であり、かつ |t| \geq 3 である場合: t に含まれる t の個数を x とすると、t の充填率は \displaystyle\frac{x-2}{|t|-2} である。ここで、|t| は t の長さを表す。
  • そうでない場合: t の充填率は 0 である。

文字列 S が与えられます。S の部分文字列の充填率としてありうる最大値を求めてください。

部分文字列とは S の部分文字列とは、S の先頭から 0 文字以上、末尾から 0 文字以上削除して得られる文字列のことをいいます。 例えば、ab, bc, bcd は abcd の部分文字列ですが、ac, dc, e は abcd の部分文字列ではありません。

制約

  • 1 \leq |S| \leq 100
  • S は英小文字からなる文字列。

入力

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

S

出力

S の部分文字列の充填率としてありうる最大値を出力せよ。

出力された値と真の値との絶対誤差が 10^{-9} 以下のとき、正答と判定される。

入力例 1

attitude

出力例 1

0.50000000000000000

ttit は S の部分文字列であり、その充填率は \displaystyle\frac{3-2}{4-2} = \frac{1}{2} です。

充填率が \frac{1}{2} より高い部分文字列は存在しないので、答えは \frac{1}{2} です。

入力例 2

ottottott

出力例 2

0.66666666666666667

ttottott は S の部分文字列であり、その充填率は \displaystyle\frac{6-2}{8-2} = \frac{2}{3} です。

充填率が \frac{2}{3} より高い部分文字列は存在しないので、答えは \frac{2}{3} です。

入力例 3

coffeecup

出力例 3

0.00000000000000000

ff は S の部分文字列であり、その充填率は 0 です。

充填率が 0 より高い部分文字列は存在しないので、答えは 0 です。

Score : 200 points

Problem Statement

I begin with T and end with T, and I am full of T. What am I?

For a string t, define the filling rate as follows:

  • If the first and last characters of t are both t and |t| \geq 3: Let x be the number of t in t. Then the filling rate of t is \displaystyle\frac{x-2}{|t|-2}, where |t| denotes the length of t.
  • Otherwise: the filling rate of t is 0.

You are given a string S. Find the maximum possible filling rate of a substring of S.

What is a substring? A substring of S is a string obtained by removing zero or more characters from the beginning and the end of S. For example, ab, bc, and bcd are substrings of abcd, while ac, dc, and e are not substrings of abcd.

Constraints

  • 1 \leq |S| \leq 100
  • S is a string consisting of lowercase English letters.

Input

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

S

Output

Print the maximum possible filling rate of a substring of S.

Your output will be judged as correct when the absolute error from the true value is at most 10^{-9}.

Sample Input 1

attitude

Sample Output 1

0.50000000000000000

ttit is a substring of S, and its filling rate is \displaystyle\frac{3-2}{4-2} = \frac{1}{2}.

There is no substring with a filling rate greater than \frac{1}{2}, so the answer is \frac{1}{2}.

Sample Input 2

ottottott

Sample Output 2

0.66666666666666667

ttottott is a substring of S, and its filling rate is \displaystyle\frac{6-2}{8-2} = \frac{2}{3}.

There is no substring with a filling rate greater than \frac{2}{3}, so the answer is \frac{2}{3}.

Sample Input 3

coffeecup

Sample Output 3

0.00000000000000000

ff is a substring of S, and its filling rate is 0.

There is no substring with a filling rate greater than 0, so the answer is 0.
E - Max Ai+Bj

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 250 点

問題文

長さ N の整数列 A,B が与えられます。1 以上 N 以下の整数 i,j を選んで、 A_i + B_j の値を最大化してください。

制約

  • 1 \leq N \leq 5 \times 10^5
  • |A_i| \leq 10^9\,(i=1,2,\dots,N)
  • |B_j| \leq 10^9\,(j=1,2,\dots,N)
  • 入力はすべて整数

入力

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

N
A_1 A_2 \dots A_N
B_1 B_2 \dots B_N

出力

A_i + B_j の最大値を出力せよ。

入力例 1

2
-1 5
3 -7

出力例 1

8

(i,j)=(1,1),(1,2),(2,1),(2,2) に対する A_i+B_j の値はそれぞれ 2,-8,8,-2 であり、(i,j)=(2,1) が最大値 8 を達成します。

入力例 2

6
15 12 3 -13 -1 -19
7 17 -13 -10 18 4

出力例 2

33

Score : 250 points

Problem Statement

You are given two integer sequences A and B, each of length N. Choose integers i, j (1 \leq i, j \leq N) to maximize the value of A_i + B_j.

Constraints

  • 1 \leq N \leq 5 \times 10^5
  • |A_i| \leq 10^9 (i=1,2,\dots,N)
  • |B_j| \leq 10^9 (j=1,2,\dots,N)
  • All input values are integers.

Input

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

N
A_1 A_2 \dots A_N
B_1 B_2 \dots B_N

Output

Print the maximum possible value of A_i + B_j.

Sample Input 1

2
-1 5
3 -7

Sample Output 1

8

For (i,j) = (1,1), (1,2), (2,1), (2,2), the values of A_i + B_j are 2, -8, 8, -2 respectively, and (i,j) = (2,1) achieves the maximum value 8.

Sample Input 2

6
15 12 3 -13 -1 -19
7 17 -13 -10 18 4

Sample Output 2

33