A - 123233

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

6 桁の正整数 N が与えられます。
この整数が以下の条件を全て満たすか判定してください。

  • N の各桁のうち、 1 は丁度 1 つである。
  • N の各桁のうち、 2 は丁度 2 つである。
  • N の各桁のうち、 3 は丁度 3 つである。

制約

  • N は 100000 \le N \le 999999 を満たす整数

入力

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

N

出力

N が問題文中の条件を全て満たすなら Yes 、そうでないなら No と 1 行に出力せよ。

入力例 1

123233

出力例 1

Yes

123233 は問題文中の条件を満たすので、 Yes と出力します。

入力例 2

123234

出力例 2

No

123234 は問題文中の条件を満たさないので、 No と出力します。

入力例 3

323132

出力例 3

Yes

入力例 4

500000

出力例 4

No

Score : 100 points

Problem Statement

You are given a 6-digit positive integer N.
Determine whether N satisfies all of the following conditions.

  • Among the digits of N, the digit 1 appears exactly once.
  • Among the digits of N, the digit 2 appears exactly twice.
  • Among the digits of N, the digit 3 appears exactly three times.

Constraints

  • N is an integer satisfying 100000 \le N \le 999999.

Input

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

N

Output

Print Yes if N satisfies all the conditions described in the problem statement, and No otherwise, in one line.

Sample Input 1

123233

Sample Output 1

Yes

123233 satisfies the conditions in the problem statement, so print Yes.

Sample Input 2

123234

Sample Output 2

No

123234 does not satisfy the conditions in the problem statement, so print No.

Sample Input 3

323132

Sample Output 3

Yes

Sample Input 4

500000

Sample Output 4

No
B - Job Interview

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

高橋君はある会社の採用面接を受けました。

面接官の人数 N と、各面接官の高橋君への評価を表す長さ N の文字列 S が与えられます。
i=1,2,\ldots,N に対し S の i 文字目が i 番目の面接官の評価に対応し、o は「良」、- は「可」、x は 「不可」を表します。

高橋君は以下の 2 つの条件を両方満たすならば合格、そうでなければ不合格です。

  • 「良」と評価した面接官が少なくとも 1 人いる
  • 「不可」と評価した面接官がいない

高橋君が合格かどうかを判定してください。

制約

  • 1 \leq N \leq 100
  • S は o, -, x のみからなる長さが N の文字列

入力

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

N
S

出力

高橋君が合格ならば Yes と、そうでなければ No と出力せよ。

入力例 1

4
oo--

出力例 1

Yes

1, 2 番目の面接官が「良」と評価していて、さらに「不可」と評価した面接官がいないため合格です。

入力例 2

3
---

出力例 2

No

「良」と評価した面接官が 1 人もいないため不合格です。

入力例 3

1
o

出力例 3

Yes

入力例 4

100
ooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooox

出力例 4

No

100 番目の面接官が「不可」と評価しているため不合格です。

Score : 100 points

Problem Statement

Takahashi had a job interview.

You are given the number of interviewers, N, and a string S of length N representing the interviewers' evaluations of him.
For each i=1,2,\ldots,N, the i-th character of S corresponds to the i-th interviewer's evaluation; o means Good, - means Fair, and x means Poor.

Takahashi will pass if both of the following conditions are satisfied, and fail otherwise.

  • At least one interviewer's evaluation is Good.
  • No interviewer's evaluation is Poor.

Determine whether Takahashi passes.

Constraints

  • 1 \leq N \leq 100
  • S is a string of length N consisting of o, -, and x.

Input

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

N
S

Output

If Takahashi passes, print Yes; otherwise, print No.

Sample Input 1

4
oo--

Sample Output 1

Yes

The first and second interviewers' evaluations are Good, and no interviewer's evaluation is Poor, so he passes.

Sample Input 2

3
---

Sample Output 2

No

No interviewer's evaluation is Good, so he fails.

Sample Input 3

1
o

Sample Output 3

Yes

Sample Input 4

100
ooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooox

Sample Output 4

No

The 100-th interviewer's evaluation is Poor, so he fails.
C - Right Triangle

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

xy 平面上に、同一直線上にない 3 点 A(x_A,y_A), B(x_B,y_B),C(x_C,y_C) があります。三角形 ABC が直角三角形であるかどうか判定してください。

制約

  • -1000\leq x_A,y_A,x_B,y_B,x_C,y_C\leq 1000
  • 3 点 A,B,C は同一直線上にない
  • 入力は全て整数

入力

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

x_A y_A
x_B y_B
x_C y_C

出力

三角形 ABC が直角三角形であるならば Yes を、そうでないならば No を出力せよ。

入力例 1

0 0
4 0
0 3

出力例 1

Yes

三角形 ABC は直角三角形です。

入力例 2

-4 3
2 1
3 4

出力例 2

Yes

三角形 ABC は直角三角形です。

入力例 3

2 4
-3 2
1 -2

出力例 3

No

三角形 ABC は直角三角形ではありません。

Score : 200 points

Problem Statement

In the xy-plane, there are three points A(x_A, y_A), B(x_B, y_B), and C(x_C, y_C) that are not collinear. Determine whether the triangle ABC is a right triangle.

Constraints

  • -1000 \leq x_A, y_A, x_B, y_B, x_C, y_C \leq 1000
  • The three points A, B, and C are not collinear.
  • All input values are integers.

Input

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

x_A y_A
x_B y_B
x_C y_C

Output

Print Yes if the triangle ABC is a right triangle, and No otherwise.

Sample Input 1

0 0
4 0
0 3

Sample Output 1

Yes

The triangle ABC is a right triangle.

Sample Input 2

-4 3
2 1
3 4

Sample Output 2

Yes

The triangle ABC is a right triangle.

Sample Input 3

2 4
-3 2
1 -2

Sample Output 3

No

The triangle ABC is not a right triangle.
D - 1122 String

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 150 点

問題文

文字列 T が以下の 3 つの条件をすべてみたすとき、かつそのときに限り、T を 1122 文字列 と呼びます。

  • \lvert T \rvert は偶数である。ここで、\lvert T \rvert は T の長さを表す。
  • 1\leq i\leq \frac{\lvert T \rvert}{2} をみたす整数 i について、T の (2i-1) 文字目と 2i 文字目は等しい。
  • 各文字は T にちょうど 0 個または 2 個現れる。すなわち、T に含まれる文字は T にちょうど 2 回ずつ登場する。

英小文字のみからなる文字列 S が与えられるので、S が 1122 文字列であるならば Yes を、そうでないならば No を出力してください。

制約

  • S は英小文字のみからなる長さ 1 以上 100 以下の文字列

入力

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

S

出力

S が 1122 文字列ならば Yes を、そうでないならば No を出力せよ。

入力例 1

aabbcc

出力例 1

Yes

S=aabbcc は 1122 文字列の条件をすべてみたしているため、Yes を出力します。

入力例 2

aab

出力例 2

No

S=aab は長さが奇数であり、 1 つめの条件をみたしていないため、No を出力します。

入力例 3

zzzzzz

出力例 3

No

S=zzzzzz は z が 6 個含まれており、 3 つめの条件をみたしていないため、No を出力します。

Score : 150 points

Problem Statement

A string T is called a 1122 string if and only if it satisfies all of the following three conditions:

  • \lvert T \rvert is even. Here, \lvert T \rvert denotes the length of T.
  • For each integer i satisfying 1\leq i\leq \frac{|T|}{2}, the (2i-1)-th and 2i-th characters of T are equal.
  • Each character appears in T exactly zero or two times. That is, every character contained in T appears exactly twice in T.

Given a string S consisting of lowercase English letters, print Yes if S is a 1122 string, and No otherwise.

Constraints

  • S is a string of length between 1 and 100, inclusive, consisting of lowercase English letters.

Input

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

S

Output

If S is a 1122 string, print Yes; otherwise, print No.

Sample Input 1

aabbcc

Sample Output 1

Yes

S=aabbcc satisfies all the conditions for a 1122 string, so print Yes.

Sample Input 2

aab

Sample Output 2

No

S=aab has an odd length and does not satisfy the first condition, so print No.

Sample Input 3

zzzzzz

Sample Output 3

No

S=zzzzzz contains six zs and does not satisfy the third condition, so print No.
E - Lining Up 2

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

人 1, 人 2,\ldots, 人 N の N 人が一列に並んでいます。

並び方の情報が長さ N の数列 A=(A _ 1,A _ 2,\ldots,A _ N) として与えられます。

A _ i\ (1\leq i\leq N) は次のような情報を表しています。

  • A _ i=-1 のとき、人 i は先頭に並んでいる。
  • A _ i\neq -1 のとき、人 i は人 A _ i のすぐ後ろに並んでいる。

列に並んでいる人の番号を先頭から順番に出力してください。

制約

  • 1\leq N\leq3\times10 ^ 5
  • A _ i=-1 もしくは 1\leq A _ i\leq N\ (1\leq i\leq N)
  • 情報と矛盾しないような N 人の並び方がただ 1 通り存在する
  • 入力はすべて整数

入力

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

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

出力

人 s _ 1, 人 s _ 2,\ldots, 人 s _ N がこの順に列に並んでいるとき、s _ 1,s _ 2,\ldots,s _ N をこの順に空白を区切りとして出力せよ。

入力例 1

6
4 1 -1 5 3 2

出力例 1

3 5 4 1 2 6

先頭から、人 3, 人 5, 人 4, 人 1, 人 2, 人 6 がこの順に列に並んでいるとき、与えられた情報と一致しています。

実際、

  • 人 1 は人 4 のすぐ後ろに並んでいます。
  • 人 2 は人 1 のすぐ後ろに並んでいます。
  • 人 3 は先頭に並んでいます。
  • 人 4 は人 5 のすぐ後ろに並んでいます。
  • 人 5 は人 3 のすぐ後ろに並んでいます。
  • 人 6 は人 2 のすぐ後ろに並んでいます。

となり、与えられた情報と一致していることが確認できます。

よって、3,5,4,1,2,6 をこの順に空白区切りで出力してください。

入力例 2

10
-1 1 2 3 4 5 6 7 8 9

出力例 2

1 2 3 4 5 6 7 8 9 10

入力例 3

30
3 25 20 6 18 12 26 1 29 -1 21 17 23 9 8 30 10 15 22 27 4 13 5 11 16 24 28 2 19 7

出力例 3

10 17 12 6 4 21 11 24 26 7 30 16 25 2 28 27 20 3 1 8 15 18 5 23 13 22 19 29 9 14

Score: 300 points

Problem Statement

There are N people standing in a line: person 1, person 2, \ldots, person N.

You are given the arrangement of the people as a sequence A=(A _ 1,A _ 2,\ldots,A _ N) of length N.

A _ i\ (1\leq i\leq N) represents the following information:

  • if A _ i=-1, person i is at the front of the line;
  • if A _ i\neq -1, person i is right behind person A _ i.

Print the people's numbers in the line from front to back.

Constraints

  • 1\leq N\leq3\times10 ^ 5
  • A _ i=-1 or 1\leq A _ i\leq N\ (1\leq i\leq N)
  • There is exactly one way to arrange the N people consistent with the information given.
  • 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

If person s _ 1, person s _ 2, \ldots, person s _ N are standing in the line in this order, print s _ 1, s _ 2, \ldots, and s _ N in this order, separated by spaces.

Sample Input 1

6
4 1 -1 5 3 2

Sample Output 1

3 5 4 1 2 6

If person 3, person 5, person 4, person 1, person 2, and person 6 stand in line in this order from front to back, the arrangement matches the given information.

Indeed, it can be seen that:

  • person 1 is standing right behind person 4,
  • person 2 is standing right behind person 1,
  • person 3 is at the front of the line,
  • person 4 is standing right behind person 5,
  • person 5 is standing right behind person 3, and
  • person 6 is standing right behind person 2.

Thus, print 3, 5, 4, 1, 2, and 6 in this order, separated by spaces.

Sample Input 2

10
-1 1 2 3 4 5 6 7 8 9

Sample Output 2

1 2 3 4 5 6 7 8 9 10

Sample Input 3

30
3 25 20 6 18 12 26 1 29 -1 21 17 23 9 8 30 10 15 22 27 4 13 5 11 16 24 28 2 19 7

Sample Output 3

10 17 12 6 4 21 11 24 26 7 30 16 25 2 28 27 20 3 1 8 15 18 5 23 13 22 19 29 9 14