実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
正の整数 X について、レベル X の 龍文字列 とは、1 個の L, X 個の o, 1 個の n, 1 個の g をこの順に並べた長さ (X+3) の文字列です。
正の整数 N が与えられるので、レベル N の龍文字列を出力してください。
大文字と小文字は区別されることに注意してください。
制約
- 1\leq N\leq 2024
- N は整数
入力
入力は以下の形式で標準入力から与えられる。
N
出力
レベル N の龍文字列を出力せよ。
入力例 1
3
出力例 1
Looong
1 個の L, 3 個の o, 1 個の n, 1 個の g をこの順に並べた文字列は Looong です。
入力例 2
1
出力例 2
Long
Score: 100 points
Problem Statement
For a positive integer X, the Dragon String of level X is a string of length (X+3) formed by one L, X occurrences of o, one n, and one g arranged in this order.
You are given a positive integer N. Print the Dragon String of level N.
Note that uppercase and lowercase letters are distinguished.
Constraints
- 1 \leq N \leq 2024
- N is an integer.
Input
The input is given from Standard Input in the following format:
N
Output
Print the Dragon String of level N.
Sample Input 1
3
Sample Output 1
Looong
Arranging one L, three os, one n, and one g in this order yields Looong.
Sample Input 2
1
Sample Output 2
Long
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
英小文字 a, b, \ldots, z の ASCII 文字コードはこの順に 97,98,\ldots,122 です。
97 以上 122 以下の整数 N が与えられるので、ASCII 文字コードが N であるような英小文字を出力してください。
制約
- N は 97 以上 122 以下の整数
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを出力せよ。
入力例 1
97
出力例 1
a
ASCII 文字コードが 97 である英小文字は a です。
入力例 2
122
出力例 2
z
Score : 100 points
Problem Statement
The ASCII values of the lowercase English letters a, b, \ldots, z are 97,98,\ldots,122 in this order.
Given an integer N between 97 and 122, print the letter whose ASCII value is N.
Constraints
- N is an integer between 97 and 122 (inclusive).
Input
Input is given from Standard Input in the following format:
N
Output
Print the answer.
Sample Input 1
97
Sample Output 1
a
97 is the ASCII value of a.
Sample Input 2
122
Sample Output 2
z
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
次の図に示す、各マスが黒または白に塗られた縦 15 行 \times 横 15 列のグリッドにおいて、 上から R 行目、左から C 列目のマスが何色かを出力して下さい。

制約
- 1 \leq R, C \leq 15
- R, C は整数
入力
入力は以下の形式で標準入力から与えられる。
R C
出力
図のグリッドにおいて上から R 行目、左から C 列目のマスが黒色の場合は black と、白色の場合は white と出力せよ。
ジャッジは英小文字と英大文字を厳密に区別することに注意せよ。
入力例 1
3 5
出力例 1
black
図のグリッドにおいて上から 3 行目、左から 5 列目のマスは黒色です。
よって、black と出力します。
入力例 2
4 5
出力例 2
white
図のグリッドにおいて上から 4 行目、左から 5 列目のマスは白色です。
よって、white と出力します。
Score : 200 points
Problem Statement
Print the color of the cell at the R-th row from the top and C-th column from the left in the following grid with 15 vertical rows and 15 horizontal columns.

Constraints
- 1 \leq R, C \leq 15
- R and C are integers.
Input
Input is given from Standard Input in the following format:
R C
Output
In the grid above, if the color of the cell at the R-th row from the top and C-th column from the left is black, then print black; if the cell is white, then print white. Note that the judge is case-sensitive.
Sample Input 1
3 5
Sample Output 1
black
In the grid above, the cell at the 3-rd row from the top and 5-th column from the left is black. Thus, black should be printed.
Sample Input 2
4 5
Sample Output 2
white
In the grid above, the cell at the 4-th row from the top and 5-th column from the left is white. Thus, white should be printed.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
長さ N の正整数列 a = (a_1, a_2, \dots, a_N) には何種類の整数が現れますか?
制約
- 1 \leq N \leq 1000
- 1 \leq a_i \leq 10^9 \, (1 \leq i \leq N)
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N a_1 \ldots a_N
出力
答えを出力せよ。
入力例 1
6 1 4 1 2 2 1
出力例 1
3
1, 2, 4 の 3 種類の整数が現れます。
入力例 2
1 1
出力例 2
1
入力例 3
11 3 1 4 1 5 9 2 6 5 3 5
出力例 3
7
Score : 200 points
Problem Statement
In a sequence of N positive integers a = (a_1, a_2, \dots, a_N), how many different integers are there?
Constraints
- 1 \leq N \leq 1000
- 1 \leq a_i \leq 10^9 \, (1 \leq i \leq N)
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N a_1 \ldots a_N
Output
Print the answer.
Sample Input 1
6 1 4 1 2 2 1
Sample Output 1
3
There are three different integers: 1, 2, 4.
Sample Input 2
1 1
Sample Output 2
1
Sample Input 3
11 3 1 4 1 5 9 2 6 5 3 5
Sample Output 3
7
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
N 本の導火線を一直線に接着したものがあります。左から i 本目の導火線は長さが A_i cm で、 1 秒あたり B_i cm の一定の速さで燃えます。
この導火線の左端と右端から同時に火をつけるとき、 2 つの火がぶつかる場所が着火前の導火線の左端から何 cm の地点か求めてください。
制約
- 1 \leq N \leq 10^5
- 1 \leq A_i,B_i \leq 1000
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 B_1 A_2 B_2 \vdots A_N B_N
出力
2 つの火がぶつかる場所が着火前の導火線の左端から何 cm の地点か(単位を除いて)出力せよ。
想定解答との絶対誤差または相対誤差が 10^{-5} 以下であれば正解として扱われる。
入力例 1
3 1 1 2 1 3 1
出力例 1
3.000000000000000
着火前の導火線の左端から 3 cm の地点で 2 つの火がぶつかります。
入力例 2
3 1 3 2 2 3 1
出力例 2
3.833333333333333
入力例 3
5 3 9 1 2 4 6 1 5 5 3
出力例 3
8.916666666666668
Score : 300 points
Problem Statement
We have N fuses connected in series. The i-th fuse from the left has a length of A_i centimeters and burns at a constant speed of B_i centimeters per second.
Consider igniting this object from left and right ends simultaneously. Find the distance between the position where the two flames will meet and the left end of the object.
Constraints
- 1 \leq N \leq 10^5
- 1 \leq A_i,B_i \leq 1000
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A_1 B_1 A_2 B_2 \vdots A_N B_N
Output
Print the distance between the position where the two flames will meet and the left end of the object, in centimeters (print just the number).
Your output will be considered correct when its absolute or relative error from our answer is at most 10^{-5}.
Sample Input 1
3 1 1 2 1 3 1
Sample Output 1
3.000000000000000
The two flames will meet at 3 centimeters from the left end of the object.
Sample Input 2
3 1 3 2 2 3 1
Sample Output 2
3.833333333333333
Sample Input 3
5 3 9 1 2 4 6 1 5 5 3
Sample Output 3
8.916666666666668
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
N 曲からなるプレイリストがあり、曲には 1, \dots, N の番号が付けられています。
曲 i の長さは A_i 秒です。
プレイリストを再生すると、曲 1、曲 2、\ldots、曲 N の順に流れます。曲 N が流れ終わると、再び曲 1 から順に流れていきます。ある曲の途中で次の曲が流れることはなく、曲が流れ終わると、その瞬間に次の曲が流れ始めます。
プレイリストを再生してから T 秒後に流れているのはどの曲ですか?また、その曲が流れ始めてから何秒の時点ですか?
ただし、T 秒後ちょうどに曲が切り替わるような入力は与えられません。
制約
- 1 \leq N \leq 10^5
- 1 \leq T \leq 10^{18}
- 1 \leq A_i \leq 10^9
- プレイリストを再生して T 秒後ちょうどに曲が切り替わることはない
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N T A_1 \ldots A_N
出力
プレイリストを再生してから T 秒後に流れている曲の番号と、その曲が流れ始めてから何秒たったかを表す整数を空白区切りで出力せよ。
入力例 1
3 600 180 240 120
出力例 1
1 60
プレイリストを再生してからの様子は次のようになります。
- 0 秒後から 180 秒後まで曲 1 が流れる。
- 180 秒後から 420 秒後まで曲 2 が流れる。
- 420 秒後から 540 秒後まで曲 3 が流れる。
- 540 秒後から 720 秒後まで曲 1 が流れる。
- 720 秒後から 960 秒後まで曲 2 が流れる。
- \qquad\vdots
600 秒後の時点で流れているのは曲 1 であり、流れ始めて 60 秒の時点です。
入力例 2
3 281 94 94 94
出力例 2
3 93
入力例 3
10 5678912340 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
出力例 3
6 678912340
Score : 300 points
Problem Statement
We have a playlist with N songs numbered 1, \dots, N.
Song i lasts A_i seconds.
When the playlist is played, song 1, song 2, \ldots, and song N play in this order. When song N ends, the playlist repeats itself, starting from song 1 again. While a song is playing, the next song does not play; when a song ends, the next song starts immediately.
At exactly T seconds after the playlist starts playing, which song is playing? Also, how many seconds have passed since the start of that song?
There is no input where the playlist changes songs at exactly T seconds after it starts playing.
Constraints
- 1 \leq N \leq 10^5
- 1 \leq T \leq 10^{18}
- 1 \leq A_i \leq 10^9
- The playlist does not change songs at exactly T seconds after it starts playing.
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N T A_1 \ldots A_N
Output
Print an integer representing the song that is playing at exactly T seconds after the playlist starts playing, and an integer representing the number of seconds that have passed since the start of that song, separated by a space.
Sample Input 1
3 600 180 240 120
Sample Output 1
1 60
When the playlist is played, the following happens. (Assume that it starts playing at time 0.)
- From time 0 to time 180, song 1 plays.
- From time 180 to time 420, song 2 plays.
- From time 420 to time 540, song 3 plays.
- From time 540 to time 720, song 1 plays.
- From time 720 to time 960, song 2 plays.
- \qquad\vdots
At time 600, song 1 is playing, and 60 seconds have passed since the start of that song.
Sample Input 2
3 281 94 94 94
Sample Output 2
3 93
Sample Input 3
10 5678912340 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
Sample Output 3
6 678912340
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 400 点
問題文
N \times N のマス目があります。上から i 行目、左から j 列目のマスを (i,j) と表します。
始め、(1,1) に駒が 1 個置かれています。あなたは以下の操作を何度でも行うことができます。
- 今駒が置かれているマスと距離がちょうど \sqrt{M} であるマスに駒を移動させる。
ここで、マス (i,j) とマス (k,l) の距離は \sqrt{(i-k)^2+(j-l)^2} とします。
全てのマス (i,j) に対して、以下の問題を解いてください。
- 駒を (1,1) から (i,j) に移動させることができるかを判定し、できる場合は操作回数の最小値を求めてください。
制約
- 1 \le N \le 400
- 1 \le M \le 10^6
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M
出力
N 行出力せよ。i 行目には N 個の整数を出力せよ。i 行目の j 個目の出力は、マス (i,j) に駒を移動させることができるのであれば操作回数の最小値を、そうでないのであれば -1 を出力せよ。
入力例 1
3 1
出力例 1
0 1 2 1 2 3 2 3 4
駒は上下左右の 4 個のマスに移動することができます。
例えば (2,2) に移動するには、以下のように 2 回の操作を行えばよいです。
- 今駒は (1,1) に置かれている。(1,1) と (1,2) の距離はちょうど \sqrt{1} であるため、駒を (1,2) に移動させる。
- 今駒は (1,2) に置かれている。(1,2) と (2,2) の距離はちょうど \sqrt{1} であるため、駒を (2,2) に移動させる。
入力例 2
10 5
出力例 2
0 3 2 3 2 3 4 5 4 5 3 4 1 2 3 4 3 4 5 6 2 1 4 3 2 3 4 5 4 5 3 2 3 2 3 4 3 4 5 6 2 3 2 3 4 3 4 5 4 5 3 4 3 4 3 4 5 4 5 6 4 3 4 3 4 5 4 5 6 5 5 4 5 4 5 4 5 6 5 6 4 5 4 5 4 5 6 5 6 7 5 6 5 6 5 6 5 6 7 6
Score : 400 points
Problem Statement
There is a grid with N \times N squares. We denote by (i, j) the square at the i-th row from the top and j-th column from the left.
Initially, a piece is placed on (1, 1). You may repeat the following operation any number of times:
- Let (i, j) be the square the piece is currently on. Move the piece to the square whose distance from (i, j) is exactly \sqrt{M}.
Here, we define the distance between square (i, j) and square (k, l) as \sqrt{(i-k)^2+(j-l)^2}.
For all squares (i, j), determine if the piece can reach (i, j). If it can, find the minimum number of operations required to do so.
Constraints
- 1 \le N \le 400
- 1 \le M \le 10^6
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N M
Output
Print N lines. The i-th line should contain N integers. If the piece can reach (i, j), the j-th integer in the i-th line should be the minimum number of operations required to do so; otherwise, it should be -1.
Sample Input 1
3 1
Sample Output 1
0 1 2 1 2 3 2 3 4
You can move the piece to four adjacent squares.
For example, we can move the piece to (2,2) with two operations as follows.
- The piece is now on (1,1). The distance between (1,1) and (1,2) is exactly \sqrt{1}, so move the piece to (1,2).
- The piece is now on (1,2). The distance between (1,2) and (2,2) is exactly \sqrt{1}, so move the piece to (2,2).
Sample Input 2
10 5
Sample Output 2
0 3 2 3 2 3 4 5 4 5 3 4 1 2 3 4 3 4 5 6 2 1 4 3 2 3 4 5 4 5 3 2 3 2 3 4 3 4 5 6 2 3 2 3 4 3 4 5 4 5 3 4 3 4 3 4 5 4 5 6 4 3 4 3 4 5 4 5 6 5 5 4 5 4 5 4 5 6 5 6 4 5 4 5 4 5 6 5 6 7 5 6 5 6 5 6 5 6 7 6
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 500 点
問題文
縦 H 行、横 W 行の H \times W マスからなるグリッドがあります。上から i 行目、左から j 列目のマスを (i, j) と表します。
はじめ、マス (x_1, y_1) にルークが置かれており、高橋君は以下の操作を K 回行います。
- 現在ルークが置かれているマスと行または列が同じマスにルークを移動させる。ただし、現在ルークが置かれているマスとは異なるマスに移動させる必要がある。
K 回の操作の後、ルークがマス (x_2, y_2) に置かれているようにする方法は何通りありますか?答えは非常に大きくなることがあるので、998244353 で割った余りを求めてください。
制約
- 2 \leq H, W \leq 10^9
- 1 \leq K \leq 10^6
- 1 \leq x_1, x_2 \leq H
- 1 \leq y_1, y_2 \leq W
入力
入力は以下の形式で標準入力から与えられる。
H W K x_1 y_1 x_2 y_2
出力
K 回の操作の後、ルークがマス (x_2, y_2) に置かれているようにする方法の総数を 998244353 で割った余りを出力せよ。
入力例 1
2 2 2 1 2 2 1
出力例 1
2
以下の 2 通りです。
- 1 回目の操作でルークをマス (1, 2) からマス (1, 1) へ動かし、2 回目の操作でルークをマス (1, 1) からマス (2, 1) に動かす。
- 1 回目の操作でルークをマス (1, 2) からマス (2, 2) へ動かし、2 回目の操作でルークをマス (2, 2) からマス (2, 1) に動かす。
入力例 2
1000000000 1000000000 1000000 1000000000 1000000000 1000000000 1000000000
出力例 2
24922282
998244353 で割った余りを求めなければならないことに注意して下さい。
入力例 3
3 3 3 1 3 3 3
出力例 3
9
Score : 500 points
Problem Statement
There is a H \times W-square grid with H horizontal rows and W vertical columns. Let (i, j) denote the square at the i-th row from the top and j-th column from the left.
The grid has a rook, initially on (x_1, y_1). Takahashi will do the following operation K times.
- Move the rook to a square that shares the row or column with the square currently occupied by the rook. Here, it must move to a square different from the current one.
How many ways are there to do the K operations so that the rook will be on (x_2, y_2) in the end? Since the answer can be enormous, find it modulo 998244353.
Constraints
- 2 \leq H, W \leq 10^9
- 1 \leq K \leq 10^6
- 1 \leq x_1, x_2 \leq H
- 1 \leq y_1, y_2 \leq W
Input
Input is given from Standard Input in the following format:
H W K x_1 y_1 x_2 y_2
Output
Print the number of ways to do the K operations so that the rook will be on (x_2, y_2) in the end, modulo 998244353.
Sample Input 1
2 2 2 1 2 2 1
Sample Output 1
2
We have the following two ways.
- First, move the rook from (1, 2) to (1, 1). Second, move it from (1, 1) to (2, 1).
- First, move the rook from (1, 2) to (2, 2). Second, move it from (2, 2) to (2, 1).
Sample Input 2
1000000000 1000000000 1000000 1000000000 1000000000 1000000000 1000000000
Sample Output 2
24922282
Be sure to find the count modulo 998244353.
Sample Input 3
3 3 3 1 3 3 3
Sample Output 3
9
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 525 点
問題文
整数 X, Y が与えられます。X, Y は X \neq 0 と Y \neq 0 の少なくとも一方を満たします。
次の条件を全て満たす整数の組 (A, B) を発見してください。そのような整数の組が存在しない場合はそれを報告してください。
- -10^{18} \leq A, B \leq 10^{18}
- xy 平面上の点 (0, 0), (X, Y), (A, B) を頂点とする三角形の面積は 1
制約
- -10^{17} \leq X, Y \leq 10^{17}
- (X, Y) \neq (0, 0)
- X, Y は整数
入力
入力は以下の形式で標準入力から与えられる。
X Y
出力
条件を満たす整数の組 (A, B) が存在する場合は以下の形式で出力せよ。
A B
条件を満たす整数の組 (A, B) が存在しない場合は -1 を出力せよ。
入力例 1
3 5
出力例 1
1 1
点 (0, 0), (3, 5), (1, 1) を頂点とする三角形の面積は 1 です。よって (A, B) = (1, 1) は条件を満たします。
入力例 2
-2 0
出力例 2
0 1
入力例 3
8752654402832944 -6857065241301125
出力例 3
-1
Score: 525 points
Problem Statement
You are given integers X and Y, which satisfy at least one of X \neq 0 and Y \neq 0.
Find a pair of integers (A, B) that satisfies all of the following conditions. If no such pair exists, report so.
- -10^{18} \leq A, B \leq 10^{18}
- The area of the triangle with vertices at points (0, 0), (X, Y), (A, B) on the xy-plane is 1.
Constraints
- -10^{17} \leq X, Y \leq 10^{17}
- (X, Y) \neq (0, 0)
- X and Y are integers.
Input
The input is given from Standard Input in the following format:
X Y
Output
If there is a pair of integers (A, B) that satisfies the conditions, print it in the following format:
A B
Otherwise, print -1.
Sample Input 1
3 5
Sample Output 1
1 1
The area of the triangle with vertices at points (0, 0), (3, 5), (1, 1) is 1. Thus, (A, B) = (1, 1) satisfies the conditions.
Sample Input 2
-2 0
Sample Output 2
0 1
Sample Input 3
8752654402832944 -6857065241301125
Sample Output 3
-1