A - もし解けなかったら木の下に埋めて貰っても構わないよ

Time Limit: 5 sec / Memory Limit: 256 MB

問題文

私、頭はあまりよくない方だとは思うけど、さすがに赤点は取らないと思うんだよね！

だって、赤点って平均点の半分以下の点数だよ？そんなに頭悪くないよ！

あれ、もしかして信じてない？

じゃあ私のクラス N 人のテストの点数を忍者の友達に頼んで秘密裏に入手したから、これで私が赤点かどうか調べてみてよ！

ちなみにリストの 1 番最初が私の点数だからね！

もし赤点だったら木の下に埋めて貰っても構わないよ！

入力

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

N
s_1
:
s_N
  • N はクラスの人数を表す整数であり、2 \leq N \leq 100 を満たす。
  • s_i は i 番目のクラスメイトの点数を表す整数であり、0 \leq s_i \leq 100 を満たす。
  • s_1 が赤点かどうか調べる対象の点数である。

出力

N 人 ( s_1 を含む) の平均点の半分以下である点数を赤点と定義する。

s_1 が赤点なら Fail 、赤点でなければ Pass と 1 行で出力せよ。出力の末尾に改行を入れること。

入力例1

5
30
100
80
30
50

出力例1

Pass

入力例2

4
20
100
100
100

出力例2

Fail

入力例3

2
30
90

出力例3

Fail

入力例4

3
34
33
34

出力例4

Pass
B - Union Find

Time Limit: 5 sec / Memory Limit: 256 MB

問題文

N 人の人をいくつかのグループにします。 はじめは全員別々のグループです。

以下の 2 つのクエリを処理してください。

  • B_i 番目の人を含むグループと C_i 番目の人を含むグループを 1 つのグループに統合する。
  • B_i 番目の人と C_i 番目の人が同じグループかを判定する。

入力

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

N Q
A_1 B_1 C_1
A_2 B_2 C_2
:
A_Q B_Q C_Q
  • 1 行目には、2 つの整数 N (1 ≦ N ≦ 10^5), Q (1 ≦ Q ≦ 10^5) が空白区切りで与えられる。
  • 2 行目からの Q 行では、クエリを表す 3 個の整数 A_i(A_i=0,1), B_i(1≦B_i≦N), C_i(1≦C_i≦N) が空白区切りで与えられる。A_i=0 は統合クエリを表し、B_i 番目の人を含むグループと C_i 番目の人を含むグループを 1 つのグループに統合する。A_i=1 は判定クエリを表し、B_i 番目の人と C_i 番目の人が同じグループかを判定する。

出力

A_i=1 である i について、B_i と C_i が同じグループならば YES を、違うグループならば NO を出力せよ。出力の末尾に改行を入れること。

入力例1

3 3
0 1 2
1 1 2
1 1 3

出力例1

YES
NO

入力例2

5 8
0 1 2
1 1 5
0 2 3
1 1 5
0 3 4
1 1 5
0 4 5
1 1 5

出力例2

NO
NO
NO
YES
C - 割り算と足し算

Time Limit: 5 sec / Memory Limit: 256 MB

問題文

正の整数 N が与えられます。N を 1 になるまで 2 以上の約数で割っていって数列を作ります。数列の各要素の各位の和の総和を最大化してください。

例えば、N=12 の場合、12,6,3,1 という数列を作ると 1+2+6+3+1=13 となり、これが最大です。

入力

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

N
  • 整数 N (1 ≦ N ≦ 100) が 1 行で与えられる。

出力

答えを出力せよ。出力の末尾に改行を入れること。

入力例1

12

出力例1

13

入力例2

1

出力例2

1

入力例3

100

出力例3

19
D - 数列圧縮

Time Limit: 5 sec / Memory Limit: 256 MB

問題文

0 ~ 9 までの数字からなる文字列 A, B が与えられる。 以下の操作で A を編集することができる。

  1. A 中で隣り合った 2 つの数字 A_i, A_{i+1} (1 \leq i \leq |A|-1) を取り除く。
  2. 1.で取り除いた 2 つの数字 A_i, A_{i+1} を整数とみなして足し、10 で割った余りを x とする。x を 2 つの数字を取り除いた位置 i に挿入する。

この編集操作を何度か ( 0 回含む) 繰り返して、B が作れるか判定せよ。

入力

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

A
B
  • A, B は0 ~ 9 までの数字からなる、長さ 1 以上 10 以下の文字列である。

出力

A に対して上記の編集操作を繰り返すことで B を作ることができるなら YES 、できないなら NO と 1 行で出力せよ。出力の末尾に改行を入れること。

入力例1

1123251011
252521

出力例1

YES

入力例2

0123456789
9876543210

出力例2

NO

入力例3

99999
99999

出力例3

YES

入力例4

39
2

出力例4

YES

入力例5

6
123

出力例5

NO