A - Candy Cookie Law

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

高橋君の住む AtCoder 国には「飴を A 個以上所持している人はクッキーを B 個以上所持していなければならない」という奇妙な法律があります。

高橋君は飴を C 個、クッキーを D 個所持しています。高橋君がこの法律に違反しているかどうか判定してください。

制約

  • 1\leq A,B,C,D \leq 100
  • 入力は全て整数

入力

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

A B C D

出力

高橋君が法律に違反しているとき Yes、違反していないとき No と出力せよ。

入力例 1

10 20 30 40

出力例 1

No

AtCoder国には「飴を 10 個以上所持している人はクッキーを 20 個以上所持していなければならない」という法律があります。

高橋君は飴を 30 個、クッキーを 40 個所持しているため、この法律に違反していません。

入力例 2

10 20 30 4

出力例 2

Yes

入力例 3

100 100 1 1

出力例 3

No

Score : 100 points

Problem Statement

In AtCoder Country where Takahashi lives, there is a strange law that "a person who possesses A or more candies must possess B or more cookies."

Takahashi possesses C candies and D cookies. Determine whether Takahashi is violating this law.

Constraints

  • 1\leq A,B,C,D \leq 100
  • All input values are integers.

Input

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

A B C D

Output

Print Yes if Takahashi is violating the law, and No otherwise.

Sample Input 1

10 20 30 40

Sample Output 1

No

In AtCoder Country, there is a law that "a person who possesses 10 or more candies must possess 20 or more cookies."

Takahashi possesses 30 candies and 40 cookies, so he is not violating this law.

Sample Input 2

10 20 30 4

Sample Output 2

Yes

Sample Input 3

100 100 1 1

Sample Output 3

No
B - Wrong Answer

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

0 以上 9 以下の整数 A, B が与えられます。

0 以上 9 以下の整数であって A + B と等しくないものをいずれかひとつ出力してください。

制約

  • 0 \leq A \leq 9
  • 0 \leq B \leq 9
  • A + B \leq 9
  • A, B は整数

入力

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

A B

出力

0 以上 9 以下の整数であって A + B と等しくないものをいずれかひとつ出力せよ。

入力例 1

2 5

出力例 1

2

A = 2, B = 5 のとき A + B = 7 です。したがって、0, 1, 2, 3, 4, 5, 6, 8, 9 のいずれかを出力すると正解となります。

入力例 2

0 0

出力例 2

9

入力例 3

7 1

出力例 3

4

Score: 100 points

Problem Statement

You are given two integers A and B, each between 0 and 9, inclusive.

Print any integer between 0 and 9, inclusive, that is not equal to A + B.

Constraints

  • 0 \leq A \leq 9
  • 0 \leq B \leq 9
  • A + B \leq 9
  • A and B are integers.

Input

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

A B

Output

Print any integer between 0 and 9, inclusive, that is not equal to A + B.

Sample Input 1

2 5

Sample Output 1

2

When A = 2, B = 5, we have A + B = 7. Thus, printing any of 0, 1, 2, 3, 4, 5, 6, 8, 9 is correct.

Sample Input 2

0 0

Sample Output 2

9

Sample Input 3

7 1

Sample Output 3

4
C - Distance Between Tokens

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

H 行 W 列のマス目があり、そのうち二つの異なるマスに駒が置かれています。

マス目の状態は H 個の長さ W の文字列 S_1, \dots, S_H で表されます。S_{i, j} = o ならば i 行目 j 列目のマスに駒が置かれていることを、S_{i, j} = - ならばそのマスには駒が置かれていないことを表します。なお、S_{i, j} は文字列 S_i の j 文字目を指します。

一方の駒をマス目の外側に出ないように上下左右の隣接するマスに動かすことを繰り返すとき、もう一方の駒と同じマスに移動させるためには最小で何回動かす必要がありますか？

制約

  • 2 \leq H, W \leq 100
  • H, W は整数
  • S_i \, (1 \leq i \leq H) は o および - のみからなる長さ W の文字列
  • S_{i, j} = o となる整数 1 \leq i \leq H, 1 \leq j \leq W の組がちょうど二つ存在する

入力

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

H W
S_1
\vdots
S_H

出力

答えを出力せよ。

入力例 1

2 3
--o
o--

出力例 1

3

1 行目 3 列目に置かれている駒を 下 \rightarrow 左 \rightarrow 左 と移動すると 3 回でもう一方の駒と同じマスに移動させることができます。2 回以下で移動させることはできないので、3 を出力します。

入力例 2

5 4
-o--
----
----
----
-o--

出力例 2

4

Score : 200 points

Problem Statement

There is a grid with H horizontal rows and W vertical columns, in which two distinct squares have a piece.

The state of the squares is represented by H strings S_1, \dots, S_H of length W. S_{i, j} = o means that there is a piece in the square at the i-th row from the top and j-th column from the left; S_{i, j} = - means that the square does not have a piece. Here, S_{i, j} denotes the j-th character of the string S_i.

Consider repeatedly moving one of the pieces to one of the four adjacent squares. It is not allowed to move the piece outside the grid. How many moves are required at minimum for the piece to reach the square with the other piece?

Constraints

  • 2 \leq H, W \leq 100
  • H and W are integers.
  • S_i \, (1 \leq i \leq H) is a string of length W consisting of o and -.
  • There exist exactly two pairs of integers 1 \leq i \leq H, 1 \leq j \leq W such that S_{i, j} = o.

Input

Input is given from Standard Input in the following format:

H W
S_1
\vdots
S_H

Output

Print the answer.

Sample Input 1

2 3
--o
o--

Sample Output 1

3

The piece at the 1-st row from the top and 3-rd column from the left can reach the square with the other piece in 3 moves: down, left, left. Since it is impossible to do so in two or less moves, 3 should be printed.

Sample Input 2

5 4
-o--
----
----
----
-o--

Sample Output 2

4
D - Sandwich Number

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

英大文字と数字からなる文字列 S が与えられるので、S が以下の条件を満たすか判定してください。

  • S は次の文字または文字列をこの順番で連結して得られる。
    • 一文字の英大文字
    • 100000 以上 999999 以下の整数を 10 進表記して得られる長さ 6 の文字列
    • 一文字の英大文字

制約

  • S は英大文字と数字からなる
  • S の長さは 1 以上 10 以下

入力

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

S

出力

S が問題文中の条件を満たすなら Yes と、満たさないなら No と出力せよ。

入力例 1

Q142857Z

出力例 1

Yes

S は Q、142857、Z をこの順に連結して得られます。
Q、Z は英大文字であり、142857 は 100000 以上 999999 以下の整数を 10 進表記して得られる長さ 6 の文字列なので、S は条件を満たします。

入力例 2

AB912278C

出力例 2

No

AB は一文字の英大文字ではないため、S は条件を満たしません。

入力例 3

X900000

出力例 3

No

S の末尾の一文字が英大文字ではないため、S は条件を満たしません。

入力例 4

K012345K

出力例 4

No

012345 は 100000 以上 999999 以下の整数を 10 進表記して得られる長さ 6 の文字列ではないため、S は条件を満たしません。

Score : 200 points

Problem Statement

You are given a string S consisting of uppercase English letters and digits. Determine whether S satisfies the following condition.

  • S is a concatenation of the following characters and string in the order listed.
    • An uppercase English letter
    • A string of length 6 that is a decimal representation of an integer between 100000 and 999999, inclusive
    • An uppercase English letter

Constraints

  • S consists of uppercase English letters and digits.
  • The length of S is between 1 and 10, inclusive.

Input

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

S

Output

If S satisfies the condition in the problem statement, print Yes; otherwise, print No.

Sample Input 1

Q142857Z

Sample Output 1

Yes

S is a concatenation of Q, 142857, and Z in this order.
Q and Z are uppercase English letters, and 142857 is a string of length 6 that is a decimal representation of an integer between 100000 and 999999, so S satisfies the condition.

Sample Input 2

AB912278C

Sample Output 2

No

AB is not an uppercase English letter, so S does not satisfy the condition.

Sample Input 3

X900000

Sample Output 3

No

The last character of S is not an uppercase English letter, so S does not satisfy the condition.

Sample Input 4

K012345K

Sample Output 4

No

012345 is not a string of length 6 that is a decimal representation of an integer between 100000 and 999999, so S does not satisfy the condition.
E - Sugoroku Destination

Time Limit: 2 sec / Memory Limit: 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