AtCoder Daily Training EASY 2024/11/26 19:30start

A - Spread

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

英大文字からなる文字列 S が与えられます。S の各文字を空白で区切り、その順で 1 文字ずつ出力してください。

制約

S は長さ 2 以上 100 以下の英大文字からなる文字列

入力

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

出力

S の各文字を空白で区切り、1 文字ずつ出力せよ。

入力例 1

ABC

出力例 1

A B C

A, B, C を空白で区切り、1 文字ずつ出力してください。

C の後ろに空白を出力する必要がないことに注意してください。

入力例 2

ZZZZZZZ

出力例 2

Z Z Z Z Z Z Z

入力例 3

OOXXOO

出力例 3

O O X X O O

Score : 100 points

Problem Statement

You are given a string S consisting of uppercase English letters. Separate each character of S with a space and print them one by one in order.

Constraints

S is a string consisting of uppercase English letters with a length between 2 and 100, inclusive.

Input

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

Output

Separate each character of S with a space and print them one by one.

Sample Input 1

ABC

Sample Output 1

A B C

Separate A, B, and C with spaces and print them one by one.

There is no need to print a space after C.

Sample Input 2

ZZZZZZZ

Sample Output 2

Z Z Z Z Z Z Z

Sample Input 3

OOXXOO

Sample Output 3

O O X X O O

B - 2^N

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

N が与えられます。2^N を出力してください。

制約

0 \leq N \leq 30
N は整数である

入力

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

出力

答えを出力せよ。

入力例 1

出力例 1

2^3=8 です。

入力例 2

出力例 2

1073741824

Score : 100 points

Problem Statement

Given N, print 2^N.

Constraints

0 \leq N \leq 30
N is an integer.

Input

Input is given from Standard Input in the following format:

Output

Print the answer.

Sample Input 1

Sample Output 1

We have 2^3=8.

Sample Input 2

Sample Output 2

1073741824

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 - Maritozzo

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

英小文字からなる 3 つの文字列 S_1, S_2, S_3 と、1、2、3 のみからなる文字列 T が与えられます。

T の各文字に対応する文字列を連結してできる文字列を出力してください。より厳密には、以下の指示にしたがって文字列を出力してください。

1 \leq i \leq |T| を満たす整数 i に対し、文字列 s_i を次のように定める。
- T の i 文字目が 1 のとき、S_1
- T の i 文字目が 2 のとき、S_2
- T の i 文字目が 3 のとき、S_3
s_1, s_2, \dots, s_{|T|} をこの順に連結してできる文字列を出力する。

制約

1 \leq |S_1|, |S_2|, |S_3| \leq 10
1 \leq |T| \leq 1000
S_1, S_2, S_3 は英小文字からなる。
T は 1、2、3 のみからなる。

入力

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

S_1
S_2
S_3
T

出力

答えを出力せよ。

入力例 1

mari
to
zzo
1321

出力例 1

marizzotomari

s_1 = mari, s_2 = zzo, s_3 = to, s_4 = mari であるので、これらを連結してできる文字列である marizzotomari を出力します。

入力例 2

abra
cad
abra
123

出力例 2

abracadabra

入力例 3

a
b
c
1

出力例 3

Score : 200 points

Problem Statement

You are given three strings S_1, S_2, S_3 consisting of lowercase English letters, and a string T consisting of 1, 2, 3.

Concatenate the three strings according to the characters in T and print the resulting string. Formally, conform to the following instructions.

For each integer i such that 1 \leq i \leq |T|, let the string s_i be defined as follows:
- S_1, if the i-th character of T is 1;
- S_2, if the i-th character of T is 2;
- S_3, if the i-th character of T is 3.
Concatenate the strings s_1, s_2, \dots, s_{|T|} in this order and print the resulting string.

Constraints

1 \leq |S_1|, |S_2|, |S_3| \leq 10
1 \leq |T| \leq 1000
S_1, S_2, and S_3 consist of lowercase English letters.
T consists of 1, 2, and 3.

Input

Input is given from Standard Input in the following format:

S_1
S_2
S_3
T

Output

Print the answer.

Sample Input 1

mari
to
zzo
1321

Sample Output 1

marizzotomari

We have s_1 = mari, s_2 = zzo, s_3 = to, s_4 = mari. Concatenate these and print the resulting string: marizzotomari.

Sample Input 2

abra
cad
abra
123

Sample Output 2

abracadabra

Sample Input 3

a
b
c
1

Sample Output 3

E - Many Balls

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

空の箱があります。
髙橋君は以下の 2 種類の魔法を好きな順番で好きな回数使えます。

魔法 A ：箱の中にボールを 1 つ増やす
魔法 B ：箱の中のボールの数を 2 倍にする

合計 \mathbf{120} 回以内の魔法で、箱の中のボールの数をちょうど N 個にする方法を 1 つ教えてください。
なお、与えられた制約のもとで条件を満たす方法が必ず存在することが示せます。

魔法以外の方法でボールの数を変化させることはできません。

制約

1 \leq N \leq 10^{18}
入力は全て整数

入力

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

出力

A , B のみからなる文字列 S を出力せよ。
S の i 文字目が A ならば、髙橋君が i 回目に使う魔法が魔法 A であることを表し、B ならば魔法 B であることを表す。

S の長さは \mathbf{120} 以下でなければならない。

入力例 1

出力例 1

AABA

ボールの数は、0 \xrightarrow{A} 1\xrightarrow{A} 2 \xrightarrow{B}4\xrightarrow{A} 5 と変化します。
AAAAA などの答えも正解になります。

入力例 2

出力例 2

BBABBAAAB

ボールの数は、0 \xrightarrow{B} 0 \xrightarrow{B} 0 \xrightarrow{A}1 \xrightarrow{B} 2 \xrightarrow{B} 4 \xrightarrow{A}5 \xrightarrow{A}6 \xrightarrow{A} 7 \xrightarrow{B}14 と変化します。
S の長さを最小化する必要はありません。

Score : 300 points

Problem Statement

We have an empty box.
Takahashi can cast the following two spells any number of times in any order.

Spell A: puts one new ball into the box.
Spell B: doubles the number of balls in the box.

Tell us a way to have exactly N balls in the box with at most \mathbf{120} casts of spells.
It can be proved that there always exists such a way under the Constraints given.

There is no way other than spells to alter the number of balls in the box.

Constraints

1 \leq N \leq 10^{18}
All values in input are integers.

Input

Input is given from Standard Input in the following format:

Output

Print a string S consisting of A and B. The i-th character of S should represent the spell for the i-th cast.

S must have at most \mathbf{120} characters.

Sample Input 1

Sample Output 1

AABA

This changes the number of balls as follows: 0 \xrightarrow{A} 1\xrightarrow{A} 2 \xrightarrow{B}4\xrightarrow{A} 5.
There are also other acceptable outputs, such as AAAAA.

Sample Input 2

Sample Output 2

BBABBAAAB

This changes the number of balls as follows: 0 \xrightarrow{B} 0 \xrightarrow{B} 0 \xrightarrow{A}1 \xrightarrow{B} 2 \xrightarrow{B} 4 \xrightarrow{A}5 \xrightarrow{A}6 \xrightarrow{A} 7 \xrightarrow{B}14.
It is not required to minimize the length of S.