A - Full Moon

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

高橋くんは満月が好きです。

今日を 1 日目とすると、今日以降で満月を見られる最初の日は M 日目です。以後は P 日ごと、つまり M+P 日目、M+2P 日目、\ldots に満月を見られます。

1 日目から N 日目まで（両端を含む）の中で、高橋くんが満月を見られる日の数を求めてください。

制約

  • 1\leq N\leq 2\times 10^5
  • 1\leq M \leq P \leq 2\times 10^5
  • 入力される数値は全て整数

入力

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

N M P

出力

答えを整数として出力せよ。

入力例 1

13 3 5

出力例 1

3

満月を見られる日は、3 日目、8 日目、13 日目、18 日目、\ldots です。

1 日目から 13 日目までの中で高橋くんが満月を見られる日は、3 日目、8 日目、13 日目の 3 個です。

入力例 2

5 6 6

出力例 2

0

高橋くんが満月を見られる日が存在しない場合もあります。

入力例 3

200000 314 318

出力例 3

628

Score : 100 points

Problem Statement

Takahashi likes full moons.

Let today be day 1. The first day on or after today on which he can see a full moon is day M. After that, he can see a full moon every P days, that is, on day M+P, day M+2P, and so on.

Find the number of days between day 1 and day N, inclusive, on which he can see a full moon.

Constraints

  • 1\leq N\leq 2\times 10^5
  • 1\leq M \leq P \leq 2\times 10^5
  • All input values are integers.

Input

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

N M P

Output

Print the answer as an integer.

Sample Input 1

13 3 5

Sample Output 1

3

He can see a full moon on day 3, 8, 13, 18, and so on.

From day 1 to 13, he can see a full moon on three days: day 3, 8, and 13.

Sample Input 2

5 6 6

Sample Output 2

0

There may be no days he can see a full moon.

Sample Input 3

200000 314 318

Sample Output 3

628
B - Overall Winner

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

高橋くんと青木くんが N 回の試合を行いました。 これらの試合の結果を表す長さ N の文字列 S が与えられます。 i 回目の試合の勝者は、S の i 文字目が T ならば高橋くん、A ならば青木くんです。

高橋くんと青木くんのうち、勝った試合の数が多い方を総合勝者とします。 ただし、勝った試合の数が同じである場合は、先にその勝ち数に達した者を総合勝者とします。 高橋くんと青木くんのどちらが総合勝者であるか求めてください。

制約

  • 1\leq N \leq 100
  • N は整数
  • S は T および A からなる長さ N の文字列

入力

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

N
S

出力

総合勝者が高橋くんならば T を、青木くんならば A を出力せよ。

入力例 1

5
TTAAT

出力例 1

T

高橋くんは 3 回の試合に勝ち、青木くんは 2 回の試合に勝ちました。 よって、勝った試合の数が多い高橋くんが総合勝者です。

入力例 2

6
ATTATA

出力例 2

T

高橋くんと青木くんのどちらも 3 回の試合に勝ちました。 また、高橋くんは 5 回目の試合で 3 勝目に達し、青木くんは 6 回目の試合で 3 勝目に達しました。 よって、先に 3 勝目に達した高橋くんが総合勝者です。

入力例 3

1
A

出力例 3

A

Score : 100 points

Problem Statement

Takahashi and Aoki played N games. You are given a string S of length N, representing the results of these games. Takahashi won the i-th game if the i-th character of S is T, and Aoki won that game if it is A.

The overall winner between Takahashi and Aoki is the one who won more games than the other. If they had the same number of wins, the overall winner is the one who reached that number of wins first. Find the overall winner: Takahashi or Aoki.

Constraints

  • 1\leq N \leq 100
  • N is an integer.
  • S is a string of length N consisting of T and A.

Input

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

N
S

Output

If the overall winner is Takahashi, print T; if it is Aoki, print A.

Sample Input 1

5
TTAAT

Sample Output 1

T

Takahashi won three games, and Aoki won two. Thus, the overall winner is Takahashi, who won more games.

Sample Input 2

6
ATTATA

Sample Output 2

T

Both Takahashi and Aoki won three games. Takahashi reached three wins in the fifth game, and Aoki in the sixth game. Thus, the overall winner is Takahashi, who reached three wins first.

Sample Input 3

1
A

Sample Output 3

A
C - Slimes

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

A 匹のスライムがいます。

すぬけくんが 1 回叫ぶたびに、スライムは K 倍に増殖します。

スライムが B 匹以上になるには、すぬけくんは最小で何回叫ぶ必要があるでしょうか？

制約

  • 1 \leq A \leq B \leq 10^9
  • 2 \leq K \leq 10^9
  • 入力は全て整数

入力

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

A B K

出力

答えを出力せよ。

入力例 1

1 4 2

出力例 1

2

はじめ、スライムが 1 匹います。すぬけくんが 1 回叫ぶとスライムは 2 匹になり、 2 回叫ぶとスライムは 4 匹になります。4 匹以上になるためには、最小で 2 回叫ぶ必要があります。

入力例 2

7 7 10

出力例 2

0

はじめからスライムは 7 匹います。

入力例 3

31 415926 5

出力例 3

6

Score : 200 points

Problem Statement

There are A slimes.

Each time Snuke shouts, the slimes multiply by K times.

In order to have B or more slimes, at least how many times does Snuke need to shout?

Constraints

  • 1 \leq A \leq B \leq 10^9
  • 2 \leq K \leq 10^9
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

A B K

Output

Print the answer.

Sample Input 1

1 4 2

Sample Output 1

2

We start with one slime. After Snuke's first shout, we have two slimes; after his second shout, we have four slimes. Thus, he needs to shout at least twice to have four or more slimes.

Sample Input 2

7 7 10

Sample Output 2

0

We have seven slimes already at the start.

Sample Input 3

31 415926 5

Sample Output 3

6
D - Count Distinct Integers

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

長さ N の正整数列 a = (a_1, a_2, \dots, a_N) には何種類の整数が現れますか？

制約

  • 1 \leq N \leq 1000
  • 1 \leq a_i \leq 10^9 \, (1 \leq i \leq N)
  • 入力は全て整数

入力

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

N
a_1 \ldots a_N

出力

答えを出力せよ。

入力例 1

6
1 4 1 2 2 1

出力例 1

3

1, 2, 4 の 3 種類の整数が現れます。

入力例 2

1
1

出力例 2

1

入力例 3

11
3 1 4 1 5 9 2 6 5 3 5

出力例 3

7

Score : 200 points

Problem Statement

In a sequence of N positive integers a = (a_1, a_2, \dots, a_N), how many different integers are there?

Constraints

  • 1 \leq N \leq 1000
  • 1 \leq a_i \leq 10^9 \, (1 \leq i \leq N)
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
a_1 \ldots a_N

Output

Print the answer.

Sample Input 1

6
1 4 1 2 2 1

Sample Output 1

3

There are three different integers: 1, 2, 4.

Sample Input 2

1
1

Sample Output 2

1

Sample Input 3

11
3 1 4 1 5 9 2 6 5 3 5

Sample Output 3

7
E - Max MEX

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

長さ N の非負整数列 A が与えられます。
A から K 要素を選んで順序を保ったまま抜き出した列を B としたとき、 MEX(B) としてありえる最大値を求めてください。

但し、数列 X に対して MEX(X) は以下の条件を満たす唯一の非負整数 m として定義されます。

  • 0 \le i < m を満たす全ての整数 i が X に含まれる。
  • m が X に含まれない。

制約

  • 入力は全て整数
  • 1 \le K \le N \le 3 \times 10^5
  • 0 \le A_i \le 10^9

入力

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

N K
A_1 A_2 \dots A_N

出力

答えを出力せよ。

入力例 1

7 3
2 0 2 3 2 1 9

出力例 1

3

この入力では A=(2,0,2,3,2,1,9) であり、ここから K=3 要素を選んで抜き出して数列 B を得ます。例えば、

  • 1,2,3 要素目を抜き出した時、 MEX(B)=MEX(2,0,2)=1
  • 3,4,6 要素目を抜き出した時、 MEX(B)=MEX(2,3,1)=0
  • 2,6,7 要素目を抜き出した時、 MEX(B)=MEX(0,1,9)=2
  • 2,3,6 要素目を抜き出した時、 MEX(B)=MEX(0,2,1)=3

のようになります。
達成可能な MEX の最大値は 3 です。

Score : 300 points

Problem Statement

You are given a length-N sequence of non-negative integers.
When B is a sequence obtained by choosing K elements from A and concatenating them without changing the order, find the maximum possible value of MEX(B).

Here, for a sequence X, we define MEX(X) as the unique non-negative integer m that satisfies the following conditions:

  • Every integer i such that 0 \le i < m is contained in X.
  • m is not contained in X.

Constraints

  • All values in the input are integers.
  • 1 \le K \le N \le 3 \times 10^5
  • 0 \le A_i \le 10^9

Input

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

N K
A_1 A_2 \dots A_N

Output

Print the answer.

Sample Input 1

7 3
2 0 2 3 2 1 9

Sample Output 1

3

In this input, A=(2,0,2,3,2,1,9), and you obtain the sequence B by picking K=3 elements. For example,

  • If the 1-st, 2-nd, and 3-rd elements are chosen, MEX(B)=MEX(2,0,2)=1.
  • If the 3-rd, 4-th, and 6-th elements are chosen, MEX(B)=MEX(2,3,1)=0.
  • If the 2-nd, 6-th, and 7-th elements are chosen, MEX(B)=MEX(0,1,9)=2.
  • If the 2-nd, 3-rd, and 6-th elements are chosen, MEX(B)=MEX(0,2,1)=3.

The maximum possible MEX is 3.