AtCoder Daily Training EASY 2024/05/28 15:30start

A - Weather Forecast

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 100 点

問題文

明日からの 7 日間の天気予報を表す文字列 S が与えられます。
i 日後の予報は S の i 文字目が o であるとき晴れ、x であるとき雨です。

N 日後の天気予報が晴れかどうかを教えてください。

制約

N は 1 以上 7 以下の整数
S は長さ 7 の文字列であり、o と x のみからなる

入力

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

N
S

出力

N 日後の天気予報が晴れであるとき Yes を、雨であるとき No を出力せよ。

入力例 1

4
oooxoox

出力例 1

No

明日からの 7 日間の天気予報は順に、晴れ、晴れ、晴れ、雨、晴れ、晴れ、雨です。
特に、今日から 4 日後の天気予報は雨です。

入力例 2

7
ooooooo

出力例 2

Yes

Score : 100 points

Problem Statement

You are given a string S, which represents a weather forecast for the seven days starting tomorrow.
The i-th of those seven days is forecast to be sunny if the i-th character of S is o, and rainy if that character is x.

Tell us whether the N-th day is forecast to be sunny.

Constraints

N is an integer between 1 and 7 (inclusive).
S is a string of length 7 consisting of o and x.

Input

Input is given from Standard Input in the following format:

N
S

Output

Print Yes if the N-th of the seven days starting tomorrow is forecast to be sunny, and No if that day is forecast to be rainy.

Sample Input 1

4
oooxoox

Sample Output 1

No

The forecast for each of the seven days starting tomorrow is as follows: sunny, sunny, sunny, rainy, sunny, sunny, rainy.
In particular, the fourth day is forecast to be rainy.

Sample Input 2

7
ooooooo

Sample Output 2

Yes

B - First Player

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 100 点

問題文

人 1 、人 2 、\ldots 、人 N と番号付けられた N 人が、この順番で時計回りに円卓に座っています。特に、時計回りで人 N の次の位置には人 1 が座っています。

i = 1, 2, \ldots, N について、人 i の名前は S_i 、年齢は A_i です。ここで、異なる 2 人が同じ名前や同じ年齢であることはありません。

年齢が最も小さい人を起点として、座っている位置の時計回りの順番で、N 人全員の名前を出力してください。

制約

2 \leq N \leq 100
N は整数
S_i は英小文字のみからなる長さ 1 以上 10 以下の文字列
i \neq j \implies S_i \neq S_j
0 \leq A_i \leq 10^9
A_i は整数
i \neq j \implies A_i \neq A_j

入力

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

N
S_1 A_1
S_2 A_2
\vdots
S_N A_N

出力

N 行出力せよ。 i = 1, 2, \ldots, N について、i 行目には、年齢が最も小さい人を起点として時計回りで i 番目の位置に座っている人の名前を出力せよ。

入力例 1

5
alice 31
bob 41
carol 5
dave 92
ellen 65

出力例 1

carol
dave
ellen
alice
bob

年齢が最も小さい人は人 3 です。よって、人 3 を起点として座っている位置の時計回りの順番、すなわち、人 3 、人 4 、人 5 、人 1 、人 2 の順に名前を出力します。

入力例 2

2
takahashi 1000000000
aoki 999999999

出力例 2

aoki
takahashi

Score : 100 points

Problem Statement

There are N people numbered 1, 2, \ldots, N, sitting in this clockwise order around a round table. In particular, person 1 is sitting next to person N in the clockwise direction.

For each i = 1, 2, \ldots, N, person i has a name S_i and an age A_i. Here, no two people have the same name or the same age.

Starting from the youngest person, print the names of all N people in the order of their seating positions in clockwise order.

Constraints

2 \leq N \leq 100
N is an integer.
S_i is a string of length between 1 and 10, consisting of lowercase English letters.
i \neq j \implies S_i \neq S_j
0 \leq A_i \leq 10^9
A_i is an integer.
i \neq j \implies A_i \neq A_j

Input

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

N
S_1 A_1
S_2 A_2
\vdots
S_N A_N

Output

Print N lines. For each i = 1, 2, \ldots, N, the i-th line should contain the name of the person sitting in the i-th position clockwise from the youngest person.

Sample Input 1

5
alice 31
bob 41
carol 5
dave 92
ellen 65

Sample Output 1

carol
dave
ellen
alice
bob

The youngest person is person 3. Therefore, starting from person 3, print the names in the clockwise order of their seating positions: person 3, person 4, person 5, person 1, and person 2.

Sample Input 2

2
takahashi 1000000000
aoki 999999999

Sample Output 2

aoki
takahashi

C - Dentist Aoki

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 200 点

問題文

高橋君には、穴 1,2,\dots,N に 1 本ずつ、全部で N 本の歯が生えています。
歯医者の青木君は、これらの歯と穴に対して、 Q 回の治療を行います。
i 回目の治療では、穴 T_i を治療します。治療内容は次の通りです。

穴 T_i に歯が生えている場合、穴 T_i から歯を抜く。
そうでない ( 穴 T_i に歯が生えていない) 場合、穴 T_i に歯を生やす。

全ての治療が終わった後、高橋君に生えている歯の本数は何本ですか?

制約

入力は全て整数
1 \le N,Q \le 1000
1 \le T_i \le N

入力

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

N Q
T_1 T_2 \dots T_Q

出力

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

入力例 1

30 6
2 9 18 27 18 9

出力例 1

高橋君には最初 30 本の歯が生えており、青木君は 6 回の治療を行います。

1 回目の治療では穴 2 を治療します。穴 2 に歯が生えているため、歯を抜きます。
2 回目の治療では穴 9 を治療します。穴 9 に歯が生えているため、歯を抜きます。
3 回目の治療では穴 18 を治療します。穴 18 に歯が生えているため、歯を抜きます。
4 回目の治療では穴 27 を治療します。穴 27 に歯が生えているため、歯を抜きます。
5 回目の治療では穴 18 を治療します。穴 18 に歯が生えていないため、歯を生やします。
6 回目の治療では穴 9 を治療します。穴 9 に歯が生えていないため、歯を生やします。

最終的な歯の本数は 28 本です。

入力例 2

1 7
1 1 1 1 1 1 1

出力例 2

入力例 3

9 20
9 5 1 2 2 2 8 9 2 1 6 2 6 5 8 7 8 5 9 8

出力例 3

Score: 200 points

Problem Statement

Takahashi has N teeth, one in each of the holes numbered 1, 2, \dots, N.
Dentist Aoki will perform Q treatments on these teeth and holes.
In the i-th treatment, hole T_i is treated as follows:

If there is a tooth in hole T_i, remove the tooth from hole T_i.
If there is no tooth in hole T_i (i.e., the hole is empty), grow a tooth in hole T_i.

After all treatments are completed, how many teeth does Takahashi have?

Constraints

All input values are integers.
1 \le N, Q \le 1000
1 \le T_i \le N

Input

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

N Q
T_1 T_2 \dots T_Q

Output

Print the number of teeth as an integer.

Sample Input 1

30 6
2 9 18 27 18 9

Sample Output 1

Initially, Takahashi has 30 teeth, and Aoki performs six treatments.

In the first treatment, hole 2 is treated. There is a tooth in hole 2, so it is removed.
In the second treatment, hole 9 is treated. There is a tooth in hole 9, so it is removed.
In the third treatment, hole 18 is treated. There is a tooth in hole 18, so it is removed.
In the fourth treatment, hole 27 is treated. There is a tooth in hole 27, so it is removed.
In the fifth treatment, hole 18 is treated. There is no tooth in hole 18, so a tooth is grown.
In the sixth treatment, hole 9 is treated. There is no tooth in hole 9, so a tooth is grown.

The final count of teeth is 28.

Sample Input 2

1 7
1 1 1 1 1 1 1

Sample Output 2

Sample Input 3

9 20
9 5 1 2 2 2 8 9 2 1 6 2 6 5 8 7 8 5 9 8

Sample Output 3

D - Rotate

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 200 点

問題文

N 行 N 列のマス目が与えられます。上から i 行目、左から j 列目のマスには整数 A_{i,j} が書かれています。ここで、A_{i,j} は 0 か 1 であることが保証されます。

マス目の外側のマスに書かれた整数を時計回りに 1 個ずつずらしたときのマス目を出力してください。

ただし外側のマスとは、1 行目、N 行目、1 列目、N 列目のいずれか 1 つ以上に属するマスの集合のことを指します。

制約

2 \le N \le 100
0 \le A_{i,j} \le 1(1 \le i,j \le N)
入力は全て整数

入力

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

N
A_{1,1}A_{1,2}\dots A_{1,N}
A_{2,1}A_{2,2}\dots A_{2,N}
\vdots
A_{N,1}A_{N,2}\dots A_{N,N}

出力

マス目の外側のマスに書かれた整数を時計回りに 1 個ずつずらしたときのマス目において、上から i 行目、左から j 列目のマスに書かれている整数を B_{i,j} と置く。このとき、以下の形式で出力せよ。

B_{1,1}B_{1,2}\dots B_{1,N}
B_{2,1}B_{2,2}\dots B_{2,N}
\vdots
B_{N,1}B_{N,2}\dots B_{N,N}

入力例 1

出力例 1

上から i 行目、左から j 列目のマスを (i,j) と呼ぶこととします。

外側のマスは (1,1) から時計回りに列挙すると (1,1),(1,2),(1,3),(1,4),(2,4),(3,4),(4,4),(4,3),(4,2),(4,1),(3,1),(2,1) の 12 個です。

これらのマスに書かれている整数を、時計回りに 1 個ずつ動かすと出力欄のようになります。

入力例 2

2
11
11

出力例 2

11
11

入力例 3

出力例 3

Score : 200 points

Problem Statement

You are given a grid with N rows and N columns. An integer A_{i, j} is written on the square at the i-th row from the top and j-th column from the left. Here, it is guaranteed that A_{i,j} is either 0 or 1.

Shift the integers written on the outer squares clockwise by one square each, and print the resulting grid.

Here, the outer squares are those in at least one of the 1-st row, N-th row, 1-st column, and N-th column.

Constraints

2 \le N \le 100
0 \le A_{i,j} \le 1(1 \le i,j \le N)
All input values are integers.

Input

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

N
A_{1,1}A_{1,2}\dots A_{1,N}
A_{2,1}A_{2,2}\dots A_{2,N}
\vdots
A_{N,1}A_{N,2}\dots A_{N,N}

Output

Let B_{i,j} be the integer written on the square at the i-th row from the top and j-th column from the left in the grid resulting from shifting the outer squares clockwise by one square each. Print them in the following format:

B_{1,1}B_{1,2}\dots B_{1,N}
B_{2,1}B_{2,2}\dots B_{2,N}
\vdots
B_{N,1}B_{N,2}\dots B_{N,N}

Sample Input 1

Sample Output 1

We denote by (i,j) the square at the i-th row from the top and j-th column from the left.

The outer squares, in clockwise order starting from (1,1), are the following 12 squares: (1,1),(1,2),(1,3),(1,4),(2,4),(3,4),(4,4),(4,3),(4,2),(4,1),(3,1), and (2,1).

The sample output shows the resulting grid after shifting the integers written on those squares clockwise by one square.

Sample Input 2

2
11
11

Sample Output 2

11
11

Sample Input 3

Sample Output 3

E - Jumping Takahashi

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

高橋君は数直線上の座標 0 の位置にいます。

これから高橋君は N 回のジャンプを行います。i \, (1 \leq i \leq N) 回目のジャンプでは、正の方向に a_i または b_i 移動します。

N 回のジャンプの後に座標 X の位置にいるようにすることはできますか？

制約

1 \leq N \leq 100
1 \leq a_i \lt b_i \leq 100 \, (1 \leq i \leq N)
1 \leq X \leq 10000
入力は全て整数

入力

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

N X
a_1 b_1
\vdots
a_N b_N

出力

N 回のジャンプの後に座標 X の位置にいるようにすることができるならば Yes と、そうでないなら No と出力せよ。

入力例 1

2 10
3 6
4 5

出力例 1

Yes

1 回目のジャンプでは b_1 (= 6) 移動し、2 回目のジャンプでは a_2 (= 4) 移動することで、座標 X (= 10) の位置にいるようにすることができます。

入力例 2

2 10
10 100
10 100

出力例 2

No

1 回目のジャンプの後に座標 X (= 10) の位置にいるようにすることはできますが、全てのジャンプの後に座標 X (= 10) の位置にいるようにすることはできません。

入力例 3

出力例 3

Yes

Score : 300 points

Problem Statement

Takahashi is standing at the coordinate 0 on a number line.

He will now perform N jumps. In the i-th jump (1 \leq i \leq N), he moves a_i or b_i in the positive direction.

Is it possible for him to be at the coordinate X after N jumps?

Constraints

1 \leq N \leq 100
1 \leq a_i \lt b_i \leq 100 \, (1 \leq i \leq N)
1 \leq X \leq 10000
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N X
a_1 b_1
\vdots
a_N b_N

Output

If it is possible for Takahashi to be at the coordinate X after N jumps, print Yes; otherwise, print No.

Sample Input 1

2 10
3 6
4 5

Sample Output 1

Yes

By moving b_1 (= 6) in the first jump and a_2 (= 4) in the second jump, he can be at the coordinate X (= 10).

Sample Input 2

2 10
10 100
10 100

Sample Output 2

No

He can be at the coordinate X (= 10) after the first jump, but not after all jumps.

Sample Input 3

Sample Output 3

Yes