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.
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
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.
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
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.
