Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
空でない文字列に対し、先頭の文字を末尾に移動する操作を左シフト、末尾の文字を先頭に移動する操作を右シフトと呼びます。
例えば、abcde に対して左シフトを 1 回行うと bcdea となり、右シフトを 2 回行うと deabc となります。
英小文字からなる空でない文字列 S が与えられます。S に対し左シフトと右シフトをそれぞれ好きな回数（0 回でもよい）行って得られる文字列のうち、辞書順で最小のものと最大のものを求めてください。
辞書順とは？
辞書順とは簡単に説明すると「単語が辞書に載っている順番」を意味します。より厳密な説明として、英小文字からなる相異なる文字列 S, T の大小を判定するアルゴリズムを以下に説明します。
以下では「 S の i 文字目の文字」を S_i のように表します。また、 S が T より辞書順で小さい場合は S \lt T 、大きい場合は S \gt T と表します。
- S, T のうち長さが大きくない方の文字列の長さを L とします。i=1,2,\dots,L に対して S_i と T_i が一致するか調べます。
- S_i \neq T_i である i が存在する場合、そのような i のうち最小のものを j とします。そして、S_j と T_j を比較して、S_j が T_j よりアルファベット順で小さい場合は S \lt T 、そうでない場合は S \gt T と決定して、アルゴリズムを終了します。
- S_i \neq T_i である i が存在しない場合、S と T の長さを比較して、S が T より短い場合は S \lt T 、長い場合は S \gt T と決定して、アルゴリズムを終了します。
制約
- S は英小文字からなる。
- S の長さは 1 以上 1000 以下である。
入力
入力は以下の形式で標準入力から与えられる。
S
出力
2 行にわたって出力せよ。S に対し左シフトと右シフトをそれぞれ好きな回数（0 回でもよい）行って得られる文字列のうち、辞書順で最小のものと最大のものをそれぞれ S_{\min}, S_{\max} とおいたとき、1 行目には S_{\min} を、2 行目には S_{\max} を出力せよ。
入力例 1
aaba
出力例 1
aaab baaa
操作によって、aaab , aaba , abaa , baaa の 4 通りの文字列を得ることができます。
これらのうち辞書順で最小、最大のものはそれぞれ aaab , baaa です。
入力例 2
z
出力例 2
z z
どのように操作を行っても、得られる文字列は z のみです。
入力例 3
abracadabra
出力例 3
aabracadabr racadabraab
Score : 200 points
Problem Statement
On a non-empty string, a left shift moves the first character to the end of the string, and a right shift moves the last character to the beginning of the string.
For example, a left shift on abcde results in bcdea, and two right shifts on abcde result in deabc.
You are given a non-empty S consisting of lowercase English letters. Among the strings that can be obtained by performing zero or more left shifts and zero or more right shifts on S, find the lexicographically smallest string and the lexicographically largest string.
What is the lexicographical order?
Simply speaking, the lexicographical order is the order in which words are listed in a dictionary. As a more formal definition, here is the algorithm to determine the lexicographical order between different strings S and T.
Below, let S_i denote the i-th character of S. Also, if S is lexicographically smaller than T, we will denote that fact as S \lt T; if S is lexicographically larger than T, we will denote that fact as S \gt T.
- Let L be the smaller of the lengths of S and T. For each i=1,2,\dots,L, we check whether S_i and T_i are the same.
- If there is an i such that S_i \neq T_i, let j be the smallest such i. Then, we compare S_j and T_j. If S_j comes earlier than T_j in alphabetical order, we determine that S \lt T and quit; if S_j comes later than T_j, we determine that S \gt T and quit.
- If there is no i such that S_i \neq T_i, we compare the lengths of S and T. If S is shorter than T, we determine that S \lt T and quit; if S is longer than T, we determine that S \gt T and quit.
Constraints
- S consists of lowercase English letters.
- The length of S is between 1 and 1000 (inclusive).
Input
Input is given from Standard Input in the following format:
S
Output
Print two lines. The first line should contain S_{\min}, and the second line should contain S_{\max}. Here, S_{\min} and S_{\max} are respectively the lexicographically smallest and largest strings obtained by performing zero or more left shifts and zero or more right shifts on S.
Sample Input 1
aaba
Sample Output 1
aaab baaa
By performing shifts, we can obtain four strings: aaab, aaba, abaa, baaa. The lexicographically smallest and largest among them are aaab and baaa, respectively.
Sample Input 2
z
Sample Output 2
z z
Any sequence of operations results in z.
Sample Input 3
abracadabra
Sample Output 3
aabracadabr racadabraab
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
縦 H 行、横 W 列のマス目があり、各マスには 1 つの整数が書かれています。 上から i 行目、左から j 列目のマスに書かれている整数は A_{i, j} です。
マス目が下記の条件を満たすかどうかを判定してください。
1 \leq i_1 < i_2 \leq H および 1 \leq j_1 < j_2 \leq W を満たすすべての整数の組 (i_1, i_2, j_1, j_2) について、A_{i_1, j_1} + A_{i_2, j_2} \leq A_{i_2, j_1} + A_{i_1, j_2} が成り立つ。
制約
- 2 \leq H, W \leq 50
- 1 \leq A_{i, j} \leq 10^9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
H W
A_{1, 1} A_{1, 2} \cdots A_{1, W}
A_{2, 1} A_{2, 2} \cdots A_{2, W}
\vdots
A_{H, 1} A_{H, 2} \cdots A_{H, W}
出力
マス目が問題文中の条件を満たす場合は Yes と出力し、条件を満たさない場合は No と出力せよ。
入力例 1
3 3 2 1 4 3 1 3 6 4 1
出力例 1
Yes
1 \leq i_1 < i_2 \leq H および 1 \leq j_1 < j_2 \leq W を満たす整数の組 (i_1, i_2, j_1, j_2) は 9 個存在し、それらすべてについて A_{i_1, j_1} + A_{i_2, j_2} \leq A_{i_2, j_1} + A_{i_1, j_2} が成り立ちます。例えば、
- (i_1, i_2, j_1, j_2) = (1, 2, 1, 2) について、A_{i_1, j_1} + A_{i_2, j_2} = 2 + 1 \leq 3 + 1 = A_{i_2, j_1} + A_{i_1, j_2}
- (i_1, i_2, j_1, j_2) = (1, 2, 1, 3) について、A_{i_1, j_1} + A_{i_2, j_2} = 2 + 3 \leq 3 + 4 = A_{i_2, j_1} + A_{i_1, j_2}
- (i_1, i_2, j_1, j_2) = (1, 2, 2, 3) について、A_{i_1, j_1} + A_{i_2, j_2} = 1 + 3 \leq 1 + 4 = A_{i_2, j_1} + A_{i_1, j_2}
- (i_1, i_2, j_1, j_2) = (1, 3, 1, 2) について、A_{i_1, j_1} + A_{i_2, j_2} = 2 + 4 \leq 6 + 1 = A_{i_2, j_1} + A_{i_1, j_2}
- (i_1, i_2, j_1, j_2) = (1, 3, 1, 3) について、A_{i_1, j_1} + A_{i_2, j_2} = 2 + 1 \leq 6 + 4 = A_{i_2, j_1} + A_{i_1, j_2}
が成り立ちます。残りの (i_1, i_2, j_1, j_2) = (1, 3, 2, 3), (2, 3, 1, 2), (2, 3, 1, 3), (2, 3, 2, 3) についても同様に確認できます。
よって、Yes を出力します。
入力例 2
2 4 4 3 2 1 5 6 7 8
出力例 2
No
問題文中の条件を満たさないので、No を出力します。
例えば、(i_1, i_2, j_1, j_2) = (1, 2, 1, 4) について、A_{i_1, j_1} + A_{i_2, j_2} = 4 + 8 > 5 + 1 = A_{i_2, j_1} + A_{i_1, j_2} です。
Score : 200 points
Problem Statement
We have a grid with H horizontal rows and W vertical columns, where each square contains an integer. The integer written on the square at the i-th row from the top and j-th column from the left is A_{i, j}.
Determine whether the grid satisfies the condition below.
A_{i_1, j_1} + A_{i_2, j_2} \leq A_{i_2, j_1} + A_{i_1, j_2} holds for every quadruple of integers (i_1, i_2, j_1, j_2) such that 1 \leq i_1 < i_2 \leq H and 1 \leq j_1 < j_2 \leq W.
Constraints
- 2 \leq H, W \leq 50
- 1 \leq A_{i, j} \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
H W
A_{1, 1} A_{1, 2} \cdots A_{1, W}
A_{2, 1} A_{2, 2} \cdots A_{2, W}
\vdots
A_{H, 1} A_{H, 2} \cdots A_{H, W}
Output
If the grid satisfies the condition in the Problem Statement, print Yes; otherwise, print No.
Sample Input 1
3 3 2 1 4 3 1 3 6 4 1
Sample Output 1
Yes
There are nine quadruples of integers (i_1, i_2, j_1, j_2) such that 1 \leq i_1 < i_2 \leq H and 1 \leq j_1 < j_2 \leq W. For all of them, A_{i_1, j_1} + A_{i_2, j_2} \leq A_{i_2, j_1} + A_{i_1, j_2} holds. Some examples follow.
- For (i_1, i_2, j_1, j_2) = (1, 2, 1, 2), we have A_{i_1, j_1} + A_{i_2, j_2} = 2 + 1 \leq 3 + 1 = A_{i_2, j_1} + A_{i_1, j_2}.
- For (i_1, i_2, j_1, j_2) = (1, 2, 1, 3), we have A_{i_1, j_1} + A_{i_2, j_2} = 2 + 3 \leq 3 + 4 = A_{i_2, j_1} + A_{i_1, j_2}.
- For (i_1, i_2, j_1, j_2) = (1, 2, 2, 3), we have A_{i_1, j_1} + A_{i_2, j_2} = 1 + 3 \leq 1 + 4 = A_{i_2, j_1} + A_{i_1, j_2}.
- For (i_1, i_2, j_1, j_2) = (1, 3, 1, 2), we have A_{i_1, j_1} + A_{i_2, j_2} = 2 + 4 \leq 6 + 1 = A_{i_2, j_1} + A_{i_1, j_2}.
- For (i_1, i_2, j_1, j_2) = (1, 3, 1, 3), we have A_{i_1, j_1} + A_{i_2, j_2} = 2 + 1 \leq 6 + 4 = A_{i_2, j_1} + A_{i_1, j_2}.
We can also see that the property holds for the other quadruples: (i_1, i_2, j_1, j_2) = (1, 3, 2, 3), (2, 3, 1, 2), (2, 3, 1, 3), (2, 3, 2, 3).
Thus, we should print Yes.
Sample Input 2
2 4 4 3 2 1 5 6 7 8
Sample Output 2
No
We should print No because the condition is not satisfied.
This is because, for example, we have A_{i_1, j_1} + A_{i_2, j_2} = 4 + 8 > 5 + 1 = A_{i_2, j_1} + A_{i_1, j_2} for (i_1, i_2, j_1, j_2) = (1, 2, 1, 4).
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
正整数 D が与えられます。
非負整数 x,y に対する |x^2+y^2-D| の最小値を求めてください。
制約
- 1\leq D \leq 2\times 10^{12}
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
D
出力
答えを出力せよ。
入力例 1
21
出力例 1
1
x=4,y=2 のとき |x^2+y^2-D| = |16+4-21|=1 となります。
|x^2+y^2-D|=0 を満たすような非負整数 x,y は存在しないので、答えは 1 です。
入力例 2
998244353
出力例 2
0
入力例 3
264428617
出力例 3
32
Score : 300 points
Problem Statement
You are given a positive integer D.
Find the minimum value of |x^2+y^2-D| for non-negative integers x and y.
Constraints
- 1\leq D \leq 2\times 10^{12}
- All input values are integers.
Input
The input is given from Standard Input in the following format:
D
Output
Print the answer.
Sample Input 1
21
Sample Output 1
1
For x=4 and y=2, we have |x^2+y^2-D| = |16+4-21|=1.
There are no non-negative integers x and y such that |x^2+y^2-D|=0, so the answer is 1.
Sample Input 2
998244353
Sample Output 2
0
Sample Input 3
264428617
Sample Output 3
32
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 250 点
問題文
9\times 9 のマス目 A があり、各マスには 1 以上 9 以下の整数が書き込まれています。
具体的には、 A の上から i 行目、左から j 列目のマスには A_{i,j} が書き込まれています。
A が次の条件をすべてみたしているならば Yes を、そうでないならば No を出力してください。
- A の各行について、その行に含まれる 9 マスには 1 以上 9 以下の整数がちょうど 1 個ずつ書き込まれている。
- A の各列について、その列に含まれる 9 マスには 1 以上 9 以下の整数がちょうど 1 個ずつ書き込まれている。
- A の行を上から 3 行ずつ 3 つに分け、同様に列も左から 3 列ずつ 3 つに分ける。 これによって A を 9 つの 3\times 3 のマス目に分けたとき、それぞれの 3\times 3 のマス目には 1 以上 9 以下の整数がちょうど 1 個ずつ書き込まれている。
制約
- 1\leq A_{i,j}\leq 9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
A_{1,1} A_{1,2} \ldots A_{1,9}
A_{2,1} A_{2,2} \ldots A_{2,9}
\vdots
A_{9,1} A_{9,2} \ldots A_{9,9}
出力
マス目 A が問題文の条件をすべてみたすならば Yes を、
そうでないならば No を出力せよ。
入力例 1
1 2 3 4 5 6 7 8 9 4 5 6 7 8 9 1 2 3 7 8 9 1 2 3 4 5 6 2 3 4 5 6 7 8 9 1 5 6 7 8 9 1 2 3 4 8 9 1 2 3 4 5 6 7 3 4 5 6 7 8 9 1 2 6 7 8 9 1 2 3 4 5 9 1 2 3 4 5 6 7 8
出力例 1
Yes
マス目 A は次のようになっています。
マス目 A は 3 つの条件をすべてみたしているため、Yes を出力します。
入力例 2
1 2 3 4 5 6 7 8 9 2 3 4 5 6 7 8 9 1 3 4 5 6 7 8 9 1 2 4 5 6 7 8 9 1 2 3 5 6 7 8 9 1 2 3 4 6 7 8 9 1 2 3 4 5 7 8 9 1 2 3 4 5 6 8 9 1 2 3 4 5 6 7 9 1 2 3 4 5 6 7 8
出力例 2
No
マス目 A は次のようになっています。
例えば左上の 3\times 3 のマス目に注目すると 3 つめの条件をみたしていないことが分かるため、No を出力します。
入力例 3
1 2 3 4 5 6 7 8 9 4 5 6 7 8 9 1 2 3 7 8 9 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 4 5 6 7 8 9 1 2 3 7 8 9 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 4 5 6 7 8 9 1 2 3 7 8 9 1 2 3 4 5 6
出力例 3
No
マス目 A は次のようになっています。
例えば一番左の列に注目すると 2 つめの条件をみたしていないことが分かるため、No を出力します。
Score : 250 points
Problem Statement
There is a 9\times 9 grid A, where each cell contains an integer between 1 and 9, inclusive.
Specifically, the cell at the i-th row from the top and j-th column from the left contains A_{i,j}.
If A satisfies all of the following conditions, print Yes. Otherwise, print No.
- For each row of A, the nine cells in that row contain each integer from 1 to 9 exactly once.
- For each column of A, the nine cells in that column contain each integer from 1 to 9 exactly once.
- Divide the rows of A into three groups, each of three rows, from top to bottom, and similarly divide the columns into three groups, each of three columns, from left to right. Each 3\times 3 grid obtained from A in this way contains each integer from 1 to 9 exactly once.
Constraints
- 1\leq A_{i,j}\leq 9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
A_{1,1} A_{1,2} \ldots A_{1,9}
A_{2,1} A_{2,2} \ldots A_{2,9}
\vdots
A_{9,1} A_{9,2} \ldots A_{9,9}
Output
If the grid A satisfies all the conditions in the problem statement, print Yes; otherwise, print No.
Sample Input 1
1 2 3 4 5 6 7 8 9 4 5 6 7 8 9 1 2 3 7 8 9 1 2 3 4 5 6 2 3 4 5 6 7 8 9 1 5 6 7 8 9 1 2 3 4 8 9 1 2 3 4 5 6 7 3 4 5 6 7 8 9 1 2 6 7 8 9 1 2 3 4 5 9 1 2 3 4 5 6 7 8
Sample Output 1
Yes
The grid A is shown below.
The grid A satisfies all three conditions, so print Yes.
Sample Input 2
1 2 3 4 5 6 7 8 9 2 3 4 5 6 7 8 9 1 3 4 5 6 7 8 9 1 2 4 5 6 7 8 9 1 2 3 5 6 7 8 9 1 2 3 4 6 7 8 9 1 2 3 4 5 7 8 9 1 2 3 4 5 6 8 9 1 2 3 4 5 6 7 9 1 2 3 4 5 6 7 8
Sample Output 2
No
The grid A is shown below.
For example, if you look at the top left 3\times 3 grid, you can see that the third condition is unsatisfied, so print No.
Sample Input 3
1 2 3 4 5 6 7 8 9 4 5 6 7 8 9 1 2 3 7 8 9 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 4 5 6 7 8 9 1 2 3 7 8 9 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 4 5 6 7 8 9 1 2 3 7 8 9 1 2 3 4 5 6
Sample Output 3
No
The grid A is shown below.
For example, if you look at the leftmost column, you can see that the second condition is unsatisfied, so print No.
Time Limit: 4 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
2 次元平面上に N 個の相異なる点があり、1,2,\ldots ,N の番号がついています。点 i\,(1 \leq i \leq N) の座標は (x_i,y_i) です。
これらの点のうち 4 つを頂点とし、全ての辺が x 軸または y 軸に平行であるような長方形はいくつありますか？
制約
- 4 \leq N \leq 2000
- 0 \leq x_i, y_i \leq 10^9
- (x_i,y_i) \neq (x_j,y_j) (i \neq j)
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
N x_1 y_1 x_2 y_2 \vdots x_N y_N
出力
答えを出力せよ。
入力例 1
6 0 0 0 1 1 0 1 1 2 0 2 1
出力例 1
3
点 1 、点 2 、点 3 、点 4 を頂点とする長方形、
点 1 、点 2 、点 5 、点 6 を頂点とする長方形、
点 3 、点 4 、点 5 、点 6 を頂点とする長方形
の合計 3 つです。
入力例 2
4 0 1 1 2 2 3 3 4
出力例 2
0
入力例 3
7 0 1 1 0 2 0 2 1 2 2 3 0 3 2
出力例 3
1
Score : 400 points
Problem Statement
We have N distinct points on a two-dimensional plane, numbered 1,2,\ldots,N. Point i (1 \leq i \leq N) has the coordinates (x_i,y_i).
How many rectangles are there whose vertices are among the given points and whose edges are parallel to the x- or y-axis?
Constraints
- 4 \leq N \leq 2000
- 0 \leq x_i, y_i \leq 10^9
- (x_i,y_i) \neq (x_j,y_j) (i \neq j)
- 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 \vdots x_N y_N
Output
Print the answer.
Sample Input 1
6 0 0 0 1 1 0 1 1 2 0 2 1
Sample Output 1
3
There are three such rectangles:
the rectangle whose vertices are Points 1, 2, 3, 4,
the rectangle whose vertices are Points 1, 2, 5, 6,
and the rectangle whose vertices are Points 3, 4, 5, 6.
Sample Input 2
4 0 1 1 2 2 3 3 4
Sample Output 2
0
Sample Input 3
7 0 1 1 0 2 0 2 1 2 2 3 0 3 2
Sample Output 3
1