Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
整数 K が与えられます。
英大文字を A から昇順に K 個繋げて得られる文字列を答えてください。
制約
- K は 1 以上 26 以下の整数
入力
入力は以下の形式で標準入力から与えられる。
K
出力
答えを出力せよ。
入力例 1
3
出力例 1
ABC
英大文字は A から昇順に A, B, C, ... です。
A から昇順に 3 個繋げて得られる文字列は ABC です。
入力例 2
1
出力例 2
A
Score : 100 points
Problem Statement
You are given an integer K.
Print a string that is a concatenation of the first K uppercase English letters in ascending order, starting from A.
Constraints
- K is an integer between 1 and 26, inclusive.
Input
The input is given from Standard Input in the following format:
K
Output
Print the answer.
Sample Input 1
3
Sample Output 1
ABC
The uppercase English letters in ascending order are A, B, C, ...
By concatenating the first three uppercase English letters, we get ABC.
Sample Input 2
1
Sample Output 2
A
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
8 個の整数 S_1,S_2,\dots,S_8 が与えられます。
以下の 3 つの条件が全て満たされるならば Yes を、そうでないならば No を出力してください。
- 数列 (S_1,S_2,\dots,S_8) は広義単調増加である。すなわち、S_1 \leq S_2 \leq \dots \leq S_8 である。
- S_1,S_2,\dots,S_8 は全て 100 以上 675 以下である。
- S_1,S_2,\dots,S_8 は全て 25 の倍数である。
制約
- 0\leq S_i \leq 1000
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
S_1 S_2 \dots S_8
出力
答えを出力せよ。
入力例 1
125 175 250 300 400 525 600 650
出力例 1
Yes
3 つの条件を全て満たしています。
入力例 2
100 250 300 400 325 575 625 675
出力例 2
No
S_4 > S_5 であるため、1 つ目の条件を満たしていません。
入力例 3
0 23 24 145 301 413 631 632
出力例 3
No
2 つ目の条件と 3 つ目の条件を満たしていません。
Score : 100 points
Problem Statement
Given eight integers S_1,S_2,\dots, and S_8,
print Yes if they satisfy all of the following three conditions, and No otherwise.
- The sequence (S_1,S_2,\dots,S_8) is monotonically non-decreasing. In other words, S_1 \leq S_2 \leq \dots \leq S_8.
- S_1,S_2,\dots, and S_8 are all between 100 and 675, inclusive.
- S_1,S_2,\dots, and S_8 are all multiples of 25.
Constraints
- 0\leq S_i \leq 1000
- All input values are integers.
Input
The input is given from Standard Input in the following format:
S_1 S_2 \dots S_8
Output
Print the answer.
Sample Input 1
125 175 250 300 400 525 600 650
Sample Output 1
Yes
They satisfy all of the three conditions.
Sample Input 2
100 250 300 400 325 575 625 675
Sample Output 2
No
They violate the first condition because S_4 > S_5.
Sample Input 3
0 23 24 145 301 413 631 632
Sample Output 3
No
They violate the second and third conditions.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
-10^{18} 以上 10^{18} 以下の整数 X が与えられるので、\left\lceil \dfrac{X}{10} \right\rceil を出力してください。
ここで、\left\lceil a \right\rceil は a 以上の整数のうち最小のものを意味します。
制約
- -10^{18} \leq X \leq 10^{18}
- X は整数
入力
入力は以下の形式で標準入力から与えられる。
X
出力
\left\lceil \dfrac{X}{10} \right\rceil を整数として出力せよ。
入力例 1
27
出力例 1
3
\frac{27}{10} = 2.7 以上の整数は 3, 4, 5, \dots です。この中で一番小さい整数は 3 なので、\left \lceil \frac{27}{10} \right \rceil = 3 となります。
入力例 2
-13
出力例 2
-1
\frac{-13}{10} = -1.3 以上の整数は、全ての正整数および 0, -1 です。この中で一番小さい整数は -1 なので、\left \lceil \frac{-13}{10} \right \rceil = -1 となります。
入力例 3
40
出力例 3
4
\frac{40}{10} = 4 以上の整数で一番小さい整数は 4 自身です。
入力例 4
-20
出力例 4
-2
入力例 5
123456789123456789
出力例 5
12345678912345679
Score: 200 points
Problem Statement
Given an integer X between -10^{18} and 10^{18}, inclusive, print \left\lceil \dfrac{X}{10} \right\rceil.
Here, \left\lceil a \right\rceil denotes the smallest integer not less than a.
Constraints
- -10^{18} \leq X \leq 10^{18}
- X is an integer.
Input
The input is given from Standard Input in the following format:
X
Output
Print \left\lceil \dfrac{X}{10} \right\rceil as an integer.
Sample Input 1
27
Sample Output 1
3
The integers not less than \frac{27}{10} = 2.7 are 3, 4, 5, \dots. Among these, the smallest is 3, so \left \lceil \frac{27}{10} \right \rceil = 3.
Sample Input 2
-13
Sample Output 2
-1
The integers not less than \frac{-13}{10} = -1.3 are all positive integers, 0, and -1. Among these, the smallest is -1, so \left \lceil \frac{-13}{10} \right \rceil = -1.
Sample Input 3
40
Sample Output 3
4
The smallest integer not less than \frac{40}{10} = 4 is 4 itself.
Sample Input 4
-20
Sample Output 4
-2
Sample Input 5
123456789123456789
Sample Output 5
12345678912345679
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
x 軸の正の向きが右、y 軸の正の向きが上であるような xy 座標平面において、点 (a,b) を原点を中心として反時計回りに d 度回転させた点を求めてください。
制約
- -1000 \leq a,b \leq 1000
- 1 \leq d \leq 360
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
a b d
出力
求めるべき点を (a',b') とするとき、 a' と b' をこの順に空白区切りで出力せよ。
なお、各出力について、解との絶対誤差または相対誤差が 10^{−6} 以下であれば正解として扱われる。
入力例 1
2 2 180
出力例 1
-2 -2
(2,2) を原点を中心として反時計回りに 180 度回転させた点は、(2,2) を原点について対称な位置に移動させた点であり、(-2,-2) となります。
入力例 2
5 0 120
出力例 2
-2.49999999999999911182 4.33012701892219364908
(5,0) を原点を中心として反時計回りに 120 度回転させた点は (-\frac {5}{2} , \frac {5\sqrt{3}}{2}) です。
この例での出力はこれらの値と厳密には一致しませんが、誤差が十分に小さいため正解として扱われます。
入力例 3
0 0 11
出力例 3
0.00000000000000000000 0.00000000000000000000
(a,b) が原点(回転の中心)なので回転させても座標が変わりません。
入力例 4
15 5 360
出力例 4
15.00000000000000177636 4.99999999999999555911
360 度回転させたので座標が変わりません。
入力例 5
-505 191 278
出力例 5
118.85878514480690171240 526.66743699786547949770
Score : 200 points
Problem Statement
In an xy-coordinate plane whose x-axis is oriented to the right and whose y-axis is oriented upwards, rotate a point (a, b) around the origin d degrees counterclockwise and find the new coordinates of the point.
Constraints
- -1000 \leq a,b \leq 1000
- 1 \leq d \leq 360
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
a b d
Output
Let the new coordinates of the point be (a', b'). Print a' and b' in this order, with a space in between.
Your output will be considered correct when, for each value printed, the absolute or relative error from the answer is at most 10^{-6}.
Sample Input 1
2 2 180
Sample Output 1
-2 -2
When (2, 2) is rotated around the origin 180 degrees counterclockwise, it becomes the symmetric point of (2, 2) with respect to the origin, which is (-2, -2).
Sample Input 2
5 0 120
Sample Output 2
-2.49999999999999911182 4.33012701892219364908
When (5, 0) is rotated around the origin 120 degrees counterclockwise, it becomes (-\frac {5}{2} , \frac {5\sqrt{3}}{2}).
This sample output does not precisely match these values, but the errors are small enough to be considered correct.
Sample Input 3
0 0 11
Sample Output 3
0.00000000000000000000 0.00000000000000000000
Since (a, b) is the origin (the center of rotation), a rotation does not change its coordinates.
Sample Input 4
15 5 360
Sample Output 4
15.00000000000000177636 4.99999999999999555911
A 360-degree rotation does not change the coordinates of a point.
Sample Input 5
-505 191 278
Sample Output 5
118.85878514480690171240 526.66743699786547949770
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 250 点
問題文
長さ N の正整数列 A=(A_1,A_2,\dots,A_N) および正整数 K が与えられます。
1 以上 K 以下の整数のうち、A の中に一度も現れないものの総和を求めてください。
制約
- 1\leq N \leq 2\times 10^5
- 1\leq K \leq 2\times 10^9
- 1\leq A_i \leq 2\times 10^9
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N K A_1 A_2 \dots A_N
出力
答えを出力せよ。
入力例 1
4 5 1 6 3 1
出力例 1
11
1 以上 5 以下の整数のうち、A の中に一度も現れないものは 2,4,5 の 3 つです。
よって、それらの総和である 2+4+5=11 を出力します。
入力例 2
1 3 346
出力例 2
6
入力例 3
10 158260522 877914575 24979445 623690081 262703497 24979445 1822804784 1430302156 1161735902 923078537 1189330739
出力例 3
12523196466007058
Score: 250 points
Problem Statement
You are given a sequence of positive integers A=(A_1,A_2,\dots,A_N) of length N and a positive integer K.
Find the sum of the integers between 1 and K, inclusive, that do not appear in the sequence A.
Constraints
- 1\leq N \leq 2\times 10^5
- 1\leq K \leq 2\times 10^9
- 1\leq A_i \leq 2\times 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N K A_1 A_2 \dots A_N
Output
Print the answer.
Sample Input 1
4 5 1 6 3 1
Sample Output 1
11
Among the integers between 1 and 5, three numbers, 2, 4, and 5, do not appear in A.
Thus, print their sum: 2+4+5=11.
Sample Input 2
1 3 346
Sample Output 2
6
Sample Input 3
10 158260522 877914575 24979445 623690081 262703497 24979445 1822804784 1430302156 1161735902 923078537 1189330739
Sample Output 3
12523196466007058
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
長さ N の整数からなる数列 A=(A_1,\ldots,A_N) であって、以下の条件を全て満たすものは何通りありますか？
-
1\le A_i \le M (1 \le i \le N)
-
\displaystyle\sum _{i=1}^N A_i \leq K
ただし、答えは非常に大きくなることがあるので、答えを 998244353 で割った余りを求めてください。
制約
- 1 \leq N, M \leq 50
- N \leq K \leq NM
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M K
出力
答えを 998244353 で割った余りを出力せよ。
入力例 1
2 3 4
出力例 1
6
条件を満たす数列は以下の 6 つです。
- (1,1)
- (1,2)
- (1,3)
- (2,1)
- (2,2)
- (3,1)
入力例 2
31 41 592
出力例 2
798416518
答えを 998244353 で割った余りを出力してください。
Score : 300 points
Problem Statement
How many integer sequences of length N, A=(A_1, \ldots, A_N), satisfy all of the conditions below?
-
1\le A_i \le M (1 \le i \le N)
-
\displaystyle\sum _{i=1}^N A_i \leq K
Since the count can get enormous, find it modulo 998244353.
Constraints
- 1 \leq N, M \leq 50
- N \leq K \leq NM
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M K
Output
Print the answer.
Sample Input 1
2 3 4
Sample Output 1
6
The following six sequences satisfy the conditions.
- (1,1)
- (1,2)
- (1,3)
- (2,1)
- (2,2)
- (3,1)
Sample Input 2
31 41 592
Sample Output 2
798416518
Be sure to print the count modulo 998244353.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
スーパーマンである高橋くんは、地上で困っている人を助けるため、あるビルの屋上から飛び降りようとしています。 高橋くんがいる星には重力の大きさを表す g という値が定まっており、 高橋くんが落下を開始してから地面に到達するまでにかかる時間は \frac{A}{\sqrt{g}} です。
現在の時刻は 0 であり、g = 1 が成り立ちます。 高橋くんは、今から次の操作を好きな回数（0 回でもよい）行います。
- 超能力により g の値を 1 増やす。時間が B 経過する。
その後、高橋くんはビルから飛び降ります。落下を開始した後は g の値を変えることはできません。 また、操作によって経過する時間と落下にかかる時間以外は考えないものとします。
高橋くんが地面に到達できる最も早い時刻を求めてください。
制約
- 1 \leq A \leq 10^{18}
- 1 \leq B \leq 10^{18}
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
A B
出力
高橋くんが地面に到達できる最も早い時刻を出力せよ。 出力は、真の値との絶対誤差または相対誤差が 10^{-6} 以下のとき正解と判定される。
入力例 1
10 1
出力例 1
7.7735026919
- 操作を 0 回行うとき、地面に到達する時刻は 1\times 0+\frac{10}{\sqrt{1}} = 10 です。
- 操作を 1 回行うとき、地面に到達する時刻は 1\times 1+\frac{10}{\sqrt{2}} \fallingdotseq 8.07 です。
- 操作を 2 回行うとき、地面に到達する時刻は 1\times 2+\frac{10}{\sqrt{3}} \fallingdotseq 7.77 です。
- 操作を 3 回行うとき、地面に到達する時刻は 1\times 3+\frac{10}{\sqrt{4}} = 8 です。
操作を 4 回以上行っても、地面への到達時刻は遅くなるのみです。 よって、操作を 2 回行ってから飛び降りるのが最適で、答えは 2+\frac{10}{\sqrt{3}} です。
入力例 2
5 10
出力例 2
5.0000000000
操作を 1 回も行わないのが最適です。
入力例 3
1000000000000000000 100
出力例 3
8772053214538.5976562500
Score : 400 points
Problem Statement
A superman, Takahashi, is about to jump off the roof of a building to help a person in trouble on the ground. Takahashi's planet has a constant value g that represents the strength of gravity, and the time it takes for him to reach the ground after starting to fall is \frac{A}{\sqrt{g}}.
It is now time 0, and g = 1. Takahashi will perform the following operation as many times as he wants (possibly zero).
- Use a superpower to increase the value of g by 1. This takes a time of B.
Then, he will jump off the building. After starting to fall, he cannot change the value of g. Additionally, we only consider the time it takes to perform the operation and fall.
Find the earliest time Takahashi can reach the ground.
Constraints
- 1 \leq A \leq 10^{18}
- 1 \leq B \leq 10^{18}
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
A B
Output
Print the earliest time Takahashi can reach the ground. Your output will be accepted when its absolute or relative error from the true value is at most 10^{-6}.
Sample Input 1
10 1
Sample Output 1
7.7735026919
- If he performs the operation zero times, he will reach the ground at time 1\times 0+\frac{10}{\sqrt{1}} = 10.
- If he performs the operation once, he will reach the ground at time 1\times 1+\frac{10}{\sqrt{2}} \fallingdotseq 8.07.
- If he performs the operation twice, he will reach the ground at time 1\times 2+\frac{10}{\sqrt{3}} \fallingdotseq 7.77.
- If he performs the operation three times, he will reach the ground at time 1\times 3+\frac{10}{\sqrt{4}} = 8.
Performing the operation four or more times will only delay the time to reach the ground. Therefore, it is optimal to perform the operation twice before jumping off, and the answer is 2+\frac{10}{\sqrt{3}}.
Sample Input 2
5 10
Sample Output 2
5.0000000000
It is optimal not to perform the operation at all.
Sample Input 3
1000000000000000000 100
Sample Output 3
8772053214538.5976562500
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 500 点
問題文
長さ N の数列 A = (A_1, A_2, \dots, A_N) および整数 X, Y があります。 次の条件をすべて満たす整数の組 (L, R) の個数を求めてください。
- 1 \leq L \leq R \leq N
- A_L, A_{L+1}, \dots, A_R の最大値は X であり、最小値は Y である。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 2 \times 10^5
- 1 \leq Y \leq X \leq 2 \times 10^5
- 入力される値はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N X Y A_1 A_2 \dots A_N
出力
答えを出力せよ。
入力例 1
4 3 1 1 2 3 1
出力例 1
4
条件を満たすのは (L,R)=(1,3),(1,4),(2,4),(3,4) の 4 通りです。
入力例 2
5 2 1 1 3 2 4 1
出力例 2
0
条件を満たす (L,R) は存在しません。
入力例 3
5 1 1 1 1 1 1 1
出力例 3
15
X=Y である場合もあります。
入力例 4
10 8 1 2 7 1 8 2 8 1 8 2 8
出力例 4
36
Score : 500 points
Problem Statement
We have a number sequence A = (A_1, A_2, \dots, A_N) of length N and integers X and Y. Find the number of pairs of integers (L, R) satisfying all the conditions below.
- 1 \leq L \leq R \leq N
- The maximum value of A_L, A_{L+1}, \dots, A_R is X, and the minimum is Y.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 2 \times 10^5
- 1 \leq Y \leq X \leq 2 \times 10^5
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N X Y A_1 A_2 \dots A_N
Output
Print the answer.
Sample Input 1
4 3 1 1 2 3 1
Sample Output 1
4
4 pairs satisfy the conditions: (L,R)=(1,3),(1,4),(2,4),(3,4).
Sample Input 2
5 2 1 1 3 2 4 1
Sample Output 2
0
No pair (L,R) satisfies the condition.
Sample Input 3
5 1 1 1 1 1 1 1
Sample Output 3
15
It may hold that X=Y.
Sample Input 4
10 8 1 2 7 1 8 2 8 1 8 2 8
Sample Output 4
36
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 500 点
問題文
S+T 頂点 M 辺の単純無向グラフ G があります。頂点には 1 から S+T の番号が、辺には 1 から M の番号が割り振られています。辺 i は頂点 u_i と頂点 v_i を結んでいます。
また、頂点集合 V_1 = \lbrace 1, 2,\dots, S\rbrace および V_2 = \lbrace S+1, S+2, \dots, S+T \rbrace はともに独立集合です。
長さ 4 のサイクルを 4-cycle と呼びます。
G が 4-cycle を含む場合、4-cycle をどれか 1 つ選び、選んだサイクルに含まれる頂点を出力してください。頂点を出力する順番は自由です。
G が 4-cycle を含まない場合、 -1 を出力してください。
独立集合とは？
グラフ G の独立集合とは、G に含まれるいくつかの頂点からなる集合 V' であって、V' に含まれる任意の 2 つの頂点の間に辺がないものを言います。制約
- 2 \leq S \leq 3 \times 10^5
- 2 \leq T \leq 3000
- 4 \leq M \leq \min(S \times T,3 \times 10^5)
- 1 \leq u_i \leq S
- S + 1 \leq v_i \leq S + T
- i \neq j ならば (u_i, v_i) \neq (u_j, v_j)
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
S T M u_1 v_1 u_2 v_2 \vdots u_M v_M
出力
G が 4-cycle を含む場合は、任意の 4-cycle を 1 つ選び、選んだサイクルに含まれている相異なる 4 個の頂点の番号を出力せよ。(頂点の順番は問わない。)
G が 4-cycle を含まない場合は -1 を出力せよ。
入力例 1
2 3 5 1 3 1 4 1 5 2 4 2 5
出力例 1
1 2 4 5
頂点 1 と 4 、4 と 2、2 と 5、5 と 1 の間に辺があるので 頂点 1,2,4,5 は 4-cycle をなします。よって 1, 2, 4, 5 を出力すればよいです。
頂点を出力する順番は自由で、出力例のほかにも例えば 2 5 1 4 のような出力も正答となります。
入力例 2
3 2 4 1 4 1 5 2 5 3 5
出力例 2
-1
G が 4-cycle を含まない入力もあります。
入力例 3
4 5 9 3 5 1 8 3 7 1 9 4 6 2 7 4 8 1 7 2 9
出力例 3
1 7 2 9
Score : 500 points
Problem Statement
We have a simple undirected graph G with (S+T) vertices and M edges. The vertices are numbered 1 through (S+T), and the edges are numbered 1 through M. Edge i connects Vertices u_i and v_i.
Here, vertex sets V_1 = \lbrace 1, 2,\dots, S\rbrace and V_2 = \lbrace S+1, S+2, \dots, S+T \rbrace are both independent sets.
A cycle of length 4 is called a 4-cycle.
If G contains a 4-cycle, choose any of them and print the vertices in the cycle. You may print the vertices in any order.
If G does not contain a 4-cycle, print -1.
What is an independent set?
An independent set of a graph G is a set V' of some of the vertices in G such that no two vertices of V' have an edge between them.Constraints
- 2 \leq S \leq 3 \times 10^5
- 2 \leq T \leq 3000
- 4 \leq M \leq \min(S \times T,3 \times 10^5)
- 1 \leq u_i \leq S
- S + 1 \leq v_i \leq S + T
- If i \neq j, then (u_i, v_i) \neq (u_j, v_j).
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
S T M u_1 v_1 u_2 v_2 \vdots u_M v_M
Output
If G contains a 4-cycle, choose any of them, and print the indices of the four distinct vertices in the cycle. (The order of the vertices does not matter.)
If G does not contain a 4-cycle, print -1.
Sample Input 1
2 3 5 1 3 1 4 1 5 2 4 2 5
Sample Output 1
1 2 4 5
There are edges between Vertices 1 and 4, 4 and 2, 2 and 5, and 5 and 1, so Vertices 1, 2, 4, and 5 form a 4-cycle. Thus, 1, 2, 4, and 5 should be printed.
The vertices may be printed in any order. Besides the Sample Output, 2 5 1 4 is also considered correct, for example.
Sample Input 2
3 2 4 1 4 1 5 2 5 3 5
Sample Output 2
-1
Some inputs may give G without a 4-cycle.
Sample Input 3
4 5 9 3 5 1 8 3 7 1 9 4 6 2 7 4 8 1 7 2 9
Sample Output 3
1 7 2 9