Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
A 以上 B 以下であるような C の倍数を、1 つ出力してください。
条件を満たす数が存在しない場合は -1
を出力してください。
制約
- 1 \leq A \leq B \leq 1000
- 1 \leq C \leq 1000
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
A B C
出力
答えを出力せよ。
条件を満たす数が存在しない場合は -1
を出力せよ。
入力例 1
123 456 100
出力例 1
200
300
や 400
も正解です。
入力例 2
630 940 314
出力例 2
-1
Score : 100 points
Problem Statement
Print a number between A and B (inclusive) that is a multiple of C.
If there is no such number, print -1
.
Constraints
- 1 \leq A \leq B \leq 1000
- 1 \leq C \leq 1000
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
A B C
Output
Print the answer.
If there is no number with the desired property, print -1
.
Sample Input 1
123 456 100
Sample Output 1
200
300
or 400
would also be accepted.
Sample Input 2
630 940 314
Sample Output 2
-1
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
整数 A,B が K 進法表記で与えられます。
A \times B を 10 進法表記で出力してください。
注記
K 進法表記については、Wikipedia「位取り記数法」 を参照してください。
制約
- 2 \leq K \leq 10
- 1 \leq A,B \leq 10^5
- A,B は K 進法表記で与えられる
入力
入力は以下の形式で標準入力から与えられる。
K A B
出力
答えを出力せよ。
入力例 1
2 1011 10100
出力例 1
220
2 進法表記の 1011
を 、10 進法表記すると 11 です。
2 進法表記の 10100
を、 10 進法表記すると 20 です。
11 \times 20 = 220 なので 220 を出力します。
入力例 2
7 123 456
出力例 2
15642
7 進法表記の 123
を 、10 進法表記すると 66 です。
7 進法表記の 456
を、 10 進法表記すると 237 です。
66 \times 237 = 15642 なので 15642 を出力します。
Score : 200 points
Problem Statement
You are given integers A and B, in base K.
Print A \times B in decimal.
Notes
For base-K representation, see Wikipedia's article on Positional notation.
Constraints
- 2 \leq K \leq 10
- 1 \leq A,B \leq 10^5
- A and B are in base-K representation.
Input
Input is given from Standard Input in the following format:
K A B
Output
Print the answer.
Sample Input 1
2 1011 10100
Sample Output 1
220
1011
in base 2 corresponds to 11 in base 10.
10100
in base 2 corresponds to 20 in base 10.
We have 11 \times 20 = 220, so print 220.
Sample Input 2
7 123 456
Sample Output 2
15642
123
in base 7 corresponds to 66 in base 10.
456
in base 7 corresponds to 237 in base 10.
We have 66 \times 237 = 15642, so print 15642.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
長さ N の正整数のみからなる数列 A=(A_1,\dots,A_N) があります。
A を 10^{100} 回連結した数列を数列 B とします。
B の項を前から順に足したとき、和が初めて X を超えるのは何項目まで足したときですか?
すなわち、以下の式を満たす最小の整数 k を求めてください。
\displaystyle{\sum_{i=1}^{k} B_i \gt X}
制約
- 1 \leq N \leq 10^5
- 1 \leq A_i \leq 10^9
- 1 \leq X \leq 10^{18}
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 \ldots A_N X
出力
答えを出力せよ。
入力例 1
3 3 5 2 26
出力例 1
8
B=(3,5,2,3,5,2,3,5,2,\dots) です。
\displaystyle{\sum_{i=1}^{8} B_i = 28 \gt 26} であり、k が 7 以下のとき条件を満たさないので、8 が答えです。
入力例 2
4 12 34 56 78 1000
出力例 2
23
Score : 300 points
Problem Statement
We have a sequence of N positive integers: A=(A_1,\dots,A_N).
Let B be the concatenation of 10^{100} copies of A.
Consider summing up the terms of B from left to right. When does the sum exceed X for the first time?
In other words, find the minimum integer k such that:
\displaystyle{\sum_{i=1}^{k} B_i \gt X}.
Constraints
- 1 \leq N \leq 10^5
- 1 \leq A_i \leq 10^9
- 1 \leq X \leq 10^{18}
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A_1 \ldots A_N X
Output
Print the answer.
Sample Input 1
3 3 5 2 26
Sample Output 1
8
We have B=(3,5,2,3,5,2,3,5,2,\dots).
\displaystyle{\sum_{i=1}^{8} B_i = 28 \gt 26} holds, but the condition is not satisfied when k is 7 or less, so the answer is 8.
Sample Input 2
4 12 34 56 78 1000
Sample Output 2
23
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
0 以上 9 以下の整数からなる長さ N の数列 A=(A_1,\dots,A_N) があり、この順に左から右に並んでいます。
数列の長さが 1 になるまで、操作 F または操作 G を繰り返し行います。
- 操作 F :左端の 2 つの値 ( x,y とする ) を削除した後、一番左に (x+y)\%10 を挿入する
- 操作 G :左端の 2 つの値 ( x,y とする ) を削除した後、一番左に (x\times y)\%10 を挿入する
なお、a\%b は a を b で割った余りを意味します。
K=0,1,\dots,9 について、以下の問題に答えてください。
操作手順としてあり得るものは 2^{N-1} 通りありますが、このうち最終的に残る値が K となる操作手順は何通りありますか?
ただし答えは非常に大きくなる可能性があるので、998244353 で割った余りを求めてください。
制約
- 2 \leq N \leq 10^5
- 0 \leq A_i \leq 9
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 \dots A_N
出力
答えを 10 行に出力せよ。
ただし、i 行目には K=i-1 としたときの答えを出力せよ。
入力例 1
3 2 7 6
出力例 1
1 0 0 0 2 1 0 0 0 0
1 回目に操作 F 、2 回目に操作 F を行ったとき:数列は (2,7,6)→(9,6)→(5) となります。
1 回目に操作 F 、2 回目に操作 G を行ったとき:数列は (2,7,6)→(9,6)→(4) となります。
1 回目に操作 G 、2 回目に操作 F を行ったとき:数列は (2,7,6)→(4,6)→(0) となります。
1 回目に操作 G 、2 回目に操作 G を行ったとき:数列は (2,7,6)→(4,6)→(4) となります。
入力例 2
5 0 1 2 3 4
出力例 2
6 0 1 1 4 0 1 1 0 2
Score : 400 points
Problem Statement
We have a sequence of N integers between 0 and 9 (inclusive): A=(A_1, \dots, A_N), arranged from left to right in this order.
Until the length of the sequence becomes 1, we will repeatedly do the operation F or G below.
- Operation F: delete the leftmost two values (let us call them x and y) and then insert (x+y)\%10 to the left end.
- Operation G: delete the leftmost two values (let us call them x and y) and then insert (x\times y)\%10 to the left end.
Here, a\%b denotes the remainder when a is divided by b.
For each K=0,1,\dots,9, answer the following question.
Among the 2^{N-1} possible ways in which we do the operations, how many end up with K being the final value of the sequence?
Since the answer can be enormous, find it modulo 998244353.
Constraints
- 2 \leq N \leq 10^5
- 0 \leq A_i \leq 9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A_1 \dots A_N
Output
Print ten lines.
The i-th line should contain the answer for the case K=i-1.
Sample Input 1
3 2 7 6
Sample Output 1
1 0 0 0 2 1 0 0 0 0
If we do Operation F first and Operation F second: the sequence becomes (2,7,6)→(9,6)→(5).
If we do Operation F first and Operation G second: the sequence becomes (2,7,6)→(9,6)→(4).
If we do Operation G first and Operation F second: the sequence becomes (2,7,6)→(4,6)→(0).
If we do Operation G first and Operation G second: the sequence becomes (2,7,6)→(4,6)→(4).
Sample Input 2
5 0 1 2 3 4
Sample Output 2
6 0 1 1 4 0 1 1 0 2
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
2^N-1 頂点からなる木があります。
頂点には 1 から 2^N-1 の番号がつけられており、各 1\leq i < 2^{N-1} について、
- 頂点 i と頂点 2i を結ぶ無向辺
- 頂点 i と頂点 2i+1 を結ぶ無向辺
が存在します。これら以外の辺はありません。
2 頂点間の距離を、その 2 頂点を結ぶ単純パスに含まれる辺の個数とします。
頂点の組 (i,j) であって、距離が D であるようなものの個数を 998244353 で割った余りを求めてください。
制約
- 2 \leq N \leq 10^6
- 1 \leq D \leq 2\times 10^6
- 入力に含まれる値は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N D
出力
答えを出力せよ。
入力例 1
3 2
出力例 1
14
与えられる木は以下の図のようなものです。
距離が 2 であるような頂点の組は (1,4),(1,5),(1,6),(1,7),(2,3),(3,2),(4,1),(4,5),(5,1),(5,4),(6,1),(6,7),(7,1),(7,6) の 14 組存在します。
入力例 2
14142 17320
出力例 2
11284501
Score : 500 points
Problem Statement
We have a tree with 2^N-1 vertices.
The vertices are numbered 1 through 2^N-1. For each 1\leq i < 2^{N-1}, the following edges exist:
- an undirected edge connecting Vertex i and Vertex 2i,
- an undirected edge connecting Vertex i and Vertex 2i+1.
There is no other edge.
Let the distance between two vertices be the number of edges in the simple path connecting those two vertices.
Find the number, modulo 998244353, of pairs of vertices (i, j) such that the distance between them is D.
Constraints
- 2 \leq N \leq 10^6
- 1 \leq D \leq 2\times 10^6
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N D
Output
Print the answer.
Sample Input 1
3 2
Sample Output 1
14
The following figure describes the given tree.
There are 14 pairs of vertices such that the distance between them is 2: (1,4),(1,5),(1,6),(1,7),(2,3),(3,2),(4,1),(4,5),(5,1),(5,4),(6,1),(6,7),(7,1),(7,6).
Sample Input 2
14142 17320
Sample Output 2
11284501
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
N 頂点の木が与えられます。頂点には 1,2,\ldots ,N の番号がついており、i 番目の辺は頂点 u_i,v_i を結ぶ無向辺です。
各整数 i\,(1 \leq i \leq N) に対して、\sum_{j=1}^{N}dis(i,j) を求めてください。
ただし、dis(i,j) は頂点 i から頂点 j に到達する際にたどる必要のある最小の辺数です。
制約
- 2 \leq N \leq 2 \times 10^5
- 1 \leq u_i < v_i \leq N
- 与えられるグラフは木
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N u_1 v_1 u_2 v_2 \vdots u_{N-1} v_{N-1}
出力
N 行出力せよ。
i 行目には \sum_{j=1}^{N}dis(i,j) を出力せよ。
入力例 1
3 1 2 2 3
出力例 1
3 2 3
dis(1,1)+dis(1,2)+dis(1,3)=0+1+2=3、
dis(2,1)+dis(2,2)+dis(2,3)=1+0+1=2、
dis(3,1)+dis(3,2)+dis(3,3)=2+1+0=3、
です。
入力例 2
2 1 2
出力例 2
1 1
入力例 3
6 1 6 1 5 1 3 1 4 1 2
出力例 3
5 9 9 9 9 9
Score : 500 points
Problem Statement
Given is a tree with N vertices. The vertices are numbered 1,2,\ldots ,N, and the i-th edge is an undirected edge connecting Vertices u_i and v_i.
For each integer i\,(1 \leq i \leq N), find \sum_{j=1}^{N}dis(i,j).
Here, dis(i,j) denotes the minimum number of edges that must be traversed to go from Vertex i to Vertex j.
Constraints
- 2 \leq N \leq 2 \times 10^5
- 1 \leq u_i < v_i \leq N
- The given graph is a tree.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N u_1 v_1 u_2 v_2 \vdots u_{N-1} v_{N-1}
Output
Print N lines.
The i-th line should contain \sum_{j=1}^{N}dis(i,j).
Sample Input 1
3 1 2 2 3
Sample Output 1
3 2 3
We have:
dis(1,1)+dis(1,2)+dis(1,3)=0+1+2=3,
dis(2,1)+dis(2,2)+dis(2,3)=1+0+1=2,
dis(3,1)+dis(3,2)+dis(3,3)=2+1+0=3.
Sample Input 2
2 1 2
Sample Output 2
1 1
Sample Input 3
6 1 6 1 5 1 3 1 4 1 2
Sample Output 3
5 9 9 9 9 9
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
xy 平面上に N 個の点があり、それぞれの点に重みがついています。
i 個目の点の座標は (X_i,Y_i) で、重みは C_i です。
N 点の中から 4 点を選んで、それらを頂点とする面積が正の等脚台形を作ります。
このとき、選んだ 4 点の重みの和の最大値はいくつですか?
等脚台形を作ることができないときは -1
と出力してください。
なお、等脚台形とは以下の条件を全て満たす四角形のことです。
- 台形である
- 平行な 2 つの辺のうち、1 つの辺の両端の角が等しい
制約
- 4 \leq N \leq 1000
- -10^9 \leq X_i,Y_i \leq 10^9
- 1 \leq C_i \leq 10^9
- i \neq j ならば (X_i,Y_i) \neq (X_j,Y_j)
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N X_1 Y_1 C_1 X_2 Y_2 C_2 \vdots X_N Y_N C_N
出力
答えを出力せよ。
入力例 1
5 0 3 10 3 3 10 -1 0 10 2 0 10000 4 0 10
出力例 1
40
点 1,2,3,5 を選ぶことで等脚台形を作ることができ、点の重みの和は 40 です。
それ以外の点の選び方では等脚台形を作ることはできません。
入力例 2
6 0 1 1 1 4 20 2 7 300 5 6 4000 4 3 50000 3 0 600000
出力例 2
650021
正方形や長方形も等脚台形に含まれることに注意してください。
入力例 3
7 -3 0 1 -2 0 1 -1 0 1 0 0 1 1 0 1 2 0 1 3 0 1
出力例 3
-1
等脚台形を作ることはできません。
Score : 600 points
Problem Statement
In the xy-plane, we have N points, each assigned a weight.
The i-th point has the coordinates (X_i,Y_i) and the weight C_i.
We will choose four of the N points to form an isosceles trapezoid whose vertices are the chosen points.
What is the maximum possible total weight of the points chosen here?
If it is impossible to form an isosceles trapezoid, print -1
.
We remind you that an isosceles trapezoid is a quadrilateral that satisfies all of the following conditions.
- It is a trapezoid.
- For one of the two parallel sides, the two angles at its ends are equal.
Constraints
- 4 \leq N \leq 1000
- -10^9 \leq X_i,Y_i \leq 10^9
- 1 \leq C_i \leq 10^9
- (X_i,Y_i) \neq (X_j,Y_j) if i \neq j.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N X_1 Y_1 C_1 X_2 Y_2 C_2 \vdots X_N Y_N C_N
Output
Print the answer.
Sample Input 1
5 0 3 10 3 3 10 -1 0 10 2 0 10000 4 0 10
Sample Output 1
40
We can choose Points 1, 2, 3, 5 to form an isosceles trapezoid, with the points having a total weight of 40.
Any other way to choose points would not form an isosceles trapezoid.
Sample Input 2
6 0 1 1 1 4 20 2 7 300 5 6 4000 4 3 50000 3 0 600000
Sample Output 2
650021
Note that a square and a rectangle are also isosceles trapezoids.
Sample Input 3
7 -3 0 1 -2 0 1 -1 0 1 0 0 1 1 0 1 2 0 1 3 0 1
Sample Output 3
-1
We cannot form an isosceles trapezoid.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
AtCoder 町は N カ所の交差点と、M 本の道からなります。
道 i は、交差点 A_i と交差点 B_i を結んでいます。
髙橋町長は、AtCoder 町の交差点に 0 個以上の監視カメラを設置することにしました。
各交差点に設置することのできる監視カメラの数は、 0 個または 1 個です。
監視カメラの設置方法は 2^N 通りありますが、このうち監視されている道が偶数本になる設置方法は何通りありますか?
ただし、以下の条件が満たされるときに、道 i は監視されていると言います。
交差点 A_i と交差点 B_i の一方または両方に監視カメラが設置されている
制約
- 2 \leq N \leq 40
- 1 \leq M \leq \frac{N(N-1)}{2}
- 1 \leq A_i \lt B_i \leq N
- i \neq j ならば (A_i,B_i) \neq (A_j,B_j)
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 B_1 A_2 B_2 \vdots A_M B_M
出力
答えを出力せよ。
入力例 1
3 2 1 2 2 3
出力例 1
6
監視カメラを設置する交差点として、 \{ \} , \{ 2 \} , \{ 1,2 \} ,\{1,3\},\{2,3\},\{1,2,3\} を選んだ場合に条件を満たします。
監視カメラを 1 つも設置しなくても良いことに注意してください。
入力例 2
20 3 5 6 3 4 1 2
出力例 2
458752
AtCoder 町は連結とは限りません。
Score : 600 points
Problem Statement
AtCoder Town has N intersections and M roads.
Road i connects Intersections A_i and B_i.
Takahashi, the mayor, has decided to install zero or more surveillance cameras at the intersections.
Each intersection can be installed with zero or one surveillance camera.
How many of the 2^N ways to install surveillance cameras monitor an even number of roads?
Here, Road i is said to be monitored when the following condition is satisfied:
a surveillance camera is installed at one or both of Intersections A_i and B_i.
Constraints
- 2 \leq N \leq 40
- 1 \leq M \leq \frac{N(N-1)}{2}
- 1 \leq A_i \lt B_i \leq N
- (A_i,B_i) \neq (A_j,B_j) if i \neq j.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M A_1 B_1 A_2 B_2 \vdots A_M B_M
Output
Print the answer.
Sample Input 1
3 2 1 2 2 3
Sample Output 1
6
The sets of towns to install surveillance cameras to satisfy the condition are: \{ \} , \{ 2 \} , \{ 1,2 \} ,\{1,3\},\{2,3\},\{1,2,3\}.
Note that it is allowed to install no surveillance camera.
Sample Input 2
20 3 5 6 3 4 1 2
Sample Output 2
458752
The town may not be connected.