A - Median?

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

整数 a, b, c が与えられます。b がこれらの整数の中央値であるかどうか判定してください。

制約

  • 1 \leq a, b, c \leq 100
  • 入力は全て整数

入力

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

a b c

出力

b が与えられた整数の中央値であるならば Yes、そうでないならば No と出力せよ。

入力例 1

5 3 2

出力例 1

Yes

与えられた整数を小さい順に並べると 2, 3, 5 となり、b はこれらの整数の中央値です。

入力例 2

2 5 3

出力例 2

No

b は与えられた整数の中央値ではありません。

入力例 3

100 100 100

出力例 3

Yes

Score : 100 points

Problem Statement

Given integers a, b, and c, determine if b is the median of these integers.

Constraints

  • 1 \leq a, b, c \leq 100
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

a b c

Output

If b is the median of the given integers, then print Yes; otherwise, print No.

Sample Input 1

5 3 2

Sample Output 1

Yes

The given integers are 2, 3, 5 when sorted in ascending order, of which b is the median.

Sample Input 2

2 5 3

Sample Output 2

No

b is not the median of the given integers.

Sample Input 3

100 100 100

Sample Output 3

Yes
B - A to Z String 2

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

A を N 個、B を N 個、…、Z を N 個この順に繋げて得られる文字列の先頭から X 番目の文字を求めてください。

制約

  • 1 \leq N \leq 100
  • 1 \leq X \leq N\times 26
  • 入力は全て整数

入力

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

N X

出力

答えを出力せよ。

入力例 1

1 3

出力例 1

C

得られる文字列は ABCDEFGHIJKLMNOPQRSTUVWXYZ です。先頭から 3 番目の文字は C です。

入力例 2

2 12

出力例 2

F

得られる文字列は AABBCCDDEEFFGGHHIIJJKKLLMMNNOOPPQQRRSSTTUUVVWWXXYYZZ です。先頭から 12 番目の文字は F です。

Score : 100 points

Problem Statement

Find the X-th character from the beginning of the string that is obtained by concatenating these characters: N copies of A's, N copies of B's, …, and N copies of Z's, in this order.

Constraints

  • 1 \leq N \leq 100
  • 1 \leq X \leq N\times 26
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N X

Output

Print the answer.

Sample Input 1

1 3

Sample Output 1

C

We obtain the string ABCDEFGHIJKLMNOPQRSTUVWXYZ, whose 3-rd character from the beginning is C.

Sample Input 2

2 12

Sample Output 2

F

We obtain the string AABBCCDDEEFFGGHHIIJJKKLLMMNNOOPPQQRRSSTTUUVVWWXXYYZZ, whose 12-th character from the beginning is F.
C - Fill the Gaps

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

正整数からなる長さ N の数列 A=(A_1,\ldots,A_N) があります。どの隣接する 2 項の値も相異なります。

この数列に対し、次の操作によりいくつか数を挿入します。

  1. 数列 A のどの隣接する 2 項の差の絶対値も 1 であるとき、操作を終了する。
  2. 数列 A の先頭から見て、隣接する 2 項の差の絶対値が 1 でない最初の箇所を A_i,A_{i+1} とする。
    • A_i < A_{i+1} ならば、A_i と A_{i+1} の間に、A_i+1,A_i+2,\ldots,A_{i+1}-1 を挿入する。
    • A_i > A_{i+1} ならば、A_i と A_{i+1} の間に、A_i-1,A_i-2,\ldots,A_{i+1}+1 を挿入する。
  3. 手順 1 に戻る。

操作が終了したときの数列を出力してください。

制約

  • 2 \leq N \leq 100
  • 1 \leq A_i \leq 100
  • A_i \neq A_{i+1}
  • 入力は全て整数

入力

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

N
A_1 A_2 \ldots A_N

出力

操作が終了したときの数列の各要素を空白区切りで出力せよ。

入力例 1

4
2 5 1 2

出力例 1

2 3 4 5 4 3 2 1 2

最初、数列は (2,5,1,2) です。操作は以下のように行われます。

  • 1 項目の 2 と 2 項目の 5 の間に 3,4 を挿入する。数列は (2,3,4,5,1,2) となる。
  • 4 項目の 5 と 5 項目の 1 の間に 4,3,2 を挿入する。数列は (2,3,4,5,4,3,2,1,2) となる。

入力例 2

6
3 4 5 6 5 4

出力例 2

3 4 5 6 5 4

一度も挿入が行われないこともあります。

Score : 200 points

Problem Statement

We have a sequence of length N consisting of positive integers: A=(A_1,\ldots,A_N). Any two adjacent terms have different values.

Let us insert some numbers into this sequence by the following procedure.

  1. If every pair of adjacent terms in A has an absolute difference of 1, terminate the procedure.
  2. Let A_i, A_{i+1} be the pair of adjacent terms nearest to the beginning of A whose absolute difference is not 1.
    • If A_i < A_{i+1}, insert A_i+1,A_i+2,\ldots,A_{i+1}-1 between A_i and A_{i+1}.
    • If A_i > A_{i+1}, insert A_i-1,A_i-2,\ldots,A_{i+1}+1 between A_i and A_{i+1}.
  3. Return to step 1.

Print the sequence when the procedure ends.

Constraints

  • 2 \leq N \leq 100
  • 1 \leq A_i \leq 100
  • A_i \neq A_{i+1}
  • All values in the input are integers.

Input

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

N
A_1 A_2 \ldots A_N

Output

Print the terms in the sequence when the procedure ends, separated by spaces.

Sample Input 1

4
2 5 1 2

Sample Output 1

2 3 4 5 4 3 2 1 2

The initial sequence is (2,5,1,2). The procedure goes as follows.

  • Insert 3,4 between the first term 2 and the second term 5, making the sequence (2,3,4,5,1,2).
  • Insert 4,3,2 between the fourth term 5 and the fifth term 1, making the sequence (2,3,4,5,4,3,2,1,2).

Sample Input 2

6
3 4 5 6 5 4

Sample Output 2

3 4 5 6 5 4

No insertions may be performed.
D - Broken Rounding

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

非負整数 X に対し、 i=0,1,\dots,K-1 の順に次の操作を行ったとき、操作を全て終えた時点での X を求めてください。

  • X の 10^i の位以下を四捨五入する。
    • 厳密には、 X を「 |Y-X| が最小となる 10^{i+1} の倍数のうち最大のもの」である Y に置き換える。
    • 具体例を挙げる。
      • 273 の 10^1 の位以下を四捨五入すれば 300 となる。
      • 999 の 10^2 の位以下を四捨五入すれば 1000 となる。
      • 100 の 10^9 の位以下を四捨五入すれば 0 となる。
      • 1015 の 10^0 の位以下を四捨五入すれば 1020 となる。

制約

  • X,K は整数
  • 0 \le X < 10^{15}
  • 1 \le K \le 15

入力

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

X K

出力

答えを整数として出力せよ。

入力例 1

2048 2

出力例 1

2100

操作の過程で、 X は 2048 \rightarrow 2050 \rightarrow 2100 と変化します。

入力例 2

1 15

出力例 2

0

入力例 3

999 3

出力例 3

1000

入力例 4

314159265358979 12

出力例 4

314000000000000

X は 32bit 整数型に収まらない可能性があります。

Score : 200 points

Problem Statement

Given a non-negative integer X, perform the following operation for i=1,2,\dots,K in this order and find the resulting X.

  • Round X off to the nearest 10^i.
    • Formally, replace X with Y that is "the largest multiple of 10^i that minimizes |Y-X|."
    • Here are some examples:
      • Rounding 273 off to the nearest 10^2 yields 300.
      • Rounding 999 off to the nearest 10^3 yields 1000.
      • Rounding 100 off to the nearest 10^{10} yields 0.
      • Rounding 1015 off to the nearest 10^1 yields 1020.

Constraints

  • X and K are integers.
  • 0 \le X < 10^{15}
  • 1 \le K \le 15

Input

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

X K

Output

Print the answer as an integer.

Sample Input 1

2048 2

Sample Output 1

2100

X changes as 2048 \rightarrow 2050 \rightarrow 2100 by the operations.

Sample Input 2

1 15

Sample Output 2

0

Sample Input 3

999 3

Sample Output 3

1000

Sample Input 4

314159265358979 12

Sample Output 4

314000000000000

X may not fit into a 32-bit integer type.
E - Jumping Takahashi

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

高橋君は数直線上の座標 0 の位置にいます。

これから高橋君は N 回のジャンプを行います。i \, (1 \leq i \leq N) 回目のジャンプでは、正の方向に a_i または b_i 移動します。

N 回のジャンプの後に座標 X の位置にいるようにすることはできますか？

制約

  • 1 \leq N \leq 100
  • 1 \leq a_i \lt b_i \leq 100 \, (1 \leq i \leq N)
  • 1 \leq X \leq 10000
  • 入力は全て整数

入力

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

N X
a_1 b_1
\vdots
a_N b_N

出力

N 回のジャンプの後に座標 X の位置にいるようにすることができるならば Yes と、そうでないなら No と出力せよ。

入力例 1

2 10
3 6
4 5

出力例 1

Yes

1 回目のジャンプでは b_1 (= 6) 移動し、2 回目のジャンプでは a_2 (= 4) 移動することで、座標 X (= 10) の位置にいるようにすることができます。

入力例 2

2 10
10 100
10 100

出力例 2

No

1 回目のジャンプの後に座標 X (= 10) の位置にいるようにすることはできますが、全てのジャンプの後に座標 X (= 10) の位置にいるようにすることはできません。

入力例 3

4 12
1 8
5 7
3 4
2 6

出力例 3

Yes

Score : 300 points

Problem Statement

Takahashi is standing at the coordinate 0 on a number line.

He will now perform N jumps. In the i-th jump (1 \leq i \leq N), he moves a_i or b_i in the positive direction.

Is it possible for him to be at the coordinate X after N jumps?

Constraints

  • 1 \leq N \leq 100
  • 1 \leq a_i \lt b_i \leq 100 \, (1 \leq i \leq N)
  • 1 \leq X \leq 10000
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N X
a_1 b_1
\vdots
a_N b_N

Output

If it is possible for Takahashi to be at the coordinate X after N jumps, print Yes; otherwise, print No.

Sample Input 1

2 10
3 6
4 5

Sample Output 1

Yes

By moving b_1 (= 6) in the first jump and a_2 (= 4) in the second jump, he can be at the coordinate X (= 10).

Sample Input 2

2 10
10 100
10 100

Sample Output 2

No

He can be at the coordinate X (= 10) after the first jump, but not after all jumps.

Sample Input 3

4 12
1 8
5 7
3 4
2 6

Sample Output 3

Yes