Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
収縮期血圧 A と拡張期血圧 B が与えられます。
平均血圧 C を求めてください。
ただし、平均血圧は以下のように定義されるとします。
- C = \frac{A-B}{3} +B
制約
- 50 \leq B \leq A \leq 300
- 入力に含まれる値は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
A B
出力
C を出力せよ。
出力値と想定解答の絶対誤差または相対誤差が 10^{-5} 以下であれば正解と判定される。
入力例 1
130 100
出力例 1
110
C = \frac{130-100}{3} +100 = 10 + 100 = 110 となります。
入力例 2
300 50
出力例 2
133.3333333
入力される値は全て整数ですが、出力する値は整数とは限らないことに注意してください。
入力例 3
123 123
出力例 3
123
Score : 100 points
Problem Statement
You are given a person's systolic blood pressure, A, and diastolic blood pressure, B.
Find the mean arterial pressure, C, which we define as follows:
- C = \frac{A-B}{3} +B.
Constraints
- 50 \leq B \leq A \leq 300
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
A B
Output
Print the value C.
Your output is considered correct when its absolute or relative error from our answer is at most 10^{-5}.
Sample Input 1
130 100
Sample Output 1
110
We have C = \frac{130-100}{3} +100 = 10 + 100 = 110.
Sample Input 2
300 50
Sample Output 2
133.3333333
Note that although all the values in input are integers, the value to output may not be an integer.
Sample Input 3
123 123
Sample Output 3
123
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
4 つの文字列 S_1, S_2, S_3, S_4 が与えられます。
この中に、H , 2B , 3B , HR がそれぞれ 1 つずつあるか判定してください。
ただし、全ての S_i は H , 2B , 3B , HR のいずれかと一致します。
制約
- S_i は
H,2B,3B,HRのいずれかと一致する
入力
入力は以下の形式で標準入力から与えられる。
S_1 S_2 S_3 S_4
出力
H , 2B , 3B , HR がそれぞれ 1 つずつあるならば Yes と出力せよ。
そうでないならば No と出力せよ。
入力例 1
3B HR 2B H
出力例 1
Yes
H , 2B , 3B , HR がそれぞれ 1 つずつあります。
入力例 2
2B 3B HR 3B
出力例 2
No
H がありません。
Score : 200 points
Problem Statement
You are given four strings S_1, S_2, S_3, and S_4.
Determine whether this sequence of strings has one of each of the following: H, 2B, 3B, and HR.
Here, it is guaranteed that every S_i is H, 2B, 3B, or HR.
Constraints
- Each S_i is
H,2B,3B, orHR.
Input
Input is given from Standard Input in the following format:
S_1 S_2 S_3 S_4
Output
If the given sequence of strings has one of each of H, 2B, 3B, and HR, print Yes.
Otherwise, print No.
Sample Input 1
3B HR 2B H
Sample Output 1
Yes
We have one of each of H, 2B, 3B, and HR.
Sample Input 2
2B 3B HR 3B
Sample Output 2
No
We have no H.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
文字列 S が与えられます。
このうち 8 文字を選び下線を引き、下線を引いた文字が左から順に c , h , o , k , u , d , a , i となるようにする方法は何通りありますか？
ただし答えは非常に大きくなる可能性があるので、(10^9 + 7) で割った余りを出力してください。
制約
- 8 \leq |S| \leq 10^5
- S は英小文字からなる
入力
入力は以下の形式で標準入力から与えられる。
S
出力
答えを (10^9 + 7) で割った余りを出力せよ。
入力例 1
chchokudai
出力例 1
3
chchokudai
chchokudai
chchokudai
上の 3 つが条件を満たします。
chchokudai
は、条件を満たさないことに注意してください。
入力例 2
atcoderrr
出力例 2
0
答えが 0 通りになることもあります。
入力例 3
chokudaichokudaichokudai
出力例 3
45
Score : 300 points
Problem Statement
You are given a string S.
How many ways are there to choose and underline eight of its characters so that those characters read c, h, o, k, u, d, a, i from left to right?
Since the count can be enormous, print it modulo (10^9 + 7).
Constraints
- 8 \leq |S| \leq 10^5
- S consists of lowercase English letters.
Input
Input is given from Standard Input in the following format:
S
Output
Print the number of ways modulo (10^9 + 7).
Sample Input 1
chchokudai
Sample Output 1
3
We have three valid ways:
chchokudai
chchokudai
chchokudai
while the following is invalid:
chchokudai
Sample Input 2
atcoderrr
Sample Output 2
0
The answer may be 0.
Sample Input 3
chokudaichokudaichokudai
Sample Output 3
45
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
AtCoder 国には 1 から N の番号がついた N 個の都市と、1 から M の番号がついた M 個の道路があります。
道路 i を通ると都市 A_i と都市 B_i の間を双方向に 1 時間で移動することができます。
都市 1 から都市 N へ最も早く移動することができる経路は何通りありますか？
答えは非常に大きくなる可能性があるので (10^9+7) で割ったあまりを求めてください。
制約
- 2 \leq N \leq 2\times 10^5
- 0 \leq M \leq 2\times 10^5
- 1 \leq A_i < B_i \leq N
- (A_i,B_i) は相異なる
- 入力に含まれる値は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 B_1 \vdots A_M B_M
出力
答えを出力せよ。
都市 1 から都市 N へ移動することが出来ない場合は 0 と出力せよ。
入力例 1
4 5 2 4 1 2 2 3 1 3 3 4
出力例 1
2
都市 1 から都市 4 へは最短 2 時間で移動することができ、それを実現する経路は 1 \to 2 \to 4 と 1 \to 3 \to 4 の 2 つです。
入力例 2
4 3 1 3 2 3 2 4
出力例 2
1
都市 1 から都市 4 へは最短 3 時間で移動することができ、それを実現する経路は 1 \to 3 \to 2 \to 4 の 1 つです。
入力例 3
2 0
出力例 3
0
都市 1 から都市 2 に移動することはできません。この場合 0 を出力してください。
入力例 4
7 8 1 3 1 4 2 3 2 4 2 5 2 6 5 7 6 7
出力例 4
4
Score : 400 points
Problem Statement
The Republic of AtCoder has N cities numbered 1 through N and M roads numbered 1 through M.
Using Road i, you can travel from City A_i to B_i or vice versa in one hour.
How many paths are there in which you can get from City 1 to City N as early as possible?
Since the count can be enormous, print it modulo (10^9 + 7).
Constraints
- 2 \leq N \leq 2\times 10^5
- 0 \leq M \leq 2\times 10^5
- 1 \leq A_i < B_i \leq N
- The pairs (A_i, B_i) are distinct.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M A_1 B_1 \vdots A_M B_M
Output
Print the answer. If it is impossible to get from City 1 to City N, print 0.
Sample Input 1
4 5 2 4 1 2 2 3 1 3 3 4
Sample Output 1
2
The shortest time needed to get from City 1 to City 4 is 2 hours, which is achieved by two paths: 1 \to 2 \to 4 and 1 \to 3 \to 4.
Sample Input 2
4 3 1 3 2 3 2 4
Sample Output 2
1
The shortest time needed to get from City 1 to City 4 is 3 hours, which is achieved by one path: 1 \to 3 \to 2 \to 4.
Sample Input 3
2 0
Sample Output 3
0
It is impossible to get from City 1 to City 2, in which case you should print 0.
Sample Input 4
7 8 1 3 1 4 2 3 2 4 2 5 2 6 5 7 6 7
Sample Output 4
4
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
N 行 N 列のマス目が与えられ、上から i 番目、左から j 番目のマスは、S_{i, j} が # なら黒く塗られており、. なら白く塗られています。
あなたは白く塗られたマスのうち、ちょうど K 個のマスを選んで赤く塗ります。以下の条件が満たされる塗り方は何通りありますか？
- 赤く塗られたマス(以下赤マスと呼ぶ)は連結である。すなわち、どの赤マスからどの赤マスへも赤マスのみを上下左右に辿って到達できる。
制約
- 1 \leq N \leq 8
- 1 \leq K \leq 8
- S_{i, j} は
#または. - N , K は整数である
入力
入力は以下の形式で標準入力から与えられる。
N
K
S_{1, 1}S_{1, 2} \dots S_{1, N}
S_{2, 1}S_{2, 2} \dots S_{2, N}
\vdots
S_{N, 1}S_{N, 2} \dots S_{N, N}
出力
答えを出力せよ。
入力例 1
3 5 #.# ... ..#
出力例 1
5
#.# #@# #@# #@# #@# @@@ .@@ @@. @@@ @@@ @@# @@# @@# .@# @.#
上のように条件を満たす塗り方が 5 通りあります。
赤マスを @ で表しました。
#@# @.@ @@#
上の塗り方は連結でないので条件を満たしません。
斜めのマス同士は連結していないことに注意してください。
入力例 2
2 2 #. .#
出力例 2
0
条件を満たす塗り方はありません。
入力例 3
8 8 ........ ........ ........ ........ ........ ........ ........ ........
出力例 3
64678
Score : 500 points
Problem Statement
You are given a grid with N rows and N columns, where the square at the i-th row from the top and j-th column from the left is painted black if S_{i, j} is # and white if S_{i, j} is ..
You will choose K of the white squares and paint them red. How many such ways to paint the grid satisfy the following condition?
- The squares painted red will be connected. That is, you will be able to get from any red square to any red square by repeatedly moving horizontally or vertically while only visiting red squares.
Constraints
- 1 \leq N \leq 8
- 1 \leq K \leq 8
- Each S_{i, j} is
#or.. - N and K are integers.
Input
Input is given from Standard Input in the following format:
N
K
S_{1, 1}S_{1, 2} \dots S_{1, N}
S_{2, 1}S_{2, 2} \dots S_{2, N}
\vdots
S_{N, 1}S_{N, 2} \dots S_{N, N}
Output
Print the answer.
Sample Input 1
3 5 #.# ... ..#
Sample Output 1
5
We have five ways to satisfy the condition as shown below, where @ stands for a red square.
#.# #@# #@# #@# #@# @@@ .@@ @@. @@@ @@@ @@# @@# @@# .@# @.#
Note that the way shown below does not satisfy the connectivity requirement since we do not consider diagonal adjacency.
#@# @.@ @@#
Sample Input 2
2 2 #. .#
Sample Output 2
0
There is no way to satisfy the condition.
Sample Input 3
8 8 ........ ........ ........ ........ ........ ........ ........ ........
Sample Output 3
64678
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
xy 平面上に N 個の多角形があります。
これらの多角形は、全ての辺が x 軸または y 軸に平行で、全ての角が 90 度または 270 度で、かつ単純です。
i 個目の多角形は M_i 個の頂点からなり、j 番目の頂点は (x_{i, j}, y_{i, j}) です。
多角形の辺は j 番目の頂点と j+1 番目の頂点を結んでできる線分です(ただし M_i+1 番目の頂点は 1 番目の頂点とします)。
多角形が単純とは
連続しないどの 2 辺も共通部分を持たない(すなわち交差も接触もしない)とき、その多角形を単純といいます。
Q 個のクエリが与えられます。 i = 1, 2, \dots, Q について、i 個目のクエリは以下の通りです。
- N 個の多角形のうち、点 (X_i + 0.5, Y_i + 0.5) を内部に含むものはいくつありますか？
制約
- 1 \leq N \leq 10^5
- 4 \leq M_i \leq 10^5
- M_i は偶数
- \sum_i M_i \leq 4 \times 10^5
- 0 \leq x_{i, j}, y_{i, j} \leq 10^5
- j \neq k ならば (x_{i, j}, y_{i, j}) \neq (x_{i, k}, y_{i, k})
- j = 1, 3, \dots M_i-1 について、x_{i, j} = x_{i, j+1}
- j = 2, 4, \dots M_i について、y_{i, j} = y_{i, j+1} (ただし、y_{i, M_i +1} = y_{i, 1} とする)
- 与えられる多角形は単純
- 1 \leq Q \leq 10^5
- 0 \leq X_i, Y_i \lt 10^5
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N
M_1
x_{1, 1} y_{1, 1} x_{1, 2} y_{1, 2} \dots x_{1, M_1} y_{1, M_1}
M_2
x_{2, 1} y_{2, 1} x_{2, 2} y_{2, 2} \dots x_{2, M_2} y_{2, M_2}
\vdots
M_N
x_{N, 1} y_{N, 1} x_{N, 2} y_{N, 2} \dots x_{N, M_N} y_{N, M_N}
Q
X_1 Y_1
X_2 Y_2
\vdots
X_Q Y_Q
出力
Q 行出力せよ。
i 行目には、i 個目のクエリに対する答えを出力せよ。
入力例 1
3 4 1 2 1 4 3 4 3 2 4 2 5 2 3 5 3 5 5 4 5 6 5 5 3 5 3 6 3 1 4 2 3 4 5
出力例 1
0 2 1
異なる多角形同士は、交差したり接触したりする可能性があることに注意してください。
入力例 2
2 4 12 3 12 5 0 5 0 3 12 1 1 1 9 10 9 10 0 4 0 4 6 6 6 6 2 8 2 8 7 2 7 2 1 4 2 6 4 4 6 3 1 8
出力例 2
0 2 1 1
多角形は単純ですが、凸多角形とは限りません。
Score : 600 points
Problem Statement
We have N polygons on the xy-plane.
Every side of these polygons is parallel to the x- or y-axis, and every interior angle is 90 or 270 degrees. All of these polygons are simple.
The i-th polygon has M_i corners, the j-th of which is (x_{i, j}, y_{i, j}).
The sides of this polygon are segments connecting the j-th and (j+1)-th corners. (Assume that (M_i+1)-th corner is the 1-st corner.)
A polygon is simple when...
for any two of its sides that are not adjacent, they do not intersect (cross or touch) each other.
You are given Q queries. For each i = 1, 2, \dots, Q, the i-th query is as follows.
- Among the N polygons, how many have the point (X_i + 0.5, Y_i + 0.5) inside them?
Constraints
- 1 \leq N \leq 10^5
- 4 \leq M_i \leq 10^5
- Each M_i is even.
- \sum_i M_i \leq 4 \times 10^5
- 0 \leq x_{i, j}, y_{i, j} \leq 10^5
- (x_{i, j}, y_{i, j}) \neq (x_{i, k}, y_{i, k}) if j \neq k.
- x_{i, j} = x_{i, j+1} for j = 1, 3, \dots M_i-1.
- y_{i, j} = y_{i, j+1} for j = 2, 4, \dots M_i. (Assume y_{i, M_i +1} = y_{i, 1}.)
- The given polygons are simple.
- 1 \leq Q \leq 10^5
- 0 \leq X_i, Y_i \lt 10^5
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
M_1
x_{1, 1} y_{1, 1} x_{1, 2} y_{1, 2} \dots x_{1, M_1} y_{1, M_1}
M_2
x_{2, 1} y_{2, 1} x_{2, 2} y_{2, 2} \dots x_{2, M_2} y_{2, M_2}
\vdots
M_N
x_{N, 1} y_{N, 1} x_{N, 2} y_{N, 2} \dots x_{N, M_N} y_{N, M_N}
Q
X_1 Y_1
X_2 Y_2
\vdots
X_Q Y_Q
Output
Print Q lines.
The i-th line should contain the answer to the i-th query.
Sample Input 1
3 4 1 2 1 4 3 4 3 2 4 2 5 2 3 5 3 5 5 4 5 6 5 5 3 5 3 6 3 1 4 2 3 4 5
Sample Output 1
0 2 1
Note that different polygons may cross or touch each other.
Sample Input 2
2 4 12 3 12 5 0 5 0 3 12 1 1 1 9 10 9 10 0 4 0 4 6 6 6 6 2 8 2 8 7 2 7 2 1 4 2 6 4 4 6 3 1 8
Sample Output 2
0 2 1 1
Although the polygons are simple, they may not be convex.