AtCoder Beginner Contest 166

A - A?C

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100 点

問題文

AtCoder 社は、毎週土曜日にコンテストを開催しています。

コンテストには ABC と ARC の 2 つの種類があり、毎週どちらか一方が開催されます。

ABC が開催された次の週には ARC が開催され、ARC が行われた次の週には ABC が開催されます。

先週開催されたコンテストを表す文字列 S が与えられるので、今週開催されるコンテストを表す文字列を出力してください。

制約

S は ABC または ARC

入力

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

出力

今週開催されるコンテストを表す文字列を出力せよ。

入力例 1

ABC

出力例 1

ARC

先週開催されたコンテストは ABC なので、今週は ARC が開催されます。

Score : 100 points

Problem Statement

AtCoder Inc. holds a contest every Saturday.

There are two types of contests called ABC and ARC, and just one of them is held at a time.

The company holds these two types of contests alternately: an ARC follows an ABC and vice versa.

Given a string S representing the type of the contest held last week, print the string representing the type of the contest held this week.

Constraints

S is ABC or ARC.

Input

Input is given from Standard Input in the following format:

Output

Print the string representing the type of the contest held this week.

Sample Input 1

ABC

Sample Output 1

ARC

They held an ABC last week, so they will hold an ARC this week.

B - Trick or Treat

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 200 点

問題文

ある街に、N 人のすぬけ君(すぬけ君 1 、すぬけ君 2 、 ...、すぬけ君 N )が住んでいます。

この街には、 K 種類のお菓子(お菓子 1 、お菓子 2 、....、お菓子 K )が売られています。お菓子 i を持っているのは、すぬけ君 A_{i, 1}, A_{i, 2}, \cdots, A_{i, {d_i}} の計 d_i 人です。

高橋君は今からこの街を回り、お菓子を 1 つも持っていないすぬけ君にいたずらをします。このとき、何人のすぬけ君がいたずらを受けるでしょうか。

制約

入力は全て整数
1 \leq N \leq 100
1 \leq K \leq 100
1 \leq d_i \leq N
1 \leq A_{i, 1} < \cdots < A_{i, d_i} \leq N

入力

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

N K
d_1
A_{1, 1} \cdots A_{1, d_1}
\vdots
d_K
A_{K, 1} \cdots A_{K, d_K}

出力

答えを出力せよ。

入力例 1

出力例 1

すぬけ君 1 はお菓子 1 を持っています。
すぬけ君 2 はお菓子を持っていません。
すぬけ君 3 はお菓子 1, 2 を持っています。

以上より、いたずらを受けるのはすぬけ君 2 の一人です。

入力例 2

出力例 2

Score : 200 points

Problem Statement

N Snukes called Snuke 1, Snuke 2, ..., Snuke N live in a town.

There are K kinds of snacks sold in this town, called Snack 1, Snack 2, ..., Snack K. The following d_i Snukes have Snack i: Snuke A_{i, 1}, A_{i, 2}, \cdots, A_{i, {d_i}}.

Takahashi will walk around this town and make mischief on the Snukes who have no snacks. How many Snukes will fall victim to Takahashi's mischief?

Constraints

All values in input are integers.
1 \leq N \leq 100
1 \leq K \leq 100
1 \leq d_i \leq N
1 \leq A_{i, 1} < \cdots < A_{i, d_i} \leq N

Input

Input is given from Standard Input in the following format:

N K
d_1
A_{1, 1} \cdots A_{1, d_1}
\vdots
d_K
A_{K, 1} \cdots A_{K, d_K}

Output

Print the answer.

Sample Input 1

Sample Output 1

Snuke 1 has Snack 1.
Snuke 2 has no snacks.
Snuke 3 has Snack 1 and 2.

Thus, there will be one victim: Snuke 2.

Sample Input 2

Sample Output 2

C - Peaks

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

AtCoder丘陵には N 個の展望台があり、展望台 i の標高は H_i です。また、異なる展望台どうしを結ぶ M 本の道があり、道 j は展望台 A_j と展望台 B_j を結んでいます。

展望台 i が良い展望台であるとは、展望台 i から一本の道を使って辿り着けるどの展望台よりも展望台 i の方が標高が高いことをいいます。展望台 i から一本の道を使って辿り着ける展望台が存在しない場合も、展望台 i は良い展望台であるといいます。

良い展望台がいくつあるか求めてください。

制約

2 \leq N \leq 10^5
1 \leq M \leq 10^5
1 \leq H_i \leq 10^9
1 \leq A_i,B_i \leq N
A_i \neq B_i
同じ展望台の組を結ぶ道が複数あることもある。
入力中の値はすべて整数である。

入力

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

N M
H_1 H_2 ... H_N
A_1 B_1
A_2 B_2
:
A_M B_M

出力

良い展望台の数を出力せよ。

入力例 1

出力例 1

展望台 1 から一本の道を使って辿り着ける展望台は展望台 3 ですが、展望台 1 の標高は展望台 3 の標高より高くないため、展望台 1 は良い展望台ではありません。
展望台 2 から一本の道を使って辿り着ける展望台は展望台 3 と展望台 4 ですが、展望台 2 の標高は展望台 3 の標高より高くないため、展望台 2 は良い展望台ではありません。
展望台 3 から一本の道を使って辿り着ける展望台は展望台 1 と展望台 2 ですが、展望台 3 の標高は展望台 1 の標高より高く、かつ展望台 2 の標高より高いため、展望台 3 は良い展望台です。
展望台 4 から一本の道を使って辿り着ける展望台は展望台 2 ですが、展望台 4 の標高は展望台 2 の標高より高いため、展望台 4 は良い展望台です。

展望台 3 と展望台 4 が良い展望台なので、良い展望台の数は 2 です。

入力例 2

6 5
8 6 9 1 2 1
1 3
4 2
4 3
4 6
4 6

出力例 2

Score : 300 points

Problem Statement

There are N observatories in AtCoder Hill, called Obs. 1, Obs. 2, ..., Obs. N. The elevation of Obs. i is H_i. There are also M roads, each connecting two different observatories. Road j connects Obs. A_j and Obs. B_j.

Obs. i is said to be good when its elevation is higher than those of all observatories that can be reached from Obs. i using just one road. Note that Obs. i is also good when no observatory can be reached from Obs. i using just one road.

How many good observatories are there?

Constraints

2 \leq N \leq 10^5
1 \leq M \leq 10^5
1 \leq H_i \leq 10^9
1 \leq A_i,B_i \leq N
A_i \neq B_i
Multiple roads may connect the same pair of observatories.
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
H_1 H_2 ... H_N
A_1 B_1
A_2 B_2
:
A_M B_M

Output

Print the number of good observatories.

Sample Input 1

Sample Output 1

From Obs. 1, you can reach Obs. 3 using just one road. The elevation of Obs. 1 is not higher than that of Obs. 3, so Obs. 1 is not good.
From Obs. 2, you can reach Obs. 3 and 4 using just one road. The elevation of Obs. 2 is not higher than that of Obs. 3, so Obs. 2 is not good.
From Obs. 3, you can reach Obs. 1 and 2 using just one road. The elevation of Obs. 3 is higher than those of Obs. 1 and 2, so Obs. 3 is good.
From Obs. 4, you can reach Obs. 2 using just one road. The elevation of Obs. 4 is higher than that of Obs. 2, so Obs. 4 is good.

Thus, the good observatories are Obs. 3 and 4, so there are two good observatories.

Sample Input 2

6 5
8 6 9 1 2 1
1 3
4 2
4 3
4 6
4 6

Sample Output 2

D - I hate Factorization

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

A^5-B^5 = X を満たす整数の組 (A,B) をひとつ示してください。ただし、与えられる X に対して、条件を満たす整数の組 (A,B) が存在することが保証されています。

制約

1 \leq X \leq 10^9
X は整数である。
条件を満たす整数の組 (A,B) が存在する。

入力

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

出力

A と B を空白区切りで出力せよ。条件を満たす整数の組 (A,B) が複数存在する場合、どれを出力してもかまわない。

A B

入力例 1

出力例 1

2 -1

A=2,B=-1 のとき、A^5-B^5 の値は 33 になります。

入力例 2

出力例 2

0 -1

Score : 400 points

Problem Statement

Give a pair of integers (A, B) such that A^5-B^5 = X. It is guaranteed that there exists such a pair for the given integer X.

Constraints

1 \leq X \leq 10^9
X is an integer.
There exists a pair of integers (A, B) satisfying the condition in Problem Statement.

Input

Input is given from Standard Input in the following format:

Output

Print A and B, with space in between. If there are multiple pairs of integers (A, B) satisfying the condition, you may print any of them.

A B

Sample Input 1

Sample Output 1

2 -1

For A=2 and B=-1, A^5-B^5 = 33.

Sample Input 2

Sample Output 2

0 -1

E - This Message Will Self-Destruct in 5s

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 500 点

問題文

AtCoder 王国の優秀なエージェントであるあなたは、盗まれた極秘情報が AlDebaran 王国の手に渡ることを阻止するため、取引現場であるパーティに潜入しました。

パーティには N 人の参加者がおり、それぞれ 1 から N までの番号がついています。参加者 i の身長は A_i です。

あなたは事前の尋問によって、極秘情報を取引するのは以下の条件を満たす 2 人組であることを知っています。

2 人の持つ番号の差の絶対値が、2 人の身長の和に等しい。

N 人の参加者のうちから 2 人を選んでペアにする方法は \frac{N(N-1)}{2} 通りありますが、このうち上の条件を満たすペアは何通りあるでしょう？

なお、極秘情報の内容が何であるかはあなたの知るところではありません。

制約

入力はすべて整数
2 \leq N \leq 2 \times 10^5
1 \leq A_i \leq 10^9\ (1 \leq i \leq N)

入力

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

N
A_1 A_2 \dots A_N

出力

条件を満たすペアの個数を出力せよ。

入力例 1

6
2 3 3 1 3 1

出力例 1

A_1 + A_4 = 3 なので、参加者 1, 4 のペアは条件を満たします。
A_2 + A_6 = 4 なので、参加者 2, 6 のペアは条件を満たします。
A_4 + A_6 = 2 なので、参加者 4, 6 のペアは条件を満たします。

その他に作れるペアはいずれも条件を満たさないので、3 を出力します。

入力例 2

6
5 2 4 2 8 8

出力例 2

条件を満たすペアが存在しないので、0 を出力します。

入力例 3

32
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6 2 6 4 3 3 8 3 2 7 9 5

出力例 3

Score: 500 points

Problem Statement

You are the top spy of AtCoder Kingdom. To prevent the stolen secret from being handed to AlDebaran Kingdom, you have sneaked into the party where the transaction happens.

There are N attendees in the party, and they are given attendee numbers from 1 through N. The height of Attendee i is A_i.

According to an examination beforehand, you know that a pair of attendees satisfying the condition below will make the transaction.

The absolute difference of their attendee numbers is equal to the sum of their heights.

There are \frac{N(N-1)}{2} ways to choose two from the N attendees and make a pair. Among them, how many satisfy the condition above?

P.S.: We cannot let you know the secret.

Constraints

All values in input are integers.
2 \leq N \leq 2 \times 10^5
1 \leq A_i \leq 10^9\ (1 \leq i \leq N)

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \dots A_N

Output

Print the number of pairs satisfying the condition.

Sample Input 1

6
2 3 3 1 3 1

Sample Output 1

A_1 + A_4 = 3, so the pair of Attendee 1 and 4 satisfy the condition.
A_2 + A_6 = 4, so the pair of Attendee 2 and 6 satisfy the condition.
A_4 + A_6 = 2, so the pair of Attendee 4 and 6 satisfy the condition.

No other pair satisfies the condition, so you should print 3.

Sample Input 2

6
5 2 4 2 8 8

Sample Output 2

No pair satisfies the condition, so you should print 0.

Sample Input 3

32
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6 2 6 4 3 3 8 3 2 7 9 5

Sample Output 3

F - Three Variables Game

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

あるゲームでは 3 つの変数があり、それぞれ A,B,C で表されます。

ゲームの進行と共に、あなたは N 回の選択に迫られます。それぞれの選択は文字列 s_i によって示され、 s_i が AB のとき、A と B のどちらかに 1 を足しもう一方から 1 を引くこと、 AC のとき、A と C のどちらかに 1 を足しもう一方から 1 を引くこと、 BC のとき、B と C のどちらかに 1 を足しもう一方から 1 を引くことを意味します。

いずれの選択の後にも、A,B,C のいずれも負の値になってはいけません。

この条件を満たしつつ N 回すべての選択を終えることが可能であるか判定し、可能であるならそのような選択方法をひとつ示してください。

制約

1 \leq N \leq 10^5
0 \leq A,B,C \leq 10^9
N, A, B, C は整数である。
s_i は AB, AC, BC のいずれか

入力

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

N A B C
s_1
s_2
:
s_N

出力

条件を満たしつつ N 個すべての選択を終えることが可能である場合は Yes を、そうでない場合は No を出力せよ。

加えて、前者の場合は続く N 行に選択方法を示せ。i+1 行目には i 回目の選択で 1 を足す変数の名前 (A, B, C のいずれか) を出力せよ。

入力例 1

2 1 3 0
AB
AC

出力例 1

Yes
A
C

次のようにすることで 2 回すべての選択を終えることができます。

1 回目の選択では、A に 1 を足し B から 1 を引く。A の値が 2 に、B の値が 2 に変化する。
2 回目の選択では、C に 1 を足し A から 1 を引く。C の値が 1 に、A の値が 1 に変化する。

入力例 2

3 1 0 0
AB
BC
AB

出力例 2

No

入力例 3

1 0 9 0
AC

出力例 3

No

入力例 4

8 6 9 1
AC
BC
AB
BC
AC
BC
AB
AB

出力例 4

Yes
C
B
B
C
C
B
A
A

Score : 600 points

Problem Statement

There is a game that involves three variables, denoted A, B, and C.

As the game progresses, there will be N events where you are asked to make a choice. Each of these choices is represented by a string s_i. If s_i is AB, you must add 1 to A or B then subtract 1 from the other; if s_i is AC, you must add 1 to A or C then subtract 1 from the other; if s_i is BC, you must add 1 to B or C then subtract 1 from the other.

After each choice, none of A, B, and C should be negative.

Determine whether it is possible to make N choices under this condition. If it is possible, also give one such way to make the choices.

Constraints

1 \leq N \leq 10^5
0 \leq A,B,C \leq 10^9
N, A, B, C are integers.
s_i is AB, AC, or BC.

Input

Input is given from Standard Input in the following format:

N A B C
s_1
s_2
:
s_N

Output

If it is possible to make N choices under the condition, print Yes; otherwise, print No.

Also, in the former case, show one such way to make the choices in the subsequent N lines. The (i+1)-th line should contain the name of the variable (A, B, or C) to which you add 1 in the i-th choice.

Sample Input 1

2 1 3 0
AB
AC

Sample Output 1

Yes
A
C

You can successfully make two choices, as follows:

In the first choice, add 1 to A and subtract 1 from B. A becomes 2, and B becomes 2.
In the second choice, add 1 to C and subtract 1 from A. C becomes 1, and A becomes 1.

Sample Input 2

3 1 0 0
AB
BC
AB

Sample Output 2

No

Sample Input 3

1 0 9 0
AC

Sample Output 3

No

Sample Input 4

8 6 9 1
AC
BC
AB
BC
AC
BC
AB
AB

Sample Output 4

Yes
C
B
B
C
C
B
A
A