A - 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
B - Sanitize Hands

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

消毒液の入ったボトルがあり、その消毒液によってちょうど M 本の手を消毒することができます。

N 人の宇宙人が順に手の消毒を行いに来ます。
i 人目 (1\leq i\leq N) の宇宙人は H_i 本の手を持っており、それぞれ自身のすべての手を 1 回ずつ消毒したいと考えています。

何人目の宇宙人までがすべての手を消毒できるか求めてください。
ただし、ある宇宙人が消毒を始める時点で、自身のすべての手を消毒する分の消毒液が残っていなかったとしても、その宇宙人はその消毒液を使い切ってしまうものとします。

制約

  • 1\leq N,M\leq 100
  • 1\leq H_i\leq 100
  • 入力はすべて整数

入力

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

N M
H_1 H_2 \ldots H_N

出力

何人目の宇宙人までが自身のすべての手を消毒できるか出力せよ。


入力例 1

5 10
2 3 2 5 3

出力例 1

3

次の手順で宇宙人は自身の手を消毒します。

  • 1 人目の宇宙人は自身の 2 本の手を消毒します。残りの消毒液によって、10-2=8 本の手を消毒できます。
  • 2 人目の宇宙人は自身の 3 本の手を消毒します。残りの消毒液によって、8-3=5 本の手を消毒できます。
  • 3 人目の宇宙人は自身の 2 本の手を消毒します。残りの消毒液によって、5-2=3 本の手を消毒できます。
  • 4 人目の宇宙人は 5 本の手を持っていますが、消毒液は 3 本分しかないため消毒液を使い切り、かつ自身のすべての手を消毒できません。

よって、3 人目の宇宙人までが自身のすべての手を消毒できるため、3 を出力します。


入力例 2

5 10
2 3 2 3 5

出力例 2

4

入力例 3

1 5
1

出力例 3

1

すべての宇宙人が自身の手を消毒することができます。

Score : 100 points

Problem Statement

There is a bottle of disinfectant that can disinfect exactly M hands.

N aliens come one by one to disinfect their hands.
The i-th alien (1 \leq i \leq N) has H_i hands and wants to disinfect all of their hands once.

Determine how many aliens can disinfect all of their hands.
Here, even if there is not enough disinfectant left for an alien to disinfect all of their hands when they start, they will use up the remaining disinfectant.

Constraints

  • 1 \leq N, M \leq 100
  • 1 \leq H_i \leq 100
  • All input values are integers.

Input

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

N M
H_1 H_2 \ldots H_N

Output

Print the number of aliens who can disinfect all of their hands.


Sample Input 1

5 10
2 3 2 5 3

Sample Output 1

3

The aliens disinfect their hands in the following steps:

  • The first alien disinfects their two hands. The remaining disinfectant can disinfect 10-2=8 hands.
  • The second alien disinfects their three hands. The remaining disinfectant can disinfect 8-3=5 hands.
  • The third alien disinfects their two hands. The remaining disinfectant can disinfect 5-2=3 hands.
  • The fourth alien has five hands, but there is only enough disinfectant for three hands, so they use up the disinfectant without disinfecting all of their hands.

Thus, the first three aliens can disinfect all of their hands, so print 3.


Sample Input 2

5 10
2 3 2 3 5

Sample Output 2

4

Sample Input 3

1 5
1

Sample Output 3

1

All aliens can disinfect their hands.

C - Subscribers

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

整数 N が与えられます。
以下の指示に従って N の近似値を出力してください。

  • N が 10^3-1 以下ならば、N をそのまま出力する。
  • N が 10^3 以上 10^4-1 以下ならば、N の一の位を切り捨てて出力する。
  • N が 10^4 以上 10^5-1 以下ならば、N の十の位以下を切り捨てて出力する。
  • N が 10^5 以上 10^6-1 以下ならば、N の百の位以下を切り捨てて出力する。
  • N が 10^6 以上 10^7-1 以下ならば、N の千の位以下を切り捨てて出力する。
  • N が 10^7 以上 10^8-1 以下ならば、N の一万の位以下を切り捨てて出力する。
  • N が 10^8 以上 10^9-1 以下ならば、N の十万の位以下を切り捨てて出力する。

制約

  • N は 0 以上 10^9-1 以下の整数

入力

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

N

出力

答えを出力せよ。


入力例 1

20230603

出力例 1

20200000

20230603 は 10^7 以上 10^8-1 以下です。
したがって、一万以下の位を切り捨てて 20200000 を出力します。


入力例 2

0

出力例 2

0

入力例 3

304

出力例 3

304

入力例 4

500600

出力例 4

500000

Score : 200 points

Problem Statement

You are given an integer N.
Print an approximation of N according to the following instructions.

  • If N is less than or equal to 10^3-1, print N as it is.
  • If N is between 10^3 and 10^4-1, inclusive, truncate the ones digit of N and print the result.
  • If N is between 10^4 and 10^5-1, inclusive, truncate the tens digit and all digits below it of N and print the result.
  • If N is between 10^5 and 10^6-1, inclusive, truncate the hundreds digit and all digits below it of N and print the result.
  • If N is between 10^6 and 10^7-1, inclusive, truncate the thousands digit and all digits below it of N and print the result.
  • If N is between 10^7 and 10^8-1, inclusive, truncate the ten-thousands digit and all digits below it of N and print the result.
  • If N is between 10^8 and 10^9-1, inclusive, truncate the hundred-thousands digit and all digits below it of N and print the result.

Constraints

  • N is an integer between 0 and 10^9-1, inclusive.

Input

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

N

Output

Print the answer.


Sample Input 1

20230603

Sample Output 1

20200000

20230603 is between 10^7 and 10^8-1 (inclusive).
Therefore, truncate the ten-thousands digit and all digits below it, and print 20200000.


Sample Input 2

0

Sample Output 2

0

Sample Input 3

304

Sample Output 3

304

Sample Input 4

500600

Sample Output 4

500000
D - Practical Computing

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

以下のような N 個の整数列 A_0,\ldots,A_{N-1} を求めてください。

  • 各 i (0\leq i \leq N-1) について、A_i の長さは i+1 である。
  • 各 i,j (0\leq i \leq N-1, 0 \leq j \leq i) について、A_i の j+1 番目の値 a_{i,j} は次のように定められる。

    • j=0 または j=i の時、a_{i,j}=1
    • それ以外の時、a_{i,j} = a_{i-1,j-1} + a_{i-1,j}

制約

  • 1 \leq N \leq 30
  • N は整数

入力

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

N

出力

N 行出力せよ。 i 行目には A_{i-1} の値を順に空白区切りで出力せよ。


入力例 1

3

出力例 1

1
1 1
1 2 1

入力例 2

10

出力例 2

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1

Score : 200 points

Problem Statement

Find the N integer sequences A_0,\ldots,A_{N-1} defined as follows.

  • For each i (0\leq i \leq N-1), the length of A_i is i+1.
  • For each i and j (0\leq i \leq N-1, 0 \leq j \leq i), the (j+1)-th term of A_i, denoted by a_{i,j}, is defined as follows.
    • a_{i,j}=1, if j=0 or j=i.
    • a_{i,j} = a_{i-1,j-1} + a_{i-1,j}, otherwise.

Constraints

  • 1 \leq N \leq 30
  • N is an integer.

Input

Input is given from Standard Input in the following format:

N

Output

Print N lines. The i-th line should contain the terms of A_{i-1} separated by spaces.


Sample Input 1

3

Sample Output 1

1
1 1
1 2 1

Sample Input 2

10

Sample Output 2

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
E - Transportation Expenses

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

あるイベントには N 人が参加し、i 番目の人の交通費は A_i 円でした。

イベントの主催者である高橋くんは、交通費補助額の上限額 x を設定して、人 i には交通費補助額として \min(x,A_i) 円を支給することとしました。ここで x は非負整数である必要があります。

高橋くんの予算が M 円であり、N 人に渡す交通費補助額の総和を M 円以下にしたいとき、交通費補助額の上限額 x は最大でいくらにできますか?

ただし、交通費補助額の上限額を無限に大きくできる場合は代わりにそのことを報告してください。

制約

  • 1\leq N\leq 2\times 10^5
  • 1\leq M \leq 2\times 10^{14}
  • 1\leq A_i \leq 10^9
  • 入力される数値は全て整数

入力

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

N M
A_1 A_2 \ldots A_{N}

出力

予算の条件を満たすときの交通費補助額の上限額 x の最大値を整数として出力せよ。

ただし、交通費補助額の上限額を無限に大きくできる場合は代わりに infinite と出力せよ。


入力例 1

4 8
1 3 2 4

出力例 1

2

交通費補助額の上限額を 2 円にすると、N 人に渡す交通費補助額の総和は \min(2,1) + \min(2,3) + \min(2,2) + \min(2,4) = 7 円となり、予算の 8 円以下となります。

交通費補助額の上限額を 3 円にすると、N 人に渡す交通費補助額の総和は \min(3,1) + \min(3,3) + \min(3,2) + \min(3,4) = 9 円となり、予算の 8 円を超えてしまいます。

よって、交通費補助額の上限額の最大値は 2 円となります。


入力例 2

3 20
5 3 2

出力例 2

infinite

交通費補助額の上限額を無限に大きくできます。


入力例 3

10 23
2 5 6 5 2 1 7 9 7 2

出力例 3

2

Score : 300 points

Problem Statement

There are N people participating in an event, and the transportation cost for the i-th person is A_i yen.

Takahashi, the organizer of the event, decided to set a maximum limit x for the transportation subsidy. The subsidy for person i will be \min(x, A_i) yen. Here, x must be a non-negative integer.

Given that Takahashi's budget is M yen, and he wants the total transportation subsidy for all N people to be at most M yen, what is the maximum possible value of the subsidy limit x?

If the subsidy limit can be made infinitely large, report that instead.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^{14}
  • 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 M
A_1 A_2 \ldots A_{N}

Output

Print the maximum value of the subsidy limit x that satisfies the budget condition, as an integer.

If the subsidy limit can be made infinitely large, print infinite instead.


Sample Input 1

4 8
1 3 2 4

Sample Output 1

2

If the subsidy limit is set to 2 yen, the total transportation subsidy for all N people is \min(2,1) + \min(2,3) + \min(2,2) + \min(2,4) = 7 yen, which is within the budget of 8 yen.

If the subsidy limit is set to 3 yen, the total transportation subsidy for all N people is \min(3,1) + \min(3,3) + \min(3,2) + \min(3,4) = 9 yen, which exceeds the budget of 8 yen.

Therefore, the maximum possible value of the subsidy limit is 2 yen.


Sample Input 2

3 20
5 3 2

Sample Output 2

infinite

The subsidy limit can be made infinitely large.


Sample Input 3

10 23
2 5 6 5 2 1 7 9 7 2

Sample Output 3

2