Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 100 点
問題文
ジャンボ高橋君はゴルフの練習をすることにしました。
ジャンボ高橋君の目標は飛距離を K の倍数にすることですが、ジャンボ高橋君の出せる飛距離の範囲は A 以上 B 以下です。
目標の達成が可能であれば OK
と、不可能であれば NG
と出力してください。
制約
- 入力はすべて整数
- 1 \leq A \leq B \leq 1000
- 1 \leq K \leq 1000
入力
入力は以下の形式で標準入力から与えられる。
K A B
出力
目標の達成が可能であれば OK
と、不可能であれば NG
と出力せよ。
入力例 1
7 500 600
出力例 1
OK
7 の倍数のうち、たとえば 567 が 500 以上 600 以下の範囲にあります。
入力例 2
4 5 7
出力例 2
NG
どんな 4 の倍数も、5 以上 7 以下の範囲にはありません。
入力例 3
1 11 11
出力例 3
OK
Score: 100 points
Problem Statement
Takahashi the Jumbo will practice golf.
His objective is to get a carry distance that is a multiple of K, while he can only make a carry distance of between A and B (inclusive).
If he can achieve the objective, print OK
; if he cannot, print NG
.
Constraints
- All values in input are integers.
- 1 \leq A \leq B \leq 1000
- 1 \leq K \leq 1000
Input
Input is given from Standard Input in the following format:
K A B
Output
If he can achieve the objective, print OK
; if he cannot, print NG
.
Sample Input 1
7 500 600
Sample Output 1
OK
Among the multiples of 7, for example, 567 lies between 500 and 600.
Sample Input 2
4 5 7
Sample Output 2
NG
No multiple of 4 lies between 5 and 7.
Sample Input 3
1 11 11
Sample Output 3
OK
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
高橋くんはAtCoder銀行に 100 円を預けています。
AtCoder銀行では、毎年預金額の 1 % の利子がつきます(複利、小数点以下切り捨て)。
利子以外の要因で預金額が変化することはないと仮定したとき、高橋くんの預金額が初めて X 円以上になるのは何年後でしょうか。
制約
- 101 \le X \le 10^{18}
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
X
出力
高橋くんの預金額が初めて X 円以上になるのは何年後かを出力せよ。
入力例 1
103
出力例 1
3
- 1 年後の預金額は 101 円です。
- 2 年後の預金額は 102 円です。
- 3 年後の預金額は 103 円です。
したがって、預金額が初めて 103 円以上になるのは 3 年後です。
入力例 2
1000000000000000000
出力例 2
3760
入力例 3
1333333333
出力例 3
1706
Score : 200 points
Problem Statement
Takahashi has a deposit of 100 yen (the currency of Japan) in AtCoder Bank.
The bank pays an annual interest rate of 1 % compounded annually. (A fraction of less than one yen is discarded.)
Assuming that nothing other than the interest affects Takahashi's balance, in how many years does the balance reach X yen or above for the first time?
Constraints
- 101 \le X \le 10^{18}
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
X
Output
Print the number of years it takes for Takahashi's balance to reach X yen or above for the first time.
Sample Input 1
103
Sample Output 1
3
- The balance after one year is 101 yen.
- The balance after two years is 102 yen.
- The balance after three years is 103 yen.
Thus, it takes three years for the balance to reach 103 yen or above.
Sample Input 2
1000000000000000000
Sample Output 2
3760
Sample Input 3
1333333333
Sample Output 3
1706
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
正整数 N , M , Q と、4 つの整数の組 ( a_i , b_i , c_i , d_i ) Q 組が与えられます。
以下の条件を満たす数列 A を考えます。
- A は、長さ N の正整数列である。
- 1 \leq A_1 \leq A_2 \le \cdots \leq A_N \leq M
この数列の得点を、以下のように定めます。
- A_{b_i} - A_{a_i} = c_i を満たすような i についての、 d_i の総和 (そのような i が存在しないときは 0)
A の得点の最大値を求めてください。
制約
- 入力は全て整数
- 2 ≤ N ≤ 10
- 1 \leq M \leq 10
- 1 \leq Q \leq 50
- 1 \leq a_i < b_i \leq N ( i = 1, 2, ..., Q )
- 0 \leq c_i \leq M - 1 ( i = 1, 2, ..., Q )
- (a_i, b_i, c_i) \neq (a_j, b_j, c_j) ( i \neq j のとき)
- 1 \leq d_i \leq 10^5 ( i = 1, 2, ..., Q )
入力
入力は以下の形式で標準入力から与えられる。
N M Q a_1 b_1 c_1 d_1 : a_Q b_Q c_Q d_Q
出力
A の得点の最大値を出力せよ。
入力例 1
3 4 3 1 3 3 100 1 2 2 10 2 3 2 10
出力例 1
110
A = \{1, 3, 4\} のとき、この数列の得点は 110 となります。この条件の下では 110 より高い得点を持つ数列は存在しませんから、答えは 110 です。
入力例 2
4 6 10 2 4 1 86568 1 4 0 90629 2 3 0 90310 3 4 1 29211 3 4 3 78537 3 4 2 8580 1 2 1 96263 1 4 2 2156 1 2 0 94325 1 4 3 94328
出力例 2
357500
入力例 3
10 10 1 1 10 9 1
出力例 3
1
Score : 300 points
Problem Statement
Given are positive integers N, M, Q, and Q quadruples of integers ( a_i , b_i , c_i , d_i ).
Consider a sequence A satisfying the following conditions:
- A is a sequence of N positive integers.
- 1 \leq A_1 \leq A_2 \le \cdots \leq A_N \leq M.
Let us define a score of this sequence as follows:
- The score is the sum of d_i over all indices i such that A_{b_i} - A_{a_i} = c_i. (If there is no such i, the score is 0.)
Find the maximum possible score of A.
Constraints
- All values in input are integers.
- 2 ≤ N ≤ 10
- 1 \leq M \leq 10
- 1 \leq Q \leq 50
- 1 \leq a_i < b_i \leq N ( i = 1, 2, ..., Q )
- 0 \leq c_i \leq M - 1 ( i = 1, 2, ..., Q )
- (a_i, b_i, c_i) \neq (a_j, b_j, c_j) (where i \neq j)
- 1 \leq d_i \leq 10^5 ( i = 1, 2, ..., Q )
Input
Input is given from Standard Input in the following format:
N M Q a_1 b_1 c_1 d_1 : a_Q b_Q c_Q d_Q
Output
Print the maximum possible score of A.
Sample Input 1
3 4 3 1 3 3 100 1 2 2 10 2 3 2 10
Sample Output 1
110
When A = \{1, 3, 4\}, its score is 110. Under these conditions, no sequence has a score greater than 110, so the answer is 110.
Sample Input 2
4 6 10 2 4 1 86568 1 4 0 90629 2 3 0 90310 3 4 1 29211 3 4 3 78537 3 4 2 8580 1 2 1 96263 1 4 2 2156 1 2 0 94325 1 4 3 94328
Sample Output 2
357500
Sample Input 3
10 10 1 1 10 9 1
Sample Output 3
1
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
整数 A, B, N が与えられます。
N 以下の非負整数 x に対する floor(Ax/B) - A × floor(x/B) の最大値を求めてください。
ただし、floor(t) とは、実数 t 以下の最大の整数のことを表します。
制約
- 1 ≤ A ≤ 10^{6}
- 1 ≤ B ≤ 10^{12}
- 1 ≤ N ≤ 10^{12}
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
A B N
出力
N 以下の非負整数 x に対する floor(Ax/B) - A × floor(x/B) の最大値を整数として出力せよ。
入力例 1
5 7 4
出力例 1
2
x=3 のとき、floor(Ax/B)-A×floor(x/B) = floor(15/7) - 5×floor(3/7) = 2 となり、これが最大です。
入力例 2
11 10 9
出力例 2
9
Score : 400 points
Problem Statement
Given are integers A, B, and N.
Find the maximum possible value of floor(Ax/B) - A × floor(x/B) for a non-negative integer x not greater than N.
Here floor(t) denotes the greatest integer not greater than the real number t.
Constraints
- 1 ≤ A ≤ 10^{6}
- 1 ≤ B ≤ 10^{12}
- 1 ≤ N ≤ 10^{12}
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
A B N
Output
Print the maximum possible value of floor(Ax/B) - A × floor(x/B) for a non-negative integer x not greater than N, as an integer.
Sample Input 1
5 7 4
Sample Output 1
2
When x=3, floor(Ax/B)-A×floor(x/B) = floor(15/7) - 5×floor(3/7) = 2. This is the maximum value possible.
Sample Input 2
11 10 9
Sample Output 2
9
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
あなたは「AtCoderじゃんけん」という一対一のゲームの大会を主催することになりました。 大会の参加者は N 人で、それぞれには 1 から N の相異なる番号が割り振られています。 アリーナには二人が入ることのできる対戦場が M 個用意されており、あなたはそれぞれの対戦場に二つの相異なる 1 以上 N 以下の整数を割り当てなければいけません。 複数の対戦場に同じ整数を割り当てることはできません。 大会は N ラウンドによって構成され、それぞれのラウンドは以下のようにして取り行われます。
- それぞれの参加者は、自分の番号が割り当てられた対戦場が存在するならそこに行き、そこに来たもう一方の相手と対戦する。
- その後、それぞれの参加者が、自分の番号に 1 を足す。もし 1 を足した後の番号が N+1 であるなら、その値を 1 に変更する。
N 回のラウンドを通じて、二回以上同じ参加者と対戦するような参加者が存在しないようにしたいです。 このような条件を満たす対戦場への整数の割り当てをひとつ出力してください。 ただし、与えられる制約のもとでそのような割り当てが必ず存在することが示せます。
制約
- 1 \leq M
- M \times 2 +1 \leq N \leq 200000
入力
入力は以下の形式で標準入力から与えられる。
N M
出力
以下の形式で M 行に出力せよ。 i 行目には i 個目の対戦場に割り当てる二つの整数を出力せよ。
a_1 b_1 a_2 b_2 : a_M b_M
入力例 1
4 1
出力例 1
2 3
参加者 4 人を A,B,C,D とし、はじめ A には 1、Bには 2、Cには 3、Dには 4 が割り振られているとします。
-
1 回目のラウンドでは 2 の割り振られた B と 3 の割り振られた C が対戦し、A の番号が 2 、B の番号が 3、Cの番号が 4、D の番号が 1となります。
-
2 回目のラウンドでは 2 の割り振られた A と 3 の割り振られた B が対戦し、A の番号が 3 、B の番号が 4、C の番号が 1、D の番号が 2 となります。
-
3 回目のラウンドでは 2 の割り振られた D と 3 の割り振られた A が対戦し、A の番号が 4 、B の番号が 1、C の番号が 2、D の番号が 3 となります。
-
4 回目のラウンドでは 2 の割り振られた C と 3 の割り振られた D が対戦し、A の番号が 1 、B の番号が 2、C の番号が 3、D の番号が 4 となります。
4 回のラウンドを通じて二回以上同じ参加者と対戦するような参加者が存在しないため、この出力は正解となります。
入力例 2
7 3
出力例 2
1 6 2 5 3 4
Score : 500 points
Problem Statement
You are going to hold a competition of one-to-one game called AtCoder Janken. (Janken is the Japanese name for Rock-paper-scissors.) N players will participate in this competition, and they are given distinct integers from 1 through N. The arena has M playing fields for two players. You need to assign each playing field two distinct integers between 1 and N (inclusive). You cannot assign the same integer to multiple playing fields. The competition consists of N rounds, each of which proceeds as follows:
- For each player, if there is a playing field that is assigned the player's integer, the player goes to that field and fight the other player who comes there.
- Then, each player adds 1 to its integer. If it becomes N+1, change it to 1.
You want to ensure that no player fights the same opponent more than once during the N rounds. Print an assignment of integers to the playing fields satisfying this condition. It can be proved that such an assignment always exists under the constraints given.
Constraints
- 1 \leq M
- M \times 2 +1 \leq N \leq 200000
Input
Input is given from Standard Input in the following format:
N M
Output
Print M lines in the format below. The i-th line should contain the two integers a_i and b_i assigned to the i-th playing field.
a_1 b_1 a_2 b_2 : a_M b_M
Sample Input 1
4 1
Sample Output 1
2 3
Let us call the four players A, B, C, and D, and assume that they are initially given the integers 1, 2, 3, and 4, respectively.
-
The 1-st round is fought by B and C, who has the integers 2 and 3, respectively. After this round, A, B, C, and D have the integers 2, 3, 4, and 1, respectively.
-
The 2-nd round is fought by A and B, who has the integers 2 and 3, respectively. After this round, A, B, C, and D have the integers 3, 4, 1, and 2, respectively.
-
The 3-rd round is fought by D and A, who has the integers 2 and 3, respectively. After this round, A, B, C, and D have the integers 4, 1, 2, and 3, respectively.
-
The 4-th round is fought by C and D, who has the integers 2 and 3, respectively. After this round, A, B, C, and D have the integers 1, 2, 3, and 4, respectively.
No player fights the same opponent more than once during the four rounds, so this solution will be accepted.
Sample Input 2
7 3
Sample Output 2
1 6 2 5 3 4
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
N 頂点の木があり、i 番目の辺は頂点 u_i と頂点 v_i を結んでいます。 また、頂点 i には整数 a_i が書かれています。 1 以上 N 以下のすべての整数 k に対して、次の問題を解いてください。
- 頂点 1 から頂点 k までの最短パス上の頂点に書かれている整数を頂点 1 に近い方から順に並べた数列の最長増加部分列の長さはいくつか。
なお、長さ L の数列 A の最長増加部分列とは、1 \leq i_1 < i_2 < ... < i_M \leq L かつ A_{i_1} < A_{i_2} < ... < A_{i_M} を満たす部分列 A_{i_1} , A_{i_2} , ... , A_{i_M} の中で 最も M が大きいものをいいます。
制約
- 2 \leq N \leq 2 \times 10^5
- 1 \leq a_i \leq 10^9
- 1 \leq u_i , v_i \leq N
- u_i \neq v_i
- 与えられるグラフは木である。
- 入力はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N a_1 a_2 ... a_N u_1 v_1 u_2 v_2 : u_{N-1} v_{N-1}
出力
N 行出力せよ。k 行目には、頂点 1 から頂点 k までの最短パス上の頂点に書かれている整数を頂点 1 に近い方から順に並べた数列の最長増加部分列の長さを出力せよ。
入力例 1
10 1 2 5 3 4 6 7 3 2 4 1 2 2 3 3 4 4 5 3 6 6 7 1 8 8 9 9 10
出力例 1
1 2 3 3 4 4 5 2 2 3
例えば、頂点 1 から頂点 5 までの最短パス上の頂点に書かれている整数を頂点 1 に近い方から順に並べた数列 A は 1,2,5,3,4 です。この数列の最長増加部分列は A_1 , A_2 , A_4 , A_5 であり、この長さは 4 です。
Score : 600 points
Problem Statement
We have a tree with N vertices, whose i-th edge connects Vertex u_i and Vertex v_i. Vertex i has an integer a_i written on it. For every integer k from 1 through N, solve the following problem:
- We will make a sequence by lining up the integers written on the vertices along the shortest path from Vertex 1 to Vertex k, in the order they appear. Find the length of the longest increasing subsequence of this sequence.
Here, the longest increasing subsequence of a sequence A of length L is the subsequence A_{i_1} , A_{i_2} , ... , A_{i_M} with the greatest possible value of M such that 1 \leq i_1 < i_2 < ... < i_M \leq L and A_{i_1} < A_{i_2} < ... < A_{i_M}.
Constraints
- 2 \leq N \leq 2 \times 10^5
- 1 \leq a_i \leq 10^9
- 1 \leq u_i , v_i \leq N
- u_i \neq v_i
- The given graph is a tree.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N a_1 a_2 ... a_N u_1 v_1 u_2 v_2 : u_{N-1} v_{N-1}
Output
Print N lines. The k-th line, print the length of the longest increasing subsequence of the sequence obtained from the shortest path from Vertex 1 to Vertex k.
Sample Input 1
10 1 2 5 3 4 6 7 3 2 4 1 2 2 3 3 4 4 5 3 6 6 7 1 8 8 9 9 10
Sample Output 1
1 2 3 3 4 4 5 2 2 3
For example, the sequence A obtained from the shortest path from Vertex 1 to Vertex 5 is 1,2,5,3,4. Its longest increasing subsequence is A_1, A_2, A_4, A_5, with the length of 4.