A - ASCII code

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

英小文字 a, b, \ldots, z の ASCII 文字コードはこの順に 97,98,\ldots,122 です。

97 以上 122 以下の整数 N が与えられるので、ASCII 文字コードが N であるような英小文字を出力してください。

制約

  • N は 97 以上 122 以下の整数

入力

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

N

出力

答えを出力せよ。


入力例 1

97

出力例 1

a

ASCII 文字コードが 97 である英小文字は a です。


入力例 2

122

出力例 2

z

Score : 100 points

Problem Statement

The ASCII values of the lowercase English letters a, b, \ldots, z are 97,98,\ldots,122 in this order.

Given an integer N between 97 and 122, print the letter whose ASCII value is N.

Constraints

  • N is an integer between 97 and 122 (inclusive).

Input

Input is given from Standard Input in the following format:

N

Output

Print the answer.


Sample Input 1

97

Sample Output 1

a

97 is the ASCII value of a.


Sample Input 2

122

Sample Output 2

z
B - T-shirt

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

あるプログラミングコンテストでは、以下のルールに従って参加者に T シャツをプレゼントします。

  • 上位 A 位までの参加者は、必ず T シャツが貰える。
  • 加えて、上位 A+1 位から B 位までの参加者のうち C 人が一様ランダムに選ばれ、選ばれた参加者は T シャツを貰える。

コンテストには 1000 人が参加し、全ての参加者が相異なる順位を取りました。
このコンテストの参加者であるいろはちゃんは、X 位を取りました。
このとき、いろはちゃんが T シャツを貰える確率を求めてください。

制約

  • 入力はすべて整数
  • 1 \le A < B \le 1000
  • 1 \le C \le B-A
  • 1 \le X \le 1000

入力

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

A B C X

出力

答えを出力せよ。 なお、想定解との絶対誤差または相対誤差が 10^{−6} 以下であれば、正解として扱われる。


入力例 1

30 500 20 103

出力例 1

0.042553191489

いろはちゃんは 103 位を取りました。
31 位から 500 位までの 470 人の参加者の中から 20 人が一様ランダムに選ばれ、ここで選ばれるといろはちゃんは T シャツを貰えます。この確率は \frac{20}{470}=0.04255319\dots です。


入力例 2

50 500 100 1

出力例 2

1.000000000000

いろはちゃんは 1 位を取りました。この入力において、いろはちゃんは確実に T シャツを貰えます。


入力例 3

1 2 1 1000

出力例 3

0.000000000000

いろはちゃんは 1000 位を取りました。この入力において、いろはちゃんが T シャツを貰えることはありません。

Score : 100 points

Problem Statement

In a certain programming contest, T-shirts are awarded to participants according to the following rules.

  • All participants who ranked A-th or higher get a T-shirt.
  • Additionally, from the participants who ranked between (A+1)-th and B-th (inclusive), C participants chosen uniformly at random get a T-shirt.

There were 1000 participants in this contest, and all of them got different ranks.
Iroha-chan, who participated in this contest, ranked X-th.
Find the probability that she gets a T-shirt.

Constraints

  • All values in input are integers.
  • 1 \le A < B \le 1000
  • 1 \le C \le B-A
  • 1 \le X \le 1000

Input

Input is given from Standard Input in the following format:

A B C X

Output

Print the answer. Your output will be considered correct if the absolute or relative error from the judge's answer is at most 10^{−6}.


Sample Input 1

30 500 20 103

Sample Output 1

0.042553191489

Iroha-chan ranked 103-rd.
She will get a T-shirt if she is among the 20 participants chosen uniformly at random from the 470 participants who ranked between 31-st and 500-th, which happens with probability \frac{20}{470}=0.04255319\dots.


Sample Input 2

50 500 100 1

Sample Output 2

1.000000000000

Iroha-chan ranked 1-st. This time, she is guaranteed to get a T-shirt.


Sample Input 3

1 2 1 1000

Sample Output 3

0.000000000000

Iroha-chan ranked 1000-th. This time, she will never get a T-shirt.

C - 326-like Numbers

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

3 桁の正整数であって、百の位の数と十の位の数の積が一の位の数と等しいものを 326-like number と呼びます。

例えば 326,400,144 は 326-like number であり、623,777,429 は 326-like number ではありません。

整数 N が与えられるので、N 以上の最小の 326-like number を求めてください。なお、制約の条件下で答えは必ず存在します。

制約

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

入力

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

N

出力

答えを出力せよ。


入力例 1

320

出力例 1

326

320,321,322,323,324,325 は 326-like number ではなく、326 は 326-like number です。


入力例 2

144

出力例 2

144

144 は 326-like number です。


入力例 3

516

出力例 3

600

Score : 200 points

Problem Statement

A 326-like number is a three-digit positive integer where the product of the hundreds and tens digits equals the ones digit.

For example, 326,400,144 are 326-like numbers, while 623,777,429 are not.

Given an integer N, find the smallest 326-like number greater than or equal to N. It always exists under the constraints.

Constraints

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

Input

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

N

Output

Print the answer.


Sample Input 1

320

Sample Output 1

326

320,321,322,323,324,325 are not 326-like numbers, while 326 is a 326-like number.


Sample Input 2

144

Sample Output 2

144

144 is a 326-like number.


Sample Input 3

516

Sample Output 3

600
D - typo

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

文字列 S, T が与えられます。以下の操作を高々 1 回行うことで、S を T と一致させることができるかを判定してください。

  • S の隣り合う 2 文字を選び、入れ替える。

なお、上記の操作を一度も行わないことも可能です。

制約

  • S, T はそれぞれ英小文字のみからなる、長さ 2 以上 100 以下の文字列
  • S の長さと T の長さは等しい

入力

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

S
T

出力

問題文中の操作を高々 1 回行うことで S を T と一致させることができるなら Yes を、できないなら No を出力せよ。


入力例 1

abc
acb

出力例 1

Yes

S の 2 文字目と 3 文字目を入れ替えることで、S を T と一致させることができます。


入力例 2

aabb
bbaa

出力例 2

No

どのように操作を行っても、S を T と一致させることはできません。


入力例 3

abcde
abcde

出力例 3

Yes

S と T は既に一致しています。

Score : 200 points

Problem Statement

You are given two strings S and T. Determine whether it is possible to make S and T equal by doing the following operation at most once:

  • choose two adjacent characters in S and swap them.

Note that it is allowed to choose not to do the operation.

Constraints

  • Each of S and T is a string of length between 2 and 100 (inclusive) consisting of lowercase English letters.
  • S and T have the same length.

Input

Input is given from Standard Input in the following format:

S
T

Output

If it is possible to make S and T equal by doing the operation in Problem Statement at most once, print Yes; otherwise, print No.


Sample Input 1

abc
acb

Sample Output 1

Yes

You can swap the 2-nd and 3-rd characters of S to make S and T equal.


Sample Input 2

aabb
bbaa

Sample Output 2

No

There is no way to do the operation to make S and T equal.


Sample Input 3

abcde
abcde

Sample Output 3

Yes

S and T are already equal.

E - Min Max Pair

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

1 以上 N 以下の整数からなる長さ N の数列 a = (a_1, \dots, a_N) が与えられます。

以下の条件を全て満たす整数 i, j の組の総数を求めてください。

  • 1 \leq i \lt j \leq N
  • \min(a_i, a_j) = i
  • \max(a_i, a_j) = j

制約

  • 2 \leq N \leq 5 \times 10^5
  • 1 \leq a_i \leq N \, (1 \leq i \leq N)
  • 入力は全て整数

入力

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

N
a_1 \ldots a_N

出力

答えを出力せよ。


入力例 1

4
1 3 2 4

出力例 1

2

(i, j) = (1, 4), (2, 3) が条件を満たします。


入力例 2

10
5 8 2 2 1 6 7 2 9 10

出力例 2

8

Score : 300 points

Problem Statement

You are given a sequence a = (a_1, \dots, a_N) of length N consisting of integers between 1 and N.

Find the number of pairs of integers i, j that satisfy all of the following conditions:

  • 1 \leq i \lt j \leq N
  • \min(a_i, a_j) = i
  • \max(a_i, a_j) = j

Constraints

  • 2 \leq N \leq 5 \times 10^5
  • 1 \leq a_i \leq N \, (1 \leq i \leq N)
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
a_1 \ldots a_N

Output

Print the answer.


Sample Input 1

4
1 3 2 4

Sample Output 1

2

(i, j) = (1, 4), (2, 3) satisfy the conditions.


Sample Input 2

10
5 8 2 2 1 6 7 2 9 10

Sample Output 2

8