AtCoder Daily Training EASY 2026/11/09 16:00start

A - AtCoder Language

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

配点 : 100 点

問題文

高橋君は、AtCoder 語を勉強しています。

高橋君は英単語に対して AtCoder 語の単語を対応させて覚えています。

高橋君は英語における red, blue, green は AtCoder 語ではそれぞれ SSS, FFF, MMM に対応していることを覚えており、他の単語は覚えていません。

英小文字からなる文字列 S が与えられます。S が高橋君が AtCoder 語との対応を覚えている英単語の表記と一致しているならば S に対応している AtCoder 語の単語を、そうでないならば文字列 Unknown を出力してください。

制約

S は長さ 1 以上 10 以下の英小文字からなる文字列

入力

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

出力

問題文中の指示に従い、文字列を出力せよ。

入力例 1

red

出力例 1

SSS

英語における red は AtCoder 語における SSS に対応します。

入力例 2

atcoder

出力例 2

Unknown

Score : 100 points

Problem Statement

Takahashi is learning AtCoderish Language.

He memorizes AtCoderish words corresponding to English words.

He knows that red, blue, and green in English respectively correspond to SSS, FFF, and MMM in AtCoderish, and he knows no other words.

You are given a string S consisting of lowercase English letters. If S equals an English word that Takahashi knows corresponds to an AtCoderish word, output the AtCoderish word corresponding to S; otherwise, output the string Unknown.

Constraints

S is a string of length between 1 and 10, inclusive, consisting of English letters.

Input

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

Output

Output a string according to the instructions in the problem statement.

Sample Input 1

red

Sample Output 1

SSS

red in English corresponds to SSS in AtCoderish.

Sample Input 2

atcoder

Sample Output 2

Unknown

B - Obesity

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

配点 : 100 点

問題文

以下の式で計算される値を \mathrm{BMI}[\mathrm{kg}/\mathrm{m}^2] と言います。

\text{体重}[\mathrm{kg}] \div \text{身長}[\mathrm{m}] \div \text{身長}[\mathrm{m}]

日本では、\mathrm{BMI} が 25 \; \mathrm{kg}/\mathrm{m}^2 以上の人は肥満とされます。
身長 H[\mathrm{cm}]、体重 W[\mathrm{kg}] の人が日本で肥満とされるかどうかを判定してください。

制約

1 \leq H \leq 300
1 \leq W \leq 300
入力される値はすべて整数

入力

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

H W

出力

身長 H[\mathrm{cm}]、体重 W[\mathrm{kg}] の人が日本で肥満とされるならば Yes を、そうでないならば No を 1 行で出力せよ。

入力例 1

180 60

出力例 1

No

身長が 180 \; \mathrm{cm}=1.8 \; \mathrm{m} なので、\mathrm{BMI} は 60 \; \mathrm{kg} \div 1.8 \; \mathrm{m} \div 1.8 \; \mathrm{m}=18.5\dots \; \mathrm{kg}/\mathrm{m}^2 となり、この人は肥満とはされません。

入力例 2

182 188

出力例 2

Yes

入力例 3

180 81

出力例 3

Yes

Score : 100 points

Problem Statement

The value calculated by the following formula is called \mathrm{BMI}[\mathrm{kg}/\mathrm{m}^2]. (\div denotes division.)

\text{Weight}[\mathrm{kg}] \div \text{Height}[\mathrm{m}] \div \text{Height}[\mathrm{m}]

In Japan, a person whose \mathrm{BMI} is 25 \; \mathrm{kg}/\mathrm{m}^2 or more is considered obese.
Determine whether a person with height H[\mathrm{cm}] and weight W[\mathrm{kg}] is considered obese in Japan.

Constraints

1 \leq H \leq 300
1 \leq W \leq 300
All input values are integers.

Input

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

H W

Output

Output Yes on one line if a person with height H[\mathrm{cm}] and weight W[\mathrm{kg}] is considered obese in Japan, and No otherwise.

Sample Input 1

180 60

Sample Output 1

No

Since the height is 180 \; \mathrm{cm}=1.8 \; \mathrm{m}, the \mathrm{BMI} is 60 \; \mathrm{kg} \div 1.8 \; \mathrm{m} \div 1.8 \; \mathrm{m}=18.5\dots \; \mathrm{kg}/\mathrm{m}^2, so this person is not considered obese.

Sample Input 2

182 188

Sample Output 2

Yes

Sample Input 3

180 81

Sample Output 3

Yes

C - 1D Keyboard

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

配点 : 200 点

問題文

26 個のキーが数直線上に並んだキーボードがあります。

このキーボードの配列は ABCDEFGHIJKLMNOPQRSTUVWXYZ を並べ替えた文字列 S で表されます。文字 S_x に対応するキーが座標 x (1 \leq x \leq 26) にあります。ここで、S_x は S の x 文字目を表します。

あなたはこのキーボードを使って ABCDEFGHIJKLMNOPQRSTUVWXYZ をこの順で右手人差し指で一度だけ入力します。ある文字を入力するためには、その文字に対応するキーの座標に指を移動させてキーを押す必要があります。

はじめ、指は A に対応するキーの座標にあります。A に対応するキーを押してから、Z に対応するキーを押すまでの指の移動距離の合計として考えられる最小値を求めてください。ただし、キーを押す動作は移動距離に含まれません。

制約

S は ABCDEFGHIJKLMNOPQRSTUVWXYZ を並べ替えた文字列である。

入力

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

出力

答えを出力せよ。

入力例 1

ABCDEFGHIJKLMNOPQRSTUVWXYZ

出力例 1

A のキーを押してから Z のキーを押すまで指を 1 ずつ正の方向に移動させる必要があり、このときの移動距離の合計は 25 です。25 未満の総移動距離でキーを全て入力することはできないため、25 と出力します。

入力例 2

MGJYIZDKSBHPVENFLQURTCWOAX

出力例 2

Score : 200 points

Problem Statement

There is a keyboard with 26 keys arranged on a number line.

The arrangement of this keyboard is represented by a string S, which is a permutation of ABCDEFGHIJKLMNOPQRSTUVWXYZ. The key corresponding to the character S_x is located at coordinate x (1 \leq x \leq 26). Here, S_x denotes the x-th character of S.

You will use this keyboard to input ABCDEFGHIJKLMNOPQRSTUVWXYZ in this order, typing each letter exactly once with your right index finger. To input a character, you need to move your finger to the coordinate of the key corresponding to that character and press the key.

Initially, your finger is at the coordinate of the key corresponding to A. Find the minimal possible total traveled distance of your finger from pressing the key for A to pressing the key for Z. Here, pressing a key does not contribute to the distance.

Constraints

S is a permutation of ABCDEFGHIJKLMNOPQRSTUVWXYZ.

Input

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

Output

Print the answer.

Sample Input 1

ABCDEFGHIJKLMNOPQRSTUVWXYZ

Sample Output 1

From pressing the key for A to pressing the key for Z, you need to move your finger 1 unit at a time in the positive direction, resulting in a total traveled distance of 25. It is impossible to press all keys with a total traveled distance less than 25, so print 25.

Sample Input 2

MGJYIZDKSBHPVENFLQURTCWOAX

Sample Output 2

D - Maintain Multiple Sequences

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

配点 : 200 点

問題文

整数からなる数列が N 個あります。
i \, (1 \leq i \leq N) 番目の数列は L_i 項からなり、i 番目の数列の第 j \, (1 \leq j \leq L_i) 項は a_{i, j} です。

Q 個のクエリが与えられます。k \, (1 \leq k \leq Q) 番目のクエリでは、整数 s_k, t_k が与えられるので、s_k 番目の数列の第 t_k 項を求めてください。

制約

1 \leq N, Q \leq 2 \times 10^5
L_i \geq 1 \, (1 \leq i \leq N)
\sum_{i=1}^N L_i \leq 2 \times 10^5
1 \leq a_{i, j} \leq 10^9 \, (1 \leq i \leq N, 1 \leq j \leq L_i)
1 \leq s_k \leq N, 1 \leq t_k \leq L_{s_k} \, (1 \leq k \leq Q)
入力は全て整数

入力

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

N Q
L_1 a_{1, 1} \ldots a_{1, L_1}
\vdots
L_N a_{N, 1} \ldots a_{N, L_N}
s_1 t_1
\vdots 
s_Q t_Q

出力

Q 行出力せよ。k \, (1 \leq k \leq Q) 行目には、k 番目のクエリに対する答えを出力せよ。

入力例 1

出力例 1

7
5

1 番目の数列は (1, 4, 7)、2 番目の数列は (5, 9) です。
それぞれのクエリに対する答えは次のようになります。

1 番目の数列の第 3 項は 7 です。
2 番目の数列の第 1 項は 5 です。

入力例 2

3 4
4 128 741 239 901
2 1 1
3 314 159 26535
1 1
2 2
3 3
1 4

出力例 2

Score : 200 points

Problem Statement

There are N sequences of integers.
The i-th (1 \leq i \leq N) sequence has L_i terms; the j-th (1 \leq j \leq L_i) term of the i-th sequence is a_{i, j}.

You are given Q queries. For the k-th (1 \leq k \leq Q) query, given integers s_k and t_k, find the t_k-th term of the s_k-th sequence.

Constraints

1 \leq N, Q \leq 2 \times 10^5
L_i \geq 1 \, (1 \leq i \leq N)
\sum_{i=1}^N L_i \leq 2 \times 10^5
1 \leq a_{i, j} \leq 10^9 \, (1 \leq i \leq N, 1 \leq j \leq L_i)
1 \leq s_k \leq N, 1 \leq t_k \leq L_{s_k} \, (1 \leq k \leq Q)
All values in the input are integers.

Input

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

N Q
L_1 a_{1, 1} \ldots a_{1, L_1}
\vdots
L_N a_{N, 1} \ldots a_{N, L_N}
s_1 t_1
\vdots 
s_Q t_Q

Output

Print Q lines. The k-th (1 \leq k \leq Q) line should contain the answer to the k-th query.

Sample Input 1

Sample Output 1

7
5

The 1-st sequence is (1, 4, 7) and the 2-nd is (5, 9).
The answer to each query is as follows:

The 3-rd term of the 1-st sequence is 7.
The 1-st term of the 2-nd sequence is 5.

Sample Input 2

3 4
4 128 741 239 901
2 1 1
3 314 159 26535
1 1
2 2
3 3
1 4

Sample Output 2

E - Reversible

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

配点 : 300 点

問題文

ボールがいくつか刺さった棒が N 本あり、各ボールには英小文字が 1 個書かれています。

i = 1, 2, \ldots, N について、i 番目の棒に刺さった各ボールの英小文字は、文字列 S_i によって表されます。具体的には、i 番目の棒には文字列 S_i の長さ |S_i| に等しい個数のボールが刺さっており、刺さっているボールの英小文字を、棒のある端から順に並べたものは文字列 S_i と等しいです。

2 つの棒は、一方の棒に刺さっているボールの英小文字をどちらかの端から並べた列と、もう一方の棒に刺さっているボールの英小文字をどちらかの端から並べた列が一致するとき、同じ棒とみなされます。より形式的には、1 以上 N 以下の整数 i, j について、i 本目の棒と j 本目の棒は、S_i が S_j と一致するか、S_i が S_j を前後反転したものと一致するとき、かつそのときに限り、同じとみなされます。

N 本の棒の中に、何種類の異なる棒があるかを出力してください。

制約

N は整数
2 \leq N \leq 2 \times 10^5
S_i は英小文字のみからなる文字列
|S_i| \geq 1
\sum_{i = 1}^N |S_i| \leq 2 \times 10^5

入力

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

N
S_1
S_2
\vdots
S_N

出力

答えを出力せよ。

入力例 1

6
a
abc
de
cba
de
abc

出力例 1

S_2 = abc が S_4 = cba を前後反転したものと一致するため、2 番目の棒と 4 番目の棒は同じとみなされます。
S_2 = abc が S_6 = abc と一致するため、2 番目の棒と 6 番目の棒は同じとみなされます。
S_3 = de が S_5 = de と一致するため、3 番目の棒と 5 番目の棒は同じとみなされます。

よって、6 本の棒の中に、1 本目の棒、2 本目の棒（ 4, 6 本目の棒と同じ）、3 本目の棒（ 5 本目の棒と同じ）の 3 種類の異なる棒があります。

Score : 300 points

Problem Statement

There are N sticks with several balls stuck onto them. Each ball has a lowercase English letter written on it.

For each i = 1, 2, \ldots, N, the letters written on the balls stuck onto the i-th stick are represented by a string S_i. Specifically, the number of balls stuck onto the i-th stick is the length |S_i| of the string S_i, and S_i is the sequence of letters on the balls starting from one end of the stick.

Two sticks are considered the same when the sequence of letters on the balls starting from one end of one stick is equal to the sequence of letters starting from one end of the other stick. More formally, for integers i and j between 1 and N, inclusive, the i-th and j-th sticks are considered the same if and only if S_i equals S_j or its reversal.

Print the number of different sticks among the N sticks.

Constraints

N is an integer.
2 \leq N \leq 2 \times 10^5
S_i is a string consisting of lowercase English letters.
|S_i| \geq 1
\sum_{i = 1}^N |S_i| \leq 2 \times 10^5

Input

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

N
S_1
S_2
\vdots
S_N

Output

Print the answer.

Sample Input 1

6
a
abc
de
cba
de
abc

Sample Output 1

S_2 = abc equals the reversal of S_4 = cba, so the second and fourth sticks are considered the same.
S_2 = abc equals S_6 = abc, so the second and sixth sticks are considered the same.
S_3 = de equals S_5 = de, so the third and fifth sticks are considered the same.

Therefore, there are three different sticks among the six: the first, second (same as the fourth and sixth), and third (same as the fifth).