Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
高橋君が 3 つのサイコロを振ったところ、出た目はそれぞれ a, b, c でした。
これらのサイコロについて、出た目とは反対の面が表す整数を足し合わせた値を求めてください。
ただし、高橋君が振るサイコロは全て一般的な立方体の 6 面ダイスであり、ある面とその反対側の面が表す整数を足すと 7 になります。
制約
- 1 \leq a, b, c \leq 6
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
a b c
出力
3 つのサイコロについて、出た目とは反対の面が表す整数を足し合わせた値を出力せよ。
入力例 1
1 4 3
出力例 1
13
出た目とは反対の面に書かれた整数はそれぞれ 6, 3, 4 です。 6 + 3 + 4 = 13 であるので、これを出力します。
入力例 2
5 6 4
出力例 2
6
Score : 100 points
Problem Statement
Takahashi has rolled three dice. They are showing numbers a, b, and c on the top faces.
Find the sum of the numbers on the bottom faces.
Here, each of these dice is a standard cubic die, where the sum of the numbers on opposite faces is 7.
Constrains
- 1 \leq a, b, c \leq 6
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
a b c
Output
Print the sum of the numbers on the bottom faces of the three dice.
Sample Input 1
1 4 3
Sample Output 1
13
The numbers on the bottom faces are 6, 3, and 4. We have 6 + 3 + 4 = 13, which should be printed.
Sample Input 2
5 6 4
Sample Output 2
6
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
0
、1
、6
、8
、9
からなる文字列 S が与えられます。
S を 180 度回転したものを出力してください。すなわち、S に次の操作を施してできる文字列を出力してください。
- S を反転する。
0
を0
に、1
を1
に、6
を9
に、8
を8
に、9
を6
に変換する。
制約
- 1 \leq |S| \leq 10^5
- S は
0
、1
、6
、8
、9
からなる。
入力
入力は以下の形式で標準入力から与えられる。
S
出力
S を 180 度回転した文字列を出力せよ。
入力例 1
0601889
出力例 1
6881090
0601889
を 180 度回転すると 6881090
になります。
入力例 2
86910
出力例 2
01698
入力例 3
01010
出力例 3
01010
S が変化しないこともあります。
Score : 200 points
Problem Statement
You are given a string S consisting of 0
, 1
, 6
, 8
, and 9
.
Rotate S 180 degrees and print the result. In other words, apply the following operations on S and print the resulting string:
- Reverse S.
- Replace each
0
with a0
, each1
with a1
, each6
with a9
, each8
with an8
, and each9
with a6
.
Constraints
- 1 \leq |S| \leq 10^5
- S consists of
0
,1
,6
,8
, and9
.
Input
Input is given from Standard Input in the following format:
S
Output
Print the result of rotating S 180 degrees.
Sample Input 1
0601889
Sample Output 1
6881090
Rotating 0601889
180 degrees results in 6881090
.
Sample Input 2
86910
Sample Output 2
01698
Sample Input 3
01010
Sample Output 3
01010
S may remain the same.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
1 以上 N 以下の整数からなる長さ N の数列 A = (A_1, A_2, \dots, A_N), B = (B_1, B_2, \dots, B_N), C = (C_1, C_2, \dots, C_N) が与えられます。
1 以上 N 以下の整数 i, j の組 (i, j) であって、A_i = B_{C_j} となるものの総数を求めてください。
制約
- 1 \leq N \leq 10^5
- 1 \leq A_i, B_i, C_i \leq N
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \ldots A_N B_1 B_2 \ldots B_N C_1 C_2 \ldots C_N
出力
A_i = B_{C_j} となる (i, j) の総数を出力せよ。
入力例 1
3 1 2 2 3 1 2 2 3 2
出力例 1
4
条件を満たす組は (1, 1), (1, 3), (2, 2), (3, 2) の 4 つです。
入力例 2
4 1 1 1 1 1 1 1 1 1 2 3 4
出力例 2
16
全ての組が条件を満たします。
入力例 3
3 2 3 3 1 3 3 1 1 1
出力例 3
0
条件を満たす組は存在しません。
Score : 300 points
Problem Statement
Given are three sequences of length N each: A = (A_1, A_2, \dots, A_N), B = (B_1, B_2, \dots, B_N), and C = (C_1, C_2, \dots, C_N), consisting of integers between 1 and N (inclusive).
How many pairs (i, j) of integers between 1 and N (inclusive) satisfy A_i = B_{C_j}?
Constraints
- 1 \leq N \leq 10^5
- 1 \leq A_i, B_i, C_i \leq N
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A_1 A_2 \ldots A_N B_1 B_2 \ldots B_N C_1 C_2 \ldots C_N
Output
Print the number of pairs (i, j) such that A_i = B_{C_j}.
Sample Input 1
3 1 2 2 3 1 2 2 3 2
Sample Output 1
4
Four pairs satisfy the condition: (1, 1), (1, 3), (2, 2), (3, 2).
Sample Input 2
4 1 1 1 1 1 1 1 1 1 2 3 4
Sample Output 2
16
All the pairs satisfy the condition.
Sample Input 3
3 2 3 3 1 3 3 1 1 1
Sample Output 3
0
No pair satisfies the condition.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
A 個の a
と B 個の b
からなる長さ A + B の文字列のうち、辞書順で K 番目のものを求めてください。
制約
- 1 \leq A, B \leq 30
- A 個の
a
と B 個のb
からなる長さ A + B の文字列の総数を S 個とおいたとき、1 \leq K \leq S - 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
A B K
出力
答えを出力せよ。
入力例 1
2 2 4
出力例 1
baab
2 個の a
と 2 個の b
からなる文字列を辞書順に並べると、aabb
、abab
、abba
、baab
、baba
、bbaa
となります。
よって、4 番目である baab
を出力します。
入力例 2
30 30 118264581564861424
出力例 2
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
K の値は 32 bit 整数に収まらないことがあります。
Score : 400 points
Problem Statement
Among the strings of length A + B containing A occurrences of a
and B occurrences of b
, find the string that comes K-th in the lexicographical order.
Constraints
- 1 \leq A, B \leq 30
- 1 \leq K \leq S, where S is the number of strings of length A + B containing A occurrences of
a
and B occurrences ofb
. - All values in input are integers.
Input
Input is given from Standard Input in the following format:
A B K
Output
Print the answer.
Sample Input 1
2 2 4
Sample Output 1
baab
Here are the strings containing two a
s and two b
s in the lexicographical order: aabb
, abab
, abba
, baab
, baba
, and bbaa
.
The fourth string, baab
, should be printed.
Sample Input 2
30 30 118264581564861424
Sample Output 2
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
K may not fit into a 32-bit integer type.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
N 頂点の根付き木があり、頂点は 1, 2, \dots, N と番号付けられています。
頂点 1 が根であり、頂点 i \, (2 \leq i \leq N) の親は P_i です。
Q 個のクエリが与えられます。i \, (1 \leq i \leq Q) 番目のクエリでは、整数 U_i, D_i が与えられるので、次の条件を全て満たす頂点 u の個数を求めてください。
- u から根への最短パス上(端点も含む)に頂点 U_i が存在する。
- u から根への最短パスに含まれる辺の数がちょうど D_i である。
制約
- 2 \leq N \leq 2 \times 10^5
- 1 \leq P_i < i
- 1 \leq Q \leq 2 \times 10^5
- 1 \leq U_i \leq N
- 0 \leq D_i \leq N - 1
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
N P_2 P_3 \ldots P_N Q U_1 D_1 U_2 D_2 \vdots U_Q D_Q
出力
Q 行出力せよ。 i 行目には i 番目のクエリに対する答えを出力せよ。
入力例 1
7 1 1 2 2 4 2 4 1 2 7 2 4 1 5 5
出力例 1
3 1 0 0
1 番目のクエリでは、頂点 4, 5, 7 が条件を満たします。 2 番目のクエリでは、頂点 7 のみが条件を満たします。 3 番目、4 番目のクエリでは、条件を満たす頂点は存在しません。
Score : 500 points
Problem Statement
We have a rooted tree with N vertices, numbered 1, 2, \dots, N.
Vertex 1 is the root, and the parent of Vertex i \, (2 \leq i \leq N) is Vertex P_i.
You are given Q queries. In the i-th query (1 \leq i \leq Q), given integers U_i and D_i, find the number of vertices u that satisfy all of the following conditions:
- Vertex U_i is in the shortest path from u to the root (including the endpoints).
- There are exactly D_i edges in the shortest path from u to the root.
Constraints
- 2 \leq N \leq 2 \times 10^5
- 1 \leq P_i < i
- 1 \leq Q \leq 2 \times 10^5
- 1 \leq U_i \leq N
- 0 \leq D_i \leq N - 1
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N P_2 P_3 \ldots P_N Q U_1 D_1 U_2 D_2 \vdots U_Q D_Q
Output
Print Q lines. The i-th line should contain the response to the i-th query.
Sample Input 1
7 1 1 2 2 4 2 4 1 2 7 2 4 1 5 5
Sample Output 1
3 1 0 0
In the 1-st query, Vertices 4, 5, and 7 satisfy the conditions. In the 2-nd query, only Vertices 7 satisfies the conditions. In the 3-rd and 4-th queries, no vertice satisfies the conditions.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
平面上に N 個の点 P_1, P_2, \dots, P_N があり、P_i の座標は (X_i, Y_i) です。どの 3 点も同一直線上にないことが分かっています。
要素数が 3 以上であるような \{ P_1, P_2, \dots, P_N \} の部分集合 S に対し、S の凸包を次のように定義します。
- S に含まれる全ての点を周上または内部に含むような凸多角形のうち、面積が最小のもの。
凸包の面積が整数となるような S の総数を (10^9 + 7) で割ったあまりを求めてください。
制約
- 3 \leq N \leq 80
- 0 \leq |X_i|, |Y_i| \leq 10^4
- どの 3 点も同一直線上にない。
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
N X_1 Y_1 X_2 Y_2 \vdots X_N Y_N
出力
答えを出力せよ。(10^9 + 7) で割ったあまりを求めることに注意すること。
入力例 1
4 0 0 1 2 0 1 1 0
出力例 1
2
\{ P_1, P_2, P_4 \}, \{ P_2, P_3, P_4 \} が条件を満たします。
入力例 2
23 -5255 7890 5823 7526 5485 -113 7302 5708 9149 2722 4904 -3918 8566 -3267 -3759 2474 -7286 -1043 -1230 1780 3377 -7044 -2596 -6003 5813 -9452 -9889 -7423 2377 1811 5351 4551 -1354 -9611 4244 1958 8864 -9889 507 -8923 6948 -5016 -6139 2769 4103 9241
出力例 2
4060436
Score : 600 points
Problem Statement
We have N points P_1, P_2, \dots, P_N on a plane. The coordinates of P_i is (X_i, Y_i). We know that no three points lie on the same line.
For a subset S of \{ P_1, P_2, \dots, P_N \} with at least three elements, let us define the convex hull of S as follows:
- The convex hull is the convex polygon with the minimum area such that every point of S is within or on the circumference of that polygon.
Find the number, modulo (10^9 + 7), of subsets S such that the area of the convex hull is an integer.
Constraints
- 3 \leq N \leq 80
- 0 \leq |X_i|, |Y_i| \leq 10^4
- No three points lie on the same line.
- All values in input are integers.
Input
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. Note that you are asked to find the count modulo (10^9 + 7).
Sample Input 1
4 0 0 1 2 0 1 1 0
Sample Output 1
2
\{ P_1, P_2, P_4 \} and \{ P_2, P_3, P_4 \} satisfy the condition.
Sample Input 2
23 -5255 7890 5823 7526 5485 -113 7302 5708 9149 2722 4904 -3918 8566 -3267 -3759 2474 -7286 -1043 -1230 1780 3377 -7044 -2596 -6003 5813 -9452 -9889 -7423 2377 1811 5351 4551 -1354 -9611 4244 1958 8864 -9889 507 -8923 6948 -5016 -6139 2769 4103 9241
Sample Output 2
4060436