Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
1 以上 K 以下の正の整数から、偶数と奇数ひとつずつの組を選ぶ方法の個数を求めてください。なお、選ぶ順番は考慮しません。
制約
- 2\leq K\leq 100
- K は整数である
入力
入力は以下の形式で標準入力から与えられる。
K
出力
1 以上 K 以下の正の整数から、偶数と奇数ひとつずつの組を選ぶ方法の個数を出力せよ。
入力例 1
3
出力例 1
2
(2,1) と (2,3) が条件を満たします。
入力例 2
6
出力例 2
9
入力例 3
11
出力例 3
30
入力例 4
50
出力例 4
625
Score : 100 points
Problem Statement
Find the number of ways to choose a pair of an even number and an odd number from the positive integers between 1 and K (inclusive). The order does not matter.
Constraints
- 2\leq K\leq 100
- K is an integer.
Input
Input is given from Standard Input in the following format:
K
Output
Print the number of ways to choose a pair of an even number and an odd number from the positive integers between 1 and K (inclusive).
Sample Input 1
3
Sample Output 1
2
Two pairs can be chosen: (2,1) and (2,3).
Sample Input 2
6
Sample Output 2
9
Sample Input 3
11
Sample Output 3
30
Sample Input 4
50
Sample Output 4
625
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
xy 平面上に正方形があり、4 つの頂点の座標は反時計回りに順番に (x_1,y_1),(x_2,y_2),(x_3,y_3),(x_4,y_4) です。 なお、x 軸は右向きに、y 軸は上向きに取ることにします。
高橋君は、これら 4 つの座標のうち (x_3,y_3),(x_4,y_4) を忘れてしまいました。
x_1,x_2,y_1,y_2 が与えられるので、x_3,y_3,x_4,y_4 を復元してください。なお、これらの条件から、x_3,y_3,x_4,y_4 は一意に存在し、整数となることが証明できます。
制約
- |x_1|,|y_1|,|x_2|,|y_2| \leq 100
- (x_1,y_1) ≠ (x_2,y_2)
- 入力はすべて整数である
入力
入力は以下の形式で標準入力から与えられる。
x_1 y_1 x_2 y_2
出力
x_3,y_3,x_4,y_4 をこの順に整数で出力せよ。
入力例 1
0 0 0 1
出力例 1
-1 1 -1 0
4 点 (0,0),(0,1),(-1,1),(-1,0) は、この順に正方形を反時計回りに見たときの 4 頂点をなします。 (x_3,y_3)=(1,1),(x_4,y_4)=(1,0) は、頂点が時計回りに並んでいるので適さないことに注意してください。
入力例 2
2 3 6 6
出力例 2
3 10 -1 7
入力例 3
31 -41 -59 26
出力例 3
-126 -64 -36 -131
Score : 200 points
Problem Statement
There is a square in the xy-plane. The coordinates of its four vertices are (x_1,y_1),(x_2,y_2),(x_3,y_3) and (x_4,y_4) in counter-clockwise order. (Assume that the positive x-axis points right, and the positive y-axis points up.)
Takahashi remembers (x_1,y_1) and (x_2,y_2), but he has forgot (x_3,y_3) and (x_4,y_4).
Given x_1,x_2,y_1,y_2, restore x_3,y_3,x_4,y_4. It can be shown that x_3,y_3,x_4 and y_4 uniquely exist and have integer values.
Constraints
- |x_1|,|y_1|,|x_2|,|y_2| \leq 100
- (x_1,y_1) ≠ (x_2,y_2)
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
x_1 y_1 x_2 y_2
Output
Print x_3,y_3,x_4 and y_4 as integers, in this order.
Sample Input 1
0 0 0 1
Sample Output 1
-1 1 -1 0
(0,0),(0,1),(-1,1),(-1,0) is the four vertices of a square in counter-clockwise order. Note that (x_3,y_3)=(1,1),(x_4,y_4)=(1,0) is not accepted, as the vertices are in clockwise order.
Sample Input 2
2 3 6 6
Sample Output 2
3 10 -1 7
Sample Input 3
31 -41 -59 26
Sample Output 3
-126 -64 -36 -131
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
整数 N,K が与えられます。N 以下の正の整数の組 (a,b,c) であって、a+b,b+c,c+a がすべて K の倍数であるようなものの個数を求めてください。 ただし、a,b,c の順番を入れ替えただけの組も異なるものとして数えます。また、a,b,c の中に同じものがあっても構いません。
制約
- 1 \leq N,K \leq 2\times 10^5
- N,K は整数である
入力
入力は以下の形式で標準入力から与えられる。
N K
出力
N 以下の正の整数の組 (a,b,c) であって、a+b,b+c,c+a がすべて K の倍数であるようなものの個数を出力せよ。
入力例 1
3 2
出力例 1
9
(1,1,1),(1,1,3),(1,3,1),(1,3,3),(2,2,2),(3,1,1),(3,1,3),(3,3,1),(3,3,3) が条件を満たします。
入力例 2
5 3
出力例 2
1
入力例 3
31415 9265
出力例 3
27
入力例 4
35897 932
出力例 4
114191
Score : 300 points
Problem Statement
You are given integers N and K. Find the number of triples (a,b,c) of positive integers not greater than N such that a+b,b+c and c+a are all multiples of K. The order of a,b,c does matter, and some of them can be the same.
Constraints
- 1 \leq N,K \leq 2\times 10^5
- N and K are integers.
Input
Input is given from Standard Input in the following format:
N K
Output
Print the number of triples (a,b,c) of positive integers not greater than N such that a+b,b+c and c+a are all multiples of K.
Sample Input 1
3 2
Sample Output 1
9
(1,1,1),(1,1,3),(1,3,1),(1,3,3),(2,2,2),(3,1,1),(3,1,3),(3,3,1) and (3,3,3) satisfy the condition.
Sample Input 2
5 3
Sample Output 2
1
Sample Input 3
31415 9265
Sample Output 3
27
Sample Input 4
35897 932
Sample Output 4
114191
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 700 点
問題文
整数 L が与えられます。以下の条件を満たす有向グラフをひとつ構成してください。構成したグラフに多重辺が含まれていても構いません。 なお、条件を満たす有向グラフは必ず存在することが証明できます。
- 頂点数 N は 20 以下で、すべての頂点には 1 以上 N 以下の相異なる番号が付けられている
- 辺数 M は 60 以下で、すべての辺には 0 以上 10^6 以下の整数の長さが付けられている
- 全ての辺は番号の小さい方の頂点から大きい方の頂点に向かって向きづけられている。すなわち、1,2,...,N はこのグラフの頂点の番号を適当なトポロジカル順序で並べてできる列である
- 頂点 1 から頂点 N への異なるパスはちょうど L 個あり、それらの長さは 0 から L-1 までの相異なる整数である
ただし、パスの長さとは、そのパス上の辺の長さの和を表します。また、2 つのパスが異なるとは、パス上の辺の集合が異なることを指します。
制約
- 2 \leq L \leq 10^6
- L は整数である
入力
入力は以下の形式で標準入力から与えられる。
L
出力
1 行目には、構成したグラフの頂点数 N と辺数 M を出力せよ。 続く M 行のうちの i 行目には、3 つの整数 u_i,v_i,w_i を出力せよ。これらはそれぞれ、i 本目の辺の始点、i 本目の辺の終点、i 本目の辺の長さを表す。 解が複数考えられる場合、どれを出力してもよい。
入力例 1
4
出力例 1
8 10 1 2 0 2 3 0 3 4 0 1 5 0 2 6 0 3 7 0 4 8 0 5 6 1 6 7 1 7 8 1
出力例のグラフには 頂点 1 から N=8 への 4 本のパスがあり、
- パス 1 → 2 → 3 → 4 → 8 の長さは 0
- パス 1 → 2 → 3 → 7 → 8 の長さは 1
- パス 1 → 2 → 6 → 7 → 8 の長さは 2
- パス 1 → 5 → 6 → 7 → 8 の長さは 3
となります。これ以外にも、正答として認められる出力があります。
入力例 2
5
出力例 2
5 7 1 2 0 2 3 1 3 4 0 4 5 0 2 4 0 1 3 3 3 5 1
Score : 700 points
Problem Statement
You are given an integer L. Construct a directed graph that satisfies the conditions below. The graph may contain multiple edges between the same pair of vertices. It can be proved that such a graph always exists.
- The number of vertices, N, is at most 20. The vertices are given ID numbers from 1 to N.
- The number of edges, M, is at most 60. Each edge has an integer length between 0 and 10^6 (inclusive).
- Every edge is directed from the vertex with the smaller ID to the vertex with the larger ID. That is, 1,2,...,N is one possible topological order of the vertices.
- There are exactly L different paths from Vertex 1 to Vertex N. The lengths of these paths are all different, and they are integers between 0 and L-1.
Here, the length of a path is the sum of the lengths of the edges contained in that path, and two paths are considered different when the sets of the edges contained in those paths are different.
Constraints
- 2 \leq L \leq 10^6
- L is an integer.
Input
Input is given from Standard Input in the following format:
L
Output
In the first line, print N and M, the number of the vertices and edges in your graph. In the i-th of the following M lines, print three integers u_i,v_i and w_i, representing the starting vertex, the ending vertex and the length of the i-th edge. If there are multiple solutions, any of them will be accepted.
Sample Input 1
4
Sample Output 1
8 10 1 2 0 2 3 0 3 4 0 1 5 0 2 6 0 3 7 0 4 8 0 5 6 1 6 7 1 7 8 1
In the graph represented by the sample output, there are four paths from Vertex 1 to N=8:
- 1 → 2 → 3 → 4 → 8 with length 0
- 1 → 2 → 3 → 7 → 8 with length 1
- 1 → 2 → 6 → 7 → 8 with length 2
- 1 → 5 → 6 → 7 → 8 with length 3
There are other possible solutions.
Sample Input 2
5
Sample Output 2
5 7 1 2 0 2 3 1 3 4 0 4 5 0 2 4 0 1 3 3 3 5 1