Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
高橋君の家には、高橋君、高橋君の父、高橋君の母の 3 人が住んでおり、全員が毎晩風呂で髪を洗います。
風呂には、高橋君の父、高橋君の母、高橋君の順に入り、それぞれシャンプーを A,B,C ミリリットル使います。
今朝の時点で、ボトルには V ミリリットルのシャンプーが残っていました。このまま補充しない時、初めてシャンプーが不足するのは誰が使おうとした時ですか?
制約
- 1 \leq V,A,B,C \leq 10^5
- 入力に含まれる値は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
V A B C
出力
初めてシャンプーが不足するのが、高橋君の父が使おうとしたときならば F、高橋君の母が使おうとしたときならば M、高橋君が使おうとしたときならば T を出力せよ。
入力例 1
25 10 11 12
出力例 1
T
シャンプーは 25 ミリリットル残っています。
- まず高橋君の父が 10 ミリリットル使い、残りは 15 ミリリットルになります。
- 次に高橋君の母が 11 ミリリットル使い、残りは 4 ミリリットルになります。
- 最後に高橋君が 12 ミリリットル使おうとしますが、4 ミリリットルしか残っておらず、不足しています。
入力例 2
30 10 10 10
出力例 2
F
シャンプーは 30 ミリリットル残っています。
- まず高橋君の父が 10 ミリリットル使い、残りは 20 ミリリットルになります。
- 次に高橋君の母が 10 ミリリットル使い、残りは 10 ミリリットルになります。
- 続いて高橋君が 10 ミリリットル使い、残りは 0 ミリリットルになります。
- 翌日、高橋君の父が 10 ミリリットル使おうとしますが、0 ミリリットルしか残っておらず、不足しています。
入力例 3
100000 1 1 1
出力例 3
M
Score : 100 points
Problem Statement
Three people live in Takahashi's house: Takahashi, his father, and his mother. All of them wash their hair in the bathroom each night.
His father, his mother, and Takahashi take a bath in this order and use A, B, and C milliliters of shampoo, respectively.
This morning, the bottle contained V milliliters of shampoo. Without refilling, who will be the first to run short of shampoo to wash their hair?
Constraints
- 1 \leq V,A,B,C \leq 10^5
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
V A B C
Output
If the first person to run short of shampoo to wash their hair is Takahashi's father, print F; if it is Takahashi's mother, print M; if it is Takahashi, print T.
Sample Input 1
25 10 11 12
Sample Output 1
T
Now, they have 25 milliliters of shampoo.
- First, Takahashi's father uses 10 milliliters, leaving 15.
- Next, Takahashi's mother uses 11 milliliters, leaving 4.
- Finally, Takahashi tries to use 12 milliliters and runs short of shampoo since only 4 is remaining.
Sample Input 2
30 10 10 10
Sample Output 2
F
Now, they have 30 milliliters of shampoo.
- First, Takahashi's father uses 10 milliliters, leaving 20.
- Next, Takahashi's mother uses 10 milliliters, leaving 10.
- Then, Takahashi uses 10 milliliters, leaving 0.
- Next day, Takahashi's father tries to use 10 milliliters and runs short of shampoo since only 0 is remaining.
Sample Input 3
100000 1 1 1
Sample Output 3
M
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
人 1 、人 2 、\ldots 、人 N と番号付けられた N 人が、この順番で時計回りに円卓に座っています。 特に、時計回りで人 N の次の位置には人 1 が座っています。
i = 1, 2, \ldots, N について、人 i の名前は S_i 、年齢は A_i です。 ここで、異なる 2 人が同じ名前や同じ年齢であることはありません。
年齢が最も小さい人を起点として、座っている位置の時計回りの順番で、N 人全員の名前を出力してください。
制約
- 2 \leq N \leq 100
- N は整数
- S_i は英小文字のみからなる長さ 1 以上 10 以下の文字列
- i \neq j \implies S_i \neq S_j
- 0 \leq A_i \leq 10^9
- A_i は整数
- i \neq j \implies A_i \neq A_j
入力
入力は以下の形式で標準入力から与えられる。
N S_1 A_1 S_2 A_2 \vdots S_N A_N
出力
N 行出力せよ。 i = 1, 2, \ldots, N について、i 行目には、年齢が最も小さい人を起点として時計回りで i 番目の位置に座っている人の名前を出力せよ。
入力例 1
5 alice 31 bob 41 carol 5 dave 92 ellen 65
出力例 1
carol dave ellen alice bob
年齢が最も小さい人は人 3 です。よって、人 3 を起点として座っている位置の時計回りの順番、すなわち、人 3 、人 4 、人 5 、人 1 、人 2 の順に名前を出力します。
入力例 2
2 takahashi 1000000000 aoki 999999999
出力例 2
aoki takahashi
Score : 100 points
Problem Statement
There are N people numbered 1, 2, \ldots, N, sitting in this clockwise order around a round table. In particular, person 1 is sitting next to person N in the clockwise direction.
For each i = 1, 2, \ldots, N, person i has a name S_i and an age A_i. Here, no two people have the same name or the same age.
Starting from the youngest person, print the names of all N people in the order of their seating positions in clockwise order.
Constraints
- 2 \leq N \leq 100
- N is an integer.
- S_i is a string of length between 1 and 10, consisting of lowercase English letters.
- i \neq j \implies S_i \neq S_j
- 0 \leq A_i \leq 10^9
- A_i is an integer.
- i \neq j \implies A_i \neq A_j
Input
The input is given from Standard Input in the following format:
N S_1 A_1 S_2 A_2 \vdots S_N A_N
Output
Print N lines. For each i = 1, 2, \ldots, N, the i-th line should contain the name of the person sitting in the i-th position clockwise from the youngest person.
Sample Input 1
5 alice 31 bob 41 carol 5 dave 92 ellen 65
Sample Output 1
carol dave ellen alice bob
The youngest person is person 3. Therefore, starting from person 3, print the names in the clockwise order of their seating positions: person 3, person 4, person 5, person 1, and person 2.
Sample Input 2
2 takahashi 1000000000 aoki 999999999
Sample Output 2
aoki takahashi
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
選挙が行われています。
N 人が投票を行い、i\,(1 \leq i \leq N) 番目の人は S_i という名前の候補者に投票しました。
得票数が最大の候補者の名前を答えてください。なお、与えられる入力では得票数が最大の候補者は一意に定まります。
制約
- 1 \leq N \leq 100
- S_i は英小文字からなる長さ 1 以上 10 以下の文字列
- N は整数
- 得票数が最大の候補者は一意に定まる
入力
入力は以下の形式で標準入力から与えられる。
N S_1 S_2 \vdots S_N
出力
得票数が最大の候補者の名前を出力せよ。
入力例 1
5 snuke snuke takahashi takahashi takahashi
出力例 1
takahashi
takahashi は 3 票、snuke は 2 票獲得しました。よって takahashi を出力します。
入力例 2
5 takahashi takahashi aoki takahashi snuke
出力例 2
takahashi
入力例 3
1 a
出力例 3
a
Score : 200 points
Problem Statement
An election is taking place.
N people voted. The i-th person (1 \leq i \leq N) cast a vote to the candidate named S_i.
Find the name of the candidate who received the most votes. The given input guarantees that there is a unique candidate with the most votes.
Constraints
- 1 \leq N \leq 100
- S_i is a string of length between 1 and 10 (inclusive) consisting of lowercase English letters.
- N is an integer.
- There is a unique candidate with the most votes.
Input
Input is given from Standard Input in the following format:
N S_1 S_2 \vdots S_N
Output
Print the name of the candidate who received the most votes.
Sample Input 1
5 snuke snuke takahashi takahashi takahashi
Sample Output 1
takahashi
takahashi got 3 votes, and snuke got 2, so we print takahashi.
Sample Input 2
5 takahashi takahashi aoki takahashi snuke
Sample Output 2
takahashi
Sample Input 3
1 a
Sample Output 3
a
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
入学試験の受験者が N 人います。
試験の結果、 i 番の受験生は数学で A_i 点、英語で B_i 点を取りました。
試験の合格者は次のように決められます。
- 数学の点が高い方から X 人を合格とする。
- 次に、この時点でまだ合格となっていない受験者のうち、英語の点が高い方から Y 人を合格とする。
- 次に、この時点でまだ合格となっていない受験者のうち、数学と英語の合計点が高い方から Z 人を合格とする。
- ここまでで合格となっていない受験者は、不合格とする。
ただし、 1. から 3. までのどの段階についても、同点であった場合は受験生の番号の小さい方を優先します。入出力例も参照してください。
以上の手順で合格者を決める時、合格となった受験生の番号を小さい方から順に改行区切りで出力してください。
制約
- 入力は全て整数
- 1 \le N \le 1000
- 0 \le X,Y,Z \le N
- 1 \le X+Y+Z \le N
- 0 \le A_i,B_i \le 100
入力
入力は以下の形式で標準入力から与えられる。
N X Y Z A_1 A_2 \dots A_N B_1 B_2 \dots B_N
出力
合格となった受験生の番号を小さい方から順に改行区切りで出力せよ。
入力例 1
6 1 0 2 80 60 80 60 70 70 40 20 50 90 90 80
出力例 1
1 4 5
- まず、数学の点が高い方から 1 人が合格となります。
- 数学の最高点は 80 点で 1 番の受験生と 3 番の受験生が並んでいますが、受験生の番号が小さい方が優先され 1 番の受験生が合格となります。
- 次に、まだ合格となっていない受験者のうち、英語の点が高い方から 0 人が合格となります。
- 明らかに、ここで合格者が増えることはありません。
- 次に、まだ合格となっていない受験者のうち、数学と英語の合計点が高い方から 2 人が合格となります。
- まず、まだ合格となっていない受験者の中で、合計点が 160 点と最も高い 5 番の受験生が合格となります。
- 次に、まだ合格となっていない受験者の中で、合計点が 150 点の 4 番の受験生と 6 番の受験生が並んでいます。受験生の番号の小さい方が優先され、 4 番の受験生が合格となります。
以上より、合格となる受験生の番号は 1,4,5 なので、小さい方から出力してください。
入力例 2
5 2 1 2 0 100 0 100 0 0 0 100 100 0
出力例 2
1 2 3 4 5
全員が合格となることもあります。
入力例 3
15 4 3 2 30 65 20 95 100 45 70 85 20 35 95 50 40 15 85 0 25 45 35 65 70 80 90 40 55 20 20 45 75 100
出力例 3
2 4 5 6 7 8 11 14 15
Score : 200 points
Problem Statement
N examinees took an entrance exam.
The examinee numbered i scored A_i points in math and B_i points in English.
The admissions are determined as follows.
- X examinees with the highest math scores are admitted.
- Then, among the examinees who are not admitted yet, Y examinees with the highest English scores are admitted.
- Then, among the examinees who are not admitted yet, Z examinees with the highest total scores in math and English are admitted.
- Those examinees who are not admitted yet are rejected.
Here, in each of the steps 1. to 3., ties are broken by examinees' numbers: an examinee with the smaller examinee's number is prioritized. See also Sample Input and Output.
Print the examinees' numbers of the admitted examinees determined by the steps above in ascending order, separated by newlines.
Constraints
- All values in input are integers.
- 1 \le N \le 1000
- 0 \le X,Y,Z \le N
- 1 \le X+Y+Z \le N
- 0 \le A_i,B_i \le 100
Input
Input is given from Standard Input in the following format:
N X Y Z A_1 A_2 \dots A_N B_1 B_2 \dots B_N
Output
Print the examinees' number of the admitted examinees in ascending order, separated by newlines.
Sample Input 1
6 1 0 2 80 60 80 60 70 70 40 20 50 90 90 80
Sample Output 1
1 4 5
- First, 1 examinee with the highest math score is admitted.
- Examinee 1 is tied with Examinee 3, scoring the highest 80 points in math, and the tie is broken by the examinees' numbers, so Examinee 1 is admitted.
- Then, among the examinees who are not admitted yet, 0 examinees with the highest English scores are admitted.
- Obviously, it does not affect the admissions.
- Then, among the examinees who are not admitted yet, 2 examinees with the highest total scores in math and English are admitted.
- First, among the examinees who are not admitted yet, Examinee 5 is admitted, scoring the highest total score of 160 points.
- Next, among the examinees who are not admitted yet, Examinee 4 is tied with Examinee 6, scoring a total score of 150 points. The tie is broken by the examinees' numbers, and Examinee 4 is admitted.
Therefore, the examinees' numbers of the admitted examinees are 1, 4, and 5. Print them in ascending order.
Sample Input 2
5 2 1 2 0 100 0 100 0 0 0 100 100 0
Sample Output 2
1 2 3 4 5
All examinees may be admitted.
Sample Input 3
15 4 3 2 30 65 20 95 100 45 70 85 20 35 95 50 40 15 85 0 25 45 35 65 70 80 90 40 55 20 20 45 75 100
Sample Output 3
2 4 5 6 7 8 11 14 15
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
ボールがいくつか刺さった棒が N 本あり、各ボールには英小文字が 1 個書かれています。
i = 1, 2, \ldots, N について、i 番目の棒に刺さった各ボールの英小文字は、文字列 S_i によって表されます。 具体的には、i 番目の棒には文字列 S_i の長さ |S_i| に等しい個数のボールが刺さっており、 刺さっているボールの英小文字を、棒のある端から順に並べたものは文字列 S_i と等しいです。
2 つの棒は、一方の棒に刺さっているボールの英小文字をどちらかの端から並べた列と、もう一方の棒に刺さっているボールの英小文字をどちらかの端から並べた列が一致するとき、同じ棒とみなされます。 より形式的には、1 以上 N 以下の整数 i, j について、i 本目の棒と j 本目の棒は、S_i が S_j と一致するか、S_i が S_j を前後反転したものと一致するとき、かつそのときに限り、同じとみなされます。
N 本の棒の中に、何種類の異なる棒があるかを出力してください。
制約
- N は整数
- 2 \leq N \leq 2 \times 10^5
- S_i は英小文字のみからなる文字列
- |S_i| \geq 1
- \sum_{i = 1}^N |S_i| \leq 2 \times 10^5
入力
入力は以下の形式で標準入力から与えられる。
N S_1 S_2 \vdots S_N
出力
答えを出力せよ。
入力例 1
6 a abc de cba de abc
出力例 1
3
- S_2 =
abcが S_4 =cbaを前後反転したものと一致するため、2 番目の棒と 4 番目の棒は同じとみなされます。 - S_2 =
abcが S_6 =abcと一致するため、2 番目の棒と 6 番目の棒は同じとみなされます。 - S_3 =
deが S_5 =deと一致するため、3 番目の棒と 5 番目の棒は同じとみなされます。
よって、6 本の棒の中に、1 本目の棒、2 本目の棒( 4, 6 本目の棒と同じ)、3 本目の棒( 5 本目の棒と同じ)の 3 種類の異なる棒があります。
Score : 300 points
Problem Statement
There are N sticks with several balls stuck onto them. Each ball has a lowercase English letter written on it.
For each i = 1, 2, \ldots, N, the letters written on the balls stuck onto the i-th stick are represented by a string S_i. Specifically, the number of balls stuck onto the i-th stick is the length |S_i| of the string S_i, and S_i is the sequence of letters on the balls starting from one end of the stick.
Two sticks are considered the same when the sequence of letters on the balls starting from one end of one stick is equal to the sequence of letters starting from one end of the other stick. More formally, for integers i and j between 1 and N, inclusive, the i-th and j-th sticks are considered the same if and only if S_i equals S_j or its reversal.
Print the number of different sticks among the N sticks.
Constraints
- N is an integer.
- 2 \leq N \leq 2 \times 10^5
- S_i is a string consisting of lowercase English letters.
- |S_i| \geq 1
- \sum_{i = 1}^N |S_i| \leq 2 \times 10^5
Input
The input is given from Standard Input in the following format:
N S_1 S_2 \vdots S_N
Output
Print the answer.
Sample Input 1
6 a abc de cba de abc
Sample Output 1
3
- S_2 =
abcequals the reversal of S_4 =cba, so the second and fourth sticks are considered the same. - S_2 =
abcequals S_6 =abc, so the second and sixth sticks are considered the same. - S_3 =
deequals S_5 =de, so the third and fifth sticks are considered the same.
Therefore, there are three different sticks among the six: the first, second (same as the fourth and sixth), and third (same as the fifth).
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 350 点
問題文
高橋君は N 組の靴下を持っており、i 番目の組は色 i の靴下 2 枚からなります。 ある日タンスの中を整理した高橋君は、色 A_1,A_2,\dots,A_K の靴下を 1 枚ずつなくしてしまったことに気づいたので、残っている 2N-K 枚の靴下を使って、靴下 2 枚ずつからなる \lfloor\frac{2N-K}{2}\rfloor 個の組を新たに作り直すことにしました。 色 i の靴下と色 j の靴下からなる組の奇妙さは |i-j| として定義され、高橋君は奇妙さの総和をできるだけ小さくしたいです。
残っている靴下をうまく組み合わせて \lfloor\frac{2N-K}{2}\rfloor 個の組を作ったとき、奇妙さの総和が最小でいくつになるか求めてください。 なお、2N-K が奇数のとき、どの組にも含まれない靴下が 1 枚存在することに注意してください。
制約
- 1\leq K\leq N \leq 2\times 10^5
- 1\leq A_1 < A_2 < \dots < A_K \leq N
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N K A_1 A_2 \dots A_K
出力
奇妙さの総和の最小値を整数として出力せよ。
入力例 1
4 2 1 3
出力例 1
2
以下、色 i の靴下と色 j の靴下からなる組を (i,j) と表記します。
色 1,2,3,4 の靴下がそれぞれ 1,2,1,2 枚ずつあります。 (1,2),(2,3),(4,4) の 3 組を作ると、奇妙さの総和は |1-2|+|2-3|+|4-4|=2 となり、これが最小です。
入力例 2
5 1 2
出力例 2
0
(1,1),(3,3),(4,4),(5,5) の 4 組を作り、色 2 の靴下を 1 枚余らせる(どの組にも入れない)のが最適です。
入力例 3
8 5 1 2 4 7 8
出力例 3
2
Score : 350 points
Problem Statement
Takahashi has N pairs of socks, and the i-th pair consists of two socks of color i. One day, after organizing his chest of drawers, Takahashi realized that he had lost one sock each of colors A_1, A_2, \dots, A_K, so he decided to use the remaining 2N-K socks to make \lfloor\frac{2N-K}{2}\rfloor new pairs of socks, each pair consisting of two socks. The weirdness of a pair of a sock of color i and a sock of color j is defined as |i-j|, and Takahashi wants to minimize the total weirdness.
Find the minimum possible total weirdness when making \lfloor\frac{2N-K}{2}\rfloor pairs from the remaining socks. Note that if 2N-K is odd, there will be one sock that is not included in any pair.
Constraints
- 1\leq K\leq N \leq 2\times 10^5
- 1\leq A_1 < A_2 < \dots < A_K \leq N
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N K A_1 A_2 \dots A_K
Output
Print the minimum total weirdness as an integer.
Sample Input 1
4 2 1 3
Sample Output 1
2
Below, let (i,j) denote a pair of a sock of color i and a sock of color j.
There are 1, 2, 1, 2 socks of colors 1, 2, 3, 4, respectively. Creating the pairs (1,2),(2,3),(4,4) results in a total weirdness of |1-2|+|2-3|+|4-4|=2, which is the minimum.
Sample Input 2
5 1 2
Sample Output 2
0
The optimal solution is to make the pairs (1,1),(3,3),(4,4),(5,5) and leave one sock of color 2 as a surplus (not included in any pair).
Sample Input 3
8 5 1 2 4 7 8
Sample Output 3
2
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
xy -平面上の N 個の円が与えられます。 i = 1, 2, \ldots, N について、i 番目の円は点 (x_i, y_i) を中心とする半径 r_i の円です。
N 個の円のうち少なくとも 1 つ以上の円の円周上にある点のみを通って、点 (s_x, s_y) から点 (t_x, t_y) に行くことができるかどうかを判定してください。
制約
- 1 \leq N \leq 3000
- -10^9 \leq x_i, y_i \leq 10^9
- 1 \leq r_i \leq 10^9
- (s_x, s_y) は N 個の円のうち少なくとも 1 つ以上の円の円周上にある
- (t_x, t_y) は N 個の円のうち少なくとも 1 つ以上の円の円周上にある
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N s_x s_y t_x t_y x_1 y_1 r_1 x_2 y_2 r_2 \vdots x_N y_N r_N
出力
点 (s_x, s_y) から点 (t_x, t_y) に行くことができる場合は Yes を、そうでない場合は No を出力せよ。
ジャッジは英小文字と英大文字を厳密に区別することに注意せよ。
入力例 1
4 0 -2 3 3 0 0 2 2 0 2 2 3 1 -3 3 3
出力例 1
Yes

例えば、下記の経路で点 (0, -2) から点 (3, 3) へ行くことができます。
- 点 (0, -2) から 1 つ目の円の円周上を反時計回りに通って点 (1, -\sqrt{3}) へ行く。
- 点 (1, -\sqrt{3}) から 2 つ目の円の円周上を時計回りに通って点 (2, 2) へ行く。
- 点 (2, 2) から 3 つ目の円の円周上を反時計回りに通って点 (3, 3) へ行く。
よって、Yes を出力します。
入力例 2
3 0 1 0 3 0 0 1 0 0 2 0 0 3
出力例 2
No

少なくとも 1 つ以上の円の円周上にある点のみを通って点 (0, 1) から点 (0, 3) に行くことはできないので No を出力します。
Score : 400 points
Problem Statement
You are given N circles on the xy-coordinate plane. For each i = 1, 2, \ldots, N, the i-th circle is centered at (x_i, y_i) and has a radius of r_i.
Determine whether it is possible to get from (s_x, s_y) to (t_x, t_y) by only passing through points that lie on the circumference of at least one of the N circles.
Constraints
- 1 \leq N \leq 3000
- -10^9 \leq x_i, y_i \leq 10^9
- 1 \leq r_i \leq 10^9
- (s_x, s_y) lies on the circumference of at least one of the N circles.
- (t_x, t_y) lies on the circumference of at least one of the N circles.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N s_x s_y t_x t_y x_1 y_1 r_1 x_2 y_2 r_2 \vdots x_N y_N r_N
Output
If it is possible to get from (s_x, s_y) to (t_x, t_y), print Yes; otherwise, print No.
Note that the judge is case-sensitive.
Sample Input 1
4 0 -2 3 3 0 0 2 2 0 2 2 3 1 -3 3 3
Sample Output 1
Yes

Here is one way to get from (0, -2) to (3, 3).
- From (0, -2), pass through the circumference of the 1-st circle counterclockwise to reach (1, -\sqrt{3}).
- From (1, -\sqrt{3}), pass through the circumference of the 2-nd circle clockwise to reach (2, 2).
- From (2, 2), pass through the circumference of the 3-rd circle counterclockwise to reach (3, 3).
Thus, Yes should be printed.
Sample Input 2
3 0 1 0 3 0 0 1 0 0 2 0 0 3
Sample Output 2
No

It is impossible to get from (0, 1) to (0, 3) by only passing through points on the circumference of at least one of the circles, so No should be printed.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 450 点
問題文
2 次元平面上に N 個の点があります。N は奇数です。 i 番目の点は (x_i, y_i) にあります。全ての点の座標は相異なります。
N 個の点のうち過半数を通る直線が存在するかを判定して、存在すればそれを出力してください。
なお、制約を満たすどのような入力においても、条件を満たす直線が存在する場合、その直線は -10^{18} 以上 10^{18} 以下の整数 a,b,c を用いて ax+by+c=0 と表すことができます。(ただし (a,b,c) \neq (0,0,0)) この a,b,c を出力してください。
制約
- 3 \leq N \leq 5 \times 10^5
- N は奇数
- -10^8 \leq x_i \leq 10^8
- -10^8 \leq y_i \leq 10^8
- i \neq j ならば (x_i, y_i) \neq (x_j, y_j)
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N x_1 y_1 x_2 y_2 \vdots x_N y_N
出力
条件を満たす直線が存在しない場合は No を出力せよ。
条件を満たす直線が存在する場合は 2 行出力せよ。1 行目には Yes を出力して、2 行目には a,b,c をこの順に空白区切りで出力せよ。a,b,c は -10^{18} 以上 10^{18} 以下かつ (a,b,c) \neq (0,0,0) である必要がある点に注意せよ。
答えが複数ある場合はどれを出力しても正答とみなされる。
入力例 1
3 1 1 3 2 2 4
出力例 1
Yes 2 1 -8
直線 2x+y-8=0 は 2 番目の点と 3 番目の点を通るので条件を満たします。
入力例 2
5 5 2 1 3 2 6 4 4 5 4
出力例 2
No
条件を満たす直線は存在しません。
入力例 3
11 -9374372 85232388 -60705467 86198234 -7475320 80628487 98066347 -23868213 -12177678 85284287 30535572 -35358356 51324557 22410787 28854279 44658587 -28804873 82911971 65052073 8819187 -67744430 68365758
出力例 3
Yes 4655800 4702358 -344340416016346
Score : 450 points
Problem Statement
There are N points on a two-dimensional plane. N is odd. The i-th point is at (x_i, y_i). All point coordinates are distinct.
Determine whether there exists a line passing through more than half of the N points, and if so, output it.
For any input satisfying the constraints, if a line satisfying the condition exists, it can be expressed as ax+by+c=0 using integers a,b,c with -10^{18} \leq a,b,c \leq 10^{18} (where (a,b,c) \neq (0,0,0)). Output these a,b,c.
Constraints
- 3 \leq N \leq 5 \times 10^5
- N is odd.
- -10^8 \leq x_i \leq 10^8
- -10^8 \leq y_i \leq 10^8
- If i \neq j, then (x_i, y_i) \neq (x_j, y_j).
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N x_1 y_1 x_2 y_2 \vdots x_N y_N
Output
If no line satisfying the condition exists, output No.
If a line satisfying the condition exists, output two lines. On the first line, output Yes, and on the second line, output a,b,c in this order separated by spaces. a,b,c must satisfy -10^{18} \leq a,b,c \leq 10^{18} and (a,b,c) \neq (0,0,0).
If there are multiple solutions, any of them will be considered correct.
Sample Input 1
3 1 1 3 2 2 4
Sample Output 1
Yes 2 1 -8
The line 2x+y-8=0 passes through the 2nd and 3rd points, so it satisfies the condition.
Sample Input 2
5 5 2 1 3 2 6 4 4 5 4
Sample Output 2
No
No line satisfying the condition exists.
Sample Input 3
11 -9374372 85232388 -60705467 86198234 -7475320 80628487 98066347 -23868213 -12177678 85284287 30535572 -35358356 51324557 22410787 28854279 44658587 -28804873 82911971 65052073 8819187 -67744430 68365758
Sample Output 3
Yes 4655800 4702358 -344340416016346
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 500 点
問題文
長さ N の数列 A = (A_1, \dots, A_N), B = (B_1, \dots, B_N) が与えられます。\{1,2,\ldots,N\} の空でない部分集合 S であって、以下の条件を満たすものの個数を数えてください。
- \max_{i \in S} A_i \geq \sum_{i \in S} B_i
なお、答えは非常に大きくなることがあるため、998244353 で割ったあまりを出力してください。
制約
- 1 \leq N \leq 5000
- 1 \leq A_i,B_i \leq 5000
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \ldots A_N B_1 B_2 \ldots B_N
出力
問題文中の条件を満たす S の個数を 998244353 で割ったあまりを出力せよ。
入力例 1
2 3 1 1 2
出力例 1
2
\{1,2,\ldots,N\} の空でない部分集合としてあり得るものは、\{1\}, \{2\}, \{1,2\} の 3 通りです。
- S=\{1\} のとき \max_{i \in S} A_i=3, \sum_{i \in S} B_i=1
- S=\{2\} のとき \max_{i \in S} A_i=1, \sum_{i \in S} B_i=2
- S=\{1,2\} のとき \max_{i \in S} A_i=3, \sum_{i \in S} B_i=3
であるため、問題文中の条件、即ち \max_{i \in S} A_i \geq \sum_{i \in S} B_i を満たす S は \{1\} と \{1,2\} の 2 通りです。
入力例 2
2 1 1 2 2
出力例 2
0
条件を満たす S が存在しない場合もあります。
入力例 3
20 1937 3980 2689 1208 3640 1979 581 2271 4229 3948 3708 1522 4161 4661 3797 96 3388 3395 2920 2247 4485 2580 174 1156 3770 3396 3558 3500 3494 479 269 3383 1230 1711 3545 3919 134 475 3796 1017
出力例 3
476
Score : 500 points
Problem Statement
Given are sequences of N integers each: A = (A_1, \dots, A_N) and B = (B_1, \dots, B_N). Find the number of non-empty subsets S of \{1,2,\ldots,N\} that satisfy the following condition:
- \max_{i \in S} A_i \geq \sum_{i \in S} B_i.
Since the count can be enormous, print it modulo 998244353.
Constraints
- 1 \leq N \leq 5000
- 1 \leq A_i,B_i \leq 5000
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A_1 A_2 \ldots A_N B_1 B_2 \ldots B_N
Output
Print the number of subsets S that satisfy the condition in the Problem Statement, modulo 998244353.
Sample Input 1
2 3 1 1 2
Sample Output 1
2
\{1,2,\ldots,N\} has three subsets: \{1\}, \{2\}, and \{1,2\}.
- For S=\{1\}, we have \max_{i \in S} A_i=3 and \sum_{i \in S} B_i=1.
- For S=\{2\}, we have \max_{i \in S} A_i=1 and \sum_{i \in S} B_i=2.
- For S=\{1,2\}, we have \max_{i \in S} A_i=3 and \sum_{i \in S} B_i=3.
Thus, the condition \max_{i \in S} A_i \geq \sum_{i \in S} B_i is satisfied by two subsets: \{1\} and \{1,2\}.
Sample Input 2
2 1 1 2 2
Sample Output 2
0
There may be no subsets that satisfy the condition.
Sample Input 3
20 1937 3980 2689 1208 3640 1979 581 2271 4229 3948 3708 1522 4161 4661 3797 96 3388 3395 2920 2247 4485 2580 174 1156 3770 3396 3558 3500 3494 479 269 3383 1230 1711 3545 3919 134 475 3796 1017
Sample Output 3
476