Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
長さ N の正整数列 a = (a_1, a_2, \dots, a_N) には何種類の整数が現れますか？
制約
- 1 \leq N \leq 1000
- 1 \leq a_i \leq 10^9 \, (1 \leq i \leq N)
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N a_1 \ldots a_N
出力
答えを出力せよ。
入力例 1
6 1 4 1 2 2 1
出力例 1
3
1, 2, 4 の 3 種類の整数が現れます。
入力例 2
1 1
出力例 2
1
入力例 3
11 3 1 4 1 5 9 2 6 5 3 5
出力例 3
7
Score : 200 points
Problem Statement
In a sequence of N positive integers a = (a_1, a_2, \dots, a_N), how many different integers are there?
Constraints
- 1 \leq N \leq 1000
- 1 \leq a_i \leq 10^9 \, (1 \leq i \leq N)
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N a_1 \ldots a_N
Output
Print the answer.
Sample Input 1
6 1 4 1 2 2 1
Sample Output 1
3
There are three different integers: 1, 2, 4.
Sample Input 2
1 1
Sample Output 2
1
Sample Input 3
11 3 1 4 1 5 9 2 6 5 3 5
Sample Output 3
7
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
N 人の学生が試験を受けました。学生には学生 1, 学生 2, \dots, 学生 N と番号がついていて、学生 i は a_i 点を取りました。
P 点未満の点数を取った学生は "不可" となり単位を取得できません。 "不可" となった学生の人数を答えてください。
制約
- 1 \leq N \leq 10^5
- 1 \leq P \leq 100
- 0 \leq a_i \leq 100 (1 \leq i \leq N)
- 入力はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N P a_1 a_2 \dots a_N
出力
"不可" となった学生の人数を出力せよ。
入力例 1
4 50 80 60 40 0
出力例 1
2
学生 1 は 80 点、学生 2 は 60 点と、 50 点以上の点数を取っているので "不可" とならず単位を取得できています。
一方、学生 3 は 40 点、学生 4 は 0 点で、 50 点を下回る点数を取っているので "不可" となります。よって答えは 2 人です。
入力例 2
3 90 89 89 89
出力例 2
3
入力例 3
2 22 6 37
出力例 3
1
Score : 200 points
Problem Statement
N students took an exam. The students are labeled as Student 1, Student 2, \dots, Student N, and Student i scored a_i points.
A student who scored less than P points are considered to have failed the exam and cannot earn the credit. Find the number of students who failed the exam.
Constraints
- 1 \leq N \leq 10^5
- 1 \leq P \leq 100
- 0 \leq a_i \leq 100 (1 \leq i \leq N)
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N P a_1 a_2 \dots a_N
Output
Print the number of students who failed the exam.
Sample Input 1
4 50 80 60 40 0
Sample Output 1
2
Students 1 and 2, who scored 80 and 60 points, respectively, succeeded in scoring at least 50 points to earn the credit.
On the other hand, Students 3 and 4, who scored 40 and 0 points, respectively, fell below 50 points and failed the exam. Thus, the answer is 2.
Sample Input 2
3 90 89 89 89
Sample Output 2
3
Sample Input 3
2 22 6 37
Sample Output 3
1
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
整数 N が与えられるので、以下の条件を全て満たす整数 X の個数を 998244353 で割った余りを求めてください。
- N 桁の正整数である。
- X の各桁を上の位から順に X_1,X_2,\dots,X_N とする。このとき以下の条件を全て満たす。
- 全ての整数 1 \le i \le N に対して、 1 \le X_i \le 9
- 全ての整数 1 \le i \le N-1 に対して、 |X_i-X_{i+1}| \le 1
制約
- N は整数
- 2 \le N \le 10^6
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを整数として出力せよ。
入力例 1
4
出力例 1
203
4 桁の整数として、例えば 1111,1234,7878,6545 が問題文中の条件を満たします。
入力例 2
2
出力例 2
25
入力例 3
1000000
出力例 3
248860093
998244353 で割った余りを求めることに注意してください。
Score : 300 points
Problem Statement
Given an integer N, find the number of integers X that satisfy all of the following conditions, modulo 998244353.
- X is an N-digit positive integer.
- Let X_1,X_2,\dots,X_N be the digits of X from top to bottom. They satisfy all of the following:
- 1 \le X_i \le 9 for all integers 1 \le i \le N;
- |X_i-X_{i+1}| \le 1 for all integers 1 \le i \le N-1.
Constraints
- N is an integer.
- 2 \le N \le 10^6
Input
Input is given from Standard Input in the following format:
N
Output
Print the answer as an integer.
Sample Input 1
4
Sample Output 1
203
Some of the 4-digit integers satisfying the conditions are 1111,1234,7878,6545.
Sample Input 2
2
Sample Output 2
25
Sample Input 3
1000000
Sample Output 3
248860093
Be sure to find the count modulo 998244353.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
2 次元グリッド上に 2 つの図形 S と T があります。グリッドは正方形のマスからなります。
S は N 行 N 列のグリッド内にあり、S_{i,j} が # であるようなマス全体からなります。
T も N 行 N 列のグリッド内にあり、T_{i,j} が # であるようなマス全体からなります。
S と T を 90 度回転及び平行移動の繰り返しによって一致させることができるか判定してください。
制約
- 1 \leq N \leq 200
- S,T は
#と.のみからなる - S,T は 1 つ以上
#を含む
入力
入力は以下の形式で標準入力から与えられる。
N
S_{1,1}S_{1,2}\ldots S_{1,N}
\vdots
S_{N,1}S_{N,2}\ldots S_{N,N}
T_{1,1}T_{1,2}\ldots T_{1,N}
\vdots
T_{N,1}T_{N,2}\ldots T_{N,N}
出力
S と T を90 度回転及び平行移動の繰り返しによって一致させることができるとき Yes を、そうでないとき No を出力せよ。
入力例 1
5 ..... ..#.. .###. ..... ..... ..... ..... ....# ...## ....#
出力例 1
Yes
S を左回りに 90 度回転させ、平行移動することで T に一致させることができます。
入力例 2
5 ##### ##..# #..## ##### ..... ##### #..## ##..# ##### .....
出力例 2
No
90 度回転と平行移動の繰り返しによって一致させることはできません。
入力例 3
4 #... ..#. ..#. .... #... #... ..#. ....
出力例 3
Yes
S 及び T は連結とは限りません。
入力例 4
4 #... .##. ..#. .... ##.. #... ..#. ....
出力例 4
No
回転や移動の操作は連結成分ごとにできるわけではなく、S,T 全体に対して行うことに注意してください。
Score : 300 points
Problem Statement
We have two figures S and T on a two-dimensional grid with square cells.
S lies within a grid with N rows and N columns, and consists of the cells where S_{i,j} is #.
T lies within the same grid with N rows and N columns, and consists of the cells where T_{i,j} is #.
Determine whether it is possible to exactly match S and T by 90-degree rotations and translations.
Constraints
- 1 \leq N \leq 200
- Each of S and T consists of
#and.. - Each of S and T contains at least one
#.
Input
Input is given from Standard Input in the following format:
N
S_{1,1}S_{1,2}\ldots S_{1,N}
\vdots
S_{N,1}S_{N,2}\ldots S_{N,N}
T_{1,1}T_{1,2}\ldots T_{1,N}
\vdots
T_{N,1}T_{N,2}\ldots T_{N,N}
Output
Print Yes if it is possible to exactly match S and T by 90-degree rotations and translations, and No otherwise.
Sample Input 1
5 ..... ..#.. .###. ..... ..... ..... ..... ....# ...## ....#
Sample Output 1
Yes
We can match S to T by rotating it 90-degrees counter-clockwise and translating it.
Sample Input 2
5 ##### ##..# #..## ##### ..... ##### #..## ##..# ##### .....
Sample Output 2
No
It is impossible to match them by 90-degree rotations and translations.
Sample Input 3
4 #... ..#. ..#. .... #... #... ..#. ....
Sample Output 3
Yes
Each of S and T may not be connected.
Sample Input 4
4 #... .##. ..#. .... ##.. #... ..#. ....
Sample Output 4
No
Note that it is not allowed to rotate or translate just a part of a figure; it is only allowed to rotate or translate a whole figure.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
xy -平面上の N 個の円が与えられます。 i = 1, 2, \ldots, N について、i 番目の円は点 (x_i, y_i) を中心とする半径 r_i の円です。
N 個の円のうち少なくとも 1 つ以上の円の円周上にある点のみを通って、点 (s_x, s_y) から点 (t_x, t_y) に行くことができるかどうかを判定してください。
制約
- 1 \leq N \leq 3000
- -10^9 \leq x_i, y_i \leq 10^9
- 1 \leq r_i \leq 10^9
- (s_x, s_y) は N 個の円のうち少なくとも 1 つ以上の円の円周上にある
- (t_x, t_y) は N 個の円のうち少なくとも 1 つ以上の円の円周上にある
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N s_x s_y t_x t_y x_1 y_1 r_1 x_2 y_2 r_2 \vdots x_N y_N r_N
出力
点 (s_x, s_y) から点 (t_x, t_y) に行くことができる場合は Yes を、そうでない場合は No を出力せよ。
ジャッジは英小文字と英大文字を厳密に区別することに注意せよ。
入力例 1
4 0 -2 3 3 0 0 2 2 0 2 2 3 1 -3 3 3
出力例 1
Yes
例えば、下記の経路で点 (0, -2) から点 (3, 3) へ行くことができます。
- 点 (0, -2) から 1 つ目の円の円周上を反時計回りに通って点 (1, -\sqrt{3}) へ行く。
- 点 (1, -\sqrt{3}) から 2 つ目の円の円周上を時計回りに通って点 (2, 2) へ行く。
- 点 (2, 2) から 3 つ目の円の円周上を反時計回りに通って点 (3, 3) へ行く。
よって、Yes を出力します。
入力例 2
3 0 1 0 3 0 0 1 0 0 2 0 0 3
出力例 2
No
少なくとも 1 つ以上の円の円周上にある点のみを通って点 (0, 1) から点 (0, 3) に行くことはできないので No を出力します。
Score : 400 points
Problem Statement
You are given N circles on the xy-coordinate plane. For each i = 1, 2, \ldots, N, the i-th circle is centered at (x_i, y_i) and has a radius of r_i.
Determine whether it is possible to get from (s_x, s_y) to (t_x, t_y) by only passing through points that lie on the circumference of at least one of the N circles.
Constraints
- 1 \leq N \leq 3000
- -10^9 \leq x_i, y_i \leq 10^9
- 1 \leq r_i \leq 10^9
- (s_x, s_y) lies on the circumference of at least one of the N circles.
- (t_x, t_y) lies on the circumference of at least one of the N circles.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N s_x s_y t_x t_y x_1 y_1 r_1 x_2 y_2 r_2 \vdots x_N y_N r_N
Output
If it is possible to get from (s_x, s_y) to (t_x, t_y), print Yes; otherwise, print No.
Note that the judge is case-sensitive.
Sample Input 1
4 0 -2 3 3 0 0 2 2 0 2 2 3 1 -3 3 3
Sample Output 1
Yes
Here is one way to get from (0, -2) to (3, 3).
- From (0, -2), pass through the circumference of the 1-st circle counterclockwise to reach (1, -\sqrt{3}).
- From (1, -\sqrt{3}), pass through the circumference of the 2-nd circle clockwise to reach (2, 2).
- From (2, 2), pass through the circumference of the 3-rd circle counterclockwise to reach (3, 3).
Thus, Yes should be printed.
Sample Input 2
3 0 1 0 3 0 0 1 0 0 2 0 0 3
Sample Output 2
No
It is impossible to get from (0, 1) to (0, 3) by only passing through points on the circumference of at least one of the circles, so No should be printed.