実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
N 枚からなるカードの山があり、上から i 枚目のカードには整数 A_i が書かれています。
山の下から K 枚のカードを取り出し、順序を保ったまま山の一番上に乗せました。
この操作後の山の上から順に、カードに書かれた整数を出力してください。
制約
- 1 \leq K < N \leq 100
- 1 \leq A_i \leq 100
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N K A_1 A_2 \ldots A_N
出力
操作後の山の上から i 枚目のカードに書かれた整数を B_i とする。B_1,B_2,\ldots,B_N をこの順に空白区切りで出力せよ。
入力例 1
5 3 1 2 3 4 5
出力例 1
3 4 5 1 2
最初、カードに書かれた整数は山の上から順に 1,2,3,4,5 です。
山の下から 3 枚のカードを取り出し、そのまま山の一番上に乗せたあと、カードに書かれた整数は山の上から順に 3,4,5,1,2 となります。
入力例 2
6 2 1 2 1 2 1 2
出力例 2
1 2 1 2 1 2
カードに書かれている整数は相異なるとは限りません。
Score : 100 points
Problem Statement
There is a stack of N cards, and the i-th card from the top has an integer A_i written on it.
You take K cards from the bottom of the stack and place them on top of the stack, maintaining their order.
Print the integers written on the cards from top to bottom after the operation.
Constraints
- 1 \leq K < N \leq 100
- 1 \leq A_i \leq 100
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N K A_1 A_2 \ldots A_N
Output
Let B_i be the integer written on the i-th card from the top of the stack after the operation. Print B_1,B_2,\ldots,B_N in this order, separated by spaces.
Sample Input 1
5 3 1 2 3 4 5
Sample Output 1
3 4 5 1 2
Initially, the integers written on the cards are 1,2,3,4,5 from top to bottom.
After taking three cards from the bottom of the stack and placing them on top, the integers written on the cards become 3,4,5,1,2 from top to bottom.
Sample Input 2
6 2 1 2 1 2 1 2
Sample Output 2
1 2 1 2 1 2
The integers written on the cards are not necessarily distinct.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
長さ N の正整数列 A = (A_1, A_2, \dots ,A_N) が与えられます。高橋くんは、以下の操作を A に含まれる正の要素の個数が 1 つ以下になるまで繰り返します。
- A を要素の降順に並び替える。それから、 A_1, A_2 を 1 減らす。
高橋くんが操作をする回数を求めてください。
制約
- 2 \leq N \leq 100
- 1 \leq A_i \leq 100
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \cdots A_N
出力
答えを出力せよ。
入力例 1
4 1 2 3 3
出力例 1
4
操作は以下のように進みます。
- 1 回目の操作で A = (2, 2, 2, 1) となる。
- 2 回目の操作で A = (1, 1, 2, 1) となる。
- 3 回目の操作で A = (1, 0, 1, 1) となる。
- 4 回目の操作で A = (0, 0, 1, 0) となる。A に含まれる正の要素の個数が 1 つ以下になったので、ここで操作を終了する。
入力例 2
3 1 1 100
出力例 2
2
Score : 200 points
Problem Statement
You are given a sequence of N positive integers A = (A_1, A_2, \dots ,A_N). Takahashi repeats the following operation until A contains one or fewer positive elements:
- Sort A in descending order. Then, decrease both A_1 and A_2 by 1.
Find the number of times he performs this operation.
Constraints
- 2 \leq N \leq 100
- 1 \leq A_i \leq 100
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \cdots A_N
Output
Print the answer.
Sample Input 1
4 1 2 3 3
Sample Output 1
4
The process goes as follows:
- After the 1st operation, A is (2, 2, 2, 1).
- After the 2nd operation, A is (1, 1, 2, 1).
- After the 3rd operation, A is (1, 0, 1, 1).
- After the 4th operation, A is (0, 0, 1, 0). A no longer contains more than one positive elements, so the process ends here.
Sample Input 2
3 1 1 100
Sample Output 2
2
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
あなたはゲームをプレイしています。
N 人の敵が一列に並んでおり、前から i 番目の敵の体力は H_i です。
あなたは 0 で初期化された変数 T を使い、全ての敵の体力が 0 以下になるまで次の行動を繰り返します。
- T を 1 増やす。その後、体力が 1 以上である最も前の敵を攻撃する。このとき、T が 3 の倍数ならばその敵の体力は 3 減り、そうでないなら 1 減る。
全ての敵の体力が 0 以下になったときの T の値を求めてください。
制約
- 1 \leq N \leq 2\times 10^5
- 1 \leq H_i \leq 10^9
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N H_1 H_2 \ldots H_N
出力
答えを出力せよ。
入力例 1
3 6 2 2
出力例 1
8
行動は次のように行われます。
- T=1 になる。1 番目の敵を攻撃し、その敵の体力は 6-1=5 となる。
- T=2 になる。1 番目の敵を攻撃し、その敵の体力は 5-1=4 となる。
- T=3 になる。1 番目の敵を攻撃し、その敵の体力は 4-3=1 となる。
- T=4 になる。1 番目の敵を攻撃し、その敵の体力は 1-1=0 となる。
- T=5 になる。2 番目の敵を攻撃し、その敵の体力は 2-1=1 となる。
- T=6 になる。2 番目の敵を攻撃し、その敵の体力は 1-3=-2 となる。
- T=7 になる。3 番目の敵を攻撃し、その敵の体力は 2-1=1 となる。
- T=8 になる。3 番目の敵を攻撃し、その敵の体力は 1-1=0 となる。
入力例 2
9 1 12 123 1234 12345 123456 1234567 12345678 123456789
出力例 2
82304529
入力例 3
5 1000000000 1000000000 1000000000 1000000000 1000000000
出力例 3
3000000000
オーバーフローに注意してください。
Score : 300 points
Problem Statement
You are playing a game.
There are N enemies lined up in a row, and the i-th enemy from the front has a health of H_i.
You will repeat the following action until the healths of all enemies become 0 or less, using a variable T initialized to 0.
- Increase T by 1. Then, attack the frontmost enemy with health 1 or more. If T is a multiple of 3, the enemy's health decreases by 3; otherwise, it decreases by 1.
Find the value of T when the healths of all enemies become 0 or less.
Constraints
- 1 \leq N \leq 2\times 10^5
- 1 \leq H_i \leq 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N H_1 H_2 \ldots H_N
Output
Print the answer.
Sample Input 1
3 6 2 2
Sample Output 1
8
The actions are performed as follows:
- T becomes 1. Attack the 1st enemy, and its health becomes 6-1=5.
- T becomes 2. Attack the 1st enemy, and its health becomes 5-1=4.
- T becomes 3. Attack the 1st enemy, and its health becomes 4-3=1.
- T becomes 4. Attack the 1st enemy, and its health becomes 1-1=0.
- T becomes 5. Attack the 2nd enemy, and its health becomes 2-1=1.
- T becomes 6. Attack the 2nd enemy, and its health becomes 1-3=-2.
- T becomes 7. Attack the 3rd enemy, and its health becomes 2-1=1.
- T becomes 8. Attack the 3rd enemy, and its health becomes 1-1=0.
Sample Input 2
9 1 12 123 1234 12345 123456 1234567 12345678 123456789
Sample Output 2
82304529
Sample Input 3
5 1000000000 1000000000 1000000000 1000000000 1000000000
Sample Output 3
3000000000
Beware of integer overflow.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 425 点
問題文
頂点に 1 から N の番号がついた N 頂点の木が与えられます。i 番目の辺は頂点 A_i と頂点 B_i を結んでいます。
このグラフからいくつかの(0 個でもよい)辺と頂点を削除してできる木のうち、指定された K 個の頂点、頂点 V_1,\ldots,V_K を全て含むようなものの頂点数の最小値を求めてください。
制約
- 1 \leq K \leq N \leq 2\times 10^5
- 1 \leq A_i,B_i \leq N
- 1 \leq V_1 < V_2 < \ldots < V_K \leq N
- 与えられるグラフは木である
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N K
A_1 B_1
\vdots
A_{N-1} B_{N-1}
V_1 \ldots V_K
出力
答えを出力せよ。
入力例 1
7 3 1 2 1 3 2 4 2 5 3 6 3 7 1 3 5
出力例 1
4
与えられた木は下図左の通りであり、そこからいくつかの辺と頂点を削除してできる木のうち頂点 1,3,5 を全て含むような頂点数最小のものは下図右の通りです。
入力例 2
4 4 3 1 1 4 2 1 1 2 3 4
出力例 2
4
入力例 3
5 1 1 4 2 3 5 2 1 2 1
出力例 3
1
Score : 425 points
Problem Statement
You are given a tree with N vertices numbered 1 to N. The i-th edge connects vertices A_i and B_i.
Consider a tree that can be obtained by removing some (possibly zero) edges and vertices from this graph. Find the minimum number of vertices in such a tree that includes all of K specified vertices V_1,\ldots,V_K.
Constraints
- 1 \leq K \leq N \leq 2\times 10^5
- 1 \leq A_i,B_i \leq N
- 1 \leq V_1 < V_2 < \ldots < V_K \leq N
- The given graph is a tree.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N K
A_1 B_1
\vdots
A_{N-1} B_{N-1}
V_1 \ldots V_K
Output
Print the answer.
Sample Input 1
7 3 1 2 1 3 2 4 2 5 3 6 3 7 1 3 5
Sample Output 1
4
The given tree is shown on the left in the figure below. The tree with the minimum number of vertices that includes all of vertices 1,3,5 is shown on the right.
Sample Input 2
4 4 3 1 1 4 2 1 1 2 3 4
Sample Output 2
4
Sample Input 3
5 1 1 4 2 3 5 2 1 2 1
Sample Output 3
1
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 475 点
問題文
Atcoder 国には 1 から N の番号がついた N 個の街と、1 から M の番号がついた M 本の電車が走っています。
電車 i は街 A_i を時刻 S_i に発車し、街 B_i に時刻 T_i に到着します。
正の整数 X_1 が与えられるので、0 以上の整数 X_2,\ldots,X_M を以下の条件を満たすように定める方法のうち、X_2+\ldots+X_M が最小になるものを求めてください。
- 条件：1 \leq i,j \leq M を満たす全ての組 (i,j) について、「B_i=A_j かつ T_i \leq S_j」ならば「T_i+X_i \leq S_j+X_j」
- すなわち、もともと乗り換え可能だった電車の組は、各電車 i の発車時刻・到着時刻を X_i 遅らせても乗り換え可能である
なお、X_2+\ldots+X_M が最小になるような X_2,\ldots,X_M の定め方は一意であることが証明できます。
制約
- 2 \leq N \leq 2\times 10^5
- 2 \leq M \leq 2\times 10^5
- 1 \leq A_i,B_i \leq N
- A_i \neq B_i
- 0 \leq S_i < T_i \leq 10^9
- 1 \leq X_1 \leq 10^9
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M X_1 A_1 B_1 S_1 T_1 \vdots A_M B_M S_M T_M
出力
条件を満たし、和を最小化するような X_2,\ldots,X_M を、この順に空白区切りで出力せよ。
入力例 1
3 6 15 1 2 10 20 1 2 20 30 2 3 25 40 2 3 35 50 3 1 15 30 3 1 45 60
出力例 1
0 10 0 0 5
街 1 から 2 へ行く電車 1 の到着が 15 遅れ、時刻 35 になりました。
街 2 での電車 1 から 3 への乗り換えのため、電車 3 の発車時刻を 10 遅らせて、時刻 35 発 時刻 50 着とします。
さらに街 3 での電車 3 から 6 への乗り換えのため、電車 6 の発車時刻を 5 遅らせて、時刻 50 発とします。
他の電車は発車を遅らせることなく、元々乗り換え可能だった電車の間を乗り換えることができるため、(X_2,X_3,X_4,X_5,X_6)=(0,10,0,0,5) は条件を満たします。
また、条件を満たすもののうち和がこれより小さいものは存在しないため、これが答えとなります。
入力例 2
10 9 100 1 10 0 1 10 2 1 100 10 3 1 100 10 4 1 100 10 5 1 100 10 6 1 100 10 7 1 100 10 8 1 100 10 9 1 100
出力例 2
100 100 100 100 100 100 100 100
入力例 3
4 4 10 1 2 0 1 1 2 0 10 2 3 100 200 2 4 100 200
出力例 3
0 0 0
Score : 475 points
Problem Statement
In the nation of Atcoder, there are N cities numbered 1 to N, and M trains numbered 1 to M. Train i departs from city A_i at time S_i and arrives at city B_i at time T_i.
Given a positive integer X_1, find a way to set non-negative integers X_2,\ldots,X_M that satisfies the following condition with the minimum possible value of X_2+\ldots+X_M.
- Condition: For all pairs (i,j) satisfying 1 \leq i,j \leq M, if B_i=A_j and T_i \leq S_j, then T_i+X_i \leq S_j+X_j.
- In other words, for any pair of trains that are originally possible to transfer between, it is still possible to transfer even after delaying the departure and arrival times of each train i by X_i.
It can be proved that such a way to set X_2,\ldots,X_M with the minimum possible value of X_2+\ldots+X_M is unique.
Constraints
- 2 \leq N \leq 2\times 10^5
- 2 \leq M \leq 2\times 10^5
- 1 \leq A_i,B_i \leq N
- A_i \neq B_i
- 0 \leq S_i < T_i \leq 10^9
- 1 \leq X_1 \leq 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M X_1 A_1 B_1 S_1 T_1 \vdots A_M B_M S_M T_M
Output
Print X_2,\ldots,X_M that satisfy the condition with the minimum possible sum, in that order, separated by spaces.
Sample Input 1
3 6 15 1 2 10 20 1 2 20 30 2 3 25 40 2 3 35 50 3 1 15 30 3 1 45 60
Sample Output 1
0 10 0 0 5
The arrival of train 1 from city 1 to 2 is delayed by 15 and becomes time 35.
To allow transfer from train 1 to 3 in city 2, the departure of train 3 is delayed by 10, making it depart at time 35 and arrive at time 50.
Further, to allow transfer from train 3 to 6 in city 3, the departure of train 6 is delayed by 5, making it depart at time 50.
Other trains can operate without delay while still allowing transfers between originally transferable trains, so (X_2,X_3,X_4,X_5,X_6)=(0,10,0,0,5) satisfies the condition.
Moreover, there is no solution with a smaller sum that satisfies the condition, so this is the answer.
Sample Input 2
10 9 100 1 10 0 1 10 2 1 100 10 3 1 100 10 4 1 100 10 5 1 100 10 6 1 100 10 7 1 100 10 8 1 100 10 9 1 100
Sample Output 2
100 100 100 100 100 100 100 100
Sample Input 3
4 4 10 1 2 0 1 1 2 0 10 2 3 100 200 2 4 100 200
Sample Output 3
0 0 0
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 475 点
問題文
各要素が 2 以上である長さ N の正整数列 A = (A_1, A_2, \dots ,A_N) が与えられます。Anna と Bruno はこれらの整数を用いてゲームをします。二人は、 Anna を先手として交互に以下の操作を行います。
- 整数 i \ (1 \leq i \leq N) を自由に選ぶ。A_i の正の約数であって A_i 自身でないものを自由に選び x とし、 A_i を x で置き換える。
操作が行えなくなった方が負けで、負けなかった方が勝ちです。両者が勝ちを目指して最適な行動を取るとき、どちらが勝つか判定してください。
制約
- 1 \leq N \leq 10^5
- 2 \leq A_i \leq 10^5
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \cdots A_N
出力
Anna がゲームに勝つ場合 Anna と、 Bruno がゲームに勝つ場合 Bruno と出力せよ。
入力例 1
3 2 3 4
出力例 1
Anna
例えば、ゲームの進行として以下のようなものが考えられます。必ずしも両者が最適な行動を取った例とは限らないことに注意してください。
- Anna が A_3 を 2 にする。
- Bruno が A_1 を 1 にする。
- Anna が A_2 を 1 にする。
- Bruno が A_3 を 1 にする。
- Anna のターンで操作ができないので Bruno の勝ちとなる。
実際には、このサンプルでは Anna が最適に行動すると常に Anna が勝つことができます。
入力例 2
4 2 3 4 6
出力例 2
Bruno
Score : 475 points
Problem Statement
You are given a sequence of N positive integers A = (A_1, A_2, \dots ,A_N), where each element is at least 2. Anna and Bruno play a game using these integers. They take turns, with Anna going first, performing the following operation.
- Choose an integer i \ (1 \leq i \leq N) freely. Then, freely choose a positive divisor x of A_i that is not A_i itself, and replace A_i with x.
The player who cannot perform the operation loses, and the other player wins. Determine who wins assuming both players play optimally for victory.
Constraints
- 1 \leq N \leq 10^5
- 2 \leq A_i \leq 10^5
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \cdots A_N
Output
Print Anna if Anna wins the game, and Bruno if Bruno wins.
Sample Input 1
3 2 3 4
Sample Output 1
Anna
For example, the game might proceed as follows. Note that this example may not necessarily represent optimal play by both players:
- Anna changes A_3 to 2.
- Bruno changes A_1 to 1.
- Anna changes A_2 to 1.
- Bruno changes A_3 to 1.
- Anna cannot operate on her turn, so Bruno wins.
Actually, for this sample, Anna always wins if she plays optimally.
Sample Input 2
4 2 3 4 6
Sample Output 2
Bruno
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 575 点
問題文
長さ N の正整数列 A, B が与えられます。以下の形式で与えられる Q 個のクエリを、与えられた順番に処理してください。クエリは次の 3 種類のいずれかです。
-
タイプ 1 :
1 i xの形式で与えられる。A_i を x に置き換える。 -
タイプ 2 :
2 i xの形式で与えられる。B_i を x に置き換える。 -
タイプ 3 :
3 l rの形式で与えられる。以下の問題を解き、答えを出力する。- はじめ v = 0 とする。i = l, l + 1, \dots ,r の順に、 v を v + A_i もしくは v \times B_i で置き換える操作を行う。最終的な v として実現できる最大値を求めよ。
ただし、入力で与えられるタイプ 3 のクエリの答えは 10^{18} 以下であることが保証されています。
制約
- 1 \leq N \leq 10^5
- 1 \leq A_i \leq 10^9
- 1 \leq B_i \leq 10^9
- 1 \leq Q \leq 10^5
- タイプ 1, 2 のクエリにおいて、 1 \leq i \leq N
- タイプ 1, 2 のクエリにおいて、 1 \leq x \leq 10^9
- タイプ 3 のクエリにおいて、 1 \leq l \leq r \leq N
- タイプ 3 のクエリにおいて、出力すべき値は 10^{18} 以下である
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \cdots A_N B_1 B_2 \cdots B_N Q query_1 query_2 \vdots query_Q
ここで query_i は i 番目のクエリであり、以下のいずれかの形式で与えられる。
1 i x
2 i x
3 l r
出力
タイプ 3 のクエリの個数を q 個として、 q 行出力せよ。i 行目には i 番目のタイプ 3 のクエリの答えを出力せよ。
入力例 1
3 3 2 4 1 2 2 3 3 1 3 1 1 1 3 1 3
出力例 1
12 7
1 番目のクエリでは、答えは ((0 + A_1) \times B_2) \times B_3 = 12 です。 3 番目のクエリでは、答えは ((0 + A_1) + A_2) + A_3 = 7 です。
入力例 2
6 65 32 12 5 8 312 4 1 3 15 16 2 6 3 2 6 3 1 5 1 5 6 2 4 9 3 2 6 3 3 5
出力例 2
46080 69840 27648 1728
Score : 575 points
Problem Statement
You are given sequences of positive integers A and B of length N. Process Q queries given in the following forms in the order they are given. Each query is of one of the following three types.
-
Type 1: Given in the form
1 i x. Replace A_i with x. -
Type 2: Given in the form
2 i x. Replace B_i with x. -
Type 3: Given in the form
3 l r. Solve the following problem and print the answer.- Initially, set v = 0. For i = l, l+1, ..., r in this order, replace v with either v + A_i or v \times B_i. Find the maximum possible value of v at the end.
It is guaranteed that the answers to the given type 3 queries are at most 10^{18}.
Constraints
- 1 \leq N \leq 10^5
- 1 \leq A_i \leq 10^9
- 1 \leq B_i \leq 10^9
- 1 \leq Q \leq 10^5
- For type 1 and 2 queries, 1 \leq i \leq N.
- For type 1 and 2 queries, 1 \leq x \leq 10^9.
- For type 3 queries, 1 \leq l \leq r \leq N.
- For type 3 queries, the value to be printed is at most 10^{18}.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \cdots A_N B_1 B_2 \cdots B_N Q query_1 query_2 \vdots query_Q
Here, query_i is the i-th query, given in one of the following formats:
1 i x
2 i x
3 l r
Output
Let q be the number of type 3 queries. Print q lines. The i-th line should contain the answer to the i-th type 3 query.
Sample Input 1
3 3 2 4 1 2 2 3 3 1 3 1 1 1 3 1 3
Sample Output 1
12 7
For the first query, the answer is ((0 + A_1) \times B_2) \times B_3 = 12. For the third query, the answer is ((0 + A_1) + A_2) + A_3 = 7.
Sample Input 2
6 65 32 12 5 8 312 4 1 3 15 16 2 6 3 2 6 3 1 5 1 5 6 2 4 9 3 2 6 3 3 5
Sample Output 2
46080 69840 27648 1728