AtCoder Daily Training EASY 2024/03/14 18:30start

A - Last Card

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100 点

問題文

1,2,\ldots,N の番号のついた N 人の人に合計 K 枚のカードを配ります。

人 A から始めて人 A,A+1,A+2,\ldots,N,1,2,\ldots の順に 1 枚ずつカードを配るとき、最後のカードは誰に配られるでしょうか？

厳密には、人 x(1 \leq x < N) の次には人 x+1 にカードを配り、人 N の次には人 1 にカードを配ります。

制約

1 \leq N,K \leq 1000
1 \leq A \leq N
入力は全て整数

入力

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

N K A

出力

最後のカードが配られた人の番号を出力せよ。

入力例 1

3 3 2

出力例 1

人 2、人 3、人 1 の順にカードを配ります。

入力例 2

1 100 1

出力例 2

入力例 3

3 14 2

出力例 3

Score : 100 points

Problem Statement

We will hand out a total of K cards to N people numbered 1, 2, \ldots, N.

Beginning with Person A, we will give the cards one by one to the people in this order: A, A+1, A+2, \ldots, N, 1, 2, \ldots. Who will get the last card?

Formally, after Person x(1 \leq x < N) gets a card, Person x+1 will get a card. After Person N gets a card, Person 1 gets a card.

Constraints

1 \leq N,K \leq 1000
1 \leq A \leq N
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K A

Output

Print a number representing the person who will get the last card.

Sample Input 1

3 3 2

Sample Output 1

The cards are given to Person 2, 3, 1 in this order.

Sample Input 2

1 100 1

Sample Output 2

Sample Input 3

3 14 2

Sample Output 3

B - Power

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100 点

問題文

整数 A, B が与えられます。 A^B の値を出力してください。

制約

1 \leq A, B \leq 9
入力はすべて整数

入力

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

A B

出力

答えを出力せよ。

入力例 1

4 3

出力例 1

4^3 = 64 であるので、64 を出力します。

入力例 2

5 5

出力例 2

入力例 3

8 1

出力例 3

Score : 100 points

Problem Statement

Given integers A and B, print the value A^B.

Constraints

1 \leq A, B \leq 9
All values in the input are integers.

Input

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

A B

Output

Print the answer.

Sample Input 1

4 3

Sample Output 1

4^3 = 64, so 64 should be printed.

Sample Input 2

5 5

Sample Output 2

Sample Input 3

8 1

Sample Output 3

C - Integer Division

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 200 点

問題文

-10^{18} 以上 10^{18} 以下の整数 X が与えられるので、\left\lfloor \dfrac{X}{10} \right\rfloor を出力してください。

注記

実数 x に対して、「x 以下の整数の中で最大の整数」を \left\lfloor x \right\rfloor と表します。たとえば \left\lfloor 4.7 \right\rfloor = 4, \left\lfloor -2.4 \right\rfloor = -3, \left\lfloor 5 \right\rfloor = 5 のようになります。(詳しくは入出力例にある説明を参考にしてください。)

制約

-10^{18} \leq X \leq 10^{18}
入力はすべて整数である。

入力

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

出力

\left\lfloor \frac{X}{10} \right\rfloor を出力せよ。整数として出力する必要があることに注意せよ。

入力例 1

出力例 1

\frac{47}{10} = 4.7 以下の整数は、すべての負の整数および 0, 1, 2, 3, 4 です。この中で一番大きい整数は 4 なので、\left\lfloor \frac{47}{10} \right\rfloor = 4 となります。

入力例 2

-24

出力例 2

-3

\frac{-24}{10} = -2.4 以下の整数の中で一番大きい整数は -3 なので、 \left\lfloor \frac{-24}{10} \right\rfloor = -3 となります。
-2 は -2.4 よりも大きいので、条件を満たさないことに注意してください。

入力例 3

出力例 3

\frac{50}{10} = 5 以下の整数の中で一番大きい整数は 5 自身です。よって \left\lfloor \frac{50}{10} \right\rfloor = 5 となります。

入力例 4

-30

出力例 4

-3

上の例と同様に \left\lfloor \frac{-30}{10} \right\rfloor = -3 となります。

入力例 5

987654321987654321

出力例 5

98765432198765432

答えは 98765432198765432 となります。すべての桁が正しく合っているか確認しましょう。

なお、もしも自分で書いたプログラムが想定通りの挙動をしない場合は、使用しているプログラミング言語の仕様を調べてみることを推奨します。
また、自分の書いたコードがどのように動作するかを確認したい場合は問題文上部の「コードテスト」をご利用ください。

Score : 200 points

Problem Statement

Given an integer X between -10^{18} and 10^{18} (inclusive), print \left\lfloor \dfrac{X}{10} \right\rfloor.

Notes

For a real number x, \left\lfloor x \right\rfloor denotes "the maximum integer not exceeding x". For example, we have \left\lfloor 4.7 \right\rfloor = 4, \left\lfloor -2.4 \right\rfloor = -3, and \left\lfloor 5 \right\rfloor = 5. (For more details, please refer to the description in the Sample Input and Output.)

Constraints

-10^{18} \leq X \leq 10^{18}
All values in input are integers.

Input

Input is given from Standard Input in the following format:

Output

Print \left\lfloor \frac{X}{10} \right\rfloor. Note that it should be output as an integer.

Sample Input 1

Sample Output 1

The integers that do not exceed \frac{47}{10} = 4.7 are all the negative integers, 0, 1, 2, 3, and 4. The maximum integer among them is 4, so we have \left\lfloor \frac{47}{10} \right\rfloor = 4.

Sample Input 2

-24

Sample Output 2

-3

Since the maximum integer not exceeding \frac{-24}{10} = -2.4 is -3, we have \left\lfloor \frac{-24}{10} \right\rfloor = -3.
Note that -2 does not satisfy the condition, as -2 exceeds -2.4.

Sample Input 3

Sample Output 3

The maximum integer that does not exceed \frac{50}{10} = 5 is 5 itself. Thus, we have \left\lfloor \frac{50}{10} \right\rfloor = 5.

Sample Input 4

-30

Sample Output 4

-3

Just like the previous example, \left\lfloor \frac{-30}{10} \right\rfloor = -3.

Sample Input 5

987654321987654321

Sample Output 5

98765432198765432

The answer is 98765432198765432. Make sure that all the digits match.

If your program does not behave as intended, we recommend you checking the specification of the programming language you use.
If you want to check how your code works, you may use "Custom Test" above the Problem Statement.

D - Star or Not

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 200 点

問題文

N 頂点 N-1 辺の木が与えられます。
頂点には 1,2,\ldots,N の番号がついており、i 本目の辺は頂点 a_i と頂点 b_i を結んでいます。

この木がスターであるか判定してください。

ただしスターとは、1 つの頂点から、他の全ての頂点に 1 本ずつ辺が出ている木のことです。

注記

「木」については、Wikipedia「木(数学)」を参照してください。

制約

3 \leq N \leq 10^5
1 \leq a_i \lt b_i \leq N
与えられるグラフは木である

入力

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

N
a_1 b_1
\vdots
a_{N-1} b_{N-1}

出力

与えられたグラフがスターであるなら Yes と、スターでないなら No と出力せよ。

入力例 1

出力例 1

Yes

与えられたグラフはスターです。

入力例 2

出力例 2

No

与えられたグラフはスターではありません。

入力例 3

出力例 3

Yes

Score : 200 points

Problem Statement

You are given a tree with N vertices and N-1 edges.
The vertices are numbered 1,2,\ldots,N. The i-th edge connects Vertex a_i and Vertex b_i.

Determine whether this tree is a star.

Here, a star is a tree where there is a vertex directly connected to all other vertices.

Notes

For the definition of a tree, see Tree (graph theory) - Wikipedia.

Constraints

3 \leq N \leq 10^5
1 \leq a_i \lt b_i \leq N
The given graph is a tree.

Input

Input is given from Standard Input in the following format:

N
a_1 b_1
\vdots
a_{N-1} b_{N-1}

Output

If the given graph is a star, print Yes; otherwise, print No.

Sample Input 1

Sample Output 1

Yes

The given graph is a star.

Sample Input 2

Sample Output 2

No

The given graph is not a star.

Sample Input 3

Sample Output 3

Yes

E - Many Balls

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 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.