Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
0 以上 1 以下の整数 x が与えられます。 x が 0 なら 1 を、1 なら 0 を出力してください。
制約
- 0 \leq x \leq 1
- x は整数
入力
入力は以下の形式で標準入力から与えられる。
x
出力
x が 0 なら 1 を、1 なら 0 を出力してください。
入力例 1
1
出力例 1
0
入力例 2
0
出力例 2
1
Score : 100 points
Problem Statement
Given is an integer x that is greater than or equal to 0, and less than or equal to 1. Output 1 if x is equal to 0, or 0 if x is equal to 1.
Constraints
- 0 \leq x \leq 1
- x is an integer
Input
Input is given from Standard Input in the following format:
x
Output
Print 1 if x is equal to 0, or 0 if x is equal to 1.
Sample Input 1
1
Sample Output 1
0
Sample Input 2
0
Sample Output 2
1
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
整数 a,b,c,d が与えられます。 a \leq x \leq b, c\leq y \leq d を満たす整数 x,y について、x \times y の最大値はいくつですか。
制約
- -10^9 \leq a \leq b \leq 10^9
- -10^9 \leq c \leq d \leq 10^9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
a b c d
出力
答えを出力せよ。
入力例 1
1 2 1 1
出力例 1
2
x=1,y=1 のとき x \times y=1、x=2,y=1 のとき x \times y=2 であるため、答えは 2 です。
入力例 2
3 5 -4 -2
出力例 2
-6
答えが負になることもあります。
入力例 3
-1000000000 0 -1000000000 0
出力例 3
1000000000000000000
Score : 200 points
Problem Statement
Given are integers a,b,c and d. If x and y are integers and a \leq x \leq b and c\leq y \leq d hold, what is the maximum possible value of x \times y?
Constraints
- -10^9 \leq a \leq b \leq 10^9
- -10^9 \leq c \leq d \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
a b c d
Output
Print the answer.
Sample Input 1
1 2 1 1
Sample Output 1
2
If x = 1 and y = 1 then x \times y = 1. If x = 2 and y = 1 then x \times y = 2. Therefore, the answer is 2.
Sample Input 2
3 5 -4 -2
Sample Output 2
-6
The answer can be negative.
Sample Input 3
-1000000000 0 -1000000000 0
Sample Output 3
1000000000000000000
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
長さ N の整数の列 A_1,A_2,\ldots,A_N であって以下の条件をすべて満たすものはいくつありますか。
- 0 \leq A_i \leq 9
- A_i=0 なる i が存在する。
- A_i=9 なる i が存在する。
ただし、答えはとても大きくなる可能性があるので、10^9+7 で割った余りを出力してください。
制約
- 1 \leq N \leq 10^6
- N は整数
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを10^9+7 で割った余りを出力せよ。
入力例 1
2
出力例 1
2
数列\{0,9\},\{9,0\}の 2 つが条件をすべて満たします。
入力例 2
1
出力例 2
0
入力例 3
869121
出力例 3
2511445
Score : 300 points
Problem Statement
How many integer sequences A_1,A_2,\ldots,A_N of length N satisfy all of the following conditions?
- 0 \leq A_i \leq 9
- There exists some i such that A_i=0 holds.
- There exists some i such that A_i=9 holds.
The answer can be very large, so output it modulo 10^9 + 7.
Constraints
- 1 \leq N \leq 10^6
- N is an integer.
Input
Input is given from Standard Input in the following format:
N
Output
Print the answer modulo 10^9 + 7.
Sample Input 1
2
Sample Output 1
2
Two sequences \{0,9\} and \{9,0\} satisfy all conditions.
Sample Input 2
1
Sample Output 2
0
Sample Input 3
869121
Sample Output 3
2511445
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
整数 S が与えられます。 すべての項が 3 以上の整数で、その総和が S であるような数列がいくつあるか求めてください。ただし、答えは非常に大きくなる可能性があるので、 10^9+7 で割った余りを出力してください。
制約
- 1 \leq S \leq 2000
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
S
出力
答えを出力せよ。
入力例 1
7
出力例 1
3
数列 \{3,4\},\{4,3\},\{7\} の 3 つが条件を満たします。
入力例 2
2
出力例 2
0
条件を満たす数列は存在しません。
入力例 3
1729
出力例 3
294867501
Score : 400 points
Problem Statement
Given is an integer S. Find how many sequences there are whose terms are all integers greater than or equal to 3, and whose sum is equal to S. The answer can be very large, so output it modulo 10^9 + 7.
Constraints
- 1 \leq S \leq 2000
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
S
Output
Print the answer.
Sample Input 1
7
Sample Output 1
3
3 sequences satisfy the condition: \{3,4\}, \{4,3\} and \{7\}.
Sample Input 2
2
Sample Output 2
0
There are no sequences that satisfy the condition.
Sample Input 3
1729
Sample Output 3
294867501
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
二次元平面上に N 個の点があり、i 番目の点の座標は (x_i,y_i) です。 同じ座標に複数の点があることもあります。 異なる二点間のマンハッタン距離として考えられる最大の値はいくつでしょうか。
ただし、二点 (x_i,y_i) と (x_j,y_j) のマンハッタン距離は |x_i-x_j|+|y_i-y_j| のことをいいます。
制約
- 2 \leq N \leq 2 \times 10^5
- 1 \leq x_i,y_i \leq 10^9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N x_1 y_1 x_2 y_2 : x_N y_N
出力
答えを出力せよ。
入力例 1
3 1 1 2 4 3 2
出力例 1
4
1 番目の点と 2 番目の点のマンハッタン距離は |1-2|+|1-4|=4 で、これが最大です。
入力例 2
2 1 1 1 1
出力例 2
0
Score : 500 points
Problem Statement
There are N points on the 2D plane, i-th of which is located on (x_i, y_i). There can be multiple points that share the same coordinate. What is the maximum possible Manhattan distance between two distinct points?
Here, the Manhattan distance between two points (x_i, y_i) and (x_j, y_j) is defined by |x_i-x_j| + |y_i-y_j|.
Constraints
- 2 \leq N \leq 2 \times 10^5
- 1 \leq x_i,y_i \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N x_1 y_1 x_2 y_2 : x_N y_N
Output
Print the answer.
Sample Input 1
3 1 1 2 4 3 2
Sample Output 1
4
The Manhattan distance between the first point and the second point is |1-2|+|1-4|=4, which is maximum possible.
Sample Input 2
2 1 1 1 1
Sample Output 2
0
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
長さ N の数列 A と B が与えられます。 A,B はそれぞれ昇順にソートされています。 B を好きに並べ替えてすべての i(1 \leq i \leq N) について A_i \neq B_i を満たすようにできるか判定し、できるならそのような B の並べ替え方を一つ示してください。
制約
- 1\leq N \leq 2 \times 10^5
- 1\leq A_i,B_i \leq N
- A,B はそれぞれ昇順にソートされている。
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \cdots A_N B_1 B_2 \cdots B_N
出力
条件を満たす並べ替え方が存在しない場合 No と出力せよ。
条件を満たす並べ替え方が存在する場合、一行目に Yes を出力し、二行目に並べ替え方を出力せよ。
二行目には並び替えた後の B を空白区切りで出力せよ。
条件を満たす並べ替え方が複数存在する場合、そのうちどれを出力しても構わない。
入力例 1
6 1 1 1 2 2 3 1 1 1 2 2 3
出力例 1
Yes 2 2 3 1 1 1
入力例 2
3 1 1 2 1 1 3
出力例 2
No
入力例 3
4 1 1 2 3 1 2 3 3
出力例 3
Yes 3 3 1 2
Score : 600 points
Problem Statement
Given are two sequences A and B, both of length N. A and B are each sorted in the ascending order. Check if it is possible to reorder the terms of B so that for each i (1 \leq i \leq N) A_i \neq B_i holds, and if it is possible, output any of the reorderings that achieve it.
Constraints
- 1\leq N \leq 2 \times 10^5
- 1\leq A_i,B_i \leq N
- A and B are each sorted in the ascending order.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A_1 A_2 \cdots A_N B_1 B_2 \cdots B_N
Output
If there exist no reorderings that satisfy the condition, print No.
If there exists a reordering that satisfies the condition, print Yes on the first line.
After that, print a reordering of B on the second line, separating terms with a whitespace.
If there are multiple reorderings that satisfy the condition, you can print any of them.
Sample Input 1
6 1 1 1 2 2 3 1 1 1 2 2 3
Sample Output 1
Yes 2 2 3 1 1 1
Sample Input 2
3 1 1 2 1 1 3
Sample Output 2
No
Sample Input 3
4 1 1 2 3 1 2 3 3
Sample Output 3
Yes 3 3 1 2