A - Rightmost

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

配点 : 100 点

問題文

英小文字からなる文字列 S が与えられます。
S に a が現れるならば最後に現れるのが何文字目かを出力し、現れないならば -1 を出力してください。

制約

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

入力

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

S

出力

答えを出力せよ。

入力例 1

abcdaxayz

出力例 1

7

S に a は 3 回現れますが、最後に現れるのは 7 文字目なので、7 を出力します。

入力例 2

bcbbbz

出力例 2

-1

S に a は現れないので、-1 を出力します。

入力例 3

aaaaa

出力例 3

5

Score : 100 points

Problem Statement

You are given a string S consisting of lowercase English letters.
If a appears in S, print the last index at which it appears; otherwise, print -1. (The index starts at 1.)

Constraints

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

Input

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

S

Output

Print the answer.

Sample Input 1

abcdaxayz

Sample Output 1

7

a appears three times in S. The last occurrence is at index 7, so you should print 7.

Sample Input 2

bcbbbz

Sample Output 2

-1

a does not appear in S, so you should print -1.

Sample Input 3

aaaaa

Sample Output 3

5
B - Nine

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

配点 : 100 点

問題文

以下のような、1 から 9 までの数字が書かれた 3 \times 3 の盤面があります。

1 以上 9 以下の整数 A,B が与えられます。ただし、A < B です。

A が書かれたマスと B が書かれたマスが左右に隣接しているか判定してください。

制約

  • 1 \le A < B \le 9
  • A, B は整数である。

入力

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

A B

出力

A が書かれたマスと B が書かれたマスが左右に隣接しているならば Yes、そうでないならば No を出力せよ。

入力例 1

7 8

出力例 1

Yes

7 が書かれたマスと 8 が書かれたマスは左右に隣り合っているので、Yes を出力します。

入力例 2

1 9

出力例 2

No

入力例 3

3 4

出力例 3

No

Score : 100 points

Problem Statement

We have the following 3 \times 3 board with integers from 1 through 9 written on it.

You are given two integers A and B between 1 and 9, where A < B.

Determine if the two squares with A and B written on them are adjacent horizontally.

Constraints

  • 1 \le A < B \le 9
  • A and B are integers.

Input

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

A B

Output

Print Yes if the two squares with A and B written on them are adjacent horizontally, and No otherwise.

Sample Input 1

7 8

Sample Output 1

Yes

The two squares with 7 and 8 written on them are adjacent horizontally, so print Yes.

Sample Input 2

1 9

Sample Output 2

No

Sample Input 3

3 4

Sample Output 3

No
C - Pentagon

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

配点 : 200 点

問題文

以下の図で表される正五角形 P があります。

P の点 S_1 と点 S_2 を結ぶ線分と、点 T_1 と点 T_2 を結ぶ線分の長さが等しいか判定してください。

制約

  • S_1,S_2,T_1,T_2 は A, B, C, D, E のいずれかの文字
  • S_1 \neq S_2
  • T_1 \neq T_2

入力

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

S_1S_2
T_1T_2

出力

P の点 S_1 と点 S_2 を結ぶ線分と、点 T_1 と点 T_2 を結ぶ線分の長さが等しい場合 Yes を、等しくない場合 No を出力せよ。

入力例 1

AC
EC

出力例 1

Yes

P の点 A と点 C を結ぶ線分と、P の点 E と点 C を結ぶ線分の長さは等しいです。

入力例 2

DA
EA

出力例 2

No

P の点 D と点 A を結ぶ線分と、P の点 E と点 A を結ぶ線分の長さは等しくありません。

入力例 3

BD
BD

出力例 3

Yes

Score : 200 points

Problem Statement

A regular pentagon P is shown in the figure below.

Determine whether the length of the line segment connecting points S_1 and S_2 of P equals the length of the line segment connecting points T_1 and T_2.

Constraints

  • Each of S_1, S_2, T_1, and T_2 is one of the characters A, B, C, D, and E.
  • S_1 \neq S_2
  • T_1 \neq T_2

Input

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

S_1S_2
T_1T_2

Output

If the length of the line segment connecting points S_1 and S_2 of P equals the length of the line segment connecting points T_1 and T_2, print Yes; otherwise, print No.

Sample Input 1

AC
EC

Sample Output 1

Yes

The length of the line segment connecting point A and point C of P equals the length of the line segment connecting point E and point C.

Sample Input 2

DA
EA

Sample Output 2

No

The length of the line segment connecting point D and point A of P does not equal the length of the line segment connecting point E and point A.

Sample Input 3

BD
BD

Sample Output 3

Yes
D - Commencement

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

配点 : 200 点

問題文

英小文字からなる文字列 S が良い文字列であるとは、すべての 1 以上の整数 i について次の性質が成り立つことであるとします。

  • S にちょうど i 回現れる文字はちょうど 0 種類またはちょうど 2 種類ある

文字列 S が与えられるので、 S が良い文字列か判定してください。

制約

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

入力

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

S

出力

S が良い文字列ならば Yes を、そうでないならば No を出力せよ。

入力例 1

commencement

出力例 1

Yes

文字列 commencement にちょうど i 回現れる文字の種類数は以下のとおりです。

  • i=1: o, t の 2 種類
  • i=2: c, n の 2 種類
  • i=3: e, m の 2 種類
  • i\geq 4: 0 種類

よって、commencement は良い文字列の条件を満たします。

入力例 2

banana

出力例 2

No

文字列 banana にちょうど 1 回現れる文字は b の 1 種類だけであり、良い文字列の条件を満たしません。

入力例 3

ab

出力例 3

Yes

Score: 200 points

Problem Statement

A string S consisting of lowercase English letters is a good string if and only if it satisfies the following property for all integers i not less than 1:

  • There are exactly zero or exactly two different letters that appear exactly i times in S.

Given a string S, determine if it is a good string.

Constraints

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

Input

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

S

Output

Print Yes if S is a good string, and No otherwise.

Sample Input 1

commencement

Sample Output 1

Yes

For the string commencement, the number of different letters that appear exactly i times is as follows:

  • i=1: two letters (o and t)
  • i=2: two letters (c and n)
  • i=3: two letters (e and m)
  • i\geq 4: zero letters

Therefore, commencement satisfies the condition of a good string.

Sample Input 2

banana

Sample Output 2

No

For the string banana, there is only one letter that appears exactly one time, which is b, so it does not satisfy the condition of a good string.

Sample Input 3

ab

Sample Output 3

Yes
E - Simple path

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

配点 : 300 点

問題文

N 頂点の木 T があり、 i (1\leq i\leq N-1) 番目の辺は頂点 U_i と頂点 V_i を結んでいます。

T 上の相異なる 2 頂点 X,Y が与えられるので、 頂点 X から頂点 Y への単純パス上の頂点（端点含む）を順に列挙してください。

ただし、木上の任意の相異なる 2 頂点 a,b について、a から b への単純パスがただ一つ存在することが証明できます。

単純パスとは？ グラフ G 上の頂点 X,Y に対して、頂点列 v_1,v_2, \ldots, v_k であって、 v_1=X, v_k=Y かつ、1\leq i\leq k-1 に対して v_i と v_{i+1} が辺で結ばれているようなものを頂点 X から頂点 Y への パス と呼びます。 さらに、v_1,v_2, \ldots, v_k がすべて異なるようなものを頂点 X から頂点 Y への 単純パス と呼びます。

制約

  • 1\leq N\leq 2\times 10^5
  • 1\leq X,Y\leq N
  • X\neq Y
  • 1\leq U_i,V_i\leq N
  • 入力はすべて整数
  • 与えられるグラフは木

入力

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

N X Y
U_1 V_1
U_2 V_2
\vdots
U_{N-1} V_{N-1}

出力

頂点 X から頂点 Y への単純パス上の頂点番号を順に空白区切りで出力せよ。

入力例 1

5 2 5
1 2
1 3
3 4
3 5

出力例 1

2 1 3 5

木 T は以下のような形であり、頂点 2 から頂点 5への単純パスは 頂点 2 \to 頂点 1 \to 頂点 3 \to 頂点 5 となります。
よって、2,1,3,5 をこの順に空白区切りで出力します。

入力例 2

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

出力例 2

1 2

木 T は以下のような形です。

Score : 300 points

Problem Statement

There is a tree T with N vertices. The i-th edge (1\leq i\leq N-1) connects vertex U_i and vertex V_i.

You are given two different vertices X and Y in T. List all vertices along the simple path from vertex X to vertex Y in order, including endpoints.

It can be proved that, for any two different vertices a and b in a tree, there is a unique simple path from a to b.

What is a simple path? For vertices X and Y in a graph G, a path from vertex X to vertex Y is a sequence of vertices v_1,v_2, \ldots, v_k such that v_1=X, v_k=Y, and v_i and v_{i+1} are connected by an edge for each 1\leq i\leq k-1. Additionally, if all of v_1,v_2, \ldots, v_k are distinct, the path is said to be a simple path from vertex X to vertex Y.

Constraints

  • 1\leq N\leq 2\times 10^5
  • 1\leq X,Y\leq N
  • X\neq Y
  • 1\leq U_i,V_i\leq N
  • All values in the input are integers.
  • The given graph is a tree.

Input

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

N X Y
U_1 V_1
U_2 V_2
\vdots
U_{N-1} V_{N-1}

Output

Print the indices of all vertices along the simple path from vertex X to vertex Y in order, with spaces in between.

Sample Input 1

5 2 5
1 2
1 3
3 4
3 5

Sample Output 1

2 1 3 5

The tree T is shown below. The simple path from vertex 2 to vertex 5 is 2 \to 1 \to 3 \to 5.
Thus, 2,1,3,5 should be printed in this order, with spaces in between.

Sample Input 2

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

Sample Output 2

1 2

The tree T is shown below.