A - Many A+B Problems

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

N 個の整数の 2 つ組 (A_1, B_1), (A_2, B_2), \ldots, (A_N, B_N) が与えられます。 各 i = 1, 2, \ldots, N について、A_i + B_i を出力してください。

制約

  • 1 \leq N \leq 1000
  • -10^9 \leq A_i, B_i \leq 10^9
  • 入力はすべて整数

入力

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

N
A_1 B_1
A_2 B_2
\vdots
A_N B_N

出力

N 行出力せよ。 i = 1, 2, \ldots, N について、i 行目には A_i+B_i を出力せよ。


入力例 1

4
3 5
2 -6
-5 0
314159265 123456789

出力例 1

8
-4
-5
437616054
  • 1 行目には、A_1 + B_1 = 3 + 5 = 8 を、
  • 2 行目には、A_2 + B_2 = 2 + (-6) = -4 を、
  • 3 行目には、A_3 + B_3 = (-5) + 0 = -5 を、
  • 4 行目には、A_4 + B_4 = 314159265 + 123456789 = 437616054 を出力します。

Score : 100 points

Problem Statement

You are given N pairs of integers: (A_1, B_1), (A_2, B_2), \ldots, (A_N, B_N). For each i = 1, 2, \ldots, N, print A_i + B_i.

Constraints

  • 1 \leq N \leq 1000
  • -10^9 \leq A_i, B_i \leq 10^9
  • All values in the input are integers.

Input

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

N
A_1 B_1
A_2 B_2
\vdots
A_N B_N

Output

Print N lines. For i = 1, 2, \ldots, N, the i-th line should contain A_i+B_i.


Sample Input 1

4
3 5
2 -6
-5 0
314159265 123456789

Sample Output 1

8
-4
-5
437616054
  • The first line should contain A_1 + B_1 = 3 + 5 = 8.
  • The second line should contain A_2 + B_2 = 2 + (-6) = -4.
  • The third line should contain A_3 + B_3 = (-5) + 0 = -5.
  • The fourth line should contain A_4 + B_4 = 314159265 + 123456789 = 437616054.
B - New Generation ABC

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

AtCoder Beginner Contest は、今回で 214 回目の開催となりました。

今までの AtCoder Beginner Contest において、出題される問題数は次のように変化しました。

  • 1 回目から 125 回目までは 4 問
  • 126 回目から 211 回目までは 6 問
  • 212 回目から 214 回目までは 8 問

N 回目の AtCoder Beginner Contest において出題された問題数を求めてください。

制約

  • 1 \leq N \leq 214
  • 入力は全て整数である。

入力

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

N

出力

答えを出力せよ。


入力例 1

214

出力例 1

8

入力例 2

1

出力例 2

4

入力例 3

126

出力例 3

6

Score : 100 points

Problem Statement

This is the 214-th AtCoder Beginner Contest (ABC).

The ABCs so far have had the following number of problems.

  • The 1-st through 125-th ABCs had 4 problems each.
  • The 126-th through 211-th ABCs had 6 problems each.
  • The 212-th through 214-th ABCs have 8 problems each.

Find the number of problems in the N-th ABC.

Constraints

  • 1 \leq N \leq 214
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N

Output

Print the answer.


Sample Input 1

214

Sample Output 1

8

Sample Input 2

1

Sample Output 2

4

Sample Input 3

126

Sample Output 3

6
C - Base K

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

整数 A,B が K 進法表記で与えられます。
A \times B を 10 進法表記で出力してください。

注記

K 進法表記については、Wikipedia「位取り記数法」 を参照してください。

制約

  • 2 \leq K \leq 10
  • 1 \leq A,B \leq 10^5
  • A,B は K 進法表記で与えられる

入力

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

K
A B

出力

答えを出力せよ。


入力例 1

2
1011 10100

出力例 1

220

2 進法表記の 1011 を 、10 進法表記すると 11 です。
2 進法表記の 10100 を、 10 進法表記すると 20 です。
11 \times 20 = 220 なので 220 を出力します。


入力例 2

7
123 456

出力例 2

15642

7 進法表記の 123 を 、10 進法表記すると 66 です。
7 進法表記の 456 を、 10 進法表記すると 237 です。
66 \times 237 = 15642 なので 15642 を出力します。

Score : 200 points

Problem Statement

You are given integers A and B, in base K.
Print A \times B in decimal.

Notes

For base-K representation, see Wikipedia's article on Positional notation.

Constraints

  • 2 \leq K \leq 10
  • 1 \leq A,B \leq 10^5
  • A and B are in base-K representation.

Input

Input is given from Standard Input in the following format:

K
A B

Output

Print the answer.


Sample Input 1

2
1011 10100

Sample Output 1

220

1011 in base 2 corresponds to 11 in base 10.
10100 in base 2 corresponds to 20 in base 10.
We have 11 \times 20 = 220, so print 220.


Sample Input 2

7
123 456

Sample Output 2

15642

123 in base 7 corresponds to 66 in base 10.
456 in base 7 corresponds to 237 in base 10.
We have 66 \times 237 = 15642, so print 15642.

D - 1D Keyboard

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

26 個のキーが数直線上に並んだキーボードがあります。

このキーボードの配列は ABCDEFGHIJKLMNOPQRSTUVWXYZ を並べ替えた文字列 S で表されます。 文字 S_x に対応するキーが座標 x (1 \leq x \leq 26) にあります。 ここで、S_x は S の x 文字目を表します。

あなたはこのキーボードを使って ABCDEFGHIJKLMNOPQRSTUVWXYZ をこの順で右手人差し指で一度だけ入力します。 ある文字を入力するためには、その文字に対応するキーの座標に指を移動させてキーを押す必要があります。

はじめ、指は A に対応するキーの座標にあります。A に対応するキーを押してから、Z に対応するキーを押すまでの指の移動距離の合計として考えられる最小値を求めてください。ただし、 キーを押す動作は移動距離に含まれません。

制約

  • S は ABCDEFGHIJKLMNOPQRSTUVWXYZ を並べ替えた文字列である。

入力

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

S

出力

答えを出力せよ。


入力例 1

ABCDEFGHIJKLMNOPQRSTUVWXYZ

出力例 1

25

A のキーを押してから Z のキーを押すまで指を 1 ずつ正の方向に移動させる必要があり、このときの移動距離の合計は 25 です。25 未満の総移動距離でキーを全て入力することはできないため、25 と出力します。


入力例 2

MGJYIZDKSBHPVENFLQURTCWOAX

出力例 2

223

Score : 200 points

Problem Statement

There is a keyboard with 26 keys arranged on a number line.

The arrangement of this keyboard is represented by a string S, which is a permutation of ABCDEFGHIJKLMNOPQRSTUVWXYZ. The key corresponding to the character S_x is located at coordinate x (1 \leq x \leq 26). Here, S_x denotes the x-th character of S.

You will use this keyboard to input ABCDEFGHIJKLMNOPQRSTUVWXYZ in this order, typing each letter exactly once with your right index finger. To input a character, you need to move your finger to the coordinate of the key corresponding to that character and press the key.

Initially, your finger is at the coordinate of the key corresponding to A. Find the minimal possible total traveled distance of your finger from pressing the key for A to pressing the key for Z. Here, pressing a key does not contribute to the distance.

Constraints

  • S is a permutation of ABCDEFGHIJKLMNOPQRSTUVWXYZ.

Input

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

S

Output

Print the answer.


Sample Input 1

ABCDEFGHIJKLMNOPQRSTUVWXYZ

Sample Output 1

25

From pressing the key for A to pressing the key for Z, you need to move your finger 1 unit at a time in the positive direction, resulting in a total traveled distance of 25. It is impossible to press all keys with a total traveled distance less than 25, so print 25.


Sample Input 2

MGJYIZDKSBHPVENFLQURTCWOAX

Sample Output 2

223
E - Simple path

Time Limit: 2 sec / Memory Limit: 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.