A - Penalty Kick

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

髙橋君はサッカーの試合で N 回ペナルティキックを蹴ります。

髙橋君は i 回目のペナルティキックでは、i が 3 の倍数の場合は失敗しそれ以外の場合は成功します。

髙橋君がペナルティキックを蹴ったときの結果を出力してください。

制約

  • 1 \leq N \leq 100
  • 入力は全て整数である。

入力

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

N

出力

髙橋君のペナルティキックの結果を表す長さ N の文字列を出力せよ。結果を表す文字列の i (1 \leq i \leq N) 文字目は髙橋君が i 回目のペナルティキックで成功した場合は o 、失敗した場合は x とする。

入力例 1

7

出力例 1

ooxooxo

髙橋君は 3 回目と 6 回目のペナルティキックに失敗するので、3 文字目と 6 文字目が x となります。

入力例 2

9

出力例 2

ooxooxoox

Score: 100 points

Problem Statement

Takahashi will have N penalty kicks in a soccer match.

For the i-th penalty kick, he will fail if i is a multiple of 3, and succeed otherwise.

Print the results of his penalty kicks.

Constraints

  • 1 \leq N \leq 100
  • All inputs are integers.

Input

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

N

Output

Print a string of length N representing the results of Takahashi's penalty kicks. The i-th character (1 \leq i \leq N) should be o if Takahashi succeeds in the i-th penalty kick, and x if he fails.

Sample Input 1

7

Sample Output 1

ooxooxo

Takahashi fails the third and sixth penalty kicks, so the third and sixth characters will be x.

Sample Input 2

9

Sample Output 2

ooxooxoox
B - Weak Beats

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

0 と 1 からなる長さ 16 の文字列 S が与えられます。

2 以上 16 以下のすべての偶数 i について S の i 文字目が 0 ならば Yes を、 そうでないならば No を出力してください。

制約

  • S は 0 と 1 からなる長さ 16 の文字列

入力

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

S

出力

2 以上 16 以下のすべての偶数 i について S の i 文字目が 0 ならば Yes を、 そうでないならば No を出力せよ。

入力例 1

1001000000001010

出力例 1

No

S= 1001000000001010 の 4 文字目が 1 であるため、No を出力します。

入力例 2

1010100000101000

出力例 2

Yes

S= 1010100000101000 の偶数番目の文字はすべて 0 であるため、Yes を出力します。

入力例 3

1111111111111111

出力例 3

No

S の偶数文字目はすべて 1 となっています。 特に「すべて 0 」ではないため、No を出力します。

Score : 100 points

Problem Statement

You are given a string S of length 16 consisting of 0 and 1.

If the i-th character of S is 0 for every even number i from 2 through 16, print Yes; otherwise, print No.

Constraints

  • S is a string of length 16 consisting of 0 and 1.

Input

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

S

Output

If the i-th character of S is 0 for every even number i from 2 through 16, print Yes; otherwise, print No.

Sample Input 1

1001000000001010

Sample Output 1

No

The 4-th character of S= 1001000000001010 is 1, so you should print No.

Sample Input 2

1010100000101000

Sample Output 2

Yes

Every even-positioned character in S= 1010100000101000 is 0, so you should print Yes.

Sample Input 3

1111111111111111

Sample Output 3

No

Every even-positioned character in S is 1. Particularly, they are not all 0, so you should print No.
C - V

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

高橋君は漢文の勉強をしていて、漢字を読む順番が分からず困っています。高橋君を助けましょう！

1 から N までの N 個の整数が小さい方から順に 1 列に並んでいます。
整数の間に M 個の「レ」が挟まっています。i 個目の「レ」は、整数 a_i と整数 a_i + 1 の間にあります。

あなたは次の手順に従って、N 個の整数を 1 回ずつ全て読みます。

  • まず、頂点に 1 から N までの番号がついた N 頂点 M 辺の無向グラフ G を考える。i 本目の辺は頂点 a_i と頂点 a_i + 1 を結んでいる。
  • そして、読まれていない整数が無くなるまで次の操作を繰り返す。
    • 読まれていない整数のうち最小のものを x とする。頂点 x が含まれる連結成分 C を選び、C に含まれる頂点の番号を大きい方から順に全て読む。

例えば、整数と「レ」が

image

という順番で並んでいる場合を考えます。(この場合 N = 5, M = 3, a = (1, 3, 4) です。)
このとき、整数が読まれる順番は以下の手順によって 2, 1, 5, 4, 3 に決定します。

  • 最初、読まれていない整数のうち最小のものは 1 であり、グラフ G の頂点 1 を含む連結成分に含まれる頂点は \lbrace 1, 2 \rbrace である。よって 2, 1 がこの順で読まれる。
  • 次に、読まれていない整数のうち最小のものは 3 であり、グラフ G の頂点 3 を含む連結成分に含まれる頂点は \lbrace 3, 4, 5 \rbrace である。よって 5, 4, 3 がこの順で読まれる。
  • すべての整数が読まれたので手順を終了する。

N, M, (a_1, a_2, \dots, a_M) が入力として与えられるので、 N 個の整数を読む順番を出力してください。

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

制約

  • 1 \leq N \leq 100
  • 0 \leq M \leq N - 1
  • 1 \leq a_1 \lt a_2 \lt \dots \lt a_M \leq N-1
  • 入力される値は全て整数

入力

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

N M
a_1 a_2 \dots a_M

出力

答えを以下の形式で出力せよ。ここで p_i は、i 番目に読まれる整数を意味する。

p_1 p_2 \dots p_N

入力例 1

5 3
1 3 4

出力例 1

2 1 5 4 3

問題文の例にある通り、整数と「レ」が

image

という順で並んでいる場合は 2, 1, 5, 4, 3 の順で読みます。

入力例 2

5 0

出力例 2

1 2 3 4 5

「レ」が存在しない場合もあります。

入力例 3

10 6
1 2 3 7 8 9

出力例 3

4 3 2 1 5 6 10 9 8 7

Score : 200 points

Problem Statement

Studying Kanbun, Takahashi is having trouble figuring out the order to read words. Help him out!

There are N integers from 1 through N arranged in a line in ascending order.
Between them are M "レ" marks. The i-th "レ" mark is between the integer a_i and integer (a_i + 1).

You read each of the N integers once by the following procedure.

  • Consider an undirected graph G with N vertices numbered 1 through N and M edges. The i-th edge connects vertex a_i and vertex (a_i+1).
  • Repeat the following operation until there is no unread integer:
    • let x be the minimum unread integer. Choose the connected component C containing vertex x, and read all the numbers of the vertices contained in C in descending order.

For example, suppose that integers and "レ" marks are arranged in the following order:

image

(In this case, N = 5, M = 3, and a = (1, 3, 4).)
Then, the order to read the integers is determined to be 2, 1, 5, 4, and 3, as follows:

  • At first, the minimum unread integer is 1, and the connected component of G containing vertex 1 has vertices \lbrace 1, 2 \rbrace, so 2 and 1 are read in this order.
  • Then, the minimum unread integer is 3, and the connected component of G containing vertex 3 has vertices \lbrace 3, 4, 5 \rbrace, so 5, 4, and 3 are read in this order.
  • Now that all integers are read, terminate the procedure.

Given N, M, and (a_1, a_2, \dots, a_M), print the order to read the N integers.

What is a connected component? A subgraph of a graph is a graph obtained by choosing some vertices and edges from the original graph.
A graph is said to be connected if and only if one can travel between any two vertices in the graph via edges.
A connected component is a connected subgraph that is not contained in any larger connected subgraph.

Constraints

  • 1 \leq N \leq 100
  • 0 \leq M \leq N - 1
  • 1 \leq a_1 \lt a_2 \lt \dots \lt a_M \leq N-1
  • All values in the input are integers.

Input

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

N M
a_1 a_2 \dots a_M

Output

Print the answer in the following format, where p_i is the i-th integers to read.

p_1 p_2 \dots p_N

Sample Input 1

5 3
1 3 4

Sample Output 1

2 1 5 4 3

As described in the Problem Statement, if integers and "レ" marks are arranged in the following order:

image

then the integers are read in the following order: 2, 1, 5, 4, and 3.

Sample Input 2

5 0

Sample Output 2

1 2 3 4 5

There may be no "レ" mark.

Sample Input 3

10 6
1 2 3 7 8 9

Sample Output 3

4 3 2 1 5 6 10 9 8 7
D - Call the ID Number

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

人 1 、人 2 、\ldots 、人 N と番号をつけられた N 人の人がいます。

N 人は、人 1 、人 2 、\ldots 、人 N の順番に下記の行動をちょうど 1 回ずつ行います。

  • 人 i 自身がまだ一度も番号を呼ばれていないなら、人 A_i の番号を呼ぶ。

最後まで番号を一度も呼ばれない人全員の番号を昇順に列挙してください。

制約

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

入力

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

N
A_1 A_2 \ldots A_N

出力

下記の形式にしたがって、最後まで番号を一度も呼ばれない人全員の番号を昇順に列挙せよ。

K
X_1 X_2 \ldots X_K

すなわち、まず 1 行目に、最後まで番号を一度も呼ばれない人の人数 K を出力し、 2 行目に、最後まで番号を一度も呼ばれない人全員の番号を昇順に並べた列 (X_1, X_2, \ldots, X_K) を空白区切りで出力せよ。

入力例 1

5
3 1 4 5 4

出力例 1

2
2 4

5 人の行動は下記の通りです。

  • 人 1 はまだ番号を一度も呼ばれていないので、人 1 は人 3 の番号を呼びます。
  • 人 2 はまだ番号を一度も呼ばれていないので、人 2 は人 1 の番号を呼びます。
  • 人 3 はすでに人 1 によって番号を呼ばれているので、何もしません。
  • 人 4 はまだ番号を一度も呼ばれていないので、人 4 は人 5 の番号を呼びます。
  • 人 5 はすでに人 4 によって番号を呼ばれているので、何もしません。

よって、最後まで番号を一度も呼ばれないのは人 2 と人 4 です。

入力例 2

20
9 7 19 7 10 4 13 9 4 8 10 15 16 3 18 19 12 13 2 12

出力例 2

10
1 2 5 6 8 11 14 17 18 20

Score : 200 points

Problem Statement

There are N people whose IDs are 1, 2, \ldots, and N.

Each of person 1, person 2, \ldots, and person N performs the following action once in this order:

  • If person i's ID has not been called out yet, call out person A_i's ID.

Enumerate the IDs of all the people whose IDs are never called out until the end in ascending order.

Constraints

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

Input

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

N
A_1 A_2 \ldots A_N

Output

Enumerate the IDs of all the people whose IDs are not called out until the end in ascending order in the following format:

K
X_1 X_2 \ldots X_K

In other words, the first line should contain the number of people, K, whose IDs are never called out until the end; the second line should contain the sequence (X_1, X_2, \ldots, X_K) of IDs of such people in ascending order, with spaces in between.

Sample Input 1

5
3 1 4 5 4

Sample Output 1

2
2 4

The five people's actions are as follows.

  • Person 1's ID has not been called out yet, so person 1 calls out person 3's ID.
  • Person 2's ID has not been called out yet, so person 2 calls out person 1's ID.
  • Person 3's ID has already been called out by person 1, so nothing happens.
  • Person 4's ID has not been called out yet, so person 4 calls out person 5's ID.
  • Person 5's ID has already been called out by person 4, so nothing happens.

Therefore, person 2 and 4's IDs are not called out until the end.

Sample Input 2

20
9 7 19 7 10 4 13 9 4 8 10 15 16 3 18 19 12 13 2 12

Sample Output 2

10
1 2 5 6 8 11 14 17 18 20
E - Previous Permutation

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

(1, \dots, N) の順列 P = (P_1, \dots, P_N) が与えられます。ただし、(P_1, \dots, P_N) \neq (1, \dots, N) です。

(1 \dots, N) の順列を全て辞書順で小さい順に並べたとき、P が K 番目であるとします。辞書順で小さい方から K-1 番目の順列を求めてください。

順列とは？

(1, \dots, N) の順列とは、(1, \dots, N) を並べ替えて得られる数列のことをいいます。

辞書順とは？

長さ N の数列 A = (A_1, \dots, A_N), B = (B_1, \dots, B_N) に対し、A が B より辞書順で真に小さいとは、ある整数 1 \leq i \leq N が存在して、下記の 2 つがともに成り立つことをいいます。

  • (A_{1},\ldots,A_{i-1}) = (B_1,\ldots,B_{i-1})
  • A_i < B_i

制約

  • 2 \leq N \leq 100
  • 1 \leq P_i \leq N \, (1 \leq i \leq N)
  • P_i \neq P_j \, (i \neq j)
  • (P_1, \dots, P_N) \neq (1, \dots, N)
  • 入力される値は全て整数

入力

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

N
P_1 \ldots P_N

出力

求める順列を Q = (Q_1, \dots, Q_N) として、Q_1, \dots, Q_N をこの順に空白区切りで一行に出力せよ。

入力例 1

3
3 1 2

出力例 1

2 3 1

(1, 2, 3) の順列を辞書順で小さい順に並べると次のようになります。

  • (1, 2, 3)
  • (1, 3, 2)
  • (2, 1, 3)
  • (2, 3, 1)
  • (3, 1, 2)
  • (3, 2, 1)

よって P = (3, 1, 2) は小さい方から 5 番目であり、求める順列、すなわち小さい方から 5 - 1 = 4 番目の順列は (2, 3, 1) です。

入力例 2

10
9 8 6 5 10 3 1 2 4 7

出力例 2

9 8 6 5 10 2 7 4 3 1

Score : 300 points

Problem Statement

You are given a permutation P = (P_1, \dots, P_N) of (1, \dots, N), where (P_1, \dots, P_N) \neq (1, \dots, N).

Assume that P is the K-th lexicographically smallest among all permutations of (1 \dots, N). Find the (K-1)-th lexicographically smallest permutation.

What are permutations?

A permutation of (1, \dots, N) is an arrangement of (1, \dots, N) into a sequence.

What is lexicographical order?

For sequences of length N, A = (A_1, \dots, A_N) and B = (B_1, \dots, B_N), A is said to be strictly lexicographically smaller than B if and only if there is an integer 1 \leq i \leq N that satisfies both of the following.

  • (A_{1},\ldots,A_{i-1}) = (B_1,\ldots,B_{i-1}).
  • A_i < B_i.

Constraints

  • 2 \leq N \leq 100
  • 1 \leq P_i \leq N \, (1 \leq i \leq N)
  • P_i \neq P_j \, (i \neq j)
  • (P_1, \dots, P_N) \neq (1, \dots, N)
  • All values in the input are integers.

Input

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

N
P_1 \ldots P_N

Output

Let Q = (Q_1, \dots, Q_N) be the sought permutation. Print Q_1, \dots, Q_N in a single line in this order, separated by spaces.

Sample Input 1

3
3 1 2

Sample Output 1

2 3 1

Here are the permutations of (1, 2, 3) in ascending lexicographical order.

  • (1, 2, 3)
  • (1, 3, 2)
  • (2, 1, 3)
  • (2, 3, 1)
  • (3, 1, 2)
  • (3, 2, 1)

Therefore, P = (3, 1, 2) is the fifth smallest, so the sought permutation, which is the fourth smallest (5 - 1 = 4), is (2, 3, 1).

Sample Input 2

10
9 8 6 5 10 3 1 2 4 7

Sample Output 2

9 8 6 5 10 2 7 4 3 1