Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
xy 平面上に長方形があります。この長方形の各辺は x 軸または y 軸に平行であり、面積は 0 ではありません。
この長方形の 4 つの頂点のうち異なる 3 つの頂点の座標 (x_1, y_1), (x_2, y_2), (x_3, y_3) が与えられるので、残る 1 つの頂点の座標を求めてください。
制約
- -100 \leq x_i, y_i \leq 100
- (x_1, y_1), (x_2, y_2), (x_3, y_3) のすべてを頂点に持つ長方形がただ一つ存在し、その各辺は x 軸または y 軸に平行であり、面積は 0 ではない。
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
x_1 y_1 x_2 y_2 x_3 y_3
出力
答えとなる頂点の座標 (x, y) を下記の形式にしたがい空白区切りで出力せよ。
x y
入力例 1
-1 -1 -1 2 3 2
出力例 1
3 -1
(-1, -1), (-1, 2), (3, 2) を頂点とする長方形の残る 1 つの頂点は (3, -1) です。
入力例 2
-60 -40 -60 -80 -20 -80
出力例 2
-20 -40
Score : 100 points
Problem Statement
There is a rectangle in the xy-plane. Each edge of this rectangle is parallel to the x- or y-axis, and its area is not zero.
Given the coordinates of three of the four vertices of this rectangle, (x_1, y_1), (x_2, y_2), and (x_3, y_3), find the coordinates of the other vertex.
Constraints
- -100 \leq x_i, y_i \leq 100
- There uniquely exists a rectangle with all of (x_1, y_1), (x_2, y_2), (x_3, y_3) as vertices, edges parallel to the x- or y-axis, and a non-zero area.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
x_1 y_1 x_2 y_2 x_3 y_3
Output
Print the sought coordinates (x, y) separated by a space in the following format:
x y
Sample Input 1
-1 -1 -1 2 3 2
Sample Output 1
3 -1
The other vertex of the rectangle with vertices (-1, -1), (-1, 2), (3, 2) is (3, -1).
Sample Input 2
-60 -40 -60 -80 -20 -80
Sample Output 2
-20 -40
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 150 点
問題文
英小文字と | のみからなる文字列 S が与えられます。S は | をちょうど 2 個含むことが保証されます。
2 つの | の間にある文字および | を S から削除した文字列を出力してください。
制約
- S は英小文字および
|のみからなる長さ 2 以上 100 以下の文字列 - S は
|をちょうど 2 個含む
入力
入力は以下の形式で標準入力から与えられる。
S
出力
答えを出力せよ。
入力例 1
atcoder|beginner|contest
出力例 1
atcodercontest
2 つの | に挟まれた文字を全て削除して出力してください。
入力例 2
|spoiler|
出力例 2
全ての文字が削除されることもあります。
入力例 3
||xyz
出力例 3
xyz
Score: 150 points
Problem Statement
You are given a string S consisting of lowercase English letters and |. S is guaranteed to contain exactly two |s.
Remove the characters between the two |s, including the |s themselves, and print the resulting string.
Constraints
- S is a string of length between 2 and 100, inclusive, consisting of lowercase English letters and
|. - S contains exactly two
|s.
Input
The input is given from Standard Input in the following format:
S
Output
Print the answer.
Sample Input 1
atcoder|beginner|contest
Sample Output 1
atcodercontest
Remove all the characters between the two |s and print the result.
Sample Input 2
|spoiler|
Sample Output 2
It is possible that all characters are removed.
Sample Input 3
||xyz
Sample Output 3
xyz
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
数字のみからなる長さ 6 の文字列が N 個与えられます。i \, (i = 1, 2, \dots, N) 番目のものを S_i と表します。
さらに、数字のみからなる長さ 3 の文字列が M 個与えられます。j \, (j = 1, 2, \dots, M) 番目のものを T_j と表します。
S_1, S_2, \dots, S_N のうち、末尾 3 文字が T_1, T_2, \dots, T_M のいずれかに一致するものの個数を求めてください。
制約
- 1 \leq N, M \leq 1000
- N, M は整数
- 全ての i = 1, 2, \dots, N に対し、S_i は数字のみからなる長さ 6 の文字列
- 全ての j = 1, 2, \dots, M に対し、T_j は数字のみからなる長さ 3 の文字列
入力
入力は以下の形式で標準入力から与えられる。
N M S_1 S_2 \vdots S_N T_1 T_2 \vdots T_M
出力
答えを出力せよ。
入力例 1
3 3 142857 004159 071028 159 287 857
出力例 1
2
S_1 の末尾 3 文字は 857 であり、これは T_3 に一致します。
S_2 の末尾 3 文字は 159 であり、これは T_1 に一致します。
S_3 の末尾 3 文字は 028 であり、これは T_1, T_2, T_3 のいずれにも一致しません。
以上から、答えは 2 です。
入力例 2
5 4 235983 109467 823476 592801 000333 333 108 467 983
出力例 2
3
入力例 3
4 4 000000 123456 987111 000000 000 111 999 111
出力例 3
3
Score : 200 points
Problem Statement
You are given N strings of length six each, consisting of digits. Let S_i be the i-th (i = 1, 2, \dots, N) of them.
You are also given M strings of length three each, consisting of digits. Let T_j be the j-th (j = 1, 2, \dots, M) of them.
Find the number of strings among S_1, S_2, \dots, S_N whose last three characters coincide with one or more of T_1, T_2, \dots, T_M.
Constraints
- 1 \leq N, M \leq 1000
- N and M are integers.
- S_i is a string of length 6 consisting of digits, for all i = 1, 2, \dots, N.
- T_j is a string of length 3 consisting of digits, for all j = 1, 2, \dots, M.
Input
The input is given from Standard Input in the following format:
N M S_1 S_2 \vdots S_N T_1 T_2 \vdots T_M
Output
Print the answer.
Sample Input 1
3 3 142857 004159 071028 159 287 857
Sample Output 1
2
The last three characters of S_1 are 857, which coincide with T_3.
The last three characters of S_2 are 159, which coincide with T_1.
The last three characters of S_3 are 028, which do not coincide with T_1, T_2, or T_3.
Thus, the answer is 2.
Sample Input 2
5 4 235983 109467 823476 592801 000333 333 108 467 983
Sample Output 2
3
Sample Input 3
4 4 000000 123456 987111 000000 000 111 999 111
Sample Output 3
3
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
高橋くんは、以下の方法で 10 個の文字列 S_1,S_2,\dots,S_{10} を生成しました。
- まず、 S_i (1 \le i \le 10)=
..........(.が 10 個並んだ文字列) とする。 - 次に、以下の条件を全て満たす 4 つの整数 A,B,C,D を選ぶ。
- 1 \le A \le B \le 10
- 1 \le C \le D \le 10
- その後、以下の条件を全て満たす全ての整数組 (i,j) について、 S_i の j 文字目を
#に書き換える。- A \le i \le B
- C \le j \le D
以上の方法で生成された S_1,S_2,\dots,S_{10} が与えられるので、高橋くんが選んだ整数 A,B,C,D を求めてください。
なお、制約より A,B,C,D は一意に定まる (答えはただひとつ存在する) ことが証明できます。
制約
- S_1,S_2,\dots,S_{10} は問題文中の方法で生成されうるそれぞれ長さ 10 の文字列
入力
入力は以下の形式で標準入力から与えられる。
S_1
S_2
\vdots
S_{10}
出力
答えを以下の形式で出力せよ。
A B C D
入力例 1
.......... .......... .......... .......... ...######. ...######. ...######. ...######. .......... ..........
出力例 1
5 8 4 9
高橋くんが選んだ整数は A=5,B=8,C=4,D=9 です。
このように選ぶことにより、 S_5,S_6,S_7,S_8 の 4 文字目から 9 文字目が # であり他の文字が . である 10 個の長さ 10 の文字列 S_1,S_2,\dots,S_{10} が生成されます。
これは入力で与えられた 10 個の文字列と一致します。
入力例 2
.......... ..#....... .......... .......... .......... .......... .......... .......... .......... ..........
出力例 2
2 2 3 3
入力例 3
########## ########## ########## ########## ########## ########## ########## ########## ########## ##########
出力例 3
1 10 1 10
Score : 200 points
Problem Statement
Takahashi generated 10 strings S_1,S_2,\dots,S_{10} as follows.
- First, let S_i (1 \le i \le 10)=
..........(10.s in a row). - Next, choose four integers A, B, C, and D satisfying all of the following.
- 1 \le A \le B \le 10.
- 1 \le C \le D \le 10.
- Then, for every pair of integers (i,j) satisfying all of the following, replace the j-th character of S_i with
#.- A \le i \le B.
- C \le j \le D.
You are given S_1,S_2,\dots,S_{10} generated as above. Find the integers A, B, C, and D Takahashi chose.
It can be proved that such integers A, B, C, and D uniquely exist (there is just one answer) under the Constraints.
Constraints
- S_1,S_2,\dots,S_{10} are strings, each of length 10, that can be generated according to the Problem Statement.
Input
The input is given from Standard Input in the following format:
S_1
S_2
\vdots
S_{10}
Output
Print the answer in the following format:
A B C D
Sample Input 1
.......... .......... .......... .......... ...######. ...######. ...######. ...######. .......... ..........
Sample Output 1
5 8 4 9
Here, Takahashi chose A=5, B=8, C=4, D=9.
This choice generates 10 strings S_1,S_2,\dots,S_{10}, each of length 10, where the 4-th through 9-th characters of S_5,S_6,S_7,S_8 are #, and the other characters are ..
These are equal to the strings given in the input.
Sample Input 2
.......... ..#....... .......... .......... .......... .......... .......... .......... .......... ..........
Sample Output 2
2 2 3 3
Sample Input 3
########## ########## ########## ########## ########## ########## ########## ########## ########## ##########
Sample Output 3
1 10 1 10
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
1, 2, \ldots, N の番号がついた N 人の人が二次元平面上におり、人 i は座標 (X_i,Y_i) で表される地点にいます。
人 1 がウイルスに感染しました。ウイルスに感染した人から距離が D 以内にいる人にウイルスはうつります。
ただし、距離はユークリッド距離、すなわち 2 点 (a_1, a_2) と (b_1, b_2) に対し、この 2 点間の距離が \sqrt {(a_1-b_1)^2 + (a_2-b_2)^2} であるものとして定められています。
十分に時間が経過した、すなわち人 i がウイルスに感染しているならば 人 i との距離が D 以内にいるすべての人がウイルスに感染している状態になったときに、各 i について人 i がウイルスに感染しているか判定してください。
制約
- 1 \leq N, D \leq 2000
- -1000 \leq X_i, Y_i \leq 1000
- i \neq j のとき (X_i, Y_i) \neq (X_j, Y_j)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N D X_1 Y_1 X_2 Y_2 \vdots X_N Y_N
出力
N 行出力せよ。i 行目には、人 i がウイルスに感染しているならば Yes を、そうでないならば No を出力せよ。
入力例 1
4 5 2 -1 3 1 8 8 0 5
出力例 1
Yes Yes No Yes
人 1 と人 2 の距離は \sqrt 5 であるため、人 2 はウイルスに感染します。
また、人 2 と人 4 の距離は 5 であるため、人 4 はウイルスに感染します。
人 3 は距離 5 以内に人がいないので、ウイルスに感染することはありません。
入力例 2
3 1 0 0 -1000 -1000 1000 1000
出力例 2
Yes No No
入力例 3
9 4 3 2 6 -1 1 6 6 5 -2 -3 5 3 2 -3 2 1 2 6
出力例 3
Yes No No Yes Yes Yes Yes Yes No
Score : 300 points
Problem Statement
There are N people numbered 1, 2, \ldots, N on a two-dimensional plane, and person i is at the point represented by the coordinates (X_i,Y_i).
Person 1 has been infected with a virus. The virus spreads to people within a distance of D from an infected person.
Here, the distance is defined as the Euclidean distance, that is, for two points (a_1, a_2) and (b_1, b_2), the distance between these two points is \sqrt {(a_1-b_1)^2 + (a_2-b_2)^2}.
After a sufficient amount of time has passed, that is, when all people within a distance of D from person i are infected with the virus if person i is infected, determine whether person i is infected with the virus for each i.
Constraints
- 1 \leq N, D \leq 2000
- -1000 \leq X_i, Y_i \leq 1000
- (X_i, Y_i) \neq (X_j, Y_j) if i \neq j.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N D X_1 Y_1 X_2 Y_2 \vdots X_N Y_N
Output
Print N lines. The i-th line should contain Yes if person i is infected with the virus, and No otherwise.
Sample Input 1
4 5 2 -1 3 1 8 8 0 5
Sample Output 1
Yes Yes No Yes
The distance between person 1 and person 2 is \sqrt 5, so person 2 gets infected with the virus.
Also, the distance between person 2 and person 4 is 5, so person 4 gets infected with the virus.
Person 3 has no one within a distance of 5, so they will not be infected with the virus.
Sample Input 2
3 1 0 0 -1000 -1000 1000 1000
Sample Output 2
Yes No No
Sample Input 3
9 4 3 2 6 -1 1 6 6 5 -2 -3 5 3 2 -3 2 1 2 6
Sample Output 3
Yes No No Yes Yes Yes Yes Yes No