Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 150 点
問題文
長さ N の整数列 A=(A_1,A_2,\ldots,A_N) が与えられます。
A に含まれる数を重複を除いて小さい順に出力してください。
制約
- 1\le N\le 100
- 1\le A_i\le 100
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \ldots A_N
出力
A に含まれる数を小さい順に C_1,C_2,\ldots , C_M として、以下の形式で出力せよ。
M C_1 C_2 \ldots C_M
入力例 1
4 3 1 4 1
出力例 1
3 1 3 4
A=(3,1,4,1) に含まれる数は小さい順に 1,3,4 の 3 つです。したがって、上記のように出力してください。
入力例 2
3 7 7 7
出力例 2
1 7
入力例 3
8 19 5 5 19 5 19 4 19
出力例 3
3 4 5 19
Score : 150 points
Problem Statement
An integer sequence A=(A_1,A_2,\ldots,A_N) of length N is given.
Output the numbers contained in A in ascending order, removing duplicates.
Constraints
- 1\le N\le 100
- 1\le A_i\le 100
- 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
Let C_1,C_2,\ldots , C_M be the numbers contained in A in ascending order. Output in the following format:
M C_1 C_2 \ldots C_M
Sample Input 1
4 3 1 4 1
Sample Output 1
3 1 3 4
The numbers contained in A=(3,1,4,1) are 1,3,4 in ascending order, totalling 3 distinct numbers. Therefore, output as shown above.
Sample Input 2
3 7 7 7
Sample Output 2
1 7
Sample Input 3
8 19 5 5 19 5 19 4 19
Sample Output 3
3 4 5 19
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 250 点
問題文
あなたは3Dゲームの当たり判定を実装しようとしています。
3 次元空間内の直方体であって、2 点 (a,b,c),(d,e,f) を結ぶ線分を対角線とし、全ての面が xy 平面、yz 平面、zx 平面のいずれかに平行なものを C(a,b,c,d,e,f) と表します。
（この定義により C(a,b,c,d,e,f) は一意に定まります）
2 つの直方体 C(a,b,c,d,e,f) と C(g,h,i,j,k,l) が与えられるので、これらの共通部分の体積が正かどうか判定してください。
制約
- 0 \leq a < d \leq 1000
- 0 \leq b < e \leq 1000
- 0 \leq c < f \leq 1000
- 0 \leq g < j \leq 1000
- 0 \leq h < k \leq 1000
- 0 \leq i < l \leq 1000
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
a b c d e f g h i j k l
出力
2 つの直方体の共通部分の体積が正なら Yes、そうでなければ No を出力せよ。
入力例 1
0 0 0 4 5 6 2 3 4 5 6 7
出力例 1
Yes
2 つの直方体の位置関係は下図のようになっており、共通部分の体積は 8 です。
入力例 2
0 0 0 2 2 2 0 0 2 2 2 4
出力例 2
No
2 つの直方体は面で接していますが、共通部分の体積は 0 です。
入力例 3
0 0 0 1000 1000 1000 10 10 10 100 100 100
出力例 3
Yes
Score : 250 points
Problem Statement
You are trying to implement collision detection in a 3D game.
In a 3-dimensional space, let C(a,b,c,d,e,f) denote the cuboid with a diagonal connecting (a,b,c) and (d,e,f), and with all faces parallel to the xy-plane, yz-plane, or zx-plane.
(This definition uniquely determines C(a,b,c,d,e,f).)
Given two cuboids C(a,b,c,d,e,f) and C(g,h,i,j,k,l), determine whether their intersection has a positive volume.
Constraints
- 0 \leq a < d \leq 1000
- 0 \leq b < e \leq 1000
- 0 \leq c < f \leq 1000
- 0 \leq g < j \leq 1000
- 0 \leq h < k \leq 1000
- 0 \leq i < l \leq 1000
- All input values are integers.
Input
The input is given from Standard Input in the following format:
a b c d e f g h i j k l
Output
Print Yes if the intersection of the two cuboids has a positive volume, and No otherwise.
Sample Input 1
0 0 0 4 5 6 2 3 4 5 6 7
Sample Output 1
Yes
The positional relationship of the two cuboids is shown in the figure below, and their intersection has a volume of 8.
Sample Input 2
0 0 0 2 2 2 0 0 2 2 2 4
Sample Output 2
No
The two cuboids touch at a face, where the volume of the intersection is 0.
Sample Input 3
0 0 0 1000 1000 1000 10 10 10 100 100 100
Sample Output 3
Yes
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 250 点
問題文
長さ N の整数列 A,B が与えられます。1 以上 N 以下の整数 i,j を選んで、 A_i + B_j の値を最大化してください。
制約
- 1 \leq N \leq 5 \times 10^5
- |A_i| \leq 10^9\,(i=1,2,\dots,N)
- |B_j| \leq 10^9\,(j=1,2,\dots,N)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \dots A_N B_1 B_2 \dots B_N
出力
A_i + B_j の最大値を出力せよ。
入力例 1
2 -1 5 3 -7
出力例 1
8
(i,j)=(1,1),(1,2),(2,1),(2,2) に対する A_i+B_j の値はそれぞれ 2,-8,8,-2 であり、(i,j)=(2,1) が最大値 8 を達成します。
入力例 2
6 15 12 3 -13 -1 -19 7 17 -13 -10 18 4
出力例 2
33
Score : 250 points
Problem Statement
You are given two integer sequences A and B, each of length N. Choose integers i, j (1 \leq i, j \leq N) to maximize the value of A_i + B_j.
Constraints
- 1 \leq N \leq 5 \times 10^5
- |A_i| \leq 10^9 (i=1,2,\dots,N)
- |B_j| \leq 10^9 (j=1,2,\dots,N)
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \dots A_N B_1 B_2 \dots B_N
Output
Print the maximum possible value of A_i + B_j.
Sample Input 1
2 -1 5 3 -7
Sample Output 1
8
For (i,j) = (1,1), (1,2), (2,1), (2,2), the values of A_i + B_j are 2, -8, 8, -2 respectively, and (i,j) = (2,1) achieves the maximum value 8.
Sample Input 2
6 15 12 3 -13 -1 -19 7 17 -13 -10 18 4
Sample Output 2
33
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
(1,2,\ldots,N) の並び替えである数列 A=(A_1,\ldots,A_N) が与えられます。
次の操作を 0 回以上 N-1 回以下行うことで、A を (1,2,\ldots,N) にしてください。
- 操作：1\leq i < j \leq N を満たす整数の組 (i,j) を自由に選ぶ。A の i 番目と j 番目の要素を入れ替える。
なお、制約の条件下で必ず A を (1,2,\ldots,N) にできることが証明できます。
制約
- 2 \leq N \leq 2\times 10^5
- (A_1,\ldots,A_N) は (1,2,\ldots,N) の並び替えである
- 入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N A_1 \ldots A_N
出力
操作回数を K として、K+1 行出力せよ。
1 行目には K を出力せよ。
l+1 行目 (1\leq l \leq K) には l 回目の操作で選ぶ整数 i,j を空白区切りで出力せよ。
問題文中の条件を満たすどのような出力も正解とみなされる。
入力例 1
5 3 4 1 2 5
出力例 1
2 1 3 2 4
操作により数列は次のように変化します。
- 最初 A=(3,4,1,2,5) である。
- 1 回目の操作で 1 番目の要素と 3 番目の要素を入れ替える。A=(1,4,3,2,5) になる。
- 2 回目の操作で 2 番目の要素と 4 番目の要素を入れ替える。A=(1,2,3,4,5) になる。
この他、次のような出力でも正解とみなされます。
4 2 3 3 4 1 2 2 3
入力例 2
4 1 2 3 4
出力例 2
0
入力例 3
3 3 1 2
出力例 3
2 1 2 2 3
Score: 300 points
Problem Statement
You are given a permutation A=(A_1,\ldots,A_N) of (1,2,\ldots,N).
Transform A into (1,2,\ldots,N) by performing the following operation between 0 and N-1 times, inclusive:
- Operation: Choose any pair of integers (i,j) such that 1\leq i < j \leq N. Swap the elements at the i-th and j-th positions of A.
It can be proved that under the given constraints, it is always possible to transform A into (1,2,\ldots,N).
Constraints
- 2 \leq N \leq 2\times 10^5
- (A_1,\ldots,A_N) is a permutation of (1,2,\ldots,N).
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A_1 \ldots A_N
Output
Let K be the number of operations. Print K+1 lines.
The first line should contain K.
The (l+1)-th line (1\leq l \leq K) should contain the integers i and j chosen for the l-th operation, separated by a space.
Any output that satisfies the conditions in the problem statement will be considered correct.
Sample Input 1
5 3 4 1 2 5
Sample Output 1
2 1 3 2 4
The operations change the sequence as follows:
- Initially, A=(3,4,1,2,5).
- The first operation swaps the first and third elements, making A=(1,4,3,2,5).
- The second operation swaps the second and fourth elements, making A=(1,2,3,4,5).
Other outputs such as the following are also considered correct:
4 2 3 3 4 1 2 2 3
Sample Input 2
4 1 2 3 4
Sample Output 2
0
Sample Input 3
3 3 1 2
Sample Output 3
2 1 2 2 3
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 425 点
問題文
長さ N の整数列 A=(A _ 1,A _ 2,\ldots,A _ N) が与えられます。 ここで、どの i\ (1\le i\le N) についても A _ i が 0 でないことが保証されます。
A を適切に並べ替えた数列 B=(B _ 1,B _ 2,\ldots,B _ N) が等比数列になることがあるか判定してください。
ただし、数列 S=(S _ 1,S _ 2,\ldots,S _ N) が等比数列であるとは、ある実数 r が存在してすべての整数 1\le i\lt N に対して S _ {i+1}=rS _ i が成り立つことをいいます。
1 つの入力ファイルにつき、T 個のテストケースを解いてください。
制約
- 1\le T\le10 ^ 5
- 2\le N\le2\times10 ^ 5
- -10 ^ 9\le A _ i\le10 ^ 9\ (1\le i\le N)
- A _ i\ne0\ (1\le i\le N)
- 1 つの入力ファイルにおける N の総和は 2\times10 ^ 5 以下
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
T
\mathrm{testcase} _ 1
\mathrm{testcase} _ 2
\vdots
\mathrm{testcase} _ T
ここで、\mathrm{testcase} _ i は i 番目 (1\le i\le T) のテストケースであり、各テストケースは以下の形式で与えられる。
N A _ 1 A _ 2 \ldots A _ N
出力
T 行にわたって出力せよ。
i 行目 (1\le i\le T) には、i 番目のテストケースにおいて A を並べ替えて等比数列にできる場合は Yes を、そうでない場合は No を出力せよ。
入力例 1
3 5 1 8 2 4 16 5 -16 24 54 81 -36 7 90000 8100 -27000 729 -300000 -2430 1000000
出力例 1
Yes No Yes
1 つめのテストケースでは、A を並べ替えた (16,8,4,2,1) は、公比 r=\dfrac12 の等比数列になります。
よって、1 行目には Yes と出力してください。
2 つめのテストケースでは、A をどのように並べ替えても条件を満たしません。
よって、2 行目には No と出力してください。
Score : 425 points
Problem Statement
You are given an integer sequence A=(A_1,A_2,\ldots,A_N) of length N. It is guaranteed that for any i\ (1\le i\le N), A_i is not 0.
Determine whether there exists a permutation B=(B_1,B_2,\ldots,B_N) of A such that B forms a geometric sequence.
A sequence S=(S_1,S_2,\ldots,S_N) is a geometric sequence if there exists a real number r such that S_{i+1}=rS_i for all integers 1\le i\lt N.
Solve T test cases per input file.
Constraints
- 1\le T\le10^5
- 2\le N\le2\times10^5
- -10^9\le A_i\le10^9\ (1\le i\le N)
- A_i\ne0\ (1\le i\le N)
- The sum of N over all test cases in a single input file is at most 2\times10^5.
- All input values are integers.
Input
The input is given from standard input in the following format:
T
\mathrm{testcase}_1
\mathrm{testcase}_2
\vdots
\mathrm{testcase}_T
where \mathrm{testcase}_i is the i-th test case (1\le i\le T), and each test case is given in the following format:
N A_1 A_2 \ldots A_N
Output
Output T lines.
The i-th line (1\le i\le T) should contain Yes if A can be rearranged to form a geometric sequence in the i-th test case, and No otherwise.
Sample Input 1
3 5 1 8 2 4 16 5 -16 24 54 81 -36 7 90000 8100 -27000 729 -300000 -2430 1000000
Sample Output 1
Yes No Yes
In the first test case, the rearrangement (16,8,4,2,1) of A forms a geometric sequence with common ratio r=\frac{1}{2}.
Thus, print Yes on the first line.
In the second test case, no rearrangement of A satisfies the condition.
Thus, print No on the second line.