Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
xy 平面上に N 人の人 1,2,\dots,N がおり、人 i は座標 (X_i,Y_i) にいます。
このうち、 K 人の人 A_1,A_2,\dots,A_K に同じ強さの明かりを持たせます。
座標 (x,y) にいる人が強さ R の明かりを持っている時、その明かりによって中心 (x,y) 、半径 R の円の内部全体(境界を含む)が照らされます。
すべての人が少なくとも 1 つの明かりによって照らされるために必要な明かりの強さの最小値を求めてください。
制約
- 入力は全て整数
- 1 \le K < N \le 1000
- 1 \le A_1 < A_2 < \dots < A_K \le N
- |X_i|,|Y_i| \le 10^5
- i \neq j ならば (X_i,Y_i) \neq (X_j,Y_j)
入力
入力は以下の形式で標準入力から与えられる。
N K A_1 A_2 \dots A_K X_1 Y_1 X_2 Y_2 \vdots X_N Y_N
出力
答えを実数として出力せよ。
出力された解と想定解との絶対誤差または相対誤差が 10^{-5} 以下であるならば、出力は正しいと見なされる。
入力例 1
4 2 2 3 0 0 0 1 1 2 2 0
出力例 1
2.23606797749978969
この入力では人が 4 人おり、そのうち人 2,3 が明かりを持ちます。
R \ge \sqrt{5} \approx 2.236068 である時、すべての人が少なくとも 1 つの明かりによって照らされます。
入力例 2
2 1 2 -100000 -100000 100000 100000
出力例 2
282842.712474619009
入力例 3
8 3 2 6 8 -17683 17993 93038 47074 58079 -57520 -41515 -89802 -72739 68805 24324 -73073 71049 72103 47863 19268
出力例 3
130379.280458974768
Score : 200 points
Problem Statement
There are N people numbered 1, 2, \dots, N in the xy-plane. Person i is at the coordinates (X_i, Y_i).
K of these people, Persons A_1, A_2, \dots, A_K, will receive lights of the same strength.
When a person at coordinates (x, y) has a light of strength R, it lights up the interior of a circle of radius R centered at (x, y) (including the boundary).
Find the minimum strength of the lights needed for every person to be lit by at least one light.
Constraints
- All values in input are integers.
- 1 \le K < N \le 1000
- 1 \le A_1 < A_2 < \dots < A_K \le N
- |X_i|,|Y_i| \le 10^5
- (X_i,Y_i) \neq (X_j,Y_j), if i \neq j.
Input
Input is given from Standard Input in the following format:
N K A_1 A_2 \dots A_K X_1 Y_1 X_2 Y_2 \vdots X_N Y_N
Output
Print the answer as a real number.
Your output will be considered correct if its absolute or relative error from the judge's output is at most 10^{-5}.
Sample Input 1
4 2 2 3 0 0 0 1 1 2 2 0
Sample Output 1
2.23606797749978969
This input contains four people. Among them, Persons 2 and 3 will have lights.
Every person will be lit by at least one light if R \ge \sqrt{5} \approx 2.236068.
Sample Input 2
2 1 2 -100000 -100000 100000 100000
Sample Output 2
282842.712474619009
Sample Input 3
8 3 2 6 8 -17683 17993 93038 47074 58079 -57520 -41515 -89802 -72739 68805 24324 -73073 71049 72103 47863 19268
Sample Output 3
130379.280458974768
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
縦 A 行、横 B 列のマスからなるタイルを縦 N 行、横 N 列に並べてできた、縦 (A\times N) 行、横 (B\times N) 列のマス目 X があります。
1\leq i,j \leq N について、上から i 行目、左から j 列目のタイルをタイル (i,j) とします。
X の各マスは以下のように塗られています。
- 各タイルは白いタイルまたは黒いタイルである。
- 白いタイルのすべてのマスは白で塗られ、黒いタイルのすべてのマスは黒で塗られている。
- タイル (1,1) は白いタイルである。
- 辺で隣接する 2 つのタイルは異なる色のタイルである。ただし、タイル (a,b) とタイル (c,d) が辺で隣接するとは、|a-c|+|b-d|=1 ( |x| を x の絶対値とする)であることを言う。
マス目 X を出力の形式に従って出力してください。
制約
- 1 \leq N,A,B \leq 10
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N A B
出力
次の条件をみたす (A\times N) 個の文字列 S_1,\ldots,S_{A\times N} を改行区切りで出力せよ。
- S_1,\ldots,S_{A\times N} はそれぞれ長さ (B\times N) の
.または#からなる文字列である。 - 各 i,j (1 \leq i \leq A\times N,1 \leq j \leq B\times N) に対し、マス目 X の上から i 行目かつ左から j 列目のマスが白で塗られているならば S_i の j 文字目は
.であり、黒く塗られているならば#である。
入力例 1
4 3 2
出力例 1
..##..## ..##..## ..##..## ##..##.. ##..##.. ##..##.. ..##..## ..##..## ..##..## ##..##.. ##..##.. ##..##..
入力例 2
5 1 5
出力例 2
.....#####.....#####..... #####.....#####.....##### .....#####.....#####..... #####.....#####.....##### .....#####.....#####.....
入力例 3
4 4 1
出力例 3
.#.# .#.# .#.# .#.# #.#. #.#. #.#. #.#. .#.# .#.# .#.# .#.# #.#. #.#. #.#. #.#.
入力例 4
1 4 4
出力例 4
.... .... .... ....
Score : 200 points
Problem Statement
Tiles are aligned in N horizontal rows and N vertical columns. Each tile has a grid with A horizontal rows and B vertical columns. On the whole, the tiles form a grid X with (A\times N) horizontal rows and (B\times N) vertical columns.
For 1\leq i,j \leq N, Tile (i,j) denotes the tile at the i-th row from the top and the j-th column from the left.
Each square of X is painted as follows.
- Each tile is either a white tile or a black tile.
- Every square in a white tile is painted white; every square in a black tile is painted black.
- Tile (1,1) is a white tile.
- Two tiles sharing a side have different colors. Here, Tile (a,b) and Tile (c,d) are said to be sharing a side if and only if |a-c|+|b-d|=1 (where |x| denotes the absolute value of x).
Print the grid X in the format specified in the Output section.
Constraints
- 1 \leq N,A,B \leq 10
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A B
Output
Print (A\times N) strings S_1,\ldots,S_{A\times N} that satisfy the following condition, with newlines in between.
- Each of S_1,\ldots,S_{A\times N} is a string of length (B\times N) consisting of
.and#. - For each i and j (1 \leq i \leq A\times N,1 \leq j \leq B\times N), the j-th character of S_i is
.if the square at the i-th row from the top and j-th column from the left in grid X is painted white; the character is#if the square is painted black.
Sample Input 1
4 3 2
Sample Output 1
..##..## ..##..## ..##..## ##..##.. ##..##.. ##..##.. ..##..## ..##..## ..##..## ##..##.. ##..##.. ##..##..
Sample Input 2
5 1 5
Sample Output 2
.....#####.....#####..... #####.....#####.....##### .....#####.....#####..... #####.....#####.....##### .....#####.....#####.....
Sample Input 3
4 4 1
Sample Output 3
.#.# .#.# .#.# .#.# #.#. #.#. #.#. #.#. .#.# .#.# .#.# .#.# #.#. #.#. #.#. #.#.
Sample Input 4
1 4 4
Sample Output 4
.... .... .... ....
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
英小文字のみからなる長さ N の文字列 S が与えられます。
S の文字を並び替えて得られる文字列（S 自身を含む）であって、長さ K の回文を部分文字列として 含まない ものの個数を求めてください。
ただし、長さ N の文字列 T が「長さ K の回文を部分文字列として含む」とは、
ある (N-K) 以下の非負整数 i が存在して、1 以上 K 以下の任意の整数 j について T_{i+j}=T_{i+K+1-j} が成り立つことをいいます。
ここで、T_k は文字列 T の k 文字目を表すものとします。
制約
- 2\leq K \leq N \leq 10
- N,K は整数
- S は英小文字のみからなる長さ N の文字列
入力
入力は以下の形式で標準入力から与えられる。
N K S
出力
S の文字を並び替えて得られる文字列であって、長さ K の回文を部分文字列として含まないものの個数を出力せよ。
入力例 1
3 2 aab
出力例 1
1
aab を並び替えて得られる文字列は aab, aba, baa の 3 つであり、このうち aab および baa は長さ 2 の回文 aa を部分文字列として含んでいます。
よって、条件をみたす文字列は aba のみであり、1 を出力します。
入力例 2
5 3 zzyyx
出力例 2
16
zzyyx を並べて得られる文字列は 30 個ありますが、そのうち長さ 3 の回文を含まないようなものは 16 個です。よって、16 を出力します。
入力例 3
10 5 abcwxyzyxw
出力例 3
440640
Score : 300 points
Problem Statement
You are given a string S of length N consisting only of lowercase English letters.
Find the number of strings obtained by permuting the characters of S (including the string S itself) that do not contain a palindrome of length K as a substring.
Here, a string T of length N is said to "contain a palindrome of length K as a substring" if and only if there exists a non-negative integer i not greater than (N-K) such that T_{i+j} = T_{i+K+1-j} for every integer j with 1 \leq j \leq K.
Here, T_k denotes the k-th character of the string T.
Constraints
- 2 \leq K \leq N \leq 10
- N and K are integers.
- S is a string of length N consisting only of lowercase English letters.
Input
The input is given from Standard Input in the following format:
N K S
Output
Print the number of strings obtained by permuting S that do not contain a palindrome of length K as a substring.
Sample Input 1
3 2 aab
Sample Output 1
1
The strings obtained by permuting aab are aab, aba, and baa. Among these, aab and baa contain the palindrome aa of length 2 as a substring.
Thus, the only string that satisfies the condition is aba, so print 1.
Sample Input 2
5 3 zzyyx
Sample Output 2
16
There are 30 strings obtained by permuting zzyyx, 16 of which do not contain a palindrome of length 3. Thus, print 16.
Sample Input 3
10 5 abcwxyzyxw
Sample Output 3
440640
Time Limit: 3 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
N 行 N 列のマス目があり、それぞれのマスは白または黒で塗られています。
マス目の状態は N 個の文字列 S_i で表され、
S_i の j 文字目が # であることはマス目の上から i 行目、左から j 列目のマスが黒く塗られていることを、
. であることは白く塗られていることをさします。
高橋君はこのマス目のうち高々 2 つの白く塗られているマスを選び、黒く塗ることができます。
マス目の中に、黒く塗られたマスが縦、横、ななめのいずれかの向きに 6 つ以上連続するようにできるか判定してください。
ただし、黒く塗られたマスがななめに 6 つ以上連続するとは、N 行 N 列のマス目に完全に含まれる 6 行 6 列のマス目であって、その少なくとも一方の対角線上のマスがすべて黒く塗られているようなものが存在する事をさします。
制約
- 6 \leq N \leq 1000
- \lvert S_i\rvert =N
- S_i は
#と.のみからなる。
入力
入力は以下の形式で標準入力から与えられる。
N S_1 S_2 \vdots S_N
出力
高々 2 つのマス目を黒く塗ることで条件をみたすようにできるなら Yes を、そうでないならば No を出力せよ。
入力例 1
8 ........ ........ .#.##.#. ........ ........ ........ ........ ........
出力例 1
Yes
上から 3 行目の左から 3, 6 番目のマスを塗ることで横方向に 6 つの黒く塗られたマスを連続させることができます。
入力例 2
6 ###### ###### ###### ###### ###### ######
出力例 2
Yes
高橋君はマス目を新たに黒く塗ることはできませんが、すでにこのマス目は条件をみたしています。
入力例 3
10 .......... #..##..... .......... .......... ....#..... ....#..... .#...#..#. .......... .......... ..........
出力例 3
No
Score : 300 points
Problem Statement
There is a grid with N horizontal rows and N vertical columns, where each square is painted white or black.
The state of the grid is represented by N strings, S_i.
If the j-th character of S_i is #, the square at the i-th row from the top and the j-th column from the left is painted black.
If the character is ., then the square is painted white.
Takahashi can choose at most two of these squares that are painted white, and paint them black.
Determine if it is possible to make the grid contain 6 or more consecutive squares painted black aligned either vertically, horizontally, or diagonally.
Here, the grid is said to be containing 6 or more consecutive squares painted black aligned diagonally if the grid with N rows and N columns completely contains a subgrid with 6 rows and 6 columns such that all the squares on at least one of its diagonals are painted black.
Constraints
- 6 \leq N \leq 1000
- \lvert S_i\rvert =N
- S_i consists of
#and..
Input
Input is given from Standard Input in the following format:
N S_1 S_2 \vdots S_N
Output
If it is possible to fulfill the condition by painting at most two squares, then print Yes; otherwise, print No.
Sample Input 1
8 ........ ........ .#.##.#. ........ ........ ........ ........ ........
Sample Output 1
Yes
By painting the 3-rd and the 6-th squares from the left in the 3-rd row from the top, there will be 6 squares painted black aligned horizontally.
Sample Input 2
6 ###### ###### ###### ###### ###### ######
Sample Output 2
Yes
While Takahashi cannot choose a square to paint black, the grid already satisfies the condition.
Sample Input 3
10 .......... #..##..... .......... .......... ....#..... ....#..... .#...#..#. .......... .......... ..........
Sample Output 3
No
Time Limit: 2.5 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
座標平面上に 1 から N の番号がついた N 人の人がいます。
人 1 は原点にいます。
次の形式の情報が M 個与えられます。
- 人 A_i から見て、人 B_i は、x 軸正方向に X_i、y 軸正方向に Y_i 離れた位置にいる
それぞれの人がいる座標を求めてください。一意に定まらないときはそのことを報告してください。
制約
- 1 \leq N \leq 2\times 10^5
- 0 \leq M \leq 2\times 10^5
- 1\leq A_i, B_i \leq N
- A_i \neq B_i
- -10^9 \leq X_i,Y_i \leq 10^9
- 入力は全て整数である
- 与えられる情報は矛盾しない
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 B_1 X_1 Y_1 \vdots A_M B_M X_M Y_M
出力
N 行出力せよ。
人 i のいる座標が一意に定まらないとき、i 行目には undecidable と出力せよ。
人 i のいる座標が (s_i,t_i) と一意に定まるとき、i 行目には s_i,t_i をこの順に空白区切りで出力せよ。
入力例 1
3 2 1 2 2 1 1 3 -1 -2
出力例 1
0 0 2 1 -1 -2
3 人の位置関係は下図のようになっています。
入力例 2
3 2 2 1 -2 -1 2 3 -3 -3
出力例 2
0 0 2 1 -1 -2
3 人の位置関係は下図のようになっています。
入力例 3
5 7 1 2 0 0 1 2 0 0 2 3 0 0 3 1 0 0 2 1 0 0 3 2 0 0 4 5 0 0
出力例 3
0 0 0 0 0 0 undecidable undecidable
同じ情報が複数回与えられたり、同じ座標に複数の人がいることもあります。
Score : 400 points
Problem Statement
There are N people numbered 1 to N on a coordinate plane.
Person 1 is at the origin.
You are given M pieces of information in the following form:
- From person A_i's perspective, person B_i is X_i units away in the positive x-direction and Y_i units away in the positive y-direction.
Determine the coordinates of each person. If the coordinates of a person cannot be uniquely determined, report that fact.
Constraints
- 1 \leq N \leq 2\times 10^5
- 0 \leq M \leq 2\times 10^5
- 1\leq A_i, B_i \leq N
- A_i \neq B_i
- -10^9 \leq X_i,Y_i \leq 10^9
- All input values are integers.
- The given information is consistent.
Input
The input is given from Standard Input in the following format:
N M A_1 B_1 X_1 Y_1 \vdots A_M B_M X_M Y_M
Output
Print N lines.
If the coordinates of person i cannot be uniquely determined, the i-th line should contain undecidable.
If they can be uniquely determined as (s_i,t_i), the i-th line should contain s_i and t_i in this order, separated by a space.
Sample Input 1
3 2 1 2 2 1 1 3 -1 -2
Sample Output 1
0 0 2 1 -1 -2
The figure below shows the positional relationship of the three people.
Sample Input 2
3 2 2 1 -2 -1 2 3 -3 -3
Sample Output 2
0 0 2 1 -1 -2
The figure below shows the positional relationship of the three people.
Sample Input 3
5 7 1 2 0 0 1 2 0 0 2 3 0 0 3 1 0 0 2 1 0 0 3 2 0 0 4 5 0 0
Sample Output 3
0 0 0 0 0 0 undecidable undecidable
The same piece of information may be given multiple times, and multiple people may be at the same coordinates.