AtCoder Daily Training EASY 2026/10/22 16:00start

A - Count Takahashi

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

文字列が N 個与えられます。

i 番目 (1\leq i\leq N) に与えられる文字列 S _ i は Takahashi か Aoki のどちらかと等しいです。

S _ i が Takahashi と等しい i がいくつあるか求めてください。

制約

1\leq N\leq 100
N は整数
S _ i は Takahashi か Aoki のいずれか (1\leq i\leq N)

入力

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

N
S _ 1
S _ 2
\vdots
S _ N

出力

S _ i が Takahashi と等しい i の個数を整数として一行に出力せよ。

入力例 1

3
Aoki
Takahashi
Takahashi

出力例 1

S _ 2,S _ 3 の 2 つが Takahashi と等しく、S _ 1 はそうではありません。

よって、2 を出力してください。

入力例 2

2
Aoki
Aoki

出力例 2

Takahashi と等しい S _ i が存在しないこともあります。

入力例 3

20
Aoki
Takahashi
Takahashi
Aoki
Aoki
Aoki
Aoki
Takahashi
Aoki
Aoki
Aoki
Takahashi
Takahashi
Aoki
Takahashi
Aoki
Aoki
Aoki
Aoki
Takahashi

出力例 3

Score : 100 points

Problem Statement

You are given N strings.

The i-th string S_i (1 \leq i \leq N) is either Takahashi or Aoki.

How many i are there such that S_i is equal to Takahashi?

Constraints

1 \leq N \leq 100
N is an integer.
Each S_i is Takahashi or Aoki. (1 \leq i \leq N)

Input

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

N
S_1
S_2
\vdots
S_N

Output

Print the count of i such that S_i is equal to Takahashi as an integer in a single line.

Sample Input 1

3
Aoki
Takahashi
Takahashi

Sample Output 1

S_2 and S_3 are equal to Takahashi, while S_1 is not.

Therefore, print 2.

Sample Input 2

2
Aoki
Aoki

Sample Output 2

It is possible that no S_i is equal to Takahashi.

Sample Input 3

20
Aoki
Takahashi
Takahashi
Aoki
Aoki
Aoki
Aoki
Takahashi
Aoki
Aoki
Aoki
Takahashi
Takahashi
Aoki
Takahashi
Aoki
Aoki
Aoki
Aoki
Takahashi

Sample Output 3

B - Median?

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

整数 a, b, c が与えられます。b がこれらの整数の中央値であるかどうか判定してください。

制約

1 \leq a, b, c \leq 100
入力は全て整数

入力

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

a b c

出力

b が与えられた整数の中央値であるならば Yes、そうでないならば No と出力せよ。

入力例 1

5 3 2

出力例 1

Yes

与えられた整数を小さい順に並べると 2, 3, 5 となり、b はこれらの整数の中央値です。

入力例 2

2 5 3

出力例 2

No

b は与えられた整数の中央値ではありません。

入力例 3

100 100 100

出力例 3

Yes

Score : 100 points

Problem Statement

Given integers a, b, and c, determine if b is the median of these integers.

Constraints

1 \leq a, b, c \leq 100
All values in input are integers.

Input

Input is given from Standard Input in the following format:

a b c

Output

If b is the median of the given integers, then print Yes; otherwise, print No.

Sample Input 1

5 3 2

Sample Output 1

Yes

The given integers are 2, 3, 5 when sorted in ascending order, of which b is the median.

Sample Input 2

2 5 3

Sample Output 2

No

b is not the median of the given integers.

Sample Input 3

100 100 100

Sample Output 3

Yes

C - Go Straight and Turn Right

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

xy 平面を考えます。x 軸の正の向きを東向き、y 軸の正の向きを北向きとします。
高橋君ははじめ、点 (x, y) = (0, 0) にいて東（ x 軸の正の向き）を向いています。

S と R のみからなる長さ N の文字列 T = t_1t_2\ldots t_N が与えられます。高橋君は i = 1, 2, \ldots, N の順番で下記を行います。

t_i = S ならば、高橋君はいま向いている方向に距離 1 だけ進む。
t_i = R ならば、高橋君はその場で右に 90 度回転する。その結果、高橋君の向いている方向が下記の通りに変わる。
- 回転前の向きが東向き（ x 軸の正の向き）ならば、回転後の向きは南向き（ y 軸の負の向き）になる。
- 回転前の向きが南向き（ y 軸の負の向き）ならば、回転後の向きは西向き（ x 軸の負の向き）になる。
- 回転前の向きが西向き（ x 軸の負の向き）ならば、回転後の向きは北向き（ y 軸の正の向き）になる。
- 回転前の向きが北向き（ y 軸の正の向き）ならば、回転後の向きは東向き（ x 軸の正の向き）になる。

上記の手順を終えた後に高橋君がいる点の座標を出力してください。

制約

1 \leq N \leq 10^5
N は整数
T は S と R のみからなる長さ N の文字列

入力

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

N
T

出力

問題文中の手順を終えた後に高橋君がいる点の座標 (x, y) を、下記の形式にしたがって空白区切りで出力せよ。

x y

入力例 1

4
SSRS

出力例 1

2 -1

高橋君ははじめ (0, 0) にいて東を向いています。その後、高橋君は下記の通りに行動します。

t_1 = S であるので、高橋君は東に距離 1 だけ進んだ (1, 0) に移動します。
t_2 = S であるので、高橋君は東に距離 1 だけ進んだ (2, 0) に移動します。
t_3 = R であるので、高橋君は右に 90 度回転し、高橋君は南を向きます。
t_4 = S であるので、高橋君は南に距離 1 だけ進んだ (2, -1) に移動します。

よって、高橋君の最終的な位置である (x, y) = (2, -1) を出力します。

入力例 2

20
SRSRSSRSSSRSRRRRRSRR

出力例 2

0 1

Score : 200 points

Problem Statement

Consider an xy-plane. The positive direction of the x-axis is in the direction of east, and the positive direction of the y-axis is in the direction of north.
Takahashi is initially at point (x, y) = (0, 0) and facing east (in the positive direction of the x-axis).

You are given a string T = t_1t_2\ldots t_N of length N consisting of S and R. Takahashi will do the following move for each i = 1, 2, \ldots, N in this order.

If t_i = S, Takahashi advances in the current direction by distance 1.
If t_i = R, Takahashi turns 90 degrees clockwise without changing his position. As a result, Takahashi's direction changes as follows.
- If he is facing east (in the positive direction of the x-axis) before he turns, he will face south (in the negative direction of the y-axis) after he turns.
- If he is facing south (in the negative direction of the y-axis) before he turns, he will face west (in the negative direction of the x-axis) after he turns.
- If he is facing west (in the negative direction of the x-axis) before he turns, he will face north (in the positive direction of the y-axis) after he turns.
- If he is facing north (in the positive direction of the y-axis) before he turns, he will face east (in the positive direction of the x-axis) after he turns.

Print the coordinates Takahashi is at after all the steps above have been done.

Constraints

1 \leq N \leq 10^5
N is an integer.
T is a string of length N consisting of S and R.

Input

Input is given from Standard Input in the following format:

N
T

Output

Print the coordinates (x, y) Takahashi is at after all the steps described in the Problem Statement have been completed, in the following format, with a space in between:

x y

Sample Input 1

4
SSRS

Sample Output 1

2 -1

Takahashi is initially at (0, 0) facing east. Then, he moves as follows.

t_1 = S, so he advances in the direction of east by distance 1, arriving at (1, 0).
t_2 = S, so he advances in the direction of east by distance 1, arriving at (2, 0).
t_3 = R, so he turns 90 degrees clockwise, resulting in facing south.
t_4 = S, so he advances in the direction of south by distance 1, arriving at (2, -1).

Thus, Takahashi's final position, (x, y) = (2, -1), should be printed.

Sample Input 2

20
SRSRSSRSSSRSRRRRRSRR

Sample Output 2

0 1

D - Split Ticketing

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

N 個の駅 1,2,\dots,N があり、これらはこの順に西から東に一直線上に並んでいます。
AtCoder 鉄道の電車はこれら N 個の駅を通り、西から東に走っています。
1 \leq i \lt j \leq N を満たす任意の 2 整数 i,j について、駅 i から電車に乗って駅 j で降りるのにコストが C_{i,j} かかります。

以下のような 3 つの整数 a,b,c が存在するかを判定してください。

1 \leq a \lt b \lt c \leq N
駅 a から電車に乗って駅 c で降りるときにかかるコストよりも、駅 a から電車に乗って駅 b で降り、再度、駅 b から電車に乗って駅 c で降りるときにかかるコストの総和の方が小さい。

制約

3 \leq N \leq 100
1 \leq C_{i,j} \leq 10^9
入力される値は全て整数

入力

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

N
C_{1,2} C_{1,3} \dots C_{1,N}
C_{2,3} \dots C_{2,N}
\vdots
C_{N-1,N}

出力

条件を満たす 3 整数 a,b,c が存在するならば Yes を、存在しないならば No を 1 行で出力せよ。

入力例 1

3
45 450
45

出力例 1

Yes

(a,b,c) として (1,2,3) を選ぶと、
C_{a,b}+C_{b,c}=C_{1,2}+C_{2,3}=45+45
C_{a,c}=C_{1,3}=450
なので、条件を満たします。

入力例 2

出力例 2

No

どのように (a,b,c) を選んでも、条件を満たしません。

Score : 200 points

Problem Statement

There are N stations 1, 2, \dots, N, arranged in a straight line from west to east in this order.
The AtCoder Railway train passes through these N stations and runs from west to east.
For any two integers i, j satisfying 1 \leq i \lt j \leq N, the cost of boarding the train at station i and getting off at station j is C_{i,j}.

Determine whether there exist three integers a, b, c such that:

1 \leq a \lt b \lt c \leq N
The total cost of boarding the train at station a, getting off at station b, then boarding the train again at station b, and getting off at station c is less than the cost of boarding the train at station a and getting off at station c.

Constraints

3 \leq N \leq 100
1 \leq C_{i,j} \leq 10^9
All input values are integers.

Input

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

N
C_{1,2} C_{1,3} \dots C_{1,N}
C_{2,3} \dots C_{2,N}
\vdots
C_{N-1,N}

Output

If there exist three integers a, b, c satisfying the conditions, output Yes; otherwise, output No, on a single line.

Sample Input 1

3
45 450
45

Sample Output 1

Yes

Choosing (a, b, c) = (1, 2, 3),
C_{a,b}+C_{b,c}=C_{1,2}+C_{2,3}=45+45
C_{a,c}=C_{1,3}=450
so the conditions are satisfied.

Sample Input 2

Sample Output 2

No

No choice of (a, b, c) satisfies the conditions.

E - Changing Jewels

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

高橋君はレベル N の赤い宝石を 1 個持っています。(他に宝石は持っていません。)
高橋君は次の操作を好きなだけ行うことができます。

レベル n の赤い宝石 (n は 2 以上) を「レベル n-1 の赤い宝石 1 個と、レベル n の青い宝石 X 個」に変換する。
レベル n の青い宝石 (n は 2 以上) を「レベル n-1 の赤い宝石 1 個と、レベル n-1 の青い宝石 Y 個」に変換する。

高橋君はレベル 1 の青い宝石ができるだけたくさんほしいです。操作によって高橋君はレベル 1 の青い宝石を最大何個入手できますか？

制約

1 \leq N \leq 10
1 \leq X \leq 5
1 \leq Y \leq 5
入力される値はすべて整数

入力

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

N X Y

出力

答えを出力せよ。

入力例 1

2 3 4

出力例 1

次のような変換を行うことで、高橋君はレベル 1 の青い宝石を 12 個手に入れることができます。

まず、レベル 2 の赤い宝石 1 個を、レベル 1 の赤い宝石 1 個とレベル 2 の青い宝石 3 個に変換します。
- 操作後の高橋君は、レベル 1 の赤い宝石 1 個とレベル 2 の青い宝石 3 個を持っています。
次に、レベル 2 の青い宝石 1 個を、レベル 1 の赤い宝石 1 個とレベル 1 の青い宝石 4 個に変換します。この変換を 3 回繰り返します。
- 操作後の高橋君は、レベル 1 の赤い宝石 4 個とレベル 1 の青い宝石 12 個を持っています。
これ以上変換を行うことはできません。

12 個より多くレベル 1 の青い宝石を手に入れることはできないので、答えは 12 になります。

入力例 2

1 5 5

出力例 2

高橋君がレベル 1 の青い宝石を 1 個も手に入れられない場合もあります。

入力例 3

10 5 5

出力例 3

3942349900

答えが 32 bit 整数に収まらない場合があることに注意してください。

Score : 300 points

Problem Statement

Takahashi has a red jewel of level N. (He has no other jewels.)
Takahashi can do the following operations any number of times.

Convert a red jewel of level n (n is at least 2) into "a red jewel of level (n-1) and X blue jewels of level n".
Convert a blue jewel of level n (n is at least 2) into "a red jewel of level (n-1) and Y blue jewels of level (n-1)".

Takahashi wants as many blue jewels of level 1 as possible. At most, how many blue jewels of level 1 can he obtain by the operations?

Constraints

1 \leq N \leq 10
1 \leq X \leq 5
1 \leq Y \leq 5
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N X Y

Output

Print the answer.

Sample Input 1

2 3 4

Sample Output 1

Takahashi can obtain 12 blue jewels of level 1 by the following conversions.

First, he converts a red jewel of level 2 into a red jewel of level 1 and 3 blue jewels of level 2.
- After this operation, Takahashi has 1 red jewel of level 1 and 3 blue jewels of level 2.
Next, he repeats the following conversion 3 times: converting a blue jewel of level 2 into a red jewel of level 1 and 4 blue jewels of level 1.
- After these operations, Takahashi has 4 red jewels of level 1 and 12 blue jewels of level 1.
He cannot perform a conversion anymore.

He cannot obtain more than 12 blue jewels of level 1, so the answer is 12.

Sample Input 2

1 5 5

Sample Output 2

Takahashi may not be able to obtain a blue jewel of level 1.

Sample Input 3

10 5 5

Sample Output 3

3942349900

Note that the answer may not fit into a 32-bit integer type.