実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
長さ N の整数列 A=(A_1,A_2,\ldots,A_N) 及び整数 L,R が与えられます。ここで L,R は L\leq R を満たします。
i=1,2,\ldots,N について以下の 2 つの条件を共に満たす整数 X_i を求めてください。なお、求める整数は常に一意に定まります。
- L\leq X_i \leq R
- L 以上 R 以下であるようなどの整数 Y についても |X_i - A_i| \leq |Y-A_i| を満たす
制約
- 1\leq N\leq 2\times 10^5
- 1\leq L\leq R \leq 10^9
- 1\leq A_i\leq 10^9
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N L R A_1 \ldots A_N
出力
i=1,2,\ldots,N について X_i を空白区切りで出力せよ。
入力例 1
5 4 7 3 1 4 9 7
出力例 1
4 4 4 7 7
i=1 では、
- |4-3|=1
- |5-3|=2
- |6-3|=3
- |7-3|=4
より X_i = 4 です。
入力例 2
3 10 10 11 10 9
出力例 2
10 10 10
Score : 200 points
Problem Statement
You are given an integer sequence A=(A_1,A_2,\ldots,A_N) of length N and integers L and R such that L\leq R.
For each i=1,2,\ldots,N, find the integer X_i that satisfies both of the following conditions. Note that the integer to be found is always uniquely determined.
- L\leq X_i \leq R.
- For every integer Y such that L \leq Y \leq R, it holds that |X_i - A_i| \leq |Y - A_i|.
Constraints
- 1\leq N\leq 2\times 10^5
- 1\leq L\leq R \leq 10^9
- 1\leq A_i\leq 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N L R A_1 \ldots A_N
Output
Print X_i for i=1,2,\ldots,N, separated by spaces.
Sample Input 1
5 4 7 3 1 4 9 7
Sample Output 1
4 4 4 7 7
For i=1:
- |4-3|=1
- |5-3|=2
- |6-3|=3
- |7-3|=4
Thus, X_i = 4.
Sample Input 2
3 10 10 11 10 9
Sample Output 2
10 10 10
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
無限に長いピアノの鍵盤があります。 この鍵盤内の連続する区間であって、白鍵 W 個と黒鍵 B 個からなるものは存在しますか？
文字列 wbwbwwbwbwbw を無限に繰り返してできる文字列を S とおきます。
S の部分文字列であって、W 個の w と B 個の b からなるものは存在しますか？
S の部分文字列とは
S の部分文字列とは、ある 2 つの正整数 l,r\ (l\leq r) に対して、S の l 文字目、l+1 文字目、\dots、r 文字目をこの順に繋げてできる文字列のことをいいます。制約
- W,B は整数
- 0\leq W,B \leq 100
- W+B \geq 1
入力
入力は以下の形式で標準入力から与えられる。
W B
出力
S の部分文字列であって、W 個の w と B 個の b からなるものが存在するならば Yes を、存在しないならば No を出力せよ。
入力例 1
3 2
出力例 1
Yes
S の最初の 15 文字は wbwbwwbwbwbwwbw であり、S の 11 文字目から 15 文字目までを取り出してできる文字列 bwwbw は 3 個の w と 2 個の b からなる部分文字列の一例です。
入力例 2
3 0
出力例 2
No
3 個の w と 0 個の b からなる文字列は www のみですが、これは S の部分文字列ではありません。
入力例 3
92 66
出力例 3
Yes
Score: 200 points
Problem Statement
There is an infinitely long piano keyboard. Is there a continuous segment within this keyboard that consists of W white keys and B black keys?
Let S be the string formed by infinitely repeating the string wbwbwwbwbwbw.
Is there a substring of S that consists of W occurrences of w and B occurrences of b?
What is a substring of S?
A substring of S is a string that can be formed by concatenating the l-th, (l+1)-th, \dots, r-th characters of S in this order for some two positive integers l and r (l\leq r).Constraints
- W and B are integers.
- 0\leq W,B \leq 100
- W+B \geq 1
Input
The input is given from Standard Input in the following format:
W B
Output
If there is a substring of S that consists of W occurrences of w and B occurrences of b, print Yes; otherwise, print No.
Sample Input 1
3 2
Sample Output 1
Yes
The first 15 characters of S are wbwbwwbwbwbwwbw. You can take the 11-th through 15-th characters to form the string bwwbw, which is a substring consisting of three occurrences of w and two occurrences of b.
Sample Input 2
3 0
Sample Output 2
No
The only string consisting of three occurrences of w and zero occurrences of b is www, which is not a substring of S.
Sample Input 3
92 66
Sample Output 3
Yes
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
N 本の導火線を一直線に接着したものがあります。左から i 本目の導火線は長さが A_i cm で、 1 秒あたり B_i cm の一定の速さで燃えます。
この導火線の左端と右端から同時に火をつけるとき、 2 つの火がぶつかる場所が着火前の導火線の左端から何 cm の地点か求めてください。
制約
- 1 \leq N \leq 10^5
- 1 \leq A_i,B_i \leq 1000
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 B_1 A_2 B_2 \vdots A_N B_N
出力
2 つの火がぶつかる場所が着火前の導火線の左端から何 cm の地点か（単位を除いて）出力せよ。
想定解答との絶対誤差または相対誤差が 10^{-5} 以下であれば正解として扱われる。
入力例 1
3 1 1 2 1 3 1
出力例 1
3.000000000000000
着火前の導火線の左端から 3 cm の地点で 2 つの火がぶつかります。
入力例 2
3 1 3 2 2 3 1
出力例 2
3.833333333333333
入力例 3
5 3 9 1 2 4 6 1 5 5 3
出力例 3
8.916666666666668
Score : 300 points
Problem Statement
We have N fuses connected in series. The i-th fuse from the left has a length of A_i centimeters and burns at a constant speed of B_i centimeters per second.
Consider igniting this object from left and right ends simultaneously. Find the distance between the position where the two flames will meet and the left end of the object.
Constraints
- 1 \leq N \leq 10^5
- 1 \leq A_i,B_i \leq 1000
- All values in input are integers.
Input
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 the distance between the position where the two flames will meet and the left end of the object, in centimeters (print just the number).
Your output will be considered correct when its absolute or relative error from our answer is at most 10^{-5}.
Sample Input 1
3 1 1 2 1 3 1
Sample Output 1
3.000000000000000
The two flames will meet at 3 centimeters from the left end of the object.
Sample Input 2
3 1 3 2 2 3 1
Sample Output 2
3.833333333333333
Sample Input 3
5 3 9 1 2 4 6 1 5 5 3
Sample Output 3
8.916666666666668
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 350 点
問題文
AtCoder 王国の 1 週間は A+B 日からなり、1 日目から A 日目が休日で、A+1 日目から A+B 日目が平日です。
高橋くんは N 個の予定があり、i 番目の予定は今日から D_i 日後です。
高橋くんは今日が 1 週間の何日目かを忘れてしまいました。高橋くんの N 個の予定が全て休日である可能性があるかを判定してください。
制約
- 1\leq N\leq 2\times 10^5
- 1\leq A,B\leq 10^9
- 1\leq D_1<D_2<\ldots<D_N\leq 10^9
入力
入力は以下の形式で標準入力から与えられる。
N A B D_1 D_2 \ldots D_N
出力
高橋くんの N 個の予定が全て休日である可能性がある場合は Yes を、そうでない場合は No を一行に出力せよ。
入力例 1
3 2 5 1 2 9
出力例 1
Yes
入力では 1 週間は 7 日からなり、1 日目から 2 日目が休日、3 日目から 7 日目が平日です。
今日が 1 週間の 7 日目だとします。このとき、1 日後は 1 週間の 1 日目、2 日後は 1 週間の 2 日目、9 日後は 1 週間の 2 日目となり、全ての予定が休日となります。そのため、高橋くんの N 個の予定が全て休日である可能性があります。
入力例 2
2 5 10 10 15
出力例 2
No
入力例 3
4 347 347 347 700 705 710
出力例 3
Yes
Score: 350 points
Problem Statement
In the Kingdom of AtCoder, a week consists of A+B days, with the first through A-th days being holidays and the (A+1)-th through (A+B)-th being weekdays.
Takahashi has N plans, and the i-th plan is scheduled D_i days later.
He has forgotten what day of the week it is today. Determine if it is possible for all of his N plans to be scheduled on holidays.
Constraints
- 1\leq N\leq 2\times 10^5
- 1\leq A,B\leq 10^9
- 1\leq D_1<D_2<\ldots<D_N\leq 10^9
Input
The input is given from Standard Input in the following format:
N A B D_1 D_2 \ldots D_N
Output
Print Yes in a single line if it is possible for all of Takahashi's N plans to be scheduled on holidays, and No otherwise.
Sample Input 1
3 2 5 1 2 9
Sample Output 1
Yes
In this input, a week consists of seven days, with the first through second days being holidays and the third through seventh days being weekdays.
Let us assume today is the seventh day of the week. In this case, one day later would be the first day of the week, two days later would be the second day of the week, and nine days later would also be the second day of the week, making all plans scheduled on holidays. Therefore, it is possible for all of Takahashi's N plans to be scheduled on holidays.
Sample Input 2
2 5 10 10 15
Sample Output 2
No
Sample Input 3
4 347 347 347 700 705 710
Sample Output 3
Yes
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 400 点
問題文
整数 N が与えられるので、以下の条件を全て満たす最小の整数 X を求めてください。
- X は N 以上である。
- 非負整数 (a,b) の組であって、 X=a^3+a^2b+ab^2+b^3 を満たすようなものが存在する。
制約
- N は整数
- 0 \le N \le 10^{18}
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを整数として出力せよ。
入力例 1
9
出力例 1
15
9 \le X \le 14 であるようなどの整数 X についても、問題文中の条件を満たすような (a,b) は存在しません。
X=15 は (a,b)=(2,1) とすると問題文中の条件を満たします。
入力例 2
0
出力例 2
0
N 自身が条件を満たすこともあります。
入力例 3
999999999989449206
出力例 3
1000000000000000000
入出力が 32bit 整数型に収まらない場合があります。
Score : 400 points
Problem Statement
Given an integer N, find the smallest integer X that satisfies all of the conditions below.
- X is greater than or equal to N.
- There is a pair of non-negative integers (a, b) such that X=a^3+a^2b+ab^2+b^3.
Constraints
- N is an integer.
- 0 \le N \le 10^{18}
Input
Input is given from Standard Input in the following format:
N
Output
Print the answer as an integer.
Sample Input 1
9
Sample Output 1
15
For any integer X such that 9 \le X \le 14, there is no (a, b) that satisfies the condition in the statement.
For X=15, (a,b)=(2,1) satisfies the condition.
Sample Input 2
0
Sample Output 2
0
N itself may satisfy the condition.
Sample Input 3
999999999989449206
Sample Output 3
1000000000000000000
Input and output may not fit into a 32-bit integer type.