A - ABC400 Party

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

ABC400 を記念した式典において、400 人の高橋君を A 行 B 列の長方形状に隙間なく並べようとしています。

正整数 A が与えられるので、このような並べ方ができるような正整数 B の値を出力してください。ただし、そのような正整数 B が存在しない場合には -1 を出力してください。

制約

  • A は 1 以上 400 以下の整数

入力

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

A

出力

問題文の指示に従って B の値あるいは -1 を出力せよ。


入力例 1

10

出力例 1

40

400 人の高橋君を 10 行 40 列の長方形状に並べることができます。


入力例 2

11

出力例 2

-1

入力例 3

400

出力例 3

1

Score : 100 points

Problem Statement

In the ceremony commemorating ABC400, we want to arrange 400 people in a rectangular formation of A rows and B columns without any gaps.

You are given a positive integer A. Print the value of a positive integer B for which such an arrangement is possible. If there is no such positive integer B, print -1.

Constraints

  • A is an integer between 1 and 400, inclusive.

Input

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

A

Output

Print the value of B or -1 as specified by the problem statement.


Sample Input 1

10

Sample Output 1

40

We can arrange 400 people in 10 rows and 40 columns.


Sample Input 2

11

Sample Output 2

-1

Sample Input 3

400

Sample Output 3

1
B - Find Takahashi

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

AtCoder 村には N 本の橋があり、i 本目( i は 1 以上 N 以下の整数)の橋の高さは H_i です。
ここで、AtCoder 村にある N 本の橋のうち、どの相異なる 2 本の橋も高さが異なります。

AtCoder 村で最も高い橋は何本目の橋か出力してください。

制約

  • 1\leq N \leq 100
  • 1\leq H_i \leq 10^9
  • H_i はすべて異なる
  • 入力はすべて整数

入力

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

N
H_1 H_2 \ldots H_N

出力

AtCoder 村で最も高い橋は何本目の橋かを、整数で出力せよ。


入力例 1

3
50 80 70

出力例 1

2

AtCoder 村には 3 本の橋があります。
1,2,3 本目の橋の高さはそれぞれ, 50,80,70 であり、 最も高い橋は 2 本目の橋です。
よって、2 を出力します。


入力例 2

1
1000000000

出力例 2

1

AtCoder 村に橋が 1 本しか存在しないため、2 本目以降の橋は存在せず、最も高い橋は 1 本目の橋となります。


入力例 3

10
22 75 26 45 72 81 47 29 97 2

出力例 3

9

AtCoder 村には 10 本の橋があり、それらのうち最も高い橋は 9 番目の橋(高さは 97 )です。

Score : 100 points

Problem Statement

There are N bridges in AtCoder Village. The height of the bridge numbered i is H_i (i is an integer between 1 and N).
Every two different bridges in the village have different heights.

Print the number representing the highest bridge in the village.

Constraints

  • 1\leq N \leq 100
  • 1\leq H_i \leq 10^9
  • All H_i are different.
  • All values in the input are integers.

Input

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

N
H_1 H_2 \ldots H_N

Output

Print the integer representing the highest bridge in AtCoder village.


Sample Input 1

3
50 80 70

Sample Output 1

2

The village has three bridges.
The first, second, and third bridges have heights of 50, 80, and 70, respectively, so the second bridge is the highest.
Thus, 2 should be printed.


Sample Input 2

1
1000000000

Sample Output 2

1

The village has only one bridge, so the first bridge is the highest.


Sample Input 3

10
22 75 26 45 72 81 47 29 97 2

Sample Output 3

9

The village has ten bridges, and the ninth bridge (with a height of 97) is the highest.

C - 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
D - Failing Grade

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

N 人の学生が試験を受けました。学生には学生 1, 学生 2, \dots, 学生 N と番号がついていて、学生 i は a_i 点を取りました。

P 点未満の点数を取った学生は "不可" となり単位を取得できません。 "不可" となった学生の人数を答えてください。

制約

  • 1 \leq N \leq 10^5
  • 1 \leq P \leq 100
  • 0 \leq a_i \leq 100 (1 \leq i \leq N)
  • 入力はすべて整数である。

入力

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

N P
a_1 a_2 \dots a_N

出力

"不可" となった学生の人数を出力せよ。


入力例 1

4 50
80 60 40 0

出力例 1

2

学生 1 は 80 点、学生 2 は 60 点と、 50 点以上の点数を取っているので "不可" とならず単位を取得できています。
一方、学生 3 は 40 点、学生 4 は 0 点で、 50 点を下回る点数を取っているので "不可" となります。よって答えは 2 人です。


入力例 2

3 90
89 89 89

出力例 2

3

入力例 3

2 22
6 37

出力例 3

1

Score : 200 points

Problem Statement

N students took an exam. The students are labeled as Student 1, Student 2, \dots, Student N, and Student i scored a_i points.

A student who scored less than P points are considered to have failed the exam and cannot earn the credit. Find the number of students who failed the exam.

Constraints

  • 1 \leq N \leq 10^5
  • 1 \leq P \leq 100
  • 0 \leq a_i \leq 100 (1 \leq i \leq N)
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N P
a_1 a_2 \dots a_N

Output

Print the number of students who failed the exam.


Sample Input 1

4 50
80 60 40 0

Sample Output 1

2

Students 1 and 2, who scored 80 and 60 points, respectively, succeeded in scoring at least 50 points to earn the credit.
On the other hand, Students 3 and 4, who scored 40 and 0 points, respectively, fell below 50 points and failed the exam. Thus, the answer is 2.


Sample Input 2

3 90
89 89 89

Sample Output 2

3

Sample Input 3

2 22
6 37

Sample Output 3

1
E - Sneaking Glances

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

数直線上の座標 0.5 に高橋君がいます。

高橋君はこれから N 回の移動を行います。
i 回目の移動では、「正の方向」「負の方向」のいずれかを選び、その方向に L_i 進みます。

高橋君は座標 0 を最大で何回通り過ぎることが出来るでしょうか?
なお、この問題の制約上、座標 0 で完了する移動が生じることはありません。

制約

  • 1 \le N \le 20
  • 1 \le L_i \le 10^9
  • 入力はすべて整数

入力

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

N
L_1 L_2 \dots L_N

出力

答えを出力せよ。


入力例 1

5
2 5 2 2 1

出力例 1

4

例えば以下のように移動の方向を選択することで座標 0 を 4 回通り過ぎることができ、これが最大です。

  • 1 回目の移動で負の方向を選び、 2 進む。高橋君は座標 0.5 から -1.5 へと移動し、座標 0 を通り過ぎる。
  • 2 回目の移動で正の方向を選び、 5 進む。高橋君は座標 -1.5 から 3.5 へと移動し、座標 0 を通り過ぎる。
  • 3 回目の移動で負の方向を選び、 2 進む。高橋君は座標 3.5 から 1.5 へと移動する。
  • 4 回目の移動で負の方向を選び、 2 進む。高橋君は座標 1.5 から -0.5 へと移動し、座標 0 を通り過ぎる。
  • 5 回目の移動で正の方向を選び、 1 進む。高橋君は座標 -0.5 から 0.5 へと移動し、座標 0 を通り過ぎる。

入力例 2

5
100 1 2 3 4

出力例 2

1

入力例 3

20
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

出力例 3

20

Score : 300 points

Problem Statement

Takahashi is at coordinate 0.5 on a number line.

He will make N moves.
In the i-th move, he chooses either the positive direction or the negative direction, and moves L_i in that direction.

What is the maximum number of times he can pass through coordinate 0?
Under the constraints of this problem, no move will end at coordinate 0.

Constraints

  • 1 \le N \le 20
  • 1 \le L_i \le 10^9
  • All input values are integers.

Input

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

N
L_1 L_2 \dots L_N

Output

Output the answer.


Sample Input 1

5
2 5 2 2 1

Sample Output 1

4

For example, by choosing the directions of movement as follows, he can pass through coordinate 0 four times, which is the maximum.

  • In the first move, choose the negative direction and move 2. He moves from coordinate 0.5 to -1.5, passing through coordinate 0.
  • In the second move, choose the positive direction and move 5. He moves from coordinate -1.5 to 3.5, passing through coordinate 0.
  • In the third move, choose the negative direction and move 2. He moves from coordinate 3.5 to 1.5.
  • In the fourth move, choose the negative direction and move 2. He moves from coordinate 1.5 to -0.5, passing through coordinate 0.
  • In the fifth move, choose the positive direction and move 1. He moves from coordinate -0.5 to 0.5, passing through coordinate 0.

Sample Input 2

5
100 1 2 3 4

Sample Output 2

1

Sample Input 3

20
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Sample Output 3

20