AtCoder Daily Training EASY 2026/10/16 18:00start

A - Rotate

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

3 つの数字 x,y,z をこの順に並べてできる 3 桁の整数を xyz と表すことにします。

どの桁も 0 でない 3 桁の整数 abc が与えられるので、abc+bca+cab を求めてください。

制約

abc はどの桁も 0 でない 3 桁の整数

入力

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

abc

出力

答えを出力せよ。

入力例 1

出力例 1

123+231+312=666 となります。

入力例 2

出力例 2

999+999+999=2997 となります。

Score : 100 points

Problem Statement

Let xyz denote the 3-digit integer whose digits are x, y, z from left to right.

Given a 3-digit integer abc none of whose digits is 0, find abc+bca+cab.

Constraints

abc is a 3-digit integer abc none of whose digits is 0.

Input

Input is given from Standard Input in the following format:

abc

Output

Print the answer.

Sample Input 1

Sample Output 1

We have 123+231+312=666.

Sample Input 2

Sample Output 2

We have 999+999+999=2997.

B - Weekly Records

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

高橋君は N 週間の間、自分が歩いた歩数を記録しました。i 日目に歩いた歩数は A_i でした。

各週に高橋君が歩いた歩数の合計を求めてください。
より正確には、1 週目( 1 日目から 7 日目まで)の 7 日間の歩数の合計、2 週目( 8 日目から 14 日目まで)の 7 日間の歩数の合計、……をそれぞれ求めてください。

制約

1 \leq N \leq 10
0 \leq A_i \leq 10^5
入力は整数

入力

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

N
A_1 A_2 \ldots A_{7N}

出力

i 週目に歩いた歩数を B_i とする。B_1,B_2,\ldots,B_N をこの順に空白区切りで出力せよ。

入力例 1

2
1000 2000 3000 4000 5000 6000 7000 2000 3000 4000 5000 6000 7000 8000

出力例 1

28000 35000

高橋君は 1 週目に 1000+2000+3000+4000+5000+6000+7000=28000 歩あるき、2 週目に 2000+3000+4000+5000+6000+7000+8000=35000 歩あるきました。

入力例 2

3
14159 26535 89793 23846 26433 83279 50288 41971 69399 37510 58209 74944 59230 78164 6286 20899 86280 34825 34211 70679 82148

出力例 2

314333 419427 335328

Score : 100 points

Problem Statement

Takahashi has recorded the number of steps he walked for N weeks. He walked A_i steps on the i-th day.

Find the total number of steps Takahashi walked each week.
More precisely, find the sum of the steps for the first week (the 1-st through 7-th day), the sum of the steps for the second week (the 8-th through 14-th day), and so on.

Constraints

1 \leq N \leq 10
0 \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 \ldots A_{7N}

Output

Let B_i be the number of steps walked for the i-th week. Print B_1,B_2,\ldots,B_N in this order, separated by spaces.

Sample Input 1

2
1000 2000 3000 4000 5000 6000 7000 2000 3000 4000 5000 6000 7000 8000

Sample Output 1

28000 35000

For the first week, he walked 1000+2000+3000+4000+5000+6000+7000=28000 steps, and for the second week, he walked 2000+3000+4000+5000+6000+7000+8000=35000 steps.

Sample Input 2

3
14159 26535 89793 23846 26433 83279 50288 41971 69399 37510 58209 74944 59230 78164 6286 20899 86280 34825 34211 70679 82148

Sample Output 2

314333 419427 335328

C - Qual B

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

あるプログラミングコンテストの予選に N 人が参加し、参加者全員が異なる順位を得ました。
長さ N の文字列 S が与えられ、この文字列は決勝への参加希望の有無を表現します。具体的には下記の通りです。

S の i 文字目が o なら、予選 i 位の参加者が決勝への参加を希望した。
S の i 文字目が x なら、予選 i 位の参加者が決勝への参加を希望しなかった。

決勝への参加を希望した参加者のうち順位の小さい方から K 人が予選を通過します。

以下の条件を満たす長さ N の文字列 T を出力してください。

予選 i 位の参加者が予選を通過する場合、 T の i 文字目は o
予選 i 位の参加者が予選を通過しない場合、 T の i 文字目は x

制約

N,K は整数
1 \le K \le N \le 100
S は o と x からなる長さ N の文字列
S には少なくとも K 個の o が含まれる

入力

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

N K
S

出力

答えを出力せよ。

入力例 1

10 3
oxxoxooxox

出力例 1

oxxoxoxxxx

この入力の場合、予選の参加者は N=10 人であり、予選を通過する人数は K=3 人です。

予選 1 位の参加者は決勝への参加を希望しているため、予選を通過します。この時点で、通過者は 1 人です。
予選 2,3 位の参加者は決勝への参加を希望していないため、予選を通過しません。
予選 4 位の参加者は決勝への参加を希望しているため、予選を通過します。この時点で、通過者は 2 人です。
予選 5 位の参加者は決勝への参加を希望していないため、予選を通過しません。
予選 6 位の参加者は決勝への参加を希望しているため、予選を通過します。この時点で、通過者は 3 人です。
ここで、予選を通過した人数が 3 人となりました。なので、予選 7 位以下の参加者は予選を通過しません。

Score : 200 points

Problem Statement

There were N contestants in the qualification round of a programming contest. All contestants got distinct ranks.
You are given a length-N string S, which represents whether the contestants want to participate in the final round or not. Specifically,

if the i-th character of S is o, the contestant ranked i-th in the qualification wants to participate in the final;
if the i-th character of S is x, the contestant ranked i-th in the qualification does not want to participate in the final.

Among those who want to participate in the final, K contestants with the smallest ranks advance to the final.

Print a string T of length N that satisfies the following conditions:

if the contestant ranked i-th in the qualification advances to the final, the i-th character of T is o;
if the contestant ranked i-th in the qualification does not advance to the final, the i-th character of T is x.

Constraints

N and K are integers.
1 \le K \le N \le 100
S is a string of length N consisting of o and x.
S has at least K o's.

Input

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

N K
S

Output

Print the answer.

Sample Input 1

10 3
oxxoxooxox

Sample Output 1

oxxoxoxxxx

In this input, N=10 people took part in the qualification round, and K=3 of them advance to the final.

The participant who ranked 1-st in the qualification wants to participate in the final, so the participant advances to the final. 1 participant has advanced so far.
The participants who ranked 2-nd and 3-rd in the qualification do not want to participate in the final, so the participants do not advance to the final.
The participant who ranked 4-th in the qualification wants to participate in the final, so the participant advances to the final. 2 participants have advanced so far.
The participants who ranked 5-th in the qualification does not want to participate in the final, so the participant does not advance to the final.
The participant who ranked 6-th in the qualification wants to participate in the final, so the participant advances to the final. 3 participants have advanced so far.
Now that 3 people have advanced to the final, no participants ranked 7-th or lower advance to the final.

D - Sensor Data Logging

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

ある測定では、時刻 0,1,\dots,T におけるセンサーの測定値を以下の規則で記録します。

時刻 0 では、測定値を保存する。
時刻 1,2,\dots,T では、「現時刻の測定値」と「直前に保存された測定値」との差の絶対値が X 以上であるとき、またその時に限り値を保存する。

時刻 i=0,1,\dots,T におけるセンサーの測定値は A_i でした。

測定値が保存された時刻と保存された値とを、時刻の昇順に出力してください。

制約

1 \le T \le 100
1 \le X \le 100
0 \le A_i \le 100
入力はすべて整数

入力

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

T X
A_0 A_1 \dots A_T

出力

測定値が k 回保存され、そのうち時刻の昇順に並べた時に i 回目の時刻が t_i 、測定値が a_i であったとき、以下の形式で出力せよ。

t_1 a_1
t_2 a_2
\vdots
t_k a_k

入力例 1

6 10
30 35 40 21 30 12 31

出力例 1

測定は以下の流れで進行します。

時刻 0 の測定値は 30 であった。これを保存する。
時刻 1 の測定値は 35 であった。最後に保存された測定値は 30 であり、この値との差の絶対値が 10 未満であるため、保存しない。
時刻 2 の測定値は 40 であった。最後に保存された測定値は 30 であり、この値との差の絶対値が 10 以上であるため、保存する。
時刻 3 の測定値は 21 であった。最後に保存された測定値は 40 であり、この値との差の絶対値が 10 以上であるため、保存する。
時刻 4 の測定値は 30 であった。最後に保存された測定値は 21 であり、この値との差の絶対値が 10 未満であるため、保存しない。
時刻 5 の測定値は 12 であった。最後に保存された測定値は 21 であり、この値との差の絶対値が 10 未満であるため、保存しない。
時刻 6 の測定値は 31 であった。最後に保存された測定値は 21 であり、この値との差の絶対値が 10 以上であるため、保存する。

Score : 200 points

Problem Statement

In a certain measurement, the sensor readings at times 0,1,\dots,T are recorded according to the following rules.

At time 0, the reading is saved.
At times 1,2,\dots,T, the reading is saved if and only if the absolute difference between the current reading and the most recently saved reading is at least X.

The sensor reading at time i=0,1,\dots,T was A_i.

Output the times at which readings were saved and the saved values, in ascending order of time.

Constraints

1 \le T \le 100
1 \le X \le 100
0 \le A_i \le 100
All input values are integers.

Input

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

T X
A_0 A_1 \dots A_T

Output

If k readings were saved, and the i-th saved reading in ascending order of time was at time t_i with value a_i, output in the following format:

t_1 a_1
t_2 a_2
\vdots
t_k a_k

Sample Input 1

6 10
30 35 40 21 30 12 31

Sample Output 1

The measurement proceeds as follows.

The reading at time 0 is 30. Save it.
The reading at time 1 is 35. The most recently saved reading is 30, and the absolute difference is less than 10, so it is not saved.
The reading at time 2 is 40. The most recently saved reading is 30, and the absolute difference is at least 10, so it is saved.
The reading at time 3 is 21. The most recently saved reading is 40, and the absolute difference is at least 10, so it is saved.
The reading at time 4 is 30. The most recently saved reading is 21, and the absolute difference is less than 10, so it is not saved.
The reading at time 5 is 12. The most recently saved reading is 21, and the absolute difference is less than 10, so it is not saved.
The reading at time 6 is 31. The most recently saved reading is 21, and the absolute difference is at least 10, so it is saved.

E - Blue Spring

Time Limit: 2 sec / Memory Limit: 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.