AtCoder Daily Training EASY 2026/07/15 16:00start

A - Last Letter

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 100 点

問題文

英小文字からなる長さ N の文字列 S が与えられます。S の末尾の文字を出力してください。

制約

N は整数
1 ≤ N ≤ 1000
S は英小文字からなる長さ N の文字列

入力

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

N
S

出力

S の末尾の文字を出力せよ。

入力例 1

5
abcde

出力例 1

S = {}abcde です。S の末尾の文字は e なので、e を出力します。

入力例 2

1
a

出力例 2

Score : 100 points

Problem Statement

Given a string S of length N consisting of lowercase English alphabets, print the last character of S.

Constraints

N is an integer.
1 ≤ N ≤ 1000
S is a string of length N consisting of lowercase English alphabets.

Input

Input is given from Standard Input in the following format:

N
S

Output

Print the last character of S.

Sample Input 1

5
abcde

Sample Output 1

The last character of S = {}abcde is e, so e should be printed.

Sample Input 2

1
a

Sample Output 2

B - π

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 100 点

問題文

正整数 D が与えられます。

直径が D の円の面積を求めて下さい。

制約

1\le D\le 100
入力される値は整数

入力

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

出力

答えを出力せよ。

真の解との絶対誤差または相対誤差が 10^{-6} 以下のとき正解と判定される。

入力例 1

出力例 1

3.141592653589793

直径が 2 の円の面積は 3.141592653589793\ldots です。

入力例 2

出力例 2

38.48451000647496

入力例 3

出力例 3

7542.9639612690935

Score : 100 points

Problem Statement

You are given a positive integer D.

Find the area of a circle with diameter D.

Constraints

1\le D\le 100
The input value is an integer.

Input

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

Output

Output the answer.

Your answer is considered correct if the absolute or relative error from the true answer is at most 10^{-6}.

Sample Input 1

Sample Output 1

3.141592653589793

The area of a circle with diameter 2 is 3.141592653589793\ldots.

Sample Input 2

Sample Output 2

38.48451000647496

Sample Input 3

Sample Output 3

7542.9639612690935

C - Takahashi's Secret

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 200 点

問題文

高橋君には N 人の友達がいます。N 人の友達はそれぞれ、友達 1 、友達 2 、\ldots 、友達 N というあだ名で呼ばれています。

ある日、高橋君はある恥ずかしい秘密を、友達の一人である友達 X に知られてしまいました。
i = 1, 2, \ldots, N について、友達 i が高橋君の秘密を知ったとき、友達 A_i がまだ高橋君の秘密を知らなければ、友達 i は高橋君の秘密を友達 A_i にも教えてしまいます。

高橋君の秘密は最終的に何人の友達に知られることになるでしょうか？

制約

2 \leq N \leq 10^5
1 \leq X \leq N
1 \leq A_i \leq N
A_i \neq i
入力はすべて整数

入力

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

N X
A_1 A_2 \cdots A_N

出力

答えを出力せよ。

入力例 1

4 2
3 1 1 2

出力例 1

高橋君の秘密は以下の流れで友達 1 、友達 2 、友達 3 の 3 人に知れ渡ります。

ある日、高橋君は秘密を友達 2 に知られてしまいました。
秘密を知った友達 2 は、その秘密を友達 1 に教えます。
秘密を知った友達 1 は、その秘密を友達 3 に教えます。

高橋君の秘密は最終的に 3 人の友達に知られることになるため、3 を出力します。

入力例 2

20 12
7 11 10 1 7 20 14 2 17 3 2 5 19 20 8 14 18 2 10 10

出力例 2

Score : 200 points

Problem Statement

Takahashi has N friends. They have nicknames: Friend 1, Friend 2, \ldots, Friend N.

One day, Takahashi accidentally let one of his friends, Friend X, learn his shameful secret.
For each i = 1, 2, \ldots, N, when Friend i learns the secret, he/she will share it with Friend A_i, if Friend A_i has not already learned it.

How many of Takahashi's friends will learn the secret in the end?

Constraints

2 \leq N \leq 10^5
1 \leq X \leq N
1 \leq A_i \leq N
A_i \neq i
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N X
A_1 A_2 \cdots A_N

Output

Print the answer.

Sample Input 1

4 2
3 1 1 2

Sample Output 1

Takahashi's secret will be learned by Friend 1, Friend 2, and Friend 3, as follows.

One day, Takahashi let Friend 2 learn the secret.
Friend 2 shares it with Friend 1.
Friend 1 shares it with Friend 3.

In the end, three of his friends learn the secret, so we print 3.

Sample Input 2

20 12
7 11 10 1 7 20 14 2 17 3 2 5 19 20 8 14 18 2 10 10

Sample Output 2

D - Looped Rope

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 200 点

問題文

縦 H マス、横 W マスのマス目があります。上から i 行目 (1\le i\le H) 、左から j 列目 (1\le j\le W) のマスをマス (i,j) と呼ぶことにします。

それぞれのマスは白もしくは黒のどちらか 1 色で塗られています。マスに塗られている色は H 個の文字列 S _ 1,S _ 2,\ldots,S _ H で表され、S _ i\ (1\le i\le H) の j 文字目 (1\le j\le W) が . のとき、マス (i,j) は白で塗られており、S _ i\ (1\le i\le H) の j 文字目 (1\le j\le W) が # のとき、マス (i,j) は黒で塗られています。

マス目が以下の条件を満たすか判定してください。

どの黒で塗られたマスについても、上下左右で隣り合うマスのうち黒く塗られているものは 2 つもしくは 4 つである。

ただし、マス (i,j)\ (1\le i\le H,1\le j\le W) とマス (k,l)\ (1\le k\le H,1\le l\le W) は、|i-k|+|j-l|=1 であるとき、かつそのときに限り上下左右で隣り合っているとします。

制約

1\le H\le 20
1\le W\le 20
H,W は整数
S _ i は . および # からなる長さ W の文字列 (1\le i\le H)

入力

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

H W
S _ 1
S _ 2
\vdots
S _ H

出力

与えられたマス目が条件を満たしているとき Yes を、条件を満たしていないとき No を出力せよ。

入力例 1

8 7
.######
##....#
#.###.#
#.#.#.#
#.#.#.#
#.#####
#...#..
#####..

出力例 1

Yes

例えば、マス (6,3) は黒で塗られており、隣り合っているマス (5,3),(6,2),(6,4),(7,3) のうち、マス (5,3) およびマス (6,4) の 2 マスが黒で塗られているため、条件を満たしています。

他の黒で塗られたどのマスについても条件を満たしているため、Yes を出力してください。

入力例 2

1 2
##

出力例 2

No

マス (1,1) は黒で塗られていますが、隣り合っているマスは 1 つしかないため、条件を満たしていません。

よって、No を出力して下さい。

入力例 3

4 3
...
...
...
...

出力例 3

Yes

黒で塗られているマスがないため、条件を満たしています。

よって、Yes を出力してください。

入力例 4

15 18
##.###..##.##..##.
##.#.##.##.##.####
...##.#.......####
###.###....###.##.
#.##.......#.#....
#..#.##.##.#.#....
#.########.####.##
#.##.##.#....##.##
#......##.........
##.##..#..##..####
.#.#####..#####..#
.#..#...##.#.....#
.#..#.####.#.....#
.##.#.#.#..##..###
..###.###...####..

出力例 4

Yes

Score : 200 points

Problem Statement

There is a grid with H rows and W columns. Let (i,j) denote the cell at the i-th row (1\le i\le H) from the top and the j-th column (1\le j\le W) from the left.

Each cell is painted with one color, white or black. The color painted on the cells is represented by H strings S _ 1,S _ 2,\ldots,S _ H. When the j-th character (1\le j\le W) of S _ i\ (1\le i\le H) is ., cell (i,j) is painted white, and when the j-th character (1\le j\le W) of S _ i\ (1\le i\le H) is #, cell (i,j) is painted black.

Determine whether the grid satisfies the following condition:

For every black cell, the number of horizontally or vertically adjacent cells that are painted black is 2 or 4.

Here, cells (i,j)\ (1\le i\le H,1\le j\le W) and (k,l)\ (1\le k\le H,1\le l\le W) are horizontally or vertically adjacent if and only if |i-k|+|j-l|=1.

Constraints

1\le H\le 20
1\le W\le 20
H and W are integers.
S _ i is a string of length W consisting of . and # (1\le i\le H).

Input

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

H W
S _ 1
S _ 2
\vdots
S _ H

Output

Output Yes if the given grid satisfies the condition, and No if it does not satisfy the condition.

Sample Input 1

8 7
.######
##....#
#.###.#
#.#.#.#
#.#.#.#
#.#####
#...#..
#####..

Sample Output 1

Yes

For example, cell (6,3) is painted black, and among the adjacent cells (5,3),(6,2),(6,4),(7,3), cells (5,3) and (6,4) are painted black, which is 2 cells, so it satisfies the condition.

Every other black cell also satisfies the condition, so output Yes.

Sample Input 2

1 2
##

Sample Output 2

No

Cell (1,1) is painted black, but it has only one adjacent cell, so it does not satisfy the condition.

Therefore, output No.

Sample Input 3

4 3
...
...
...
...

Sample Output 3

Yes

There are no black cells, so the condition is satisfied.

Therefore, output Yes.

Sample Input 4

15 18
##.###..##.##..##.
##.#.##.##.##.####
...##.#.......####
###.###....###.##.
#.##.......#.#....
#..#.##.##.#.#....
#.########.####.##
#.##.##.#....##.##
#......##.........
##.##..#..##..####
.#.#####..#####..#
.#..#...##.#.....#
.#..#.####.#.....#
.##.#.#.#..##..###
..###.###...####..

Sample Output 4

Yes

E - Sugoroku Destination

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

マス 1, マス 2,\ldots, マス N の N 個のマスが 1 列に並んでいます。マス i には整数 A _ i (i\le A_ i\le N) が書かれています。

s=1,2,\ldots,N のそれぞれについて、以下の問題を解いてください。

はじめ、マス s に駒を置く。「駒が置かれているマスに書かれている整数を x として、駒をマス x に移動させる」という操作を 10 ^ {100} 回行った後、駒が置かれているマスの番号を出力する。

制約

1\le N\le5\times10 ^ 5
i\le A _ i\le N\ (1\le i\le N)
入力はすべて整数

入力

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

N
A _ 1 A _ 2 \ldots A _ N

出力

s=1,2,\ldots,N に対する答えを、この順に空白を区切りとして一行に出力せよ。

入力例 1

7
2 4 7 5 5 6 7

出力例 1

5 5 7 5 5 6 7

s=1 のとき、駒は以下の図のように移動します。

駒がマス 5 に置かれているとき、操作が行われても駒は移動しないため、s=1 のときの答えは 5 となります。

入力例 2

5
1 2 3 4 5

出力例 2

1 2 3 4 5

駒が一度も移動しないこともあります。

入力例 3

15
11 3 10 7 15 10 10 11 11 13 11 12 14 14 15

出力例 3

11 14 14 14 15 14 14 11 11 14 11 12 14 14 15

Score : 300 points

Problem Statement

There are N cells, cell 1, cell 2,\ldots, cell N, arranged in a line. Cell i has an integer A_i\ (i \le A_i \le N) written on it.

For each of s=1,2,\ldots,N, solve the following problem.

Initially, place a piece on cell s. After performing the operation "let x be the integer written on the cell where the piece is placed, and then move the piece to cell x" 10^{100} times, output the number of the cell where the piece is placed.

Constraints

1 \le N \le 5\times10^5
i \le A_i \le N\ (1 \le i \le N)
All input values are integers.

Input

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

N
A_1 A_2 \ldots A_N

Output

Output the answers for s=1,2,\ldots,N in this order on a single line, separated by spaces.

Sample Input 1

7
2 4 7 5 5 6 7

Sample Output 1

5 5 7 5 5 6 7

For s=1, the piece moves as shown in the following figure.

When the piece is placed on cell 5, the operation does not move the piece, so the answer for s=1 is 5.

Sample Input 2

5
1 2 3 4 5

Sample Output 2

1 2 3 4 5

It is possible that the piece never moves.

Sample Input 3

15
11 3 10 7 15 10 10 11 11 13 11 12 14 14 15

Sample Output 3

11 14 14 14 15 14 14 11 11 14 11 12 14 14 15