AtCoder Daily Training MEDIUM 2024/03/20 20:00start

C - Slimes

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

A 匹のスライムがいます。

すぬけくんが 1 回叫ぶたびに、スライムは K 倍に増殖します。

スライムが B 匹以上になるには、すぬけくんは最小で何回叫ぶ必要があるでしょうか？

制約

1 \leq A \leq B \leq 10^9
2 \leq K \leq 10^9
入力は全て整数

入力

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

A B K

出力

答えを出力せよ。

入力例 1

1 4 2

出力例 1

はじめ、スライムが 1 匹います。すぬけくんが 1 回叫ぶとスライムは 2 匹になり、 2 回叫ぶとスライムは 4 匹になります。4 匹以上になるためには、最小で 2 回叫ぶ必要があります。

入力例 2

7 7 10

出力例 2

はじめからスライムは 7 匹います。

入力例 3

31 415926 5

出力例 3

Score : 200 points

Problem Statement

There are A slimes.

Each time Snuke shouts, the slimes multiply by K times.

In order to have B or more slimes, at least how many times does Snuke need to shout?

Constraints

1 \leq A \leq B \leq 10^9
2 \leq K \leq 10^9
All values in input are integers.

Input

Input is given from Standard Input in the following format:

A B K

Output

Print the answer.

Sample Input 1

1 4 2

Sample Output 1

We start with one slime. After Snuke's first shout, we have two slimes; after his second shout, we have four slimes. Thus, he needs to shout at least twice to have four or more slimes.

Sample Input 2

7 7 10

Sample Output 2

We have seven slimes already at the start.

Sample Input 3

31 415926 5

Sample Output 3

D - Same Name

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

N 人の人がいます。i \, (1 \leq i \leq N) 人目の人の姓は S_i、名は T_i です。

同姓同名であるような人の組が存在するか、すなわち 1 \leq i \lt j \leq N かつ S_i=S_j かつ T_i=T_j を満たすような整数対 (i,j) が存在するか判定してください。

制約

2 \leq N \leq 1000
N は整数
S_i,T_i は英小文字のみからなる長さ 1 以上 10 以下の文字列

入力

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

N
S_1 T_1
S_2 T_2
\hspace{0.6cm}\vdots
S_N T_N

出力

同姓同名であるような人の組が存在するなら Yes を、存在しないなら No を出力せよ。

入力例 1

3
tanaka taro
sato hanako
tanaka taro

出力例 1

Yes

1 人目の人と 3 人目の人が同姓同名です。

入力例 2

3
saito ichiro
saito jiro
saito saburo

出力例 2

No

同姓同名であるような人の組は存在しません。

入力例 3

4
sypdgidop bkseq
bajsqz hh
ozjekw mcybmtt
qfeysvw dbo

出力例 3

No

Score : 200 points

Problem Statement

There are N people. The family name and given name of the i-th person (1 \leq i \leq N) are S_i and T_i, respectively.

Determine whether there is a pair of people with the same family and given names. In other words, determine whether there is a pair of integers (i,j) such that 1 \leq i \lt j \leq N, S_i=S_j, and T_i=T_j.

Constraints

2 \leq N \leq 1000
N is an integer.
Each of S_i and T_i is a string of length between 1 and 10 (inclusive) consisting of English lowercase letters.

Input

Input is given from Standard Input in the following format:

N
S_1 T_1
S_2 T_2
\hspace{0.6cm}\vdots
S_N T_N

Output

If there is a pair of people with the same family and given names, print Yes; otherwise, print No.

Sample Input 1

3
tanaka taro
sato hanako
tanaka taro

Sample Output 1

Yes

The first and third persons have the same family and given names.

Sample Input 2

3
saito ichiro
saito jiro
saito saburo

Sample Output 2

No

No two persons have the same family and given names.

Sample Input 3

4
sypdgidop bkseq
bajsqz hh
ozjekw mcybmtt
qfeysvw dbo

Sample Output 3

No

E - Happy New Year!

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

10 進法で表記したときに 0,2 のみからなる正整数のうち、 K 番目に小さいものを求めてください。

制約

K は 1 以上 10^{18} 以下の整数

入力

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

出力

答えを整数として出力せよ。
ただし、たとえ答えが大きな整数であっても、求める答えを正確に整数として出力する必要がある。たとえば、 2.34e+22 のような指数表記や、 0523 のような先頭に不要な 0 を付けたような表記は許されない。

入力例 1

出力例 1

10 進法で表記した時に 0,2 のみからなる正整数を小さい方から並べると、 2,20,22,\dots となります。
このうち K=3 番目である 22 を出力してください。

入力例 2

出力例 2

入力例 3

923423423420220108

出力例 3

220022020000202020002022022000002020002222002200002022002200

たとえ答えが大きな整数であっても、求める答えを正確に整数として出力する必要があることに注意してください。

Score : 300 points

Problem Statement

Among the positive integers that consist of 0's and 2's when written in base 10, find the K-th smallest integer.

Constraints

K is an integer between 1 and 10^{18} (inclusive).

Input

Input is given from Standard Input in the following format:

Output

Print the answer as an integer.
Here, the exact value must be printed as an integer, even if it is big. Exponential notations such as 2.34e+22, for example, or unnecessary leading zeros such as 0523 are not allowed.

Sample Input 1

Sample Output 1

The positive integers that consist of 0's and 2's when written in base 10 are 2,20,22,\dots in ascending order.
The (K=) 3-rd of them, which is 22, should be printed.

Sample Input 2

Sample Output 2

Sample Input 3

923423423420220108

Sample Output 3

220022020000202020002022022000002020002222002200002022002200

Note that the exact value of the answer must be printed as an integer, even if it is big.

F - Make Takahashi Happy

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

H 行 W 列のマス目があります。 1 \leq i \leq H かつ 1 \leq j \leq W を満たす 2 つの整数 i, j について、上から i 行目、左から j 列目のマス（以下、(i, j) と表す）には、整数 A_{i, j} が書かれています。

いま、高橋君は (1, 1) にいます。これから高橋君は「いまいるマスから右または下に隣接するマスに移動する」ことを繰り返して、(H, W) まで移動します。ただし、その過程でマス目の外部に移動することは出来ません。

その結果、高橋君が通ったマス（始点 (1, 1) と終点 (H, W) を含む）に書かれた整数がすべて異なるとき、高橋君は嬉しくなります。高橋君の移動経路として考えられるもののうち、高橋君が嬉しくなるものの個数を出力してください。

制約

2 \leq H, W \leq 10
1 \leq A_{i, j} \leq 10^9
入力はすべて整数

入力

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

H W
A_{1, 1} A_{1, 2} \ldots A_{1, W}
A_{2, 1} A_{2, 2} \ldots A_{2, W}
\vdots
A_{H, 1} A_{H, 2} \ldots A_{H, W}

出力

答えを出力せよ。

入力例 1

出力例 1

高橋君の移動経路として考えられるものは下記の 6 通りです。

(1, 1) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (2, 3) \rightarrow (3, 3)：通ったマスに書かれた整数は 3, 2, 2, 3, 4 であり、高橋君は嬉しくなりません。
(1, 1) \rightarrow (1, 2) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (3, 3)：通ったマスに書かれた整数は 3, 2, 1, 3, 4 であり、高橋君は嬉しくなりません。
(1, 1) \rightarrow (1, 2) \rightarrow (2, 2) \rightarrow (3, 2) \rightarrow (3, 3)：通ったマスに書かれた整数は 3, 2, 1, 5, 4 であり、高橋君は嬉しくなります。
(1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (3, 3)：通ったマスに書かれた整数は 3, 2, 1, 3, 4 であり、高橋君は嬉しくなりません。
(1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (3, 2) \rightarrow (3, 3)：通ったマスに書かれた整数は 3, 2, 1, 5, 4 であり、高橋君は嬉しくなります。
(1, 1) \rightarrow (2, 1) \rightarrow (3, 1) \rightarrow (3, 2) \rightarrow (3, 3)：通ったマスに書かれた整数は 3, 2, 1, 5, 4 であり、高橋君は嬉しくなります。

よって、高橋君が嬉しくなる移動経路は、上で 3, 5, 6 番目に述べた 3 個です。

入力例 2

10 10
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
81 82 83 84 85 86 87 88 89 90
91 92 93 94 95 96 97 98 99 100

出力例 2

この例では、高橋君は考えられるどの経路を通っても嬉しくなります。

Score : 300 points

Problem Statement

There is a grid with H horizontal rows and W vertical columns. For two integers i and j such that 1 \leq i \leq H and 1 \leq j \leq W, the square at the i-th row from the top and j-th column from the left (which we denote by (i, j)) has an integer A_{i, j} written on it.

Takahashi is currently at (1,1). From now on, he repeats moving to an adjacent square to the right of or below his current square until he reaches (H, W). When he makes a move, he is not allowed to go outside the grid.

Takahashi will be happy if the integers written on the squares he visits (including initial (1, 1) and final (H, W)) are distinct. Find the number of his possible paths that make him happy.

Constraints

2 \leq H, W \leq 10
1 \leq A_{i, j} \leq 10^9
All values in the input are integers.

Input

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

H W
A_{1, 1} A_{1, 2} \ldots A_{1, W}
A_{2, 1} A_{2, 2} \ldots A_{2, W}
\vdots
A_{H, 1} A_{H, 2} \ldots A_{H, W}

Output

Print the answer.

Sample Input 1

Sample Output 1

There are six possible paths:

(1, 1) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (2, 3) \rightarrow (3, 3): the integers written on the squares he visits are 3, 2, 2, 3, 4, so he will not be happy.
(1, 1) \rightarrow (1, 2) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (3, 3): the integers written on the squares he visits are 3, 2, 1, 3, 4, so he will not be happy.
(1, 1) \rightarrow (1, 2) \rightarrow (2, 2) \rightarrow (3, 2) \rightarrow (3, 3): the integers written on the squares he visits are 3, 2, 1, 5, 4, so he will be happy.
(1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (3, 3): the integers written on the squares he visits are 3, 2, 1, 3, 4, so he will not be happy.
(1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (3, 2) \rightarrow (3, 3): the integers written on the squares he visits are 3, 2, 1, 5, 4, so he will be happy.
(1, 1) \rightarrow (2, 1) \rightarrow (3, 1) \rightarrow (3, 2) \rightarrow (3, 3): the integers written on the squares he visits are 3, 2, 1, 5, 4, so he will be happy.

Thus, the third, fifth, and sixth paths described above make him happy.

Sample Input 2

10 10
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
81 82 83 84 85 86 87 88 89 90
91 92 93 94 95 96 97 98 99 100

Sample Output 2

In this example, every possible path makes him happy.

G - Make Bipartite 2

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

N 個の頂点と M 本の辺からなる単純な（すなわち、自己ループも多重辺も含まない）無向グラフ G が与えられます。 i = 1, 2, \ldots, M について、i 番目の辺は頂点 u_i と頂点 v_i を結びます。

1 \leq u \lt v \leq N を満たす整数の組 (u, v) であって、下記の 2 つの条件をともに満たすものの個数を出力してください。

グラフ G において、頂点 u と頂点 v を結ぶ辺は存在しない。
グラフ G に、頂点 u と頂点 v を結ぶ辺を追加して得られるグラフは、二部グラフである。

二部グラフとは？

無向グラフが二部グラフであるとは、下記の条件を満たすように各頂点を黒または白のどちらかの色で塗ることができることを言います。

同じ色に塗られた頂点どうしを結ぶ辺は存在しない。

制約

2 \leq N \leq 2 \times 10^5
0 \leq M \leq \min \lbrace 2 \times 10^5, N(N-1)/2 \rbrace
1 \leq u_i, v_i \leq N
グラフ G は単純
入力はすべて整数

入力

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

N M
u_1 v_1
u_2 v_2
\vdots
u_M v_M

出力

答えを出力せよ。

入力例 1

出力例 1

問題文中の条件を満たす整数の組 (u, v) は、(1, 4) と (1, 5) の 2 つです。よって、2 を出力します。
他の組については、例えば、(1, 3) はグラフ G において頂点 1 と頂点 3 を結ぶ辺が存在することから、 (4, 5) はグラフ G に頂点 4 と頂点 5 を結ぶ辺を追加して得られるグラフが二部グラフではないことから、それぞれ問題文中の条件を満たしません。

入力例 2

出力例 2

与えられるグラフが二部グラフであったり連結であるとは限らないことに注意してください。

入力例 3

出力例 3

Score : 400 points

Problem Statement

You are given a simple undirected graph G with N vertices and M edges (a simple graph does not contain self-loops or multi-edges). For i = 1, 2, \ldots, M, the i-th edge connects vertex u_i and vertex v_i.

Print the number of pairs of integers (u, v) that satisfy 1 \leq u \lt v \leq N and both of the following conditions.

The graph G does not have an edge connecting vertex u and vertex v.
Adding an edge connecting vertex u and vertex v in the graph G results in a bipartite graph.

What is a bipartite graph?

An undirected graph is said to be bipartite if and only if one can paint each vertex black or white to satisfy the following condition.

No edge connects vertices painted in the same color.

Constraints

2 \leq N \leq 2 \times 10^5
0 \leq M \leq \min \lbrace 2 \times 10^5, N(N-1)/2 \rbrace
1 \leq u_i, v_i \leq N
The graph G is simple.
All values in the input are integers.

Input

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

N M
u_1 v_1
u_2 v_2
\vdots
u_M v_M

Output

Print the answer.

Sample Input 1

Sample Output 1

We have two pairs of integers (u, v) that satisfy the conditions in the problem statement: (1, 4) and (1, 5). Thus, you should print 2.
The other pairs do not satisfy the conditions. For instance, for (1, 3), the graph G has an edge connecting vertex 1 and vertex 3; for (4, 5), adding an edge connecting vertex 4 and vertex 5 in the graph G does not result in a bipartite graph.

Sample Input 2

Sample Output 2

Note that the given graph may not be bipartite or connected.

Sample Input 3