AtCoder Daily Training EASY 2025/04/01 15:30start

A - Five Integers

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

与えられる 5 つの整数 A, B, C, D, E の中に何種類の整数があるかを出力してください。

制約

0 \leq A, B, C, D, E \leq 100
入力はすべて整数

入力

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

A B C D E

出力

答えを出力せよ。

入力例 1

31 9 24 31 24

出力例 1

与えられる 5 つの整数 31, 9, 24, 31, 24 の中には、9, 24, 31 という 3 種類の整数があります。よって、3 を出力します。

入力例 2

0 0 0 0 0

出力例 2

Score : 100 points

Problem Statement

Print how many distinct integers there are in given five integers A, B, C, D, and E.

Constraints

0 \leq A, B, C, D, E \leq 100
All values in input are integers.

Input

Input is given from Standard Input in the following format:

A B C D E

Output

Print the answer.

Sample Input 1

31 9 24 31 24

Sample Output 1

In the given five integers 31, 9, 24, 31, and 24, there are three distinct integers 9, 24, and 31. Thus, 3 should be printed.

Sample Input 2

0 0 0 0 0

Sample Output 2

B - Cyclic

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

各桁が 1 以上 9 以下の整数である 3 桁の整数 N が与えられます。

N の 100 の位を a、10 の位を b、1 の位を c としたとき、b,c,a をこの順に並べた整数と c,a,b をこの順に並べた整数をそれぞれ出力してください。

制約

N は各桁が 1 以上 9 以下の整数である 3 桁の整数

入力

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

出力

b,c,a をこの順に並べた整数と c,a,b をこの順に並べた整数をこの順で空白区切りで出力せよ。

入力例 1

出力例 1

793 937

379 の 100 の位は 3、10 の位は 7、1 の位は 9 です。よって、793 と 937 をそれぞれ出力します。

入力例 2

出力例 2

199 991

919 の 100 の位は 9、10 の位は 1、1 の位は 9 です。よって、199 と 991 をそれぞれ出力します。

Score : 100 points

Problem Statement

You are given a three-digit integer N where each digit is an integer between 1 and 9, inclusive.

Let a, b, c be the hundreds, tens, ones digits of N, respectively. Print an integer formed by arranging b, c, a in this order, and an integer formed by arranging c, a, b in this order.

Constraints

N is a three-digit integer where each digit is an integer between 1 and 9, inclusive.

Input

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

Output

Print two integers separated by a space in the following order: an integer formed by arranging b, c, a in this order, and an integer formed by arranging c, a, b in this order.

Sample Input 1

Sample Output 1

793 937

The hundreds, tens, ones digits of 379 are 3, 7, 9, respectively, so print 793 and 937.

Sample Input 2

Sample Output 2

199 991

The hundreds, tens, ones digits of 919 are 9, 1, 9, respectively, so print 199 and 991.

C - 3-smooth Numbers

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

正の整数 N が与えられます。 N=2^x3^y を満たす整数 x,y が存在するなら Yes 、そうでなければ No と出力してください。

制約

1\leq N\leq10^{18}
N は整数

入力

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

出力

条件を満たす整数 x,y が存在するなら Yes 、そうでなければ No と 1 行に出力せよ。

入力例 1

出力例 1

Yes

x=2,y=4 とすると、2^x3^y=2^23^4=4\times81=324 となるため条件を満たします。よって、Yes と出力してください。

入力例 2

出力例 2

No

どのような整数 x,y をとっても 2^x3^y=5 とすることはできません。よって、No と出力してください。

入力例 3

出力例 3

Yes

x=5,y=0 とすると、2^x3^y=32\times1=32 となるため、Yes と出力してください。

入力例 4

37748736

出力例 4

Yes

Score : 200 points

Problem Statement

You are given a positive integer N. If there are integers x and y such that N=2^x3^y, print Yes; otherwise, print No.

Constraints

1\leq N\leq10^{18}
N is an integer.

Input

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

Output

Print a single line containing Yes if there are integers x and y that satisfy the condition, and No otherwise.

Sample Input 1

Sample Output 1

Yes

For x=2,y=4, we have 2^x3^y=2^23^4=4\times81=324, so the condition is satisfied. Thus, you should print Yes.

Sample Input 2

Sample Output 2

No

There are no integers x and y such that 2^x3^y=5. Thus, you should print No.

Sample Input 3

Sample Output 3

Yes

For x=5,y=0, we have 2^x3^y=32\times1=32, so you should print Yes.

Sample Input 4

37748736

Sample Output 4

Yes

D - Find snuke

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 250 点

問題文

縦 H マス \times 横 W マスのマス目があり、各マスに 1 つずつ英小文字が書き込まれています。上から i 行目かつ左から j 列目のマスを (i,j) で表します。

マス目に書き込まれている英小文字は H 個の長さ W の文字列 S_1,S_2,\ldots, S_H によって与えられ、 S_i の j 文字目が、(i, j) に書き込まれた英小文字を表します。

マス目の中に、s, n, u, k, e が この順に(縦・横・ななめのいずれかの方向に) 連続して並んでいる 場所がただ 1 つ存在します。
そのような場所を見つけ、そのマスの位置を出力の形式に従って出力してください。

ただし、s, n, u, k, e が この順に(縦・横・ななめのいずれかの方向に) 連続して並んでいる場所とは、 5 つのマスの組 (A_1,A_2,A_3,A_4,A_5) であって、次をすべてみたすものをさします。

A_1,A_2,A_3,A_4,A_5 に書き込まれた英小文字はそれぞれ s, n, u, k, e である。
1\leq i\leq 4 について、A_i と A_{i+1} は頂点または辺を共有している。
A_1,A_2,A_3,A_4,A_5 の中心はこの順に一直線上に等間隔で並んでいる。

制約

5\leq H\leq 100
5\leq W\leq 100
H,W は整数
S_i は英小文字のみからなる長さ W の文字列
与えられるマス目の中に条件をみたす場所がただ 1 つ存在する

入力

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

H W
S_1
S_2
\vdots
S_H

出力

次の形式にしたがって、5 行出力せよ。

条件をみたす場所のうち s, n, u, k, e が書かれたマスがそれぞれ (R_1,C_1), (R_2,C_2)\ldots,(R_5,C_5) であるとき、 i 行目には R_i と C_i をこの順に空白区切りで出力せよ。

すなわち、以下のように出力せよ。

R_1 C_1
R_2 C_2
\vdots
R_5 C_5

以下の入力例も参考にせよ。

入力例 1

6 6
vgxgpu
amkxks
zhkbpp
hykink
esnuke
zplvfj

出力例 1

この時、(A_1,A_2,A_3,A_4,A_5)=((5,2),(5,3),(5,4),(5,5),(5,6)) とすると、
それぞれのマスに書き込まれた英小文字は s, n, u, k, e であり、
1\leq i\leq 4 について、A_i と A_{i+1} は辺を共有しており、
各マスの中心は一直線上に存在するため、条件をみたしています。

入力例 2

5 5
ezzzz
zkzzz
ezuzs
zzznz
zzzzs

出力例 2

(A_1,A_2,A_3,A_4,A_5)=((5,5),(4,4),(3,3),(2,2),(1,1)) が条件をみたしています。
例えば、(A_1,A_2,A_3,A_4,A_5)=((3,5),(4,4),(3,3),(2,2),(3,1)) は、1,2 つめの条件をみたしていますが、
マスの中心が一直線上に存在しないため、3 つめの条件をみたしていません。

入力例 3

10 10
kseeusenuk
usesenesnn
kskekeeses
nesnusnkkn
snenuuenke
kukknkeuss
neunnennue
sknuessuku
nksneekknk
neeeuknenk

出力例 3

Score : 250 points

Problem Statement

There is a grid with H horizontal rows and W vertical columns. Each cell has a lowercase English letter written on it. We denote by (i, j) the cell at the i-th row from the top and j-th column from the left.

The letters written on the grid are represented by H strings S_1,S_2,\ldots, S_H, each of length W. The j-th letter of S_i represents the letter written on (i, j).

There is a unique set of contiguous cells (going vertically, horizontally, or diagonally) in the grid with s, n, u, k, and e written on them in this order.
Find the positions of such cells and print them in the format specified in the Output section.

A tuple of five cells (A_1,A_2,A_3,A_4,A_5) is said to form a set of contiguous cells (going vertically, horizontally, or diagonally) with s, n, u, k, and e written on them in this order if and only if all of the following conditions are satisfied.

A_1,A_2,A_3,A_4 and A_5 have letters s, n, u, k, and e written on them, respectively.
For all 1\leq i\leq 4, cells A_i and A_{i+1} share a corner or a side.
The centers of A_1,A_2,A_3,A_4, and A_5 are on a common line at regular intervals.

Constraints

5\leq H\leq 100
5\leq W\leq 100
H and W are integers.
S_i is a string of length W consisting of lowercase English letters.
The given grid has a unique conforming set of cells.

Input

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

H W
S_1
S_2
\vdots
S_H

Output

Print five lines in the following format.

Let (R_1,C_1), (R_2,C_2)\ldots,(R_5,C_5) be the cells in the sought set with s, n, u, k, and e written on them, respectively. The i-th line should contain R_i and C_i in this order, separated by a space.

In other words, print them in the following format:

R_1 C_1
R_2 C_2
\vdots
R_5 C_5

See also Sample Inputs and Outputs below.

Sample Input 1

6 6
vgxgpu
amkxks
zhkbpp
hykink
esnuke
zplvfj

Sample Output 1

Tuple (A_1,A_2,A_3,A_4,A_5)=((5,2),(5,3),(5,4),(5,5),(5,6)) satisfies the conditions.
Indeed, the letters written on them are s, n, u, k, and e;
for all 1\leq i\leq 4, cells A_i and A_{i+1} share a side;
and the centers of the cells are on a common line.

Sample Input 2

5 5
ezzzz
zkzzz
ezuzs
zzznz
zzzzs

Sample Output 2

Tuple (A_1,A_2,A_3,A_4,A_5)=((5,5),(4,4),(3,3),(2,2),(1,1)) satisfies the conditions.
However, for example, (A_1,A_2,A_3,A_4,A_5)=((3,5),(4,4),(3,3),(2,2),(3,1)) violates the third condition because the centers of the cells are not on a common line, although it satisfies the first and second conditions.

Sample Input 3

10 10
kseeusenuk
usesenesnn
kskekeeses
nesnusnkkn
snenuuenke
kukknkeuss
neunnennue
sknuessuku
nksneekknk
neeeuknenk

Sample Output 3

E - Count Connected Components

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

頂点に 1 から N の番号が、辺に 1 から M の番号がついた N 頂点 M 辺の単純無向グラフが与えられます。辺 i は頂点 u_i と頂点 v_i を結んでいます。
グラフに含まれる連結成分の個数を求めてください。

注釈

単純無向グラフ とは、単純で辺に向きの無いグラフのことをいいます。
グラフが単純であるとは、グラフが自己ループや多重辺を含まないことをいいます。

あるグラフの 部分グラフ とは、元のグラフのいくつかの頂点といくつかの辺を選んでできるグラフのことをいいます。
グラフが連結であるとは、グラフに含まれるすべての頂点同士が辺を経由して互いに行き来できることをいいます。
連結成分 とは、連結な部分グラフのうち、そのグラフを含んだより大きい連結な部分グラフが存在しないものをいいます。

制約

1 \leq N \leq 100
0 \leq M \leq \frac{N(N - 1)}{2}
1 \leq u_i, v_i \leq N
入力で与えられるグラフは単純
入力される値はすべて整数

入力

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

N M
u_1 v_1
u_2 v_2
\vdots
u_M v_M

出力

答えを出力せよ。

入力例 1

出力例 1

与えられるグラフに含まれる連結成分は次の 2 個です。

頂点 1, 2, 3 および辺 1, 2 からなる部分グラフ
頂点 4, 5 および辺 3 からなる部分グラフ

入力例 2

5 0

出力例 2

入力例 3

出力例 3

Score : 300 points

Problem Statement

You are given a simple undirected graph with N vertices numbered 1 to N and M edges numbered 1 to M. Edge i connects vertex u_i and vertex v_i.
Find the number of connected components in this graph.

Notes

A simple undirected graph is a graph that is simple and has undirected edges.
A graph is simple if and only if it has no self-loop or multi-edge.

A subgraph of a graph is a graph formed from some of the vertices and edges of that graph.
A graph is connected if and only if one can travel between every pair of vertices via edges.
A connected component is a connected subgraph that is not part of any larger connected subgraph.

Constraints

1 \leq N \leq 100
0 \leq M \leq \frac{N(N - 1)}{2}
1 \leq u_i, v_i \leq N
The given graph 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

The given graph contains the following two connected components:

a subgraph formed from vertices 1, 2, 3, and edges 1, 2;
a subgraph formed from vertices 4, 5, and edge 3.

Sample Input 2

5 0

Sample Output 2

Sample Input 3