AtCoder Daily Training EASY 2024/1/3 18:00start

A - Signed Difficulty

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

実数 X.Y が与えられます。ただし Y はちょうど 1 桁です。

0 \leq Y \leq 2 ならば、X-
3 \leq Y \leq 6 ならば、X
7 \leq Y \leq 9 ならば、X+

と出力してください。

制約

1 \leq X \leq 15
0 \leq Y \leq 9
X と Y は整数

入力

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

X.Y

出力

答えを出力せよ。

入力例 1

15.8

出力例 1

15+

15 + のような出力は不正解とみなされます。
X と + の間や、X と - の間には空白を入れずに出力してください。

入力例 2

1.0

出力例 2

1-

1.00 や 1 などの値が入力として与えられることはありません。

入力例 3

12.5

出力例 3

Score : 100 points

Problem Statement

You are given a real number X.Y, where Y is a single digit.

Print the following: (quotes for clarity)

X-, if 0 \leq Y \leq 2;
X, if 3 \leq Y \leq 6;
X+, if 7 \leq Y \leq 9.

Constraints

1 \leq X \leq 15
0 \leq Y \leq 9
X and Y are integers.

Input

Input is given from Standard Input in the following format:

X.Y

Output

Print the answer.

Sample Input 1

15.8

Sample Output 1

15+

Here, printing 15 + will not be accepted: do not print a space between X and +, or between X and -.

Sample Input 2

1.0

Sample Output 2

1-

You will not get inputs such as 1.00 and 1.

Sample Input 3

12.5

Sample Output 3

B - Leyland Number

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

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

制約

2 \leq A \leq B \leq 9
入力される数値はすべて整数

入力

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

A B

出力

答えを整数として出力せよ。

入力例 1

2 8

出力例 1

A = 2, B = 8 のとき、A^B = 256, B^A = 64 なので A^B + B^A = 320 です。

入力例 2

9 9

出力例 2

774840978

入力例 3

5 6

出力例 3

Score : 100 points

Problem Statement

You are given positive integers A and B.
Print the value A^B+B^A.

Constraints

2 \leq A \leq B \leq 9
All input values are integers.

Input

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

A B

Output

Print the answer as an integer.

Sample Input 1

2 8

Sample Output 1

For A = 2, B = 8, we have A^B = 256, B^A = 64, so A^B + B^A = 320.

Sample Input 2

9 9

Sample Output 2

774840978

Sample Input 3

5 6

Sample Output 3

C - Star or Not

Time Limit: 2 sec / Memory Limit: 1024 MiB

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

D - Who is Saikyo?

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

N 人の競技プログラマーがいます。順に人 1, 人 2, \dots, 人 N と呼びます。
競技プログラマーの間には強さと呼ばれる関係性があり、相異なる 2 人組 (人 X, 人 Y) 全てに対して「人 X は人 Y より強い」または「人 Y は人 X より強い」のどちらか一方が成り立ちます。
強さは 推移律 が成り立ちます。言い換えると、相異なる 3 人組 (人 X, 人 Y, 人 Z) 全てに対して次の条件が成り立ちます。

人 X が人 Y よりも強く、かつ人 Y が人 Z よりも強いとき、人 X は人 Z よりも強い。

人 X が自分以外のどの人 Y に対しても「人 X は人 Y より強い」という関係が成り立つ時、人 X を 最強のプログラマー と呼びます。(上記の制約下においてそのような人がちょうど 1 人存在することが証明できます)

あなたは M 個の強さに関する情報を知っています。i 個目の情報は「人 A_i は人 B_i より強い」という情報です。
あなたは情報を元に N 人の中から最強のプログラマーを特定することができますか？
最強のプログラマーを特定できる場合はその人の番号を出力してください。特定できない場合、つまり最強のプログラマーとしてあり得る人が複数人いる場合は -1 を出力してください。

制約

2 \leq N \leq 50
0 \leq M \leq \frac{N(N-1)}{2}
1 \leq A_i, B_i \leq N
A_i \neq B_i
i \neq j ならば (A_i, B_i) \neq (A_j, B_j)
全ての情報が正しくなるように、全ての相異なる 2 人組にどちらが強いかを割り当てる方法が少なくとも 1 通り存在する

入力

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

N M
A_1 B_1
A_2 B_2
\vdots
A_M B_M

出力

最強のプログラマーを特定できる場合はその人の番号を出力せよ。特定できない場合は -1 を出力せよ。

入力例 1

3 2
1 2
2 3

出力例 1

あなたは「人 1 は人 2 より強い」「人 2 は人 3 より強い」という情報が分かっています。
推移律から「人 1 は人 3 より強い」という情報もわかるので、人 1 は最強のプログラマーです。

入力例 2

3 2
1 3
2 3

出力例 2

-1

最強のプログラマーである可能性がある人は人 1 と人 2 です。最強のプログラマーを一意に特定できないので -1 を出力してください。

入力例 3

出力例 3

-1

Score : 300 points

Problem Statement

There are N competitive programmers numbered person 1, person 2, \ldots, and person N.
There is a relation called superiority between the programmers. For all pairs of distinct programmers (person X, person Y), exactly one of the following two relations holds: "person X is stronger than person Y" or "person Y is stronger than person X."
The superiority is transitive. In other words, for all triplets of distinct programmers (person X, person Y, person Z), it holds that:

if person X is stronger than person Y and person Y is stronger than person Z, then person X is stronger than person Z.

A person X is said to be the strongest programmer if person X is stronger than person Y for all people Y other than person X. (Under the constraints above, we can prove that there is always exactly one such person.)

You have M pieces of information on their superiority. The i-th of them is that "person A_i is stronger than person B_i."
Can you determine the strongest programmer among the N based on the information?
If you can, print the person's number. Otherwise, that is, if there are multiple possible strongest programmers, print -1.

Constraints

2 \leq N \leq 50
0 \leq M \leq \frac{N(N-1)}{2}
1 \leq A_i, B_i \leq N
A_i \neq B_i
If i \neq j, then (A_i, B_i) \neq (A_j, B_j).
There is at least one way to determine superiorities for all pairs of distinct programmers, that is consistent with the given information.

Input

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

N M
A_1 B_1
A_2 B_2
\vdots
A_M B_M

Output

If you can uniquely determine the strongest programmer, print the person's number; otherwise, print -1.

Sample Input 1

3 2
1 2
2 3

Sample Output 1

You have two pieces of information: "person 1 is stronger than person 2" and "person 2 is stronger than person 3."
By the transitivity, you can also infer that "person 1 is stronger than person 3," so person 1 is the strongest programmer.

Sample Input 2

3 2
1 3
2 3

Sample Output 2

-1

Both person 1 and person 2 may be the strongest programmer. Since you cannot uniquely determine which is the strongest, you should print -1.

Sample Input 3

Sample Output 3

-1

E - Calendar Validator

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

10^{100} 行 7 列の行列 A があり、任意の整数対 (i,j)\ (1 \leq i \leq 10^{100}, 1 \leq j \leq 7) についてその (i,j) 成分は (i-1) \times 7 + j です。

N 行 M 列の行列 B が与えられるので、B が A から一部の矩形領域を（向きを変えずに）切り出したものであるかを判定してください。

制約

1 \leq N \leq 10^4
1 \leq M \leq 7
1 \leq B_{i,j} \leq 10^9
入力はすべて整数

入力

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

N M
B_{1,1} B_{1,2} \ldots B_{1,M}
B_{2,1} B_{2,2} \ldots B_{2,M}
\hspace{1.6cm}\vdots
B_{N,1} B_{N,2} \ldots B_{N,M}

出力

B が A から一部の矩形領域を切り出したものであれば Yes と、そうでないなら No と出力せよ。

入力例 1

2 3
1 2 3
8 9 10

出力例 1

Yes

与えられる B は、A の左上 2 行 3 列を切り出したものとなっています。

入力例 2

2 1
1
2

出力例 2

No

与えられる B を 90 度回転させると A の左上 1 行 2 列と一致しますが、問題文中に「向きを変えずに」とある通り回転による一致は認められていないため、答えは No となります。

入力例 3

10 4
1346 1347 1348 1349
1353 1354 1355 1356
1360 1361 1362 1363
1367 1368 1369 1370
1374 1375 1376 1377
1381 1382 1383 1384
1388 1389 1390 1391
1395 1396 1397 1398
1402 1403 1404 1405
1409 1410 1411 1412

出力例 3

Yes

Score : 300 points

Problem Statement

There is a 10^{100} \times 7 matrix A, where the (i,j)-th entry is (i-1) \times 7 + j for every pair of integers (i,j)\ (1 \leq i \leq 10^{100}, 1 \leq j \leq 7).

Given an N \times M matrix B, determine whether B is some (unrotated) rectangular part of A.

Constraints

1 \leq N \leq 10^4
1 \leq M \leq 7
1 \leq B_{i,j} \leq 10^9
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
B_{1,1} B_{1,2} \ldots B_{1,M}
B_{2,1} B_{2,2} \ldots B_{2,M}
\hspace{1.6cm}\vdots
B_{N,1} B_{N,2} \ldots B_{N,M}

Output

If B is some rectangular part of A, print Yes; otherwise, print No.

Sample Input 1

2 3
1 2 3
8 9 10

Sample Output 1

Yes

The given matrix B is the top-left 2 \times 3 submatrix of A.

Sample Input 2

2 1
1
2

Sample Output 2

No

Although the given matrix B would match the top-left 1 \times 2 submatrix of A after rotating 90 degrees, the Problem Statement asks whether B is an unrotated part of A, so the answer is No.

Sample Input 3

10 4
1346 1347 1348 1349
1353 1354 1355 1356
1360 1361 1362 1363
1367 1368 1369 1370
1374 1375 1376 1377
1381 1382 1383 1384
1388 1389 1390 1391
1395 1396 1397 1398
1402 1403 1404 1405
1409 1410 1411 1412

Sample Output 3

Yes