AtCoder Daily Training EASY 2026/02/24 18:00start

A - AtCoder Language

Time Limit: 2 sec / Memory Limit: 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 - Find Multiple

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

A 以上 B 以下であるような C の倍数を、1 つ出力してください。

条件を満たす数が存在しない場合は -1 を出力してください。

制約

1 \leq A \leq B \leq 1000
1 \leq C \leq 1000
入力は全て整数

入力

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

A B C

出力

答えを出力せよ。
条件を満たす数が存在しない場合は -1 を出力せよ。

入力例 1

123 456 100

出力例 1

300 や 400 も正解です。

入力例 2

630 940 314

出力例 2

-1

Score : 100 points

Problem Statement

Print a number between A and B (inclusive) that is a multiple of C.

If there is no such number, print -1.

Constraints

1 \leq A \leq B \leq 1000
1 \leq C \leq 1000
All values in input are integers.

Input

Input is given from Standard Input in the following format:

A B C

Output

Print the answer.
If there is no number with the desired property, print -1.

Sample Input 1

123 456 100

Sample Output 1

300 or 400 would also be accepted.

Sample Input 2

630 940 314

Sample Output 2

-1

C - Fibonacci Reversed

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

正整数 x に対し、f(x) を以下のように定義します。

x を（先頭に余分な 0 をつけずに）十進表記して得られる文字列を s_x、s_x を反転して得られる文字列を \text{rev}(s_x) とおく。 f(x) の値は、\text{rev}(s_x) を整数の十進表記としてみなすことで得られる整数である。

例えば、x=13 のとき \text{rev}(s_x)=\ 31 より f(x)=31 であり、x=10 のとき \text{rev}(s_x)=\ 01 より f(x)=1 です。特に、どのような正整数 x に対しても f(x) の値は正整数です。

正整数 X,Y が与えられます。正整数列 A=(a_1,a_2,\dots,a_{10}) を以下のように定義します。

a_1 = X
a_2 = Y
a_i = f(a_{i-1}＋a_{i-2})\ (i\geq 3)

a_{10} の値を求めてください。

制約

1\leq X,Y \leq 10^5
入力は全て整数

入力

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

X Y

出力

a_{10} の値を出力せよ。

入力例 1

1 1

出力例 1

A の各要素の値は以下の通りです。

a_1=1
a_2=1
a_3=2
a_4=3
a_5=5
a_6=8
a_7=31
a_8=93
a_9=421
a_{10}=415

よって 415 を出力します。

入力例 2

3 7

出力例 2

入力例 3

90701 90204

出力例 3

9560800101

Score : 200 points

Problem Statement

For a positive integer x, define f(x) as follows:

Let s_x be the string obtained by representing x in decimal notation (without leading zeros), and let \text{rev}(s_x) be the string obtained by reversing s_x. The value of f(x) is the integer obtained by interpreting \text{rev}(s_x) as a decimal representation of an integer.

For example, when x=13, we have \text{rev}(s_x)= 31, so f(x)=31; when x=10, we have \text{rev}(s_x)= 01, so f(x)=1. Particularly, for any positive integer x, the value of f(x) is a positive integer.

You are given positive integers X and Y. Define a sequence of positive integers A=(a_1,a_2,\dots,a_{10}) as follows:

a_1 = X
a_2 = Y
a_i = f(a_{i-1}+a_{i-2})\ (i\geq 3)

Find the value of a_{10}.

Constraints

1\leq X,Y \leq 10^5
All input values are integers.

Input

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

X Y

Output

Print the value of a_{10}.

Sample Input 1

1 1

Sample Output 1

The values of the elements of A are as follows:

a_1=1
a_2=1
a_3=2
a_4=3
a_5=5
a_6=8
a_7=31
a_8=93
a_9=421
a_{10}=415

Thus, print 415.

Sample Input 2

3 7

Sample Output 2

Sample Input 3

90701 90204

Sample Output 3

9560800101

D - Maintain Multiple Sequences

Time Limit: 2 sec / Memory Limit: 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 - Four Variables

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

正整数 N が与えられます。
正整数の組 (A,B,C,D) であって、AB + CD = N を満たすものの個数を求めてください。

なお、本問の制約の下、答えが 9 \times 10^{18} 以下であることが証明できます。

制約

2 \leq N \leq 2 \times 10^5
N は整数

入力

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

出力

答えを出力せよ。

入力例 1

出力例 1

(A,B,C,D) として以下の 8 個が考えられます。

(A,B,C,D)=(1,1,1,3)
(A,B,C,D)=(1,1,3,1)
(A,B,C,D)=(1,2,1,2)
(A,B,C,D)=(1,2,2,1)
(A,B,C,D)=(1,3,1,1)
(A,B,C,D)=(2,1,1,2)
(A,B,C,D)=(2,1,2,1)
(A,B,C,D)=(3,1,1,1)

入力例 2

出力例 2

入力例 3

出力例 3

Score : 300 points

Problem Statement

You are given a positive integer N.
Find the number of quadruples of positive integers (A,B,C,D) such that AB + CD = N.

Under the constraints of this problem, it can be proved that the answer is at most 9 \times 10^{18}.

Constraints

2 \leq N \leq 2 \times 10^5
N is an integer.

Input

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

Output

Print the answer.

Sample Input 1

Sample Output 1

Here are the eight desired quadruples.

(A,B,C,D)=(1,1,1,3)
(A,B,C,D)=(1,1,3,1)
(A,B,C,D)=(1,2,1,2)
(A,B,C,D)=(1,2,2,1)
(A,B,C,D)=(1,3,1,1)
(A,B,C,D)=(2,1,1,2)
(A,B,C,D)=(2,1,2,1)
(A,B,C,D)=(3,1,1,1)