A - CAPS LOCK

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

配点 : 100 点

問題文

英小文字のみからなる文字列 S が与えられます。

S の各文字を英大文字に変換して得られる文字列 T を出力してください。

制約

  • S は英小文字のみからなる、長さが 1 以上 100 以下の文字列

入力

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

S

出力

T を出力せよ。


入力例 1

abc

出力例 1

ABC

abc の各文字を英大文字に変換すると ABC になります。


入力例 2

a

出力例 2

A

入力例 3

abcdefghjiklnmoqprstvuwxyz

出力例 3

ABCDEFGHJIKLNMOQPRSTVUWXYZ

Score : 100 points

Problem Statement

You are given a string S consisting of lowercase English letters.

Uppercase each character of S and print the resulting string T.

Constraints

  • S is a string consisting of lowercase English letters whose length is between 1 and 100, inclusive.

Input

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

S

Output

Print T.


Sample Input 1

abc

Sample Output 1

ABC

Uppercase each character of abc, and you have ABC.


Sample Input 2

a

Sample Output 2

A

Sample Input 3

abcdefghjiklnmoqprstvuwxyz

Sample Output 3

ABCDEFGHJIKLNMOQPRSTVUWXYZ
B - Bitwise Exclusive Or

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

配点 : 100 点

問題文

0 以上 255 以下の整数 A,B が与えられます。 A \text{ xor }C=B となる 0 以上の整数 C を求めてください。

なお、そのような C はただ 1 つ存在し、0 以上 255 以下であることが証明されます。

\text{ xor } とは

整数 a, b のビットごとの排他的論理和 a \text{ xor } b は、以下のように定義されます。

  • a \text{ xor } b を二進表記した際の 2^k (k \geq 0) の位の数は、a, b を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。
例えば、3 \text{ xor } 5 = 6 となります (二進表記すると: 011 \text{ xor } 101 = 110)。

制約

  • 0\leq A,B \leq 255
  • 入力に含まれる値は全て整数である

入力

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

A B

出力

答えを出力せよ。


入力例 1

3 6

出力例 1

5

3 は 二進表記で 11、5 は二進表記で 101 なので、これらの \text{xor} は二進表記で 110 であり、十進表記で 6 です。

このように、3 \text{ xor } 5 = 6 となるので、答えは 5 です。


入力例 2

10 12

出力例 2

6

図

Score : 100 points

Problem Statement

You are given integers A and B between 0 and 255 (inclusive). Find a non-negative integer C such that A \text{ xor }C=B.

It can be proved that there uniquely exists such C, and it will be between 0 and 255 (inclusive).

What is bitwise \mathrm{XOR}?

The bitwise \mathrm{XOR} of integers A and B, A\ \mathrm{XOR}\ B, is defined as follows:

  • When A\ \mathrm{XOR}\ B is written in base two, the digit in the 2^k's place (k \geq 0) is 1 if exactly one of A and B is 1, and 0 otherwise.
For example, we have 3\ \mathrm{XOR}\ 5 = 6 (in base two: 011\ \mathrm{XOR}\ 101 = 110).

Constraints

  • 0\leq A,B \leq 255
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

A B

Output

Print the answer.


Sample Input 1

3 6

Sample Output 1

5

When written in binary, 3 will be 11, and 5 will be 101. Thus, their \text{xor} will be 110 in binary, or 6 in decimal.

In short, 3 \text{ xor } 5 = 6, so the answer is 5.


Sample Input 2

10 12

Sample Output 2

6

Figure

C - Tournament Result

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

配点 : 200 点

問題文

N 人の人が総当り戦の試合をしました。

N 行 N 列からなる試合の結果の表 A が与えられます。A の i 行目 j 列目の要素を A_{i,j} と表します。
A_{i,j} は i=j のとき - であり、それ以外のとき W, L, D のいずれかです。
A_{i,j} が W, L, D であることは、人 i が人 j との試合に勝った、負けた、引き分けたことをそれぞれ表します。

与えられた表に矛盾があるかどうかを判定してください。

次のいずれかが成り立つとき、与えられた表には矛盾があるといいます。

  • ある組 (i,j) が存在して、人 i が人 j に勝ったが、人 j が人 i に負けていない
  • ある組 (i,j) が存在して、人 i が人 j に負けたが、人 j が人 i に勝っていない
  • ある組 (i,j) が存在して、人 i が人 j に引き分けたが、人 j が人 i に引き分けていない

制約

  • 2 \leq N \leq 1000
  • A_{i,i} は - である
  • i\neq j のとき、A_{i,j} は W, L, D のいずれかである

入力

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

N
A_{1,1}A_{1,2}\ldots A_{1,N}
A_{2,1}A_{2,2}\ldots A_{2,N}
\vdots
A_{N,1}A_{N,2}\ldots A_{N,N}

出力

与えられた表に矛盾がないとき correct、矛盾があるとき incorrect と出力せよ。


入力例 1

4
-WWW
L-DD
LD-W
LDW-

出力例 1

incorrect

人 3 が人 4 に勝ったにもかかわらず、人 4 も人 3 に勝ったことになっており、矛盾しています。


入力例 2

2
-D
D-

出力例 2

correct

矛盾はありません。

Score : 200 points

Problem Statement

N players played a round-robin tournament.

You are given an N-by-N table A containing the results of the matches. Let A_{i,j} denote the element at the i-th row and j-th column of A.
A_{i,j} is - if i=j, and W, L, or D otherwise.
A_{i,j} is W if Player i beat Player j, L if Player i lost to Player j, and D if Player i drew with Player j.

Determine whether the given table is contradictory.

The table is said to be contradictory when some of the following holds:

  • There is a pair (i,j) such that Player i beat Player j, but Player j did not lose to Player i;
  • There is a pair (i,j) such that Player i lost to Player j, but Player j did not beat Player i;
  • There is a pair (i,j) such that Player i drew with Player j, but Player j did not draw with Player i.

Constraints

  • 2 \leq N \leq 1000
  • A_{i,i} is -.
  • A_{i,j} is W, L, or D, for i\neq j.

Input

Input is given from Standard Input in the following format:

N
A_{1,1}A_{1,2}\ldots A_{1,N}
A_{2,1}A_{2,2}\ldots A_{2,N}
\vdots
A_{N,1}A_{N,2}\ldots A_{N,N}

Output

If the given table is not contradictory, print correct; if it is contradictory, print incorrect.


Sample Input 1

4
-WWW
L-DD
LD-W
LDW-

Sample Output 1

incorrect

Player 3 beat Player 4, while Player 4 also beat Player 3, which is contradictory.


Sample Input 2

2
-D
D-

Sample Output 2

correct

There is no contradiction.

D - You're a teapot

実行時間制限: 2 sec / メモリ制限: 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 - Path Graph?

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

配点 : 300 点

問題文

N 頂点 M 辺の単純無向グラフが与えられます。頂点には 1, 2, \dots, N の番号が、辺には 1, 2, \dots, M の番号が付けられています。
辺 i \, (i = 1, 2, \dots, M) は頂点 u_i, v_i を結んでいます。

このグラフがパスグラフであるか判定してください。

単純無向グラフとは 単純無向グラフとは、自己ループや多重辺を含まず、辺に向きの無いグラフのことをいいます。

パスグラフとは 頂点に 1, 2, \dots, N の番号が付けられたN 頂点のグラフがパスグラフであるとは、(1, 2, \dots, N) を並べ変えて得られる数列 (v_1, v_2, \dots, v_N) であって、以下の条件を満たすものが存在することをいいます。
  • 全ての i = 1, 2, \dots, N-1 に対して、頂点 v_i, v_{i+1} を結ぶ辺が存在する
  • 整数 i, j が 1 \leq i, j \leq N, |i - j| \geq 2 を満たすならば、頂点 v_i, v_j を結ぶ辺は存在しない

制約

  • 2 \leq N \leq 2 \times 10^5
  • 0 \leq M \leq 2 \times 10^5
  • 1 \leq u_i, v_i \leq N \, (i = 1, 2, \dots, M)
  • 入力される値は全て整数
  • 入力で与えられるグラフは単純

入力

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

N M
u_1 v_1
u_2 v_2
\vdots
u_M v_M

出力

与えられたグラフがパスグラフなら Yes、そうでないなら No と出力せよ。


入力例 1

4 3
1 3
4 2
3 2

出力例 1

Yes

与えらえたグラフは下図のようであり、これはパスグラフです。

example_00


入力例 2

2 0

出力例 2

No

与えらえたグラフは下図のようであり、これはパスグラフではありません。

example_01


入力例 3

5 5
1 2
2 3
3 4
4 5
5 1

出力例 3

No

与えらえたグラフは下図のようであり、これはパスグラフではありません。

example_02

Score : 300 points

Problem Statement

You are given a simple undirected graph with N vertices and M edges. The vertices are numbered 1, 2, \dots, N, and the edges are numbered 1, 2, \dots, M.
Edge i \, (i = 1, 2, \dots, M) connects vertices u_i and v_i.

Determine if this graph is a path graph.

What is a simple undirected graph? A simple undirected graph is a graph without self-loops or multiple edges whose edges do not have a direction.

What is a path graph? A graph with N vertices numbered 1, 2, \dots, N is said to be a path graph if and only if there is a sequence (v_1, v_2, \dots, v_N) that is a permutation of (1, 2, \dots, N) and satisfies the following conditions:
  • For all i = 1, 2, \dots, N-1, there is an edge connecting vertices v_i and v_{i+1}.
  • If integers i and j satisfies 1 \leq i, j \leq N and |i - j| \geq 2, then there is no edge that connects vertices v_i and v_j.

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • 0 \leq M \leq 2 \times 10^5
  • 1 \leq u_i, v_i \leq N \, (i = 1, 2, \dots, M)
  • All values in the input are integers.
  • The graph given in the input is simple.

Input

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

N M
u_1 v_1
u_2 v_2
\vdots
u_M v_M

Output

Print Yes if the given graph is a path graph; print No otherwise.


Sample Input 1

4 3
1 3
4 2
3 2

Sample Output 1

Yes

Illustrated below is the given graph, which is a path graph.

example_00


Sample Input 2

2 0

Sample Output 2

No

Illustrated below is the given graph, which is not a path graph.

example_01


Sample Input 3

5 5
1 2
2 3
3 4
4 5
5 1

Sample Output 3

No

Illustrated below is the given graph, which is not a path graph.

example_02