A - Exponential or Quadratic

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

2^n \gt n^2 ですか?

制約

  • n は 1 以上 10^9 以下の整数

入力

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

n

出力

2^n \gt n^2 なら Yes を、そうでないなら No を出力せよ。


入力例 1

5

出力例 1

Yes

2^5=32,\ 5^2=25 より 2^n \gt n^2 であるため、Yes を出力します。


入力例 2

2

出力例 2

No

n=2 の場合 2^n=n^2=2^2 となり、故に 2^n \gt n^2 ではありません。よって No を出力します。


入力例 3

623947744

出力例 3

Yes

Score : 100 points

Problem Statement

Does 2^n \gt n^2 hold?

Constraints

  • n is an integer between 1 and 10^9 (inclusive).

Input

Input is given from Standard Input in the following format:

n

Output

If 2^n \gt n^2, print Yes; otherwise, print No.


Sample Input 1

5

Sample Output 1

Yes

Since 2^5=32,\ 5^2=25, we have 2^n \gt n^2, so Yes should be printed.


Sample Input 2

2

Sample Output 2

No

For n=2, we have 2^n=n^2=2^2, so 2^n \gt n^2 does not hold. Thus, No should be printed.


Sample Input 3

623947744

Sample Output 3

Yes
B - Seismic magnitude scales

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

地震のマグニチュードは、その地震のエネルギーの大きさを対数で表した値です。マグニチュードが 1 増える度にエネルギーは約 32 倍になることが知られています。
ここではマグニチュードが 1 増える度に地震のエネルギーがちょうど 32 倍になるとします。このとき、マグニチュード A の地震のエネルギーの大きさはマグニチュード B の地震のエネルギーの大きさの何倍ですか?

制約

  • 3\leq B\leq A\leq 9
  • A , B は整数

入力

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

A B

出力

答えを整数で出力せよ。


入力例 1

6 4

出力例 1

1024

6 は 4 より 2 だけ大きいので、 マグニチュード 6 の地震はマグニチュード 4 の地震と比べて 32\times 32=1024 倍のエネルギーを持っています。


入力例 2

5 5

出力例 2

1

マグニチュードが同じなのでエネルギーの大きさも同じです。

Score : 100 points

Problem Statement

The magnitude of an earthquake is a logarithmic scale of the energy released by the earthquake. It is known that each time the magnitude increases by 1, the amount of energy gets multiplied by approximately 32.
Here, we assume that the amount of energy gets multiplied by exactly 32 each time the magnitude increases by 1. In this case, how many times is the amount of energy of a magnitude A earthquake as much as that of a magnitude B earthquake?

Constraints

  • 3\leq B\leq A\leq 9
  • A and B are integers.

Input

Input is given from Standard Input in the following format:

A B

Output

Print the answer as an integer.


Sample Input 1

6 4

Sample Output 1

1024

6 is 2 greater than 4, so a magnitude 6 earthquake has 32\times 32=1024 times as much energy as a magnitude 4 earthquake has.


Sample Input 2

5 5

Sample Output 2

1

Earthquakes with the same magnitude have the same amount of energy.

C - Caesar Cipher

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

高橋君は英小文字からなる文字列 S を持っています。

高橋君は文字列 S に対して、下記の操作をちょうど 1 回行います。

  • まず、非負整数 K を選ぶ。
  • その後、S の各文字を K 個後ろの英小文字に変更する。

ただし、

  • a の 1 個後ろの英小文字は b であり、
  • b の 1 個後ろの英小文字は c であり、
  • c の 1 個後ろの英小文字は d であり、
  • \cdots
  • y の 1 個後ろの英小文字は z であり、
  • z の 1 個後ろの英小文字は a です。

例えば、b の 4 個後ろの英小文字は f であり、y の 3 個後ろの英小文字は b です。

文字列 T が与えられます。 高橋君が上記の操作によって S を T に一致させることができるかを判定してください。

制約

  • S と T はそれぞれ英小文字からなる長さ 1 以上 10^5 以下の文字列
  • S の長さと T の長さは等しい

入力

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

S
T

出力

高橋君が S を T に一致させることができる場合は Yes と出力し、 できない場合は No と出力せよ。


入力例 1

abc
ijk

出力例 1

Yes

高橋君が K=8 を選ぶと、

  • a は 8 個後ろの i に
  • b は 8 個後ろの j に
  • c は 8 個後ろの k に

それぞれ変更され、S と T が一致します。
高橋君が S を T に一致させることができるため Yes と出力します。


入力例 2

z
a

出力例 2

Yes

高橋君が K=1 を選ぶと S と T が一致します。
z の 1 個後ろの英小文字は a であることに注意してください。


入力例 3

ppq
qqp

出力例 3

No

高橋君は非負整数 K をどのように選んでも S を T に一致させることができません。 よって、No と出力します。


入力例 4

atcoder
atcoder

出力例 4

Yes

高橋君が K=0 を選ぶと S と T が一致します。

Score : 200 points

Problem Statement

Takahashi has a string S consisting of lowercase English letters.

On this string, he will do the operation below just once.

  • First, choose a non-negative integer K.
  • Then, shift each character of S to the right by K (see below).

Here,

  • a shifted to the right by 1 is b;
  • b shifted to the right by 1 is c;
  • c shifted to the right by 1 is d;
  • \cdots
  • y shifted to the right by 1 is z;
  • z shifted to the right by 1 is a.

For example, b shifted to the right by 4 is f, and y shifted to the right by 3 is b.

You are given a string T. Determine whether Takahashi can make S equal T by the operation above.

Constraints

  • Each of S and T is a string of length between 1 and 10^5 (inclusive) consisting of lowercase English letters.
  • The lengths of S and T are equal.

Input

Input is given from Standard Input in the following format:

S
T

Output

If Takahashi can make S equal T, print Yes; if not, print No.


Sample Input 1

abc
ijk

Sample Output 1

Yes

When Takahashi chooses K=8,

  • a is shifted to the right by 8 and becomes i,
  • b is shifted to the right by 8 and becomes j,
  • c is shifted to the right by 8 and becomes k,

and now S and T are equal.
Therefore, he can make S equal T, so Yes should be printed.


Sample Input 2

z
a

Sample Output 2

Yes

Choosing K=1 makes S and T equal.
Note that the letter on the right of z is a.


Sample Input 3

ppq
qqp

Sample Output 3

No

There is no non-negative integer K that he can choose to make S equal T, so No should be printed.


Sample Input 4

atcoder
atcoder

Sample Output 4

Yes

Choosing K=0 makes S and T equal.

D - Who is missing?

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

整数 1, 2, \dots, N が書かれたカードが 4 枚ずつ、合計 4N 枚あります。

高橋君は、これらのカードをシャッフルしたのち 1 枚のカードを選んで抜き取り、残りの 4N - 1 枚を束にしてあなたに渡しました。渡された束の i \, (1 \leq i \leq 4N - 1) 枚目のカードには、整数 A_i が書かれています。

高橋君が抜き取ったカードに書かれていた整数を求めてください。

制約

  • 1 \leq N \leq 10^5
  • 1 \leq A_i \leq N \, (1 \leq i \leq 4N - 1)
  • 各 k \, (1 \leq k \leq N) に対し、A_i = k となる i は 4 個以下である。
  • 入力は全て整数である。

入力

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

N
A_1 A_2 \ldots A_{4N - 1}

出力

答えを出力せよ。


入力例 1

3
1 3 2 3 3 2 2 1 1 1 2

出力例 1

3

高橋君が抜き取ったカードには 3 が書かれています。


入力例 2

1
1 1 1

出力例 2

1

入力例 3

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

出力例 3

2

Score : 200 points

Problem Statement

We have 4 cards with an integer 1 written on it, 4 cards with 2, \ldots, 4 cards with N, for a total of 4N cards.

Takahashi shuffled these cards, removed one of them, and gave you a pile of the remaining 4N-1 cards. The i-th card (1 \leq i \leq 4N - 1) of the pile has an integer A_i written on it.

Find the integer written on the card removed by Takahashi.

Constraints

  • 1 \leq N \leq 10^5
  • 1 \leq A_i \leq N \, (1 \leq i \leq 4N - 1)
  • For each k \, (1 \leq k \leq N), there are at most 4 indices i such that A_i = k.
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \ldots A_{4N - 1}

Output

Print the answer.


Sample Input 1

3
1 3 2 3 3 2 2 1 1 1 2

Sample Output 1

3

Takahashi removed a card with 3 written on it.


Sample Input 2

1
1 1 1

Sample Output 2

1

Sample Input 3

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

Sample Output 3

2
E - A+B+C

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 250 点

問題文

3 個の数列 A=(A_1,\ldots,A_N), B=(B_1,\ldots,B_M), C=(C_1,\ldots,C_L) が与えられます。

さらに数列 X=(X_1,\ldots,X_Q) が与えられるので、各 i=1,\ldots,Q に対して次の問題を解いてください。

問題:A,B,C からそれぞれ 1 個ずつ要素を選び、和を X_i にすることができるか?

制約

  • 1 \leq N,M,L \leq 100
  • 0 \leq A_i, B_i ,C_i \leq 10^8
  • 1 \leq Q \leq 2\times 10^5
  • 0 \leq X_i \leq 3\times 10^8
  • 入力は全て整数である

入力

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

N
A_1 \ldots A_N
M
B_1 \ldots B_M
L
C_1 \ldots C_L
Q
X_1 \ldots X_Q

出力

Q 行出力せよ。
i 行目には、A,B,C からそれぞれ 1 個ずつ要素を選び和を X_i にすることができるならば Yes、できないならば No と出力せよ。


入力例 1

3
1 2 3
2
2 4
6
1 2 4 8 16 32
4
1 5 10 50

出力例 1

No
Yes
Yes
No
  • A,B,C からそれぞれ 1 個ずつ要素を選び和を 1 にすることはできません。
  • A,B,C からそれぞれ 1,2,2 を選ぶと和を 5 にすることができます。
  • A,B,C からそれぞれ 2,4,4 を選ぶと和を 10 にすることができます。
  • A,B,C からそれぞれ 1 個ずつ要素を選び和を 50 にすることはできません。

Score: 250 points

Problem Statement

You are given three sequences A=(A_1,\ldots,A_N), B=(B_1,\ldots,B_M), and C=(C_1,\ldots,C_L).

Additionally, a sequence X=(X_1,\ldots,X_Q) is given. For each i=1,\ldots,Q, solve the following problem:

Problem: Is it possible to select one element from each of A, B, and C so that their sum is X_i?

Constraints

  • 1 \leq N,M,L \leq 100
  • 0 \leq A_i, B_i ,C_i \leq 10^8
  • 1 \leq Q \leq 2\times 10^5
  • 0 \leq X_i \leq 3\times 10^8
  • All input values are integers.

Input

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

N
A_1 \ldots A_N
M
B_1 \ldots B_M
L 
C_1 \ldots C_L
Q
X_1 \ldots X_Q

Output

Print Q lines. The i-th line should contain Yes if it is possible to select one element from each of A, B, and C so that their sum is X_i, and No otherwise.


Sample Input 1

3
1 2 3
2
2 4
6
1 2 4 8 16 32
4
1 5 10 50

Sample Output 1

No
Yes
Yes
No
  • It is impossible to select one element from each of A, B, and C so that their sum is 1.
  • Selecting 1, 2, and 2 from A, B, and C, respectively, makes the sum 5.
  • Selecting 2, 4, and 4 from A, B, and C, respectively, makes the sum 10.
  • It is impossible to select one element from each of A, B, and C so that their sum is 50.