A - Glutton Takahashi

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

高橋君は N 個の料理を食べようとしています。

i 番目に食べようとしている料理は、S_i = sweet のとき甘い料理であり、S_i = salty のとき塩辛い料理です。

高橋君は甘い料理を 2 つ連続で食べると気持ち悪くなってしまい、その後料理が食べられなくなってしまいます。

高橋君がすべての料理を食べることができるか判定してください。

制約

  • N は 1 以上 100 以下の整数
  • S_i は sweet または salty

入力

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

N
S_1
S_2
\vdots
S_N

出力

高橋君がすべての料理を食べることができるならば Yes を、できないならば No を出力せよ。

入力例 1

5
salty
sweet
salty
salty
sweet

出力例 1

Yes

高橋君は甘い料理を 2 つ連続で食べることがないので、気持ち悪くなることなくすべての料理を食べることができます。

入力例 2

4
sweet
salty
sweet
sweet

出力例 2

Yes

高橋君は気持ち悪くなってしまいますが、すべての料理を食べることができます。

入力例 3

6
salty
sweet
sweet
salty
sweet
sweet

出力例 3

No

高橋君は 3 番目の料理を食べると気持ち悪くなってしまい、4 番目以降の料理が食べられなくなります。

Score : 100 points

Problem Statement

Takahashi is planning to eat N dishes.

The i-th dish he plans to eat is sweet if S_i = sweet, and salty if S_i = salty.

If he eats two sweet dishes consecutively, he will feel sick and be unable to eat any more dishes.

Determine whether he can eat all the dishes.

Constraints

  • N is an integer between 1 and 100, inclusive.
  • Each S_i is sweet or salty.

Input

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

N
S_1
S_2
\vdots
S_N

Output

Print Yes if Takahashi can eat all the dishes, and No otherwise.

Sample Input 1

5
salty
sweet
salty
salty
sweet

Sample Output 1

Yes

He will not eat two sweet dishes consecutively, so he can eat all the dishes without feeling sick.

Sample Input 2

4
sweet
salty
sweet
sweet

Sample Output 2

Yes

He will feel sick but can still eat all the dishes.

Sample Input 3

6
salty
sweet
sweet
salty
sweet
sweet

Sample Output 3

No

He feels sick when eating the 3rd dish and cannot eat the 4th and subsequent dishes.
B - Good morning

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

ある日、高橋君は A 時 B 分ちょうどに、青木君は C 時 D 分 1 秒に起きました。
高橋君の起床時刻が青木君より早いならば Takahashi を、そうでないならば Aoki を出力してください。

制約

  • 0 \leq A \leq 23
  • 0 \leq B \leq 59
  • 0 \leq C \leq 23
  • 0 \leq D \leq 59
  • 入力はすべて整数である。

入力

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

A B C D

出力

高橋君の起床時刻が青木君より早いならば Takahashi を、そうでないならば Aoki を出力せよ。

入力例 1

7 0 6 30

出力例 1

Aoki

高橋君は 7 時ちょうどに、青木君は 6 時 30 分 1 秒に起きました。 青木君の起床時刻の方が早いため、Aoki を出力します。

入力例 2

7 30 7 30

出力例 2

Takahashi

高橋君は 7 時 30 分ちょうどに、青木君は 7 時 30 分 1 秒に起きました。 高橋君の起床時刻の方が 1 秒だけ早いため、Takahashi を出力します。

入力例 3

0 0 23 59

出力例 3

Takahashi

ある日の 0 時 0 分ちょうどはその日の 0 時 1 分の 1 分前であり、 その日の 23 時 59 分の 1 分後、すなわちいわゆる 24 時ちょうどのことではありません。 よって、高橋君の起床時刻の方が早く、Takahashi を出力します。

Score : 100 points

Problem Statement

One day, Takahashi got up at exactly B minutes past A o'clock (in 24-hour clock), and Aoki got up at exactly D minutes and 1 second past C o'clock.
If Takahashi got up earlier than Aoki, print Takahashi; otherwise, print Aoki.

Constraints

  • 0 \leq A \leq 23
  • 0 \leq B \leq 59
  • 0 \leq C \leq 23
  • 0 \leq D \leq 59
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

A B C D

Output

If Takahashi got up earlier than Aoki, print Takahashi; otherwise, print Aoki.

Sample Input 1

7 0 6 30

Sample Output 1

Aoki

Takahashi got up at 7 sharp, and Aoki got up at 30 minutes and 1 second past 6 o'clock. Aoki was the first to get up, so Aoki should be printed.

Sample Input 2

7 30 7 30

Sample Output 2

Takahashi

Takahashi got up at exactly half past 7, and Aoki got up at 30 minutes and 1 second past 7 o'clock. Just by one second, Takahashi was the first to get up, so Takahashi should be printed.

Sample Input 3

0 0 23 59

Sample Output 3

Takahashi

0:00 in a day is one minute before 0:01, not one minute past 23:59 ("24:00"). Thus, Takahashi was the first to get up, so Takahashi should be printed.
C - Card Pile

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

整数 0 の書かれたカードが 100 枚積み重なったカードの山があります。

Q 個のクエリを処理してください。それぞれのクエリは以下のいずれかです。

  • タイプ 1 : 整数 x の書かれたカードを 1 枚カードの山の一番上に積み重ねる。
  • タイプ 2 : カードの山の一番上のカードを取り除き、取り除いたカードに書かれている整数を出力する。ここで、本問題の制約下では必ず山にカードが存在する。

制約

  • 1\le Q\le 100
  • 1\le x\le 100
  • タイプ 2 のクエリが 1 つ以上存在する。
  • 入力される値は全て整数

入力

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

Q
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q

i 番目のクエリ \text{query}_i では、まずクエリのタイプ c_i （1,2 のいずれか）が与えられる。 c_i=1 の場合はさらに整数 x が追加で与えられる。

すなわち、各クエリは以下に示す 2 つの形式のいずれかである。

1 x

2

出力

c_i=2 を満たすクエリの回数を q として、 q 行出力せよ。

j (1\le j\le q) 行目では j 番目のそのようなクエリに対する答えを出力せよ。

入力例 1

6
2
1 4
1 3
2
2
2

出力例 1

0
3
4
0

各クエリを処理した後の山は順に以下のようになります：

  • カードの山の一番上のカードを取り除く。取り除いたカードに書かれた整数は 0 であるため、 0 を出力する。
    • カードの山は 0 の書かれたカードが 99 枚となる。
  • 4 が書かれたカードを山の上に追加する。
    • カードの山は上から順に 4 の書かれたカードが 1 枚、 0 の書かれたカードが 99 枚となる。
  • 3 が書かれたカードを山の上に追加する。
    • カードの山は上から順に 3 の書かれたカードが 1 枚、 4 の書かれたカードが 1 枚、 0 の書かれたカードが 99 枚となる。
  • カードの山の一番上のカードを取り除く。取り除いたカードに書かれた整数は 3 であるため、 3 を出力する。
    • カードの山は上から順に 4 の書かれたカードが 1 枚、 0 の書かれたカードが 99 枚となる。
  • カードの山の一番上のカードを取り除く。取り除いたカードに書かれた整数は 4 であるため、 4 を出力する。
    • カードの山は 0 の書かれたカードが 99 枚となる。
  • カードの山の一番上のカードを取り除く。取り除いたカードに書かれた整数は 0 であるため、 0 を出力する。
    • カードの山は 0 の書かれたカードが 98 枚となる。

入力例 2

5
2
2
2
2
2

出力例 2

0
0
0
0
0

Score : 200 points

Problem Statement

There is a stack of 100 cards, each labeled with the integer 0.

Process Q queries. Each query is of one of the following:

  • Type 1: Place a card labeled with an integer x on top of the stack.
  • Type 2: Remove the top card of the stack and output the integer written on that removed card. Under the constraints of this problem, the stack always has at least one card.

Constraints

  • 1 \le Q \le 100
  • 1 \le x \le 100
  • There is at least one query of type 2.
  • All input values are integers.

Input

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

Q
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q

The i-th query \text{query}_i starts with the query type c_i (1 or 2), followed by the integer x if c_i=1.

That is, each query is in one of the following two formats:

1 x

2

Output

Let q be the number of queries with c_i=2. Print q lines.

The j-th line (1 \le j \le q) should contain the answer to the j-th such query.

Sample Input 1

6
2
1 4
1 3
2
2
2

Sample Output 1

0
3
4
0

After processing each query, the stack is as follows:

  • Remove the top card of the stack. The integer on the removed card is 0, so output 0.
    • The stack then has 99 cards labeled with 0.
  • Add a card labeled 4 on top.
    • The stack then has 1 card labeled 4, and 99 cards labeled 0, from top to bottom.
  • Add a card labeled 3 on top.
    • The stack then has 1 card labeled 3, 1 card labeled 4, and 99 cards labeled 0, from top to bottom.
  • Remove the top card. The integer on that card is 3, so output 3.
    • The stack then has 1 card labeled 4, and 99 cards labeled 0, from top to bottom.
  • Remove the top card. The integer on that card is 4, so output 4.
    • The stack then has 99 cards labeled 0.
  • Remove the top card. The integer on that card is 0, so output 0.
    • The stack then has 98 cards labeled 0.

Sample Input 2

5
2
2
2
2
2

Sample Output 2

0
0
0
0
0
D - Strawberries

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

高橋君は歯が左右一列に N 本生えています。現在の高橋君の歯の状態はある文字列 S によって表されます。

S の i 文字目が O のとき、左から i 番目の歯が丈夫であることを表します。S の i 文字目が X のとき、左から i 番目の歯が虫歯にかかっていることを表します。丈夫である歯は虫歯にかかっていません。

高橋君はある連続する K 本の歯が丈夫であるとき、その K 本の歯を使ってイチゴを 1 個食べることができます。イチゴを食べると、その K 本の歯が虫歯にかかり丈夫でなくなります。

このとき、高橋君は最大で何個のイチゴを食べることができるか求めてください。

制約

  • 1 \leq K \leq N \leq 100
  • N,K は整数
  • S は O と X からなる長さ N の文字列

入力

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

N K
S

出力

答えを出力せよ。

入力例 1

7 3
OOXOOOO

出力例 1

1

左から 4 本目の歯から左から 6 本目の歯までの連続する 3 本の丈夫な歯を使ってイチゴを 1 個食べることができます。これ以降、イチゴを食べることができません。また、他にどのような方法でイチゴを食べても 1 個以下しか食べることができません。よって、1 を出力します。

入力例 2

12 2
OXXOOOXOOOOX

出力例 2

3

入力例 3

22 5
XXOOOOOOOOXXOOOOOXXXXX

出力例 3

2

Score : 200 points

Problem Statement

Takahashi has N teeth arranged in a single row from left to right. The current condition of his teeth is represented by a string S.

If the i-th character of S is O, it means that the i-th tooth from the left is healthy. If it is X, it means that the i-th tooth has a cavity. Healthy teeth do not have cavities.

When he has K consecutive healthy teeth, he can eat one strawberry using those K teeth. After eating a strawberry, those K teeth develop cavities and become unhealthy.

Find the maximum number of strawberries he can eat.

Constraints

  • 1 \leq K \leq N \leq 100
  • N and K are integers.
  • S is a string of length N consisting of O and X.

Input

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

N K
S

Output

Print the answer.

Sample Input 1

7 3
OOXOOOO

Sample Output 1

1

He can eat one strawberry by using the three consecutive healthy teeth from the 4th to 6th tooth from the left. After this, he cannot eat any more strawberries. Besides, there is no way for him to eat more than one strawberry. Therefore, print 1.

Sample Input 2

12 2
OXXOOOXOOOOX

Sample Output 2

3

Sample Input 3

22 5
XXOOOOOOOOXXOOOOOXXXXX

Sample Output 3

2
E - Centers

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 250 点

問題文

1,2,\dots,N がちょうど 3 回ずつ現れる長さ 3N の数列 A=(A_1,A_2,\dots,A_{3N}) が与えられます。

i=1,2,\dots,N について、A の中にある i のうち真ん中にあるものの添字を f(i) と定めます。 1,2,\dots,N を f(i) の昇順に並べ替えてください。

f(i) の定義は厳密には以下の通りです。

  • A_j = i を満たす j が j=\alpha,\beta,\gamma\ (\alpha < \beta < \gamma) であるとする。このとき、f(i) = \beta である。

制約

  • 1\leq N \leq 10^5
  • 1 \leq A_j \leq N
  • i=1,2,\dots,N それぞれについて、A の中に i はちょうど 3 回現れる
  • 入力は全て整数

入力

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

N
A_1 A_2 \dots A_{3N}

出力

1,2,\dots,N を f(i) の昇順に並べ替えてできる長さ N の数列を空白区切りで出力せよ。

入力例 1

3
1 1 3 2 3 2 2 3 1

出力例 1

1 3 2
  • A の中にある 1 は A_1,A_2,A_9 なので、f(1) = 2 です。
  • A の中にある 2 は A_4,A_6,A_7 なので、f(2) = 6 です。
  • A の中にある 3 は A_3,A_5,A_8 なので、f(3) = 5 です。

よって、f(1) < f(3) < f(2) であるため 1,3,2 の順に出力します。

入力例 2

1
1 1 1

出力例 2

1

入力例 3

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

出力例 3

3 4 1 2

Score : 250 points

Problem Statement

You are given a sequence A=(A_1,A_2,\dots,A_{3N}) of length 3N where each of 1,2,\dots, and N occurs exactly three times.

For i=1,2,\dots,N, let f(i) be the index of the middle occurrence of i in A. Sort 1,2,\dots,N in ascending order of f(i).

Formally, f(i) is defined as follows.

  • Suppose that those j such that A_j = i are j=\alpha,\beta,\gamma\ (\alpha < \beta < \gamma). Then, f(i) = \beta.

Constraints

  • 1\leq N \leq 10^5
  • 1 \leq A_j \leq N
  • i occurs in A exactly three times, for each i=1,2,\dots,N.
  • All input values are integers.

Input

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

N
A_1 A_2 \dots A_{3N}

Output

Print the sequence of length N obtained by sorting 1,2,\dots,N in ascending order of f(i), separated by spaces.

Sample Input 1

3
1 1 3 2 3 2 2 3 1

Sample Output 1

1 3 2
  • 1 occurs in A at A_1,A_2,A_9, so f(1) = 2.
  • 2 occurs in A at A_4,A_6,A_7, so f(2) = 6.
  • 3 occurs in A at A_3,A_5,A_8, so f(3) = 5.

Thus, f(1) < f(3) < f(2), so 1,3, and 2 should be printed in this order.

Sample Input 2

1
1 1 1

Sample Output 2

1

Sample Input 3

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

Sample Output 3

3 4 1 2