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 点
問題文
正整数 N が与えられます。
N 以下の正整数であって回文立方数であるものの最大値を求めてください。
ただし、正整数 K は以下の 2 つの条件を満たすとき、またそのときに限り回文立方数であると定義します。
- ある正整数 x が存在し、x^3 = K を満たす。
- K を先頭に 0 をつけずに 10 進表記した文字列が回文となる。より厳密には、0 以上 9 以下の整数 A_0, A_1, \ldots, A_{L-2} および 1 以上 9 以下の整数 A_{L-1} を用いて K = \sum_{i = 0}^{L-1} A_i10^i と表記したときに i = 0, 1, \ldots, L-1 に対して A_i = A_{L-1-i} を満たす。
制約
- N は 10^{18} 以下の正整数
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを出力せよ。
入力例 1
345
出力例 1
343
343 は回文立方数であり、344, 345 は回文立方数ではありません。したがって、343 が答えとなります。
入力例 2
6
出力例 2
1
入力例 3
123456789012345
出力例 3
1334996994331
Score: 250 points
Problem Statement
You are given a positive integer N.
Find the maximum value of a palindromic cube number not greater than N.
Here, a positive integer K is defined to be a palindromic cube number if and only if it satisfies the following two conditions:
- There is a positive integer x such that x^3 = K.
- The decimal representation of K without leading zeros is a palindrome. More precisely, if K is represented as K = \sum_{i = 0}^{L-1} A_i10^i using integers A_0, A_1, \ldots, A_{L-2} between 0 and 9, inclusive, and an integer A_{L-1} between 1 and 9, inclusive, then A_i = A_{L-1-i} for all i = 0, 1, \ldots, L-1.
Constraints
- N is a positive integer not greater than 10^{18}.
Input
The input is given from Standard Input in the following format:
N
Output
Print the answer.
Sample Input 1
345
Sample Output 1
343
343 is a palindromic cube number, while 344 and 345 are not. Thus, the answer is 343.
Sample Input 2
6
Sample Output 2
1
Sample Input 3
123456789012345
Sample Output 3
1334996994331
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 350 点
問題文
縦 N 行 横 N 列のマスからなるグリッドがあります。ここで、N は 45 以下の奇数です。
上から i 行目、左から j 列目のマスをマス (i,j) と表します。
このグリッドに、以下の条件を満たすように高橋君と 1 から N^2-1 までの番号がついた N^2-1 個のパーツからなる 1 匹の龍を配置します。
- 高橋君はグリッドの中央、すなわちマス (\frac{N+1}{2},\frac{N+1}{2}) に配置しなければならない。
- 高橋君がいるマスを除く各マスには龍のパーツをちょうど 1 つ配置しなければならない。
- 2 \leq x \leq N^2-1 を満たす全ての整数 x について、龍のパーツ x はパーツ x-1 があるマスと辺で隣接するマスに配置しなければならない。
- マス (i,j) とマス (k,l) が辺で隣接するとは、|i-k|+|j-l|=1 であることを意味します。
条件を満たす配置方法を 1 つ出力してください。なお、条件を満たす配置は必ず存在します。
制約
- 3 \leq N \leq 45
- N は奇数である
入力
入力は以下の形式で標準入力から与えられる。
N
出力
N 行出力せよ。
X_{i,j} を、マス (i,j) に高橋君を配置するとき T、パーツ x を配置するとき x とし、i 行目には X_{i,1},\ldots,X_{i,N} を空白区切りで出力せよ。
入力例 1
5
出力例 1
1 2 3 4 5 16 17 18 19 6 15 24 T 20 7 14 23 22 21 8 13 12 11 10 9
この他、以下の出力も条件をすべて満たすため正解となります。
9 10 11 14 15 8 7 12 13 16 5 6 T 18 17 4 3 24 19 20 1 2 23 22 21
一方、以下の出力はそれぞれ不正解となります。
高橋君が中央にいない。
1 2 3 4 5 10 9 8 7 6 11 12 13 14 15 20 19 18 17 16 21 22 23 24 T
パーツ 23 とパーツ 24 のあるマスが辺で隣接していない。
1 2 3 4 5 10 9 8 7 6 11 12 24 22 23 14 13 T 21 20 15 16 17 18 19
Score : 350 points
Problem Statement
There is a grid with N rows and N columns, where N is an odd number at most 45.
Let (i,j) denote the cell at the i-th row from the top and j-th column from the left.
In this grid, you will place Takahashi and a dragon consisting of N^2-1 parts numbered 1 to N^2-1 in such a way that satisfies the following conditions:
- Takahashi must be placed at the center of the grid, that is, in cell (\frac{N+1}{2},\frac{N+1}{2}).
- Except for the cell where Takahashi is, exactly one dragon part must be placed in each cell.
- For every integer x satisfying 2 \leq x \leq N^2-1, the dragon part x must be placed in a cell adjacent by an edge to the cell containing part x-1.
- Cells (i,j) and (k,l) are said to be adjacent by an edge if and only if |i-k|+|j-l|=1.
Print one way to arrange the parts to satisfy the conditions. It is guaranteed that there is at least one arrangement that satisfies the conditions.
Constraints
- 3 \leq N \leq 45
- N is odd.
Input
The input is given from Standard Input in the following format:
N
Output
Print N lines.
The i-th line should contain X_{i,1},\ldots,X_{i,N} separated by spaces, where X_{i,j} is T when placing Takahashi in cell (i,j) and x when placing part x there.
Sample Input 1
5
Sample Output 1
1 2 3 4 5 16 17 18 19 6 15 24 T 20 7 14 23 22 21 8 13 12 11 10 9
The following output also satisfies all the conditions and is correct.
9 10 11 14 15 8 7 12 13 16 5 6 T 18 17 4 3 24 19 20 1 2 23 22 21
On the other hand, the following outputs are incorrect for the reasons given.
Takahashi is not at the center.
1 2 3 4 5 10 9 8 7 6 11 12 13 14 15 20 19 18 17 16 21 22 23 24 T
The cells containing parts 23 and 24 are not adjacent by an edge.
1 2 3 4 5 10 9 8 7 6 11 12 24 22 23 14 13 T 21 20 15 16 17 18 19
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 450 点
問題文
AtCoder 国には駅 1, 駅 2,\ldots, 駅 N の N 個の駅があります。
AtCoder 国に存在する電車の情報が M 個与えられます。 i 番目 (1\leq i\leq M) の情報は正整数の 6 つ組 (l _ i,d _ i,k _ i,c _ i,A _ i,B _ i) で表され、次のような情報に対応しています。
- t=l _ i,l _ i+d _ i,l _ i+2d _ i,\ldots,l _ i+(k _ i-1)d _ i それぞれについて、次のような電車が存在する。
- 時刻 t に 駅 A _ i を出発し、時刻 t+c _ i に駅 B _ i に到着する。
これらの情報にあてはまらない電車は存在せず、電車以外の方法である駅から異なる駅へ移動することはできません。
また、乗り換えにかかる時間は無視できるとします。
駅 S から駅 N に到着できる最終時刻を f(S) とします。
より厳密には、整数の 4 つ組の列 \big((t _ i,c _ i,A _ i,B _ i)\big) _ {i=1,2,\ldots,k} であって、次のすべての条件を満たすものが存在するような t の最大値を f(S) とします。
- t\leq t _ 1
- A _ 1=S,B _ k=N
- すべての 1\leq i\lt k について、B _ i=A _ {i+1}
- すべての 1\leq i\leq k について、時刻 t _ i に駅 A _ i を出発して時刻 t _ i+c _ i に駅 B _ i に到着する電車が存在する。
- すべての 1\leq i\lt k について、t _ i+c _ i\leq t _ {i+1}
ただし、そのような t が存在しないとき f(S)=-\infty とします。
f(1),f(2),\ldots,f(N-1) を求めてください。
制約
- 2\leq N\leq2\times10 ^ 5
- 1\leq M\leq2\times10 ^ 5
- 1\leq l _ i,d _ i,k _ i,c _ i\leq10 ^ 9\ (1\leq i\leq M)
- 1\leq A _ i,B _ i\leq N\ (1\leq i\leq M)
- A _ i\neq B _ i\ (1\leq i\leq M)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M l _ 1 d _ 1 k _ 1 c _ 1 A _ 1 B _ 1 l _ 2 d _ 2 k _ 2 c _ 2 A _ 2 B _ 2 \vdots l _ M d _ M k _ M c _ M A _ M B _ M
出力
N-1 行出力せよ。
k 行目には f(k)\neq-\infty ならば f(k) を、f(k)=-\infty ならば Unreachable を出力せよ。
入力例 1
6 7 10 5 10 3 1 3 13 5 10 2 3 4 15 5 10 7 4 6 3 10 2 4 2 5 7 10 2 3 5 6 5 3 18 2 2 3 6 3 20 4 2 1
出力例 1
55 56 58 60 17
AtCoder 国に走っている電車は以下の図のようになります(発着時間の情報は図には含まれていません)。

駅 2 から駅 6 に到着できる最終時刻について考えます。 次の図のように、駅 2 を時刻 56 に出発して駅 2\rightarrow 駅 3\rightarrow 駅 4\rightarrow 駅 6 のように移動することで駅 6 に到着することができます。

駅 2 を時刻 56 より遅く出発して駅 6 に到着することはできないため、f(2)=56 です。
入力例 2
5 5 1000000000 1000000000 1000000000 1000000000 1 5 5 9 2 6 2 3 10 4 1 6 2 3 1 1 1 1 3 5 3 1 4 1 5 1
出力例 2
1000000000000000000 Unreachable 1 Unreachable
駅 1 を時刻 10 ^ {18} に出発して駅 5 に時刻 10 ^ {18}+10 ^ 9 に到着するような電車が存在します。それ以降に駅 1 を出発する電車はないため、f(1)=10 ^ {18} です。 このように、答えが 32\operatorname{bit} 整数におさまらない場合もあります。
また、時刻 14 に駅 2 を出発して時刻 20 に駅 3 に到着するような電車は 2 番目の情報と 3 番目の情報の両方で存在が保証されています。 このように、複数の情報に重複している電車もあります。
入力例 3
16 20 4018 9698 2850 3026 8 11 2310 7571 7732 1862 13 14 2440 2121 20 1849 11 16 2560 5115 190 3655 5 16 1936 6664 39 8822 4 16 7597 8325 20 7576 12 5 5396 1088 540 7765 15 1 3226 88 6988 2504 13 5 1838 7490 63 4098 8 3 1456 5042 4 2815 14 7 3762 6803 5054 6994 10 9 9526 6001 61 8025 7 8 5176 6747 107 3403 1 5 2014 5533 2031 8127 8 11 8102 5878 58 9548 9 10 3788 174 3088 5950 3 13 7778 5389 100 9003 10 15 556 9425 9458 109 3 11 5725 7937 10 3282 2 9 6951 7211 8590 1994 15 12
出力例 3
720358 77158 540926 255168 969295 Unreachable 369586 466218 343148 541289 42739 165772 618082 16582 591828
Score: 450 points
Problem Statement
In the country of AtCoder, there are N stations: station 1, station 2, \ldots, station N.
You are given M pieces of information about trains in the country. The i-th piece of information (1\leq i\leq M) is represented by a tuple of six positive integers (l _ i,d _ i,k _ i,c _ i,A _ i,B _ i), which corresponds to the following information:
- For each t=l _ i,l _ i+d _ i,l _ i+2d _ i,\ldots,l _ i+(k _ i-1)d _ i, there is a train as follows:
- The train departs from station A _ i at time t and arrives at station B _ i at time t+c _ i.
No trains exist other than those described by this information, and it is impossible to move from one station to another by any means other than by train.
Also, assume that the time required for transfers is negligible.
Let f(S) be the latest time at which one can arrive at station N from station S.
More precisely, f(S) is defined as the maximum value of t for which there is a sequence of tuples of four integers \big((t _ i,c _ i,A _ i,B _ i)\big) _ {i=1,2,\ldots,k} that satisfies all of the following conditions:
- t\leq t _ 1
- A _ 1=S,B _ k=N
- B _ i=A _ {i+1} for all 1\leq i\lt k,
- For all 1\leq i\leq k, there is a train that departs from station A _ i at time t _ i and arrives at station B _ i at time t _ i+c _ i.
- t _ i+c _ i\leq t _ {i+1} for all 1\leq i\lt k.
If no such t exists, set f(S)=-\infty.
Find f(1),f(2),\ldots,f(N-1).
Constraints
- 2\leq N\leq2\times10 ^ 5
- 1\leq M\leq2\times10 ^ 5
- 1\leq l _ i,d _ i,k _ i,c _ i\leq10 ^ 9\ (1\leq i\leq M)
- 1\leq A _ i,B _ i\leq N\ (1\leq i\leq M)
- A _ i\neq B _ i\ (1\leq i\leq M)
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M l _ 1 d _ 1 k _ 1 c _ 1 A _ 1 B _ 1 l _ 2 d _ 2 k _ 2 c _ 2 A _ 2 B _ 2 \vdots l _ M d _ M k _ M c _ M A _ M B _ M
Output
Print N-1 lines.
The k-th line should contain f(k) if f(k)\neq-\infty, and Unreachable if f(k)=-\infty.
Sample Input 1
6 7 10 5 10 3 1 3 13 5 10 2 3 4 15 5 10 7 4 6 3 10 2 4 2 5 7 10 2 3 5 6 5 3 18 2 2 3 6 3 20 4 2 1
Sample Output 1
55 56 58 60 17
The following diagram shows the trains running in the country (information about arrival and departure times is omitted).

Consider the latest time at which one can arrive at station 6 from station 2. As shown in the following diagram, one can arrive at station 6 by departing from station 2 at time 56 and moving as station 2\rightarrow station 3\rightarrow station 4\rightarrow station 6.

It is impossible to depart from station 2 after time 56 and arrive at station 6, so f(2)=56.
Sample Input 2
5 5 1000000000 1000000000 1000000000 1000000000 1 5 5 9 2 6 2 3 10 4 1 6 2 3 1 1 1 1 3 5 3 1 4 1 5 1
Sample Output 2
1000000000000000000 Unreachable 1 Unreachable
There is a train that departs from station 1 at time 10 ^ {18} and arrives at station 5 at time 10 ^ {18}+10 ^ 9. There are no trains departing from station 1 after that time, so f(1)=10 ^ {18}. As seen here, the answer may not fit within a 32\operatorname{bit} integer.
Also, both the second and third pieces of information guarantee that there is a train that departs from station 2 at time 14 and arrives at station 3 at time 20. As seen here, some trains may appear in multiple pieces of information.
Sample Input 3
16 20 4018 9698 2850 3026 8 11 2310 7571 7732 1862 13 14 2440 2121 20 1849 11 16 2560 5115 190 3655 5 16 1936 6664 39 8822 4 16 7597 8325 20 7576 12 5 5396 1088 540 7765 15 1 3226 88 6988 2504 13 5 1838 7490 63 4098 8 3 1456 5042 4 2815 14 7 3762 6803 5054 6994 10 9 9526 6001 61 8025 7 8 5176 6747 107 3403 1 5 2014 5533 2031 8127 8 11 8102 5878 58 9548 9 10 3788 174 3088 5950 3 13 7778 5389 100 9003 10 15 556 9425 9458 109 3 11 5725 7937 10 3282 2 9 6951 7211 8590 1994 15 12
Sample Output 3
720358 77158 540926 255168 969295 Unreachable 369586 466218 343148 541289 42739 165772 618082 16582 591828
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 500 点
問題文
座標平面上でチェックポイント 1,2,\dots,N をこの順に通るレースが行われます。
チェックポイント i の座標は (X_i,Y_i) であり、すべてのチェックポイントの座標は異なります。
チェックポイント 1,N 以外のチェックポイントは、通過を省略することもできます。
ただし、通らなかったチェックポイントの個数を C として、以下の通りペナルティが課せられます。
- C>0 なら \displaystyle 2^{C−1}
- C=0 なら 0
チェックポイント 1 からチェックポイント N までの総移動距離(ユークリッド距離)とペナルティの和を s とします。
このとき、 s として達成可能な最小の値を求めてください。
制約
- 入力は全て整数
- 2 \le N \le 10^4
- 0 \le X_i,Y_i \le 10^4
- i \neq j ならば (X_i,Y_i) \neq (X_j,Y_j)
入力
入力は以下の形式で標準入力から与えられる。
N X_1 Y_1 X_2 Y_2 \vdots X_N Y_N
出力
答えを出力せよ。 出力は、真の値との絶対誤差または相対誤差が 10^{−5} 以下のとき正解と判定される。
入力例 1
6 0 0 1 1 2 0 0 1 1 0 2 1
出力例 1
5.82842712474619009753
チェックポイント 1,2,5,6 を通過し、 3,4 の通過を省略することを考えます。
- チェックポイント 1 \rightarrow 2 に移動する。 2 点間の距離は \sqrt{2} である。
- チェックポイント 2 \rightarrow 5 に移動する。 2 点間の距離は 1 である。
- チェックポイント 5 \rightarrow 6 に移動する。 2 点間の距離は \sqrt{2} である。
- 通らなかったチェックポイントは 2 つであり、このとき科せられるペナルティは 2 である。
以上のようにして、 s = 3 + 2\sqrt{2} \approx 5.828427 を達成できます。
s をこの値より小さくすることはできません。
入力例 2
10 1 8 3 7 9 4 4 9 6 1 7 5 0 0 1 3 6 8 6 4
出力例 2
24.63441361516795872523
入力例 3
10 34 24 47 60 30 31 12 97 87 93 64 46 82 50 14 7 17 24 3 78
出力例 3
110.61238353245736230207
Score : 500 points
Problem Statement
There is a race through checkpoints 1,2,\dots,N in this order on a coordinate plane.
The coordinates of checkpoint i are (X_i,Y_i), and all checkpoints have different coordinates.
Checkpoints other than checkpoints 1 and N can be skipped.
However, let C be the number of checkpoints skipped, and the following penalty will be imposed:
- \displaystyle 2^{C−1} if C>0, and
- 0 if C=0.
Let s be the total distance traveled (Euclidean distance) from checkpoint 1 to checkpoint N plus the penalty.
Find the minimum achievable value as s.
Constraints
- All input values are integers.
- 2 \le N \le 10^4
- 0 \le X_i,Y_i \le 10^4
- (X_i,Y_i) \neq (X_j,Y_j) if i \neq j.
Input
The 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. Your output is considered correct if the absolute or relative error from the true value is at most 10^{-5}.
Sample Input 1
6 0 0 1 1 2 0 0 1 1 0 2 1
Sample Output 1
5.82842712474619009753
Consider passing through checkpoints 1,2,5,6 and skip checkpoints 3,4.
- Move from checkpoint 1 to 2. The distance between them is \sqrt{2}.
- Move from checkpoint 2 to 5. The distance between them is 1.
- Move from checkpoint 5 to 6. The distance between them is \sqrt{2}.
- Two checkpoints are skipped, so the penalty of 2 is imposed.
In this way, you can achieve s = 3 + 2\sqrt{2} \approx 5.828427.
You cannot make s smaller than this value.
Sample Input 2
10 1 8 3 7 9 4 4 9 6 1 7 5 0 0 1 3 6 8 6 4
Sample Output 2
24.63441361516795872523
Sample Input 3
10 34 24 47 60 30 31 12 97 87 93 64 46 82 50 14 7 17 24 3 78
Sample Output 3
110.61238353245736230207