AtCoder Beginner Contest 155

A - Poor

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 100 点

問題文

3 つ組の数について、ある 2 つが等しく、残りの 1 つがそれらと異なるとき、その 3 つ組を「かわいそう」であるといいます。

3 つの整数 A, B, C が与えられるので、この 3 つ組がかわいそうであれば Yes を、そうでなければ No を出力してください。

制約

A, B, C はいずれも 1 以上 9 以下の整数

入力

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

A B C

出力

与えられる 3 つ組がかわいそうであれば Yes を、そうでなければ No を出力せよ。

入力例 1

5 7 5

出力例 1

Yes

A と C が等しく、B がそれらと異なるので、この 3 つ組はかわいそうです。

入力例 2

4 4 4

出力例 2

No

A, B, C がいずれも等しいので、この 3 つ組はかわいそうではありません。

入力例 3

4 9 6

出力例 3

No

入力例 4

3 3 4

出力例 4

Yes

Score: 100 points

Problem Statement

A triple of numbers is said to be poor when two of those numbers are equal but the other number is different from those two numbers.

You will be given three integers A, B, and C. If this triple is poor, print Yes; otherwise, print No.

Constraints

A, B, and C are all integers between 1 and 9 (inclusive).

Input

Input is given from Standard Input in the following format:

A B C

Output

If the given triple is poor, print Yes; otherwise, print No.

Sample Input 1

5 7 5

Sample Output 1

Yes

A and C are equal, but B is different from those two numbers, so this triple is poor.

Sample Input 2

4 4 4

Sample Output 2

No

A, B, and C are all equal, so this triple is not poor.

Sample Input 3

4 9 6

Sample Output 3

No

Sample Input 4

3 3 4

Sample Output 4

Yes

B - Papers, Please

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 200 点

問題文

あなたは AtCoder 王国の入国審査官です。入国者の書類にはいくつかの整数が書かれており、あなたの仕事はこれらが条件を満たすか判定することです。

規約では、次の条件を満たすとき、またその時に限り、入国を承認することになっています。

書類に書かれている整数のうち、偶数であるものは全て、3 または 5 で割り切れる。

上の規約に従うとき、書類に N 個の整数 A_1, A_2, \dots, A_N が書かれた入国者を承認するならば APPROVED を、しないならば DENIED を出力してください。

注記

問題文中の条件は、「x が書類に書かれている整数のうち、偶数であるものならば、x は 3 または 5 で割り切れる。」と言い換えられます。ここで、「または」「ならば」は論理学における意味です。

制約

入力はすべて整数
1 \leq N \leq 100
1 \leq A_i \leq 1000

入力

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

N
A_1 A_2 \dots A_N

出力

規約に従うとき、入国者を承認するならば APPROVED を、しないならば DENIED を出力せよ。

入力例 1

5
6 7 9 10 31

出力例 1

APPROVED

書類に書かれている整数のうち、偶数であるものは 6, 10 です。

これらは全て 3 または 5 で割り切れるので、この入国者は承認します。

入力例 2

3
28 27 24

出力例 2

DENIED

28 が条件を満たさないので、この入国者は承認しません。

Score: 200 points

Problem Statement

You are an immigration officer in the Kingdom of AtCoder. The document carried by an immigrant has some number of integers written on it, and you need to check whether they meet certain criteria.

According to the regulation, the immigrant should be allowed entry to the kingdom if and only if the following condition is satisfied:

All even numbers written on the document are divisible by 3 or 5.

If the immigrant should be allowed entry according to the regulation, output APPROVED; otherwise, print DENIED.

Notes

The condition in the statement can be rephrased as "If x is an even number written on the document, x is divisible by 3 or 5". Here "if" and "or" are logical terms.

Constraints

All values in input are integers.
1 \leq N \leq 100
1 \leq A_i \leq 1000

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \dots A_N

Output

If the immigrant should be allowed entry according to the regulation, print APPROVED; otherwise, print DENIED.

Sample Input 1

5
6 7 9 10 31

Sample Output 1

APPROVED

The even numbers written on the document are 6 and 10.

All of them are divisible by 3 or 5, so the immigrant should be allowed entry.

Sample Input 2

3
28 27 24

Sample Output 2

DENIED

28 violates the condition, so the immigrant should not be allowed entry.

C - Poll

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 300 点

問題文

N 枚の投票用紙があり、i\ (1 \leq i \leq N) 枚目には文字列 S_i が書かれています。

書かれた回数が最も多い文字列を全て、辞書順で小さい順に出力してください。

制約

1 \leq N \leq 2 \times 10^5
S_i は英小文字のみからなる文字列 (1 \leq i \leq N)
S_i の長さは 1 以上 10 以下 (1 \leq i \leq N)

入力

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

N
S_1
:
S_N

出力

あてはまる文字列を全て辞書順で小さい順に、改行区切りで出力せよ。

入力例 1

7
beat
vet
beet
bed
vet
bet
beet

出力例 1

beet
vet

書かれた回数は beet と vet が 2 回、beat と bed と bet が 1 回です。したがって、2 回書かれた beet と vet を出力します。

入力例 2

8
buffalo
buffalo
buffalo
buffalo
buffalo
buffalo
buffalo
buffalo

出力例 2

buffalo

入力例 3

7
bass
bass
kick
kick
bass
kick
kick

出力例 3

kick

入力例 4

4
ushi
tapu
nichia
kun

出力例 4

kun
nichia
tapu
ushi

Score: 300 points

Problem Statement

We have N voting papers. The i-th vote (1 \leq i \leq N) has the string S_i written on it.

Print all strings that are written on the most number of votes, in lexicographical order.

Constraints

1 \leq N \leq 2 \times 10^5
S_i (1 \leq i \leq N) are strings consisting of lowercase English letters.
The length of S_i (1 \leq i \leq N) is between 1 and 10 (inclusive).

Input

Input is given from Standard Input in the following format:

N
S_1
:
S_N

Output

Print all strings in question in lexicographical order.

Sample Input 1

7
beat
vet
beet
bed
vet
bet
beet

Sample Output 1

beet
vet

beet and vet are written on two sheets each, while beat, bed, and bet are written on one vote each. Thus, we should print the strings beet and vet.

Sample Input 2

8
buffalo
buffalo
buffalo
buffalo
buffalo
buffalo
buffalo
buffalo

Sample Output 2

buffalo

Sample Input 3

7
bass
bass
kick
kick
bass
kick
kick

Sample Output 3

kick

Sample Input 4

4
ushi
tapu
nichia
kun

Sample Output 4

kun
nichia
tapu
ushi

D - Pairs

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 400 点

問題文

N 個の整数 A_1, A_2, ..., A_N があります。

このうち 2 つを選んでペアにする方法は \frac{N(N-1)}{2} 通りありますが、それぞれのペアについて積を求め、小さい順に並べ替えたとき、K 番目にくる数は何になるでしょう？

制約

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

入力

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

N K
A_1 A_2 \dots A_N

出力

答えを出力せよ。

入力例 1

4 3
3 3 -4 -2

出力例 1

-6

ペアの組み方は 6 通りあり、それぞれの積は 9, -12, -6, -12, -6, 8 です。

小さい順に並べ替えると -12, -12, -6, -6, 8, 9 となり、3 番目にくる数は -6 です。

入力例 2

10 40
5 4 3 2 -1 0 0 0 0 0

出力例 2

入力例 3

30 413
-170202098 -268409015 537203564 983211703 21608710 -443999067 -937727165 -97596546 -372334013 398994917 -972141167 798607104 -949068442 -959948616 37909651 0 886627544 -20098238 0 -948955241 0 -214720580 277222296 -18897162 834475626 0 -425610555 110117526 663621752 0

出力例 3

448283280358331064

Score: 400 points

Problem Statement

We have N integers A_1, A_2, ..., A_N.

There are \frac{N(N-1)}{2} ways to choose two of them and form a pair. If we compute the product of each of those pairs and sort the results in ascending order, what will be the K-th number in that list?

Constraints

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

Input

Input is given from Standard Input in the following format:

N K
A_1 A_2 \dots A_N

Output

Print the answer.

Sample Input 1

4 3
3 3 -4 -2

Sample Output 1

-6

There are six ways to form a pair. The products of those pairs are 9, -12, -6, -12, -6, 8.

Sorting those numbers in ascending order, we have -12, -12, -6, -6, 8, 9. The third number in this list is -6.

Sample Input 2

10 40
5 4 3 2 -1 0 0 0 0 0

Sample Output 2

Sample Input 3

30 413
-170202098 -268409015 537203564 983211703 21608710 -443999067 -937727165 -97596546 -372334013 398994917 -972141167 798607104 -949068442 -959948616 37909651 0 886627544 -20098238 0 -948955241 0 -214720580 277222296 -18897162 834475626 0 -425610555 110117526 663621752 0

Sample Output 3

448283280358331064

E - Payment

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 500 点

問題文

AtCoder 王国の通貨は 10^{100}+1 種類の紙幣のみであり、価値はそれぞれ 1, 10, 10^2, 10^3, \dots, 10^{(10^{100})} です。あなたは商店街で、価値 N のたこ焼き器を 1 つ買おうとしています。

あなたは N 以上の金額を決めて支払います。その後、支払額よりちょうど N だけ少ない金額を、店員がお釣りとして支払います。

あなたと店員が使う紙幣の組合せを適切に設定するとき、両者の使う紙幣の枚数の合計は最小で何枚になるでしょう？

なお、あなたも店員も任意の紙幣を十分多く持っているとします。

制約

N は 1 以上 10^{1,000,000} 以下の整数

入力

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

出力

支払う紙幣の枚数とお釣りとして受け取る紙幣の枚数の合計の最小値を出力せよ。

入力例 1

出力例 1

あなたが価値 10 の紙幣 4 枚を支払い、店員が価値 1 の紙幣 4 枚をお釣りに渡すと、使う紙幣の枚数は合計で 8 枚になります。

8 枚より少ない合計枚数を達成することはできないので、答えは 8 です。

入力例 2

出力例 2

あなたが価値 100 の紙幣 1 枚と価値 1 の紙幣 1 枚を支払い、店員が価値 10 の紙幣 1 枚をお釣りに渡すと、使う紙幣の枚数は合計で 3 枚になります。

入力例 3

314159265358979323846264338327950288419716939937551058209749445923078164062862089986280348253421170

出力例 3

Score: 500 points

Problem Statement

In the Kingdom of AtCoder, only banknotes are used as currency. There are 10^{100}+1 kinds of banknotes, with the values of 1, 10, 10^2, 10^3, \dots, 10^{(10^{100})}. You have come shopping at a mall and are now buying a takoyaki machine with a value of N. (Takoyaki is the name of a Japanese snack.)

To make the payment, you will choose some amount of money which is at least N and give it to the clerk. Then, the clerk gives you back the change, which is the amount of money you give minus N.

What will be the minimum possible number of total banknotes used by you and the clerk, when both choose the combination of banknotes to minimize this count?

Assume that you have sufficient numbers of banknotes, and so does the clerk.

Constraints

N is an integer between 1 and 10^{1,000,000} (inclusive).

Input

Input is given from Standard Input in the following format:

Output

Print the minimum possible number of total banknotes used by you and the clerk.

Sample Input 1

Sample Output 1

If you give four banknotes of value 10 each, and the clerk gives you back four banknotes of value 1 each, a total of eight banknotes are used.

The payment cannot be made with less than eight banknotes in total, so the answer is 8.

Sample Input 2

Sample Output 2

If you give two banknotes of value 100, 1, and the clerk gives you back one banknote of value 10, a total of three banknotes are used.

Sample Input 3

314159265358979323846264338327950288419716939937551058209749445923078164062862089986280348253421170

Sample Output 3

F - Perils in Parallel

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 600 点

問題文

AlDebaran 王国の侵攻によって、AtCoder 王国の各地に爆弾が仕掛けられてしまいました。

幸いにも AtCoder 王国 ABC 隊の健闘により制御装置の一部が手に入ったので、あなたはこれを使って解除を試みることにしました。

仕掛けられた爆弾は N 個あり、1 から N の番号がついています。爆弾 i は座標 A_i にあり、電源は B_i=1 のときオンに、B_i=0 のときオフになっています。

制御装置には M 本のコードがあり、1 から M の番号がついています。コード j を切ると、座標が L_j 以上 R_j 以下の全ての爆弾の電源のオン・オフが切り替わります。

切るコードをうまく選ぶことで全ての爆弾の電源をオフにできるか判定し、できるならばそのようなコードの組合せを 1 つ出力してください。

制約

入力はすべて整数
1 \leq N \leq 10^5
1 \leq A_i \leq 10^9\ (1 \leq i \leq N)
A_i は互いに相異なる
B_i は 0 か 1 のいずれか (1 \leq i \leq N)
1 \leq M \leq 2 \times 10^5
1 \leq L_j \leq R_j \leq 10^9\ (1 \leq j \leq M)

入力

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

N M
A_1 B_1
:
A_N B_N
L_1 R_1
:
L_M R_M

出力

全ての爆弾の電源をオフにすることが不可能であれば -1 と出力せよ。可能であれば、それを達成するコードの組合せを次のように出力せよ。

k
c_1 c_2 \dots c_k

ここで、k は切るコードの本数 (0 でもよい) である。

また、c_1, c_2, \dots, c_k は切るコードの番号であり、1 \leq c_1 < c_2 < \dots < c_k \leq M を満たす必要がある。

入力例 1

出力例 1

2
1 4

座標 5, 10 に電源がオンの爆弾が、座標 8 に電源がオフの爆弾があります。

コード 1 を切ると座標 1 以上 10 以下にある爆弾、つまり全ての爆弾の電源が切り替わります。

コード 4 を切ると座標 8 以上 9 以下にある爆弾、つまり爆弾 3 のみの電源が切り替わります。

したがって、コード 1, 4 の 2 本を切ることで全ての爆弾の電源がオフになります。

入力例 2

出力例 2

-1

切るコードをどう選んでも、全ての爆弾の電源をオフにすることは不可能です。

入力例 3

出力例 3

はじめから全ての爆弾の電源がオフなので、コードを切る必要はありません。

入力例 4

12 20
536130100 1
150049660 1
79245447 1
132551741 0
89484841 1
328129089 0
623467741 0
248785745 0
421631475 0
498966877 0
43768791 1
112237273 0
21499042 142460201
58176487 384985131
88563042 144788076
120198276 497115965
134867387 563350571
211946499 458996604
233934566 297258009
335674184 555985828
414601661 520203502
101135608 501051309
90972258 300372385
255474956 630621190
436210625 517850028
145652401 192476406
377607297 520655694
244404406 304034433
112237273 359737255
392593015 463983307
150586788 504362212
54772353 83124235

出力例 4

5
1 7 8 9 11

条件を満たすコードの組合せが複数あり得る場合、どれを出力しても構いません。

Score: 600 points

Problem Statement

After being invaded by the Kingdom of AlDebaran, bombs are planted throughout our country, AtCoder Kingdom.

Fortunately, our military team called ABC has managed to obtain a device that is a part of the system controlling the bombs.

There are N bombs, numbered 1 to N, planted in our country. Bomb i is planted at the coordinate A_i. It is currently activated if B_i=1, and deactivated if B_i=0.

The device has M cords numbered 1 to M. If we cut Cord j, the states of all the bombs planted between the coordinates L_j and R_j (inclusive) will be switched - from activated to deactivated, and vice versa.

Determine whether it is possible to deactivate all the bombs at the same time. If the answer is yes, output a set of cords that should be cut.

Constraints

All values in input are integers.
1 \leq N \leq 10^5
1 \leq A_i \leq 10^9\ (1 \leq i \leq N)
A_i are pairwise distinct.
B_i is 0 or 1. (1 \leq i \leq N)
1 \leq M \leq 2 \times 10^5
1 \leq L_j \leq R_j \leq 10^9\ (1 \leq j \leq M)

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1
:
A_N B_N
L_1 R_1
:
L_M R_M

Output

If it is impossible to deactivate all the bombs at the same time, print -1. If it is possible to do so, print a set of cords that should be cut, as follows:

k
c_1 c_2 \dots c_k

Here, k is the number of cords (possibly 0), and c_1, c_2, \dots, c_k represent the cords that should be cut. 1 \leq c_1 < c_2 < \dots < c_k \leq M must hold.

Sample Input 1

Sample Output 1

2
1 4

There are two activated bombs at the coordinates 5, 10, and one deactivated bomb at the coordinate 8.

Cutting Cord 1 switches the states of all the bombs planted between the coordinates 1 and 10, that is, all of the three bombs.

Cutting Cord 4 switches the states of all the bombs planted between the coordinates 8 and 9, that is, Bomb 3.

Thus, we can deactivate all the bombs by cutting Cord 1 and Cord 4.

Sample Input 2

Sample Output 2

-1

Cutting any set of cords will not deactivate all the bombs at the same time.

Sample Input 3

Sample Output 3

All the bombs are already deactivated, so we do not need to cut any cord.

Sample Input 4

12 20
536130100 1
150049660 1
79245447 1
132551741 0
89484841 1
328129089 0
623467741 0
248785745 0
421631475 0
498966877 0
43768791 1
112237273 0
21499042 142460201
58176487 384985131
88563042 144788076
120198276 497115965
134867387 563350571
211946499 458996604
233934566 297258009
335674184 555985828
414601661 520203502
101135608 501051309
90972258 300372385
255474956 630621190
436210625 517850028
145652401 192476406
377607297 520655694
244404406 304034433
112237273 359737255
392593015 463983307
150586788 504362212
54772353 83124235

Sample Output 4

5
1 7 8 9 11

If there are multiple sets of cords that deactivate all the bombs when cut, any of them can be printed.