実行時間制限: 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
配点 : 300 点
問題文
以下の条件を満たす正整数 x を 321-like Number と呼びます。 この定義は A 問題と同様です。
- x の各桁を上から見ると狭義単調減少になっている。
- すなわち、x が d 桁の整数だとすると、 1 \le i < d を満たす全ての整数 i について以下の条件を満たす。
- ( x の上から i 桁目 ) > ( x の上から i+1 桁目 )
なお、 1 桁の正整数は必ず 321-like Number であることに注意してください。
例えば、 321,96410,1 は 321-like Number ですが、 123,2109,86411 は 321-like Number ではありません。
K 番目に小さい 321-like Number を求めてください。
制約
- 入力は全て整数
- 1 \le K
- 321-like Number は K 個以上存在する
入力
入力は以下の形式で標準入力から与えられる。
K
出力
K 番目に小さい 321-like Number を整数として出力せよ。
入力例 1
15
出力例 1
32
321-like Number は小さいものから順に (1,2,3,4,5,6,7,8,9,10,20,21,30,31,32,40,\dots) です。
このうち 15 番目に小さいものは 32 です。
入力例 2
321
出力例 2
9610
入力例 3
777
出力例 3
983210
Score : 300 points
Problem Statement
A positive integer x is called a 321-like Number when it satisfies the following condition. This definition is the same as the one in Problem A.
- The digits of x are strictly decreasing from top to bottom.
- In other words, if x has d digits, it satisfies the following for every integer i such that 1 \le i < d:
- (the i-th digit from the top of x) > (the (i+1)-th digit from the top of x).
Note that all one-digit positive integers are 321-like Numbers.
For example, 321, 96410, and 1 are 321-like Numbers, but 123, 2109, and 86411 are not.
Find the K-th smallest 321-like Number.
Constraints
- All input values are integers.
- 1 \le K
- At least K 321-like Numbers exist.
Input
The input is given from Standard Input in the following format:
K
Output
Print the K-th smallest 321-like Number as an integer.
Sample Input 1
15
Sample Output 1
32
The 321-like Numbers are (1,2,3,4,5,6,7,8,9,10,20,21,30,31,32,40,\dots) from smallest to largest.
The 15-th smallest of them is 32.
Sample Input 2
321
Sample Output 2
9610
Sample Input 3
777
Sample Output 3
983210
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 400 点
問題文
湖の周りに N 個の休憩所があります。
休憩所には時計回りに 1,2,\dots,N の番号が付いています。
休憩所 i から休憩所 i+1 まで時計回りに歩くには A_i 歩かかります ( 但し、休憩所 N+1 は休憩所 1 を指します ) 。
休憩所 s から休憩所 t ( s \neq t ) まで時計回りに歩くのにかかる最小の歩数は M の倍数でした。
(s,t) の組として考えられるものの数を求めてください。
制約
- 入力は全て整数
- 2 \le N \le 2 \times 10^5
- 1 \le A_i \le 10^9
- 1 \le M \le 10^6
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 A_2 \dots A_N
出力
答えを整数として出力せよ。
入力例 1
4 3 2 1 4 3
出力例 1
4
- 休憩所 1 から休憩所 2 まで時計回りに歩くのにかかる最小の歩数は 2 歩で、これは 3 の倍数ではありません。
- 休憩所 1 から休憩所 3 まで時計回りに歩くのにかかる最小の歩数は 3 歩で、これは 3 の倍数です。
- 休憩所 1 から休憩所 4 まで時計回りに歩くのにかかる最小の歩数は 7 歩で、これは 3 の倍数ではありません。
- 休憩所 2 から休憩所 3 まで時計回りに歩くのにかかる最小の歩数は 1 歩で、これは 3 の倍数ではありません。
- 休憩所 2 から休憩所 4 まで時計回りに歩くのにかかる最小の歩数は 5 歩で、これは 3 の倍数ではありません。
- 休憩所 2 から休憩所 1 まで時計回りに歩くのにかかる最小の歩数は 8 歩で、これは 3 の倍数ではありません。
- 休憩所 3 から休憩所 4 まで時計回りに歩くのにかかる最小の歩数は 4 歩で、これは 3 の倍数ではありません。
- 休憩所 3 から休憩所 1 まで時計回りに歩くのにかかる最小の歩数は 7 歩で、これは 3 の倍数ではありません。
- 休憩所 3 から休憩所 2 まで時計回りに歩くのにかかる最小の歩数は 9 歩で、これは 3 の倍数です。
- 休憩所 4 から休憩所 1 まで時計回りに歩くのにかかる最小の歩数は 3 歩で、これは 3 の倍数です。
- 休憩所 4 から休憩所 2 まで時計回りに歩くのにかかる最小の歩数は 5 歩で、これは 3 の倍数ではありません。
- 休憩所 4 から休憩所 3 まで時計回りに歩くのにかかる最小の歩数は 6 歩で、これは 3 の倍数です。
以上より、求めるべき (s,t) の組の数は 4 個です。
入力例 2
2 1000000 1 1
出力例 2
0
入力例 3
9 5 9 9 8 2 4 4 3 5 3
出力例 3
11
Score : 400 points
Problem Statement
There are N rest areas around a lake.
The rest areas are numbered 1, 2, ..., N in clockwise order.
It takes A_i steps to walk clockwise from rest area i to rest area i+1 (where rest area N+1 refers to rest area 1).
The minimum number of steps required to walk clockwise from rest area s to rest area t (s \neq t) is a multiple of M.
Find the number of possible pairs (s,t).
Constraints
- All input values are integers
- 2 \le N \le 2 \times 10^5
- 1 \le A_i \le 10^9
- 1 \le M \le 10^6
Input
The input is given from Standard Input in the following format:
N M A_1 A_2 \dots A_N
Output
Print the answer as an integer.
Sample Input 1
4 3 2 1 4 3
Sample Output 1
4
- The minimum number of steps to walk clockwise from rest area 1 to rest area 2 is 2, which is not a multiple of 3.
- The minimum number of steps to walk clockwise from rest area 1 to rest area 3 is 3, which is a multiple of 3.
- The minimum number of steps to walk clockwise from rest area 1 to rest area 4 is 7, which is not a multiple of 3.
- The minimum number of steps to walk clockwise from rest area 2 to rest area 3 is 1, which is not a multiple of 3.
- The minimum number of steps to walk clockwise from rest area 2 to rest area 4 is 5, which is not a multiple of 3.
- The minimum number of steps to walk clockwise from rest area 2 to rest area 1 is 8, which is not a multiple of 3.
- The minimum number of steps to walk clockwise from rest area 3 to rest area 4 is 4, which is not a multiple of 3.
- The minimum number of steps to walk clockwise from rest area 3 to rest area 1 is 7, which is not a multiple of 3.
- The minimum number of steps to walk clockwise from rest area 3 to rest area 2 is 9, which is a multiple of 3.
- The minimum number of steps to walk clockwise from rest area 4 to rest area 1 is 3, which is a multiple of 3.
- The minimum number of steps to walk clockwise from rest area 4 to rest area 2 is 5, which is not a multiple of 3.
- The minimum number of steps to walk clockwise from rest area 4 to rest area 3 is 6, which is a multiple of 3.
Therefore, there are four possible pairs (s,t).
Sample Input 2
2 1000000 1 1
Sample Output 2
0
Sample Input 3
9 5 9 9 8 2 4 4 3 5 3
Sample Output 3
11
実行時間制限: 3 sec / メモリ制限: 1024 MiB
配点 : 500 点
問題文
AtCoder 王国では、N 種類のたこ焼きが売られています。i 種類目のたこ焼きの値段は A_i 円です。
高橋君は、合計で 1 個以上のたこ焼きを買います。このとき、同じたこ焼きを複数個買うことも許されます。
高橋君が支払う金額としてあり得るもののうち、安い方から K 番目の金額を求めてください。ただし、同じ金額を支払う方法が複数存在する場合は 1 回だけ数えます。
制約
- 1 \le N \le 10
- 1 \le K \le 2 \times 10^5
- 1 \le A_i \le 10^9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N K A_1 A_2 \dots A_N
出力
答えを整数として出力せよ。
入力例 1
4 6 20 25 30 100
出力例 1
50
AtCoder 王国で売られている 4 種類のたこ焼きは、それぞれ 20 円、25 円、30 円、100 円です。
高橋君の支払う金額としてあり得るものは、安い方から 6 個を列挙すると 20 円、25 円、30 円、40 円、45 円、50 円となります。よって、答えは 50 円です。
合計で 1 個以上たこ焼きを買う必要があることに注意してください。
入力例 2
2 10 2 1
出力例 2
10
同じ金額の買い方が何通りかあっても、重複してカウントしないことに注意してください。
入力例 3
10 200000 955277671 764071525 871653439 819642859 703677532 515827892 127889502 881462887 330802980 503797872
出力例 3
5705443819
Score : 500 points
Problem Statement
In AtCoder Kingdom, N kinds of takoyakis (ball-shaped Japanese food) are sold. A takoyaki of the i-th kind is sold for A_i yen.
Takahashi will buy at least one takoyaki in total. He is allowed to buy multiple takoyakis of the same kind.
Find the K-th lowest price that Takahashi may pay. Here, if there are multiple sets of takoyakis that cost the same price, the price is counted only once.
Constraints
- 1 \le N \le 10
- 1 \le K \le 2 \times 10^5
- 1 \le A_i \le 10^9
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N K A_1 A_2 \dots A_N
Output
Print the answer as an integer.
Sample Input 1
4 6 20 25 30 100
Sample Output 1
50
The four kinds of takoyakis sold in AtCoder Kingdom cost 20 yen, 25 yen, 30 yen, and 100 yen.
The six lowest prices that Takahashi may pay are 20 yen, 25 yen, 30 yen, 40 yen, 45 yen, and 50 yen. Thus, the answer is 50.
Note that at least one takoyaki must be bought.
Sample Input 2
2 10 2 1
Sample Output 2
10
Note that a price is not counted more than once even if there are multiple sets of takoyakis costing that price.
Sample Input 3
10 200000 955277671 764071525 871653439 819642859 703677532 515827892 127889502 881462887 330802980 503797872
Sample Output 3
5705443819
実行時間制限: 5 sec / メモリ制限: 1024 MiB
配点 : 550 点
問題文
キーエンスは即納で有名です。
この問題において、暦は 1 日、 2 日、 3 日、 \dots と続いています。
注文 1,2,\dots,N があり、注文 i は T_i 日に発生することが分かっています。
これらの注文に対し、以下のルールに従って出荷を行います。
- 出荷は注文 K 個分までまとめて行うことができる。
- 注文 i は、 T_i 日以降にしか出荷できない。
- 一度出荷すると、その出荷の X 日後になるまで次の出荷が行えない。
- すなわち、 a 日に出荷を行った時、次の出荷ができるのは a+X 日である。
注文から出荷までにかかった日数 1 日につき、不満度が 1 蓄積します。
すなわち、注文 i が S_i 日に出荷されたとき、その注文によって蓄積する不満度は (S_i - T_i) です。
出荷するタイミングを上手く定めた時、全ての注文において蓄積した不満度の総和として達成可能な最小値を求めてください。
制約
- 入力は全て整数
- 1 \le K \le N \le 100
- 1 \le X \le 10^9
- 1 \le T_1 \le T_2 \le \dots \le T_N \le 10^{12}
入力
入力は以下の形式で標準入力から与えられる。
N K X T_1 T_2 \dots T_N
出力
答えを整数として出力せよ。
入力例 1
5 2 3 1 5 6 10 12
出力例 1
2
例えば、次の通り出荷することで不満度の総和を 2 にすることができ、これが達成可能な最小です。
- 注文 1 を 1 日に出荷する。
- これにより不満度は (1-1) = 0 蓄積し、次の出荷ができるのは 4 日である。
- 注文 2,3 を 6 日に出荷する。
- これにより不満度は (6-5) + (6-6) = 1 蓄積し、次の出荷ができるのは 9 日である。
- 注文 4 を 10 日に出荷する。
- これにより不満度は (10-10)=0 蓄積し、次の出荷ができるのは 13 日である。
- 注文 5 を 13 日に出荷する。
- これにより不満度は (13-12)=1 蓄積し、次の出荷ができるのは 16 日である。
入力例 2
1 1 1000000000 1000000000000
出力例 2
0
入力例 3
15 4 5 1 3 3 6 6 6 10 10 10 10 15 15 15 15 15
出力例 3
35
Score : 550 points
Problem Statement
KEYENCE is famous for quick delivery.
In this problem, the calendar proceeds as Day 1, Day 2, Day 3, \dots.
There are orders 1,2,\dots,N, and it is known that order i will be placed on Day T_i.
For these orders, shipping is carried out according to the following rules.
- At most K orders can be shipped together.
- Order i can only be shipped on Day T_i or later.
- Once a shipment is made, the next shipment cannot be made until X days later.
- That is, if a shipment is made on Day a, the next shipment can be made on Day a+X.
For each day that passes from order placement to shipping, dissatisfaction accumulates by 1 per day.
That is, if order i is shipped on Day S_i, the dissatisfaction accumulated for that order is (S_i - T_i).
Find the minimum possible total dissatisfaction accumulated over all orders when you optimally schedule the shipping dates.
Constraints
- All input values are integers.
- 1 \le K \le N \le 100
- 1 \le X \le 10^9
- 1 \le T_1 \le T_2 \le \dots \le T_N \le 10^{12}
Input
The input is given from Standard Input in the following format:
N K X T_1 T_2 \dots T_N
Output
Print the answer as an integer.
Sample Input 1
5 2 3 1 5 6 10 12
Sample Output 1
2
For example, by scheduling shipments as follows, we can achieve a total dissatisfaction of 2, which is the minimum possible.
- Ship order 1 on Day 1.
- This results in dissatisfaction of (1-1) = 0, and the next shipment can be made on Day 4.
- Ship orders 2 and 3 on Day 6.
- This results in dissatisfaction of (6-5) + (6-6) = 1, and the next shipment can be made on Day 9.
- Ship order 4 on Day 10.
- This results in dissatisfaction of (10-10) = 0, and the next shipment can be made on Day 13.
- Ship order 5 on Day 13.
- This results in dissatisfaction of (13-12) = 1, and the next shipment can be made on Day 16.
Sample Input 2
1 1 1000000000 1000000000000
Sample Output 2
0
Sample Input 3
15 4 5 1 3 3 6 6 6 10 10 10 10 15 15 15 15 15
Sample Output 3
35