A - Favorite Sound

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100 点

問題文

高橋くんは、自動販売機でジュースを買ったときの音が好きです。

その音は 1 回 A 円で聞くことができます。

高橋くんは B 円持っていますが、お気に入りの音を C 回聞くと満足するため、B 円で最大 C 回まで聞けるだけ聞きます。

高橋くんはお気に入りの音を何回聞くことになるでしょうか。

制約

  • 入力は全て整数である。
  • 1 \leq A, B, C \leq 100

入力

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

A B C

出力

高橋くんはお気に入りの音を何回聞くことになるか出力せよ。

入力例 1

2 11 4

出力例 1

4

高橋くんは 8 円以上持っているのでお気に入りの音を 4 回聞いて満足します。

入力例 2

3 9 5

出力例 2

3

高橋くんが満足できないこともあります。

入力例 3

100 1 10

出力例 3

0

Score : 100 points

Problem Statement

Takahashi likes the sound when he buys a drink from a vending machine.

That sound can be heard by spending A yen (the currency of Japan) each time.

Takahashi has B yen. He will hear the sound as many times as he can with that money, but at most C times, as he would be satisfied at that time.

How many times will he hear the sound?

Constraints

  • All values in input are integers.
  • 1 \leq A, B, C \leq 100

Input

Input is given from Standard Input in the following format:

A B C

Output

Print the number of times Takahashi will hear his favorite sound.

Sample Input 1

2 11 4

Sample Output 1

4

Since he has not less than 8 yen, he will hear the sound four times and be satisfied.

Sample Input 2

3 9 5

Sample Output 2

3

He may not be able to be satisfied.

Sample Input 3

100 1 10

Sample Output 3

0
B - K-th Common Divisor

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 200 点

問題文

正整数 A, B が与えられます。

A も B も割り切る正整数のうち、K 番目に大きいものを求めてください。

なお、与えられる入力では、A も B も割り切る正整数のうち K 番目に大きいものが存在することが保証されます。

制約

  • 入力は全て整数である。
  • 1 \leq A, B \leq 100
  • A も B も割り切る正整数のうち、K 番目に大きいものが存在する。
  • K \geq 1

入力

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

A B K

出力

A も B も割り切る正整数のうち、K 番目に大きいものを出力せよ。

入力例 1

8 12 2

出力例 1

2

8 と 12 を割り切る正整数は 1, 2, 4 です。 この中で 2 番目に大きいものは 2 です。

入力例 2

100 50 4

出力例 2

5

入力例 3

1 1 1

出力例 3

1

Score : 200 points

Problem Statement

You are given positive integers A and B.

Find the K-th largest positive integer that divides both A and B.

The input guarantees that there exists such a number.

Constraints

  • All values in input are integers.
  • 1 \leq A, B \leq 100
  • The K-th largest positive integer that divides both A and B exists.
  • K \geq 1

Input

Input is given from Standard Input in the following format:

A B K

Output

Print the K-th largest positive integer that divides both A and B.

Sample Input 1

8 12 2

Sample Output 1

2

Three positive integers divides both 8 and 12: 1, 2 and 4. Among them, the second largest is 2.

Sample Input 2

100 50 4

Sample Output 2

5

Sample Input 3

1 1 1

Sample Output 3

1
C - Unification

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

机の上に N 個のキューブが縦に積まれています。長さ N の文字列 S が与えられます。

下から i 番目のキューブの色は、S の i 文字目が 0 のとき赤色、1 のとき青色です。

あなたは、赤色のキューブと青色のキューブが隣り合っているような部分を選んで、それら 2 個のキューブを取り除く操作を何度でも行えます。

このとき、取り除いたキューブの上にあったキューブは真下の物体の上に落下します。

最大で何個のキューブを取り除けるでしょうか。

制約

  • 1 \leq N \leq 10^5
  • |S| = N
  • S の各文字は 0 または 1 である。

入力

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

S

出力

最大で何個のキューブを取り除けるかを出力せよ。

入力例 1

0011

出力例 1

4

以下の順に操作を行うと 4 個全てのキューブを取り除けます。

  • 下から 2 番目のキューブと 3 番目のキューブを取り除きます。その結果、下から 4 番目のキューブが下から 1 番目のキューブの上に落下します。
  • 下から 1 番目のキューブと 2 番目のキューブを取り除きます。

入力例 2

11011010001011

出力例 2

12

入力例 3

0

出力例 3

0

Score : 300 points

Problem Statement

There are N cubes stacked vertically on a desk.

You are given a string S of length N. The color of the i-th cube from the bottom is red if the i-th character in S is 0, and blue if that character is 1.

You can perform the following operation any number of times: choose a red cube and a blue cube that are adjacent, and remove them. Here, the cubes that were stacked on the removed cubes will fall down onto the object below them.

At most how many cubes can be removed?

Constraints

  • 1 \leq N \leq 10^5
  • |S| = N
  • Each character in S is 0 or 1.

Input

Input is given from Standard Input in the following format:

S

Output

Print the maximum number of cubes that can be removed.

Sample Input 1

0011

Sample Output 1

4

All four cubes can be removed, by performing the operation as follows:

  • Remove the second and third cubes from the bottom. Then, the fourth cube drops onto the first cube.
  • Remove the first and second cubes from the bottom.

Sample Input 2

11011010001011

Sample Output 2

12

Sample Input 3

0

Sample Output 3

0
D - Decayed Bridges

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

N 個の島と M 本の橋があります。

i 番目の橋は A_i 番目の島と B_i 番目の島を繋いでおり、双方向に行き来可能です。

はじめ、どの 2 つの島についてもいくつかの橋を渡って互いに行き来できます。

調査の結果、老朽化のためこれら M 本の橋は 1 番目の橋から順に全て崩落することがわかりました。

「いくつかの橋を渡って互いに行き来できなくなった 2 つの島の組 (a, b) (a < b) の数」を不便さと呼ぶことにします。

各 i (1 \leq i \leq M) について、i 番目の橋が崩落した直後の不便さを求めてください。

制約

  • 入力は全て整数である。
  • 2 \leq N \leq 10^5
  • 1 \leq M \leq 10^5
  • 1 \leq A_i < B_i \leq N
  • (A_i, B_i) の組は全て異なる。
  • 初期状態における不便さは 0 である。

入力

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

N M
A_1 B_1
A_2 B_2
\vdots
A_M B_M

出力

i = 1, 2, ..., M の順に、i 番目の橋が崩落した直後の不便さを出力せよ。 答えが 32 bit整数型に収まらない場合があることに注意すること。

入力例 1

4 5
1 2
3 4
1 3
2 3
1 4

出力例 1

0
0
4
5
6

例えば、1 から 3 番目の橋が崩落したとき、(1, 2), (1, 3), (2, 4), (3, 4) の島の組について行き来できなくなるので不便さは 4 です。

入力例 2

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

出力例 2

8
9
12
14
15

入力例 3

2 1
1 2

出力例 3

1

Score : 400 points

Problem Statement

There are N islands and M bridges.

The i-th bridge connects the A_i-th and B_i-th islands bidirectionally.

Initially, we can travel between any two islands using some of these bridges.

However, the results of a survey show that these bridges will all collapse because of aging, in the order from the first bridge to the M-th bridge.

Let the inconvenience be the number of pairs of islands (a, b) (a < b) such that we are no longer able to travel between the a-th and b-th islands using some of the bridges remaining.

For each i (1 \leq i \leq M), find the inconvenience just after the i-th bridge collapses.

Constraints

  • All values in input are integers.
  • 2 \leq N \leq 10^5
  • 1 \leq M \leq 10^5
  • 1 \leq A_i < B_i \leq N
  • All pairs (A_i, B_i) are distinct.
  • The inconvenience is initially 0.

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1
A_2 B_2
\vdots
A_M B_M

Output

In the order i = 1, 2, ..., M, print the inconvenience just after the i-th bridge collapses. Note that the answer may not fit into a 32-bit integer type.

Sample Input 1

4 5
1 2
3 4
1 3
2 3
1 4

Sample Output 1

0
0
4
5
6

For example, when the first to third bridges have collapsed, the inconvenience is 4 since we can no longer travel between the pairs (1, 2), (1, 3), (2, 4) and (3, 4).

Sample Input 2

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

Sample Output 2

8
9
12
14
15

Sample Input 3

2 1
1 2

Sample Output 3

1