AtCoder Daily Training EASY 2026/08/21 18:00start

A - Double Click

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 100 点

問題文

高橋君は、時刻 0 にパソコンの電源をつけ、それからマウスを N 回クリックしました。i(1 \le i \le N) 回目のクリックは時刻 T_i に行われました。

高橋君が時刻 x_1 と時刻 x_2 (ただし x_1 < x_2)にマウスを連続してクリックしたとき、x_2 - x_1 \le D であれば時刻 x_2 にダブルクリックが成立したと言います。

高橋君が最初にダブルクリックを成立させた時刻を求めてください。ただし、高橋君が 1 回もダブルクリックを成立させていないならば -1 を出力してください。

制約

1 \le N \le 100
1 \le D \le 10^9
1 \le T_i \le 10^9(1 \le i \le N)
T_i < T_{i+1}(1 \le i \le N-1)
入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N D
T_1 T_2 \dots T_N

出力

高橋君が 1 回でもダブルクリックを成立させたならば最初にダブルクリックが成立した時刻を、そうでないならば -1 を出力せよ。

入力例 1

4 500
300 900 1300 1700

出力例 1

高橋君は時刻 900,1300 にマウスをクリックしていて、1300 - 900 \le 500 であるため時刻 1300 にダブルクリックが成立しています。

時刻 1300 より前にダブルクリックは成立していないため、1300 を出力してください。

入力例 2

5 99
100 200 300 400 500

出力例 2

-1

高橋君は 1 回もダブルクリックを成立させていません。よって、-1 を出力してください。

入力例 3

4 500
100 600 1100 1600

出力例 3

高橋君が複数回ダブルクリックを成立させていても、そのうち最初の時刻のみを出力することに注意してください。

Score : 100 points

Problem Statement

Takahashi turned on a computer at time 0 and clicked the mouse N times. The i-th (1 \le i \le N) click was at time T_i.

If he consecutively clicked the mouse at time x_1 and time x_2 (where x_1 < x_2), a double click is said to be fired at time x_2 if and only if x_2 - x_1 \le D.

What time was a double click fired for the first time? If no double click was fired, print -1 instead.

Constraints

1 \le N \le 100
1 \le D \le 10^9
1 \le T_i \le 10^9(1 \le i \le N)
T_i < T_{i+1}(1 \le i \le N-1)
All values in the input are integers.

Input

The input is given from Standard Input in the following format:

N D
T_1 T_2 \dots T_N

Output

If at least one double click was fired, print the time of the first such event; otherwise, print -1.

Sample Input 1

4 500
300 900 1300 1700

Sample Output 1

Takahashi clicked the mouse at time 900 and 1300. Since 1300 - 900 \le 500, a double click was fired at time 1300.

A double click had not been fired before time 1300, so 1300 should be printed.

Sample Input 2

5 99
100 200 300 400 500

Sample Output 2

-1

No double click was fired, so print -1.

Sample Input 3

4 500
100 600 1100 1600

Sample Output 3

If multiple double clicks were fired, be sure to print only the first such event.

B - Exact Price

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 100 点

問題文

高橋君の財布の中には 100 円硬貨が 1 枚以上入っており、それ以外には何も入っていません。

高橋君の財布の中の合計金額が X 円である可能性はありますか？

制約

0 \leq X \leq 1000
入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

出力

高橋君の財布の中の合計金額が X 円である可能性がある場合は Yes、そうでない場合は No と出力せよ。

入力例 1

出力例 1

Yes

財布に 100 円硬貨が 5 枚入っているとき、合計金額は 500 円になります。故に財布の中の合計金額は X=500 円になりうるため、Yes を出力します。

入力例 2

出力例 2

No

入力例 3

出力例 3

No

財布の中には 100 円硬貨が 1 枚以上入っていることに注意してください。

Score : 100 points

Problem Statement

Takahashi's purse has one or more 100-yen coins in it and nothing else. (Yen is the Japanese currency.)

Is it possible that the total amount of money in the purse is X yen?

Constraints

0 \leq X \leq 1000
All values in input are integers.

Input

Input is given from Standard Input in the following format:

Output

If it is possible that the total amount of money in Takahashi's purse is X yen, print Yes; otherwise, print No.

Sample Input 1

Sample Output 1

Yes

If the purse has five 100-yen coins, the total amount of money is 500 yen. Thus, it is possible that the total amount is X=500 yen, so we should print Yes.

Sample Input 2

Sample Output 2

No

Sample Input 3

Sample Output 3

No

Note that the purse has at least one 100-yen coin.

C - Everyone is Friends

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 200 点

問題文

1,2,\ldots,N の番号がついた N 人の人がいます。

M 回の舞踏会が行われました。 i (1\leq i \leq M) 回目の舞踏会には k_i 人が参加し、参加した人は人 x_{i,1},x_{i,2},\ldots,x_{i,k_i} でした。

どの二人も少なくとも 1 回同じ舞踏会に参加したか判定してください。

制約

2\leq N \leq 100
1\leq M \leq 100
2\leq k_i \leq N
1\leq x_{i,1}<x_{i,2}<\ldots < x_{i,k_i}\leq N
入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N M
k_1 x_{1,1} x_{1,2} \ldots x_{1,k_1}
\vdots
k_M x_{M,1} x_{M,2} \ldots x_{M,k_M}

出力

どの二人も少なくとも 1 回同じ舞踏会に参加した場合 Yes を、そうでない場合 No を出力せよ。

入力例 1

出力例 1

Yes

人 1 と人 2 は共に 1 回目の舞踏会に参加しています。

人 2 と人 3 は共に 2 回目の舞踏会に参加しています。

人 1 と人 3 は共に 3 回目の舞踏会に参加しています。

以上よりどの二人も少なくとも 1 回同じ舞踏会に参加したので、答えは Yes です。

入力例 2

4 2
3 1 2 4
3 2 3 4

出力例 2

No

人 1 と人 3 は 1 回も同じ舞踏会に参加していないので、答えは No です。

Score : 200 points

Problem Statement

There are N people numbered 1,2,\ldots,N.

M parties were held. k_i people attended the i-th (1\leq i \leq M) party, and they were People x_{i,1},x_{i,2},\ldots,x_{i,k_i}.

Determine if every two people attended the same party at least once.

Constraints

2\leq N \leq 100
1\leq M \leq 100
2\leq k_i \leq N
1\leq x_{i,1}<x_{i,2}<\ldots < x_{i,k_i}\leq N
All values in the input are integers.

Input

The input is given from Standard Input in the following format:

N M
k_1 x_{1,1} x_{1,2} \ldots x_{1,k_1}
\vdots
k_M x_{M,1} x_{M,2} \ldots x_{M,k_M}

Output

Print Yes if every two people attended the same party at least once; print No otherwise.

Sample Input 1

Sample Output 1

Yes

Both Person 1 and Person 2 attended the 1-st party.

Both Person 2 and Person 3 attended the 2-nd party.

Both Person 1 and Person 3 attended the 3-rd party.

Therefore, every two people attended the same party at least once, so the answer is Yes.

Sample Input 2

4 2
3 1 2 4
3 2 3 4

Sample Output 2

No

Person 1 and Person 3 did not attend the same party, so the answer is No.

D - Product Calculator

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 200 点

問題文

高橋君は電卓を持っています。電卓には最初 1 が表示されています。
高橋君は電卓に対して N 回操作を行います。
i 回目 (1\leq i\leq N) の操作では、その時点で画面に表示されている数に正の整数 A_i をかけます。
しかし、電卓には K 桁までしか表示できないため、計算結果が (K+1) 桁以上になる場合、代わりに 1 が画面に表示されます。そうでない場合は正しく計算結果が表示されます。

N 回の操作の後に電卓に表示されている数を求めてください。

制約

1 \leq N \leq 100
1 \leq K \leq 18
1 \leq A_i < 10^K
入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N K
A_1 A_2 \ldots A_N

出力

N 回の操作の後に電卓に表示されている数を出力せよ。

入力例 1

5 2
7 13 3 2 5

出力例 1

今回電卓は 2 桁まで表示することができ、最初 1 が表示されています。これに対して、次のように高橋君は操作を行います。

1 回目の操作で、7 をかけます。1\times 7=7 であり、電卓には 7 が表示されます。
2 回目の操作で、13 をかけます。7\times 13=91 であり、電卓には 91 が表示されます。
3 回目の操作で、3 をかけます。91\times 3=273 であり、3 桁になってしまうため、電卓には 1 が表示されます。
4 回目の操作で、2 をかけます。1\times 2=2 であり、電卓には 2 が表示されます。
5 回目の操作で、5 をかけます。2\times 5=10 であり、電卓には 10 が表示されます。

入力例 2

2 1
2 5

出力例 2

Score : 200 points

Problem Statement

Takahashi has a calculator that initially displays 1.
He will perform N operations on the calculator.
In the i-th operation (1 \leq i \leq N), he multiplies the currently displayed number by a positive integer A_i.
However, the calculator can display at most K digits. If the result of the multiplication has (K+1) or more digits, the display shows 1 instead; otherwise, the result is shown correctly.

Find the number showing on the calculator after the N operations.

Constraints

1 \leq N \leq 100
1 \leq K \leq 18
1 \leq A_i < 10^K
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

Output the number shown on the calculator after the N operations.

Sample Input 1

5 2
7 13 3 2 5

Sample Output 1

This calculator can display at most two digits and initially shows 1. Takahashi operates as follows:

The 1st operation multiplies by 7. Since 1 \times 7 = 7, the calculator shows 7.
The 2nd operation multiplies by 13. Since 7 \times 13 = 91, the calculator shows 91.
The 3rd operation multiplies by 3. Since 91\times 3=273, which has three digits, the calculator shows 1.
The 4th operation multiplies by 2. Since 1\times 2=2, the calculator shows 2.
The 5th operation multiplies by 5. Since 2\times 5=10, the calculator shows 10.

Sample Input 2

2 1
2 5

Sample Output 2

E - Blue Spring

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

高橋君は N 日間の鉄道旅行を計画しています。
高橋君はそれぞれの日について、運賃の通常料金を払うか、1 日周遊パスを 1 枚使用するか選ぶことができます。

ここで、1\leq i\leq N について、i 日目の旅行にかかる運賃の通常料金は F_i 円です。
一方、1 日周遊パスは D 枚セットで P 円で発売されており、何セットでも購入することが可能ですが、D 枚単位でしか購入することができません。
また、購入したパスは 1 枚ずつ好きな日に使うことができ、旅行が終了した時点で余っていても構いません。

N 日間の旅行でかかる金額、すなわち 1 日周遊パスの購入にかかった代金と、1 日周遊パスを利用しなかった日における運賃の通常料金の合計金額の和としてあり得る最小値を求めてください。

制約

1\leq N\leq 2\times 10^5
1\leq D\leq 2\times 10^5
1\leq P\leq 10^9
1\leq F_i\leq 10^9
入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N D P
F_1 F_2 \ldots F_N

出力

N 日間の旅行でかかる金額としてあり得る最小値を出力せよ。

入力例 1

5 2 10
7 1 6 3 6

出力例 1

1 日周遊パスを 1 セットだけ購入し、1 日目と 3 日目に使用すると、合計金額は (10\times 1)+(0+1+0+3+6)=20 となり、このときかかる金額が最小となります。
よって、20 を出力します。

入力例 2

3 1 10
1 2 3

出力例 2

3 日間すべてにおいて運賃の通常料金を支払ったときに最小となります。

入力例 3

8 3 1000000000
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

出力例 3

3000000000

1 日周遊パスを 3 セット購入し、8 日間すべてにおいて 1 日周遊パスを利用したときに最小となります。
答えが 32 bit 整数型に収まらないことがあることに注意してください。

Score : 300 points

Problem Statement

Takahashi is planning an N-day train trip.
For each day, he can pay the regular fare or use a one-day pass.

Here, for 1\leq i\leq N, the regular fare for the i-th day of the trip is F_i yen.
On the other hand, a batch of D one-day passes is sold for P yen. You can buy as many passes as you want, but only in units of D.
Each purchased pass can be used on any day, and it is fine to have some leftovers at the end of the trip.

Find the minimum possible total cost for the N-day trip, that is, the cost of purchasing one-day passes plus the total regular fare for the days not covered by one-day passes.

Constraints

1\leq N\leq 2\times 10^5
1\leq D\leq 2\times 10^5
1\leq P\leq 10^9
1\leq F_i\leq 10^9
All input values are integers.

Input

The input is given from Standard Input in the following format:

N D P
F_1 F_2 \ldots F_N

Output

Print the minimum possible total cost for the N-day trip.

Sample Input 1

5 2 10
7 1 6 3 6

Sample Output 1

If he buys just one batch of one-day passes and uses them for the first and third days, the total cost will be (10\times 1)+(0+1+0+3+6)=20, which is the minimum cost needed.
Thus, print 20.

Sample Input 2

3 1 10
1 2 3

Sample Output 2

The minimum cost is achieved by paying the regular fare for all three days.

Sample Input 3

8 3 1000000000
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 3

3000000000

The minimum cost is achieved by buying three batches of one-day passes and using them for all eight days.
Note that the answer may not fit into a 32-bit integer type.