A - Integer Sum

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

N 個の整数 A_1,A_2,\dots,A_N が与えられます。

N 個の整数を合計した値を求めてください。

制約

  • 1 \le N \le 100
  • 1 \le A_i \le 100
  • 入力はすべて整数

入力

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

N
A_1 A_2 \dots A_N

出力

答えを出力せよ。

入力例 1

3
2 7 2

出力例 1

11

3 個の整数 2,7,2 が与えられます。

答えは 2 + 7 + 2 = 11 です。

入力例 2

1
3

出力例 2

3

Score : 100 points

Problem Statement

You are given N integers A_1,A_2,\dots, and A_N.

Find the sum of the N integers.

Constraints

  • 1 \le N \le 100
  • 1 \le A_i \le 100
  • All values in the input are integers.

Input

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

N
A_1 A_2 \dots A_N

Output

Print the answer.

Sample Input 1

3
2 7 2

Sample Output 1

11

You are given three integers: 2, 7, and 2.

The answer is 2 + 7 + 2 = 11.

Sample Input 2

1
3

Sample Output 2

3
B - Count Down

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

N 以下の非負整数を大きい方から順にすべて出力してください。

制約

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

入力

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

N

出力

N 以下の非負整数が X 個存在するとき、X 行出力せよ。
i=1,2,\ldots,X に対し、i 行目には N 以下の非負整数のうち大きい方から i 番目のものを出力せよ。

入力例 1

3

出力例 1

3
2
1
0

3 以下の非負整数は 0,1,2,3 の 4 個です。
1 行目に 3 を、2 行目に 2 を、3 行目に 1 を、4 行目に 0 を出力することでこれらを大きい方から順に出力したことになります。

入力例 2

22

出力例 2

22
21
20
19
18
17
16
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
0

Score : 100 points

Problem Statement

Print all non-negative integers less than or equal to N in descending order.

Constraints

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

Input

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

N

Output

Print X lines, where X is the number of non-negative integers less than or equal to N.
For each i=1, 2, \ldots, X, the i-th line should contain the i-th greatest non-negative integer less than or equal to N.

Sample Input 1

3

Sample Output 1

3
2
1
0

We have four non-negative integers less than or equal to 3, which are 0, 1, 2, and 3.
To print them in descending order, print 3 in the first line, 2 in the second, 1 in the third, and 0 in the fourth.

Sample Input 2

22

Sample Output 2

22
21
20
19
18
17
16
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
0
C - 1D Akari

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 250 点

問題文

. および # からなる文字列 S が与えられます。

以下の条件を全て満たす文字列 T のうち、 o の文字数が最大となるものを一つ求めてください。

  • T の長さは S の長さと等しい。
  • T は .、#、o からなる。
  • S_i= # であるとき、またそのときに限り T_i= # である。
  • T_i=T_j= o (i < j) ならば、 T_{i+1},\ldots,T_{j-1} の中に # が 1 つ以上存在する。

制約

  • S は . および # からなる長さ 1 以上 100 以下の文字列

入力

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

S

出力

条件を全て満たす文字列 T のうち、 o の文字数が最大となるものを一つ出力せよ。

そのような文字列が複数ある場合、どれを出力しても正答となる。

入力例 1

#..#.

出力例 1

#o.#o

T= #o.#o とすると全ての条件を満たすことが確認できます。

全ての条件を満たす T であって、 o の文字数が 2 より多い文字列は存在しないので #o.#o を出力すると正答となります。

この他にも #.o#o を出力しても正答となります。

入力例 2

#

出力例 2

#

入力例 3

.....

出力例 3

..o..

この他にも o....、.o...、...o.、....o を出力しても正答となります。

入力例 4

...#..#.##.#.

出力例 4

o..#.o#o##o#o

Score : 250 points

Problem Statement

You are given a string S consisting of . and #.

Among all strings T that satisfy all of the following conditions, find one with the maximum number of os.

  • The length of T is equal to the length of S.
  • T consists of ., #, or o.
  • T_i= # if and only if S_i= #.
  • If T_i=T_j= o (i < j), then there exists at least one # among T_{i+1},\ldots,T_{j-1}.

Constraints

  • S is a string consisting of . and # with length between 1 and 100, inclusive.

Input

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

S

Output

Output one string with the maximum number of os among all strings T that satisfy all conditions.

If there are multiple such strings, printing any of them will be considered correct.

Sample Input 1

#..#.

Sample Output 1

#o.#o

Setting T= #o.#o satisfies all conditions.

There is no string T that satisfies all conditions and has more than two os, so outputting #o.#o is correct.

Outputting #.o#o is also correct.

Sample Input 2

#

Sample Output 2

#

Sample Input 3

.....

Sample Output 3

..o..

Outputting o...., .o..., ...o., or ....o is also correct.

Sample Input 4

...#..#.##.#.

Sample Output 4

o..#.o#o##o#o
D - AtCoder Amusement Park

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

AtCoder 遊園地には K 人乗りのアトラクションがあります。 現在、このアトラクションの待機列には N グループが並んでいます。

先頭から i 番目 (1\leq i\leq N) のグループは A _ i 人組です。 すべての i (1\leq i\leq N) について、A _ i\leq K です。

高橋君はこのアトラクションのスタッフとして、並んでいるグループを次の手順に従って誘導します。

はじめ、アトラクションには誰も誘導されておらず、空席は K 個あります。

  1. 待機列に並んでいるグループがない場合、アトラクションをスタートさせ、誘導を終了する。
  2. アトラクションの空席の数と待機列の先頭に並んでいるグループの人数を比較し、次のどちらかを行う。
    • 待機列の先頭に並んでいるグループの人数よりアトラクションの空席の数のほうが少ない場合、アトラクションをスタートさせる。 スタートしたのち、アトラクションの空席が K 個になる。
    • そうでない場合、待機列の先頭に並んでいるグループを全員アトラクションへ誘導する。 先頭のグループが待機列から取り出され、アトラクションの空席がグループの人数ぶんだけ減少する。
  3. 1 に戻る。

ただし、誘導を開始したあとに追加でグループが並ぶことはないとします。 以上の条件のもとで、この手順が有限回で終了することが示せます。

高橋君が誘導を開始してから誘導を終了するまで、何回アトラクションをスタートさせるか求めてください。

制約

  • 1\leq N\leq100
  • 1\leq K\leq100
  • 1\leq A _ i\leq K\ (1\leq i\leq N)
  • 入力はすべて整数

入力

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

N K
A _ 1 A _ 2 \ldots A _ N

出力

答えを出力せよ。

入力例 1

7 6
2 5 1 4 1 2 3

出力例 1

4

はじめ、7 つのグループは以下のように並んでいます。

高橋君の誘導の様子の一部を以下の図に示します。

  • はじめ、先頭に並んでいるグループは 2 人のグループで、空席は 6 個です。よって、高橋君は先頭のグループをアトラクションに誘導し、空席は 4 個になります。
  • 次に、先頭に並んでいるグループは 5 人のグループで、空席の個数 4 より多いため、アトラクションをスタートさせます。
  • 空席が 6 個になったため、先頭のグループをアトラクションに誘導し、空席は 1 個になります。
  • 次に先頭に並んでいるのは 1 人なので、アトラクションに誘導し、空席は 0 個になります。

すべての誘導が終了するまでに、高橋君は 4 回アトラクションをスタートさせることになります。 よって、4 を出力してください。

入力例 2

7 10
1 10 1 10 1 10 1

出力例 2

7

入力例 3

15 100
73 8 55 26 97 48 37 47 35 55 5 17 62 2 60

出力例 3

8

Score: 200 points

Problem Statement

The AtCoder amusement park has an attraction that can accommodate K people. Now, there are N groups lined up in the queue for this attraction.

The i-th group from the front (1\leq i\leq N) consists of A_i people. For all i (1\leq i\leq N), it holds that A_i \leq K.

Takahashi, as a staff member of this attraction, will guide the groups in the queue according to the following procedure.

Initially, no one has been guided to the attraction, and there are K empty seats.

  1. If there are no groups in the queue, start the attraction and end the guidance.
  2. Compare the number of empty seats in the attraction with the number of people in the group at the front of the queue, and do one of the following:
    • If the number of empty seats is less than the number of people in the group at the front, start the attraction. Then, the number of empty seats becomes K again.
    • Otherwise, guide the entire group at the front of the queue to the attraction. The front group is removed from the queue, and the number of empty seats decreases by the number of people in the group.
  3. Go back to step 1.

Here, no additional groups will line up after the guidance has started. Under these conditions, it can be shown that this procedure will end in a finite number of steps.

Determine how many times the attraction will be started throughout the guidance.

Constraints

  • 1\leq N\leq 100
  • 1\leq K\leq 100
  • 1\leq A_i\leq K\ (1\leq i\leq N)
  • 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

Print the answer.

Sample Input 1

7 6
2 5 1 4 1 2 3

Sample Output 1

4

Initially, the seven groups are lined up as follows:

Part of Takahashi's guidance is shown in the following figure:

  • Initially, the group at the front has 2 people, and there are 6 empty seats. Thus, he guides the front group to the attraction, leaving 4 empty seats.
  • Next, the group at the front has 5 people, which is more than the 4 empty seats, so the attraction is started.
  • After the attraction is started, there are 6 empty seats again, so the front group is guided to the attraction, leaving 1 empty seat.
  • Next, the group at the front has 1 person, so they are guided to the attraction, leaving 0 empty seats.

In total, he starts the attraction four times before the guidance is completed. Therefore, print 4.

Sample Input 2

7 10
1 10 1 10 1 10 1

Sample Output 2

7

Sample Input 3

15 100
73 8 55 26 97 48 37 47 35 55 5 17 62 2 60

Sample Output 3

8
E - New Skill Acquired

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

高橋君はゲームをしています。このゲームには 1 から N の番号がついた N 個のスキルがあります。

N 個の整数の組 (A_1,B_1), \dots,(A_N,B_N) が与えられます。
(A_i,B_i)=(0,0) のとき高橋君はスキル i を習得済みです。
そうでないとき、スキル A_i,B_i の少なくとも一方を習得済みのときかつそのときに限りスキル i を習得することができます。

既に取得済みのスキルも含め、高橋君が最終的に習得することができるスキルの個数を求めてください。

制約

  • 1\leq N \leq 2\times 10^5
  • (A_i,B_i)=(0,0) または 1\leq A_i,B_i \leq N
  • 入力は全て整数

入力

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

N
A_1 B_1
A_2 B_2
\vdots
A_N B_N

出力

答えを出力せよ。

入力例 1

6
0 0
1 3
3 2
5 5
4 6
6 4

出力例 1

3

最初、高橋君はスキル 1 を習得済みです。スキル 1 を習得済みのためスキル 2 を習得することができ、スキル 2 を習得したことでスキル 3 を習得できます。
スキル 4,5,6 を習得することはできないため、答えは 3 となります。

入力例 2

4
0 0
0 0
0 0
0 0

出力例 2

4

Score : 300 points

Problem Statement

Takahashi is playing a game. This game has N skills numbered 1 through N.

You are given N pairs of integers (A_1,B_1), \dots,(A_N,B_N).
If (A_i,B_i)=(0,0), then Takahashi has already learned skill i.
Otherwise, Takahashi can learn skill i if and only if at least one of skills A_i and B_i has already been learned.

Including the skills already learned, find the number of skills that Takahashi can ultimately learn.

Constraints

  • 1\leq N \leq 2\times 10^5
  • (A_i,B_i)=(0,0) or 1\leq A_i,B_i \leq N
  • All input values are integers.

Input

The 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

Output the answer.

Sample Input 1

6
0 0
1 3
3 2
5 5
4 6
6 4

Sample Output 1

3

At first, Takahashi has already learned skill 1. Because skill 1 has been learned, skill 2 can be learned, and learning skill 2 enables learning skill 3. Since it is impossible to learn skills 4,5,6, the answer is 3.

Sample Input 2

4
0 0
0 0
0 0
0 0

Sample Output 2

4