Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
高橋君はプログラミングコンテストサイト「ButCoder」の会員です。
ButCoder の会員には 2 つのレーティング 内部レーティング と 表示レーティング が割り当てられています。
表示レーティングは、その会員のコンテスト参加回数が 10 以上のときは内部レーティングに等しく、そうでないときは、会員のコンテスト参加回数を K として、内部レーティングから 100 \times (10 - K) を引いたものになります。
高橋君のコンテスト参加回数が N で表示レーティングが R であるとき、高橋君の内部レーティングを求めてください。
制約
- 入力は全て整数である
- 1 \leq N \leq 100
- 0 \leq R \leq 4111
入力
入力は以下の形式で標準入力から与えられる。
N R
出力
高橋君の内部レーティングを出力せよ。
入力例 1
2 2919
出力例 1
3719
コンテスト参加回数が 10 より少ない 2 であるため、内部レーティングから 100 \times (10 - 2) = 800 を引いたものが高橋君の表示レーティングになっています。
よって高橋君の内部レーティングは 2919 + 800 = 3719 となります。
入力例 2
22 3051
出力例 2
3051
Score : 100 points
Problem Statement
Takahashi is a member of a programming competition site, ButCoder.
Each member of ButCoder is assigned two values: Inner Rating and Displayed Rating.
The Displayed Rating of a member is equal to their Inner Rating if the member has participated in 10 or more contests. Otherwise, the Displayed Rating will be their Inner Rating minus 100 \times (10 - K) when the member has participated in K contests.
Takahashi has participated in N contests, and his Displayed Rating is R. Find his Inner Rating.
Constraints
- All values in input are integers.
- 1 \leq N \leq 100
- 0 \leq R \leq 4111
Input
Input is given from Standard Input in the following format:
N R
Output
Print his Inner Rating.
Sample Input 1
2 2919
Sample Output 1
3719
Takahashi has participated in 2 contests, which is less than 10, so his Displayed Rating is his Inner Rating minus 100 \times (10 - 2) = 800.
Thus, Takahashi's Inner Rating is 2919 + 800 = 3719.
Sample Input 2
22 3051
Sample Output 2
3051
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
整数 N を K 進数で表したとき、何桁になるかを求めてください。
注記
K 進表記については、Wikipedia「位取り記数法」を参照してください。
制約
- 入力は全て整数である。
- 1 \leq N \leq 10^9
- 2 \leq K \leq 10
入力
入力は以下の形式で標準入力から与えられる。
N K
出力
整数 N を K 進数で表したとき、何桁になるかを出力せよ。
入力例 1
11 2
出力例 1
4
11 を 2 進数で表記すると 1011
です。
入力例 2
1010101 10
出力例 2
7
入力例 3
314159265 3
出力例 3
18
Score : 200 points
Problem Statement
Given is an integer N. Find the number of digits that N has in base K.
Notes
For information on base-K representation, see Positional notation - Wikipedia.
Constraints
- All values in input are integers.
- 1 \leq N \leq 10^9
- 2 \leq K \leq 10
Input
Input is given from Standard Input in the following format:
N K
Output
Print the number of digits that N has in base K.
Sample Input 1
11 2
Sample Output 1
4
In binary, 11 is represented as 1011
.
Sample Input 2
1010101 10
Sample Output 2
7
Sample Input 3
314159265 3
Sample Output 3
18
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
数直線上に N 人の人が住んでいます。
i 番目の人が住んでいるのは座標 X_i です。
あなたは N 人全員が参加する集会を開くことを考えています。
集会は数直線上の任意の 整数値の座標 で開くことができ、座標 P で集会を開くとき、i 番目の人は集会に参加するために (X_i - P)^2 の体力を消費します。
N 人が消費する体力の総和としてありえる値の最小値を求めてください。
制約
- 入力は全て整数である。
- 1 \leq N \leq 100
- 1 \leq X_i \leq 100
入力
入力は以下の形式で標準入力から与えられる。
N X_1 X_2 ... X_N
出力
N 人が消費する体力の総和としてありえる値の最小値を出力せよ。
入力例 1
2 1 4
出力例 1
5
座標 2 で集会を開くとき、1 番目の人が消費する体力は (1 - 2)^2 = 1、 2 番目の人が消費する体力は (4 - 2)^2 = 4、よってその総和は 5 です。 これが 2 人が消費する体力の総和としてありえる値の最小値です。
集会を開くことができるのは整数値の座標だけであることに注意してください。
入力例 2
7 14 14 2 13 56 2 37
出力例 2
2354
Score : 300 points
Problem Statement
There are N people living on a number line.
The i-th person lives at coordinate X_i.
You are going to hold a meeting that all N people have to attend.
The meeting can be held at any integer coordinate. If you choose to hold the meeting at coordinate P, the i-th person will spend (X_i - P)^2 points of stamina to attend the meeting.
Find the minimum total points of stamina the N people have to spend.
Constraints
- All values in input are integers.
- 1 \leq N \leq 100
- 1 \leq X_i \leq 100
Input
Input is given from Standard Input in the following format:
N X_1 X_2 ... X_N
Output
Print the minimum total stamina the N people have to spend.
Sample Input 1
2 1 4
Sample Output 1
5
Assume the meeting is held at coordinate 2. In this case, the first person will spend (1 - 2)^2 points of stamina, and the second person will spend (4 - 2)^2 = 4 points of stamina, for a total of 5 points of stamina. This is the minimum total stamina that the 2 people have to spend.
Note that you can hold the meeting only at an integer coordinate.
Sample Input 2
7 14 14 2 13 56 2 37
Sample Output 2
2354
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
あかりさんは n 種類の花を 1 本ずつ持っています。
あかりさんは、これらの花から 1 本以上を選び、花束を作ろうとしています。
ただし、あかりさんは a と b の 2 つの数を苦手としていて、いずれかと一致するような本数の花からなる花束は作ることができません。
あかりさんが作ることのできる花束は何種類あるでしょうか。
(10^9 + 7) で割った余りを求めてください。
ここで 2 つの花束は、一方では使われているが、 もう一方では使われていない種類の花があるとき、別の種類の花束であるとみなします。
制約
- 入力は全て整数である。
- 2 \leq n \leq 10^9
- 1 \leq a < b \leq \textrm{min}(n, 2 \times 10^5)
入力
入力は以下の形式で標準入力から与えられる。
n a b
出力
あかりさんが作ることのできる花束の種類数を (10^9 + 7) で割った余りを出力せよ。(そのような花束がないときは 0
と出力せよ。)
入力例 1
4 1 3
出力例 1
7
この場合、あかりさんは 2 本または 4 本の花を選んで花束を作ることができます。
4 本ある花の中から 2 本を選ぶ方法は 6 通り、4 本を選ぶ方法は 1 通りあるので、 あかりさんが作ることができる花束の種類数は合わせて 7 通りです。
入力例 2
1000000000 141421 173205
出力例 2
34076506
(10^9 + 7) で割った余りを出力してください。
Score : 400 points
Problem Statement
Akari has n kinds of flowers, one of each kind.
She is going to choose one or more of these flowers to make a bouquet.
However, she hates two numbers a and b, so the number of flowers in the bouquet cannot be a or b.
How many different bouquets are there that Akari can make?
Find the count modulo (10^9 + 7).
Here, two bouquets are considered different when there is a flower that is used in one of the bouquets but not in the other bouquet.
Constraints
- All values in input are integers.
- 2 \leq n \leq 10^9
- 1 \leq a < b \leq \textrm{min}(n, 2 \times 10^5)
Input
Input is given from Standard Input in the following format:
n a b
Output
Print the number of bouquets that Akari can make, modulo (10^9 + 7). (If there are no such bouquets, print 0
.)
Sample Input 1
4 1 3
Sample Output 1
7
In this case, Akari can choose 2 or 4 flowers to make the bouquet.
There are 6 ways to choose 2 out of the 4 flowers, and 1 way to choose 4, so there are a total of 7 different bouquets that Akari can make.
Sample Input 2
1000000000 141421 173205
Sample Output 2
34076506
Print the count modulo (10^9 + 7).
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
n 個の部屋がある建物があります。 部屋には 1 から n までの番号が付いています。
建物の各部屋から、他の任意の部屋に移ることが可能です。
ここで、建物のある部屋 i にいる人が、別の部屋 j~ (i \neq j) に移ることを 人の移動 と呼ぶことにします。
最初、建物の各部屋には人が 1 人いました。
このあと現在までに、人の移動がちょうど k 回起きたことが分かっています。
現在、建物の各部屋にいる人の数の組合せとして、ありえるものは何通りでしょうか。
(10^9 + 7) で割った余りを求めてください。
制約
- 入力は全て整数である。
- 3 \leq n \leq 2 \times 10^5
- 2 \leq k \leq 10^9
入力
入力は以下の形式で標準入力から与えられる。
n k
出力
現在、建物の各部屋にいる人の数の組合せとして、ありえるものの個数を (10^9 + 7) で割った余りを出力せよ。
入力例 1
3 2
出力例 1
10
現在、部屋 1 にいる人の数を c_1、部屋 2 にいる人の数を c_2、部屋 3 にいる人の数を c_3 と すると、(c_1, c_2, c_3) としてありえるものは、
- (0, 0, 3)
- (0, 1, 2)
- (0, 2, 1)
- (0, 3, 0)
- (1, 0, 2)
- (1, 1, 1)
- (1, 2, 0)
- (2, 0, 1)
- (2, 1, 0)
- (3, 0, 0)
の 10 通りです。
例えば、まず部屋 1 にいる人が部屋 2 に移動し、 次に部屋 2 にいる誰かが部屋 3 に移動した場合を考えると、 (c_1, c_2, c_3) は (0, 1, 2) になります。
入力例 2
200000 1000000000
出力例 2
607923868
個数を (10^9 + 7) で割った余りを出力してください。
入力例 3
15 6
出力例 3
22583772
Score : 500 points
Problem Statement
There is a building with n rooms, numbered 1 to n.
We can move from any room to any other room in the building.
Let us call the following event a move: a person in some room i goes to another room j~ (i \neq j).
Initially, there was one person in each room in the building.
After that, we know that there were exactly k moves happened up to now.
We are interested in the number of people in each of the n rooms now. How many combinations of numbers of people in the n rooms are possible?
Find the count modulo (10^9 + 7).
Constraints
- All values in input are integers.
- 3 \leq n \leq 2 \times 10^5
- 2 \leq k \leq 10^9
Input
Input is given from Standard Input in the following format:
n k
Output
Print the number of possible combinations of numbers of people in the n rooms now, modulo (10^9 + 7).
Sample Input 1
3 2
Sample Output 1
10
Let c_1, c_2, and c_3 be the number of people in Room 1, 2, and 3 now, respectively. There are 10 possible combination of (c_1, c_2, c_3):
- (0, 0, 3)
- (0, 1, 2)
- (0, 2, 1)
- (0, 3, 0)
- (1, 0, 2)
- (1, 1, 1)
- (1, 2, 0)
- (2, 0, 1)
- (2, 1, 0)
- (3, 0, 0)
For example, (c_1, c_2, c_3) will be (0, 1, 2) if the person in Room 1 goes to Room 2 and then one of the persons in Room 2 goes to Room 3.
Sample Input 2
200000 1000000000
Sample Output 2
607923868
Print the count modulo (10^9 + 7).
Sample Input 3
15 6
Sample Output 3
22583772
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
長さ k の数列 d_0,d_1,...,d_{k - 1} があります。
以下のクエリ q 個を順に処理してください。
- i 番目のクエリは 3 つの整数 n_i,x_i,m_i からなる。 長さ n_i の数列 a_0,a_1,...,a_{n_i - 1} を、 \[ \begin{aligned} a_j = \begin{cases} x_i & ( j = 0 ) \\ a_{j - 1} + d_{(j - 1)~\textrm{mod}~k} & ( 0 < j \leq n_i - 1 ) \end{cases}\end{aligned} \] と定める。 (a_j~\textrm{mod}~m_i) < (a_{j + 1}~\textrm{mod}~m_i) であるような、j~(0 \leq j < n_i - 1) の個数を出力する。
ここで 2 つの整数 y, z~(z > 0) について、(y~\textrm{mod}~z) は y を z で割った余りを表します。
制約
- 入力は全て整数である。
- 1 \leq k, q \leq 5000
- 0 \leq d_i \leq 10^9
- 2 \leq n_i \leq 10^9
- 0 \leq x_i \leq 10^9
- 2 \leq m_i \leq 10^9
入力
入力は以下の形式で標準入力から与えられる。
k q d_0 d_1 ... d_{k - 1} n_1 x_1 m_1 n_2 x_2 m_2 : n_q x_q m_q
出力
q 行出力せよ。
i 行目には、i 番目のクエリに対する答えを出力せよ。
入力例 1
3 1 3 1 4 5 3 2
出力例 1
1
1 つ目のクエリについて、問題文で示した数列 {a_j} は 3,6,7,11,14 になります。
- (a_0~\textrm{mod}~2) > (a_1~\textrm{mod}~2)
- (a_1~\textrm{mod}~2) < (a_2~\textrm{mod}~2)
- (a_2~\textrm{mod}~2) = (a_3~\textrm{mod}~2)
- (a_3~\textrm{mod}~2) > (a_4~\textrm{mod}~2)
であるため、このクエリに対する答えは 1 です。
入力例 2
7 3 27 18 28 18 28 46 1000000000 1000000000 1 7 1000000000 2 10 1000000000 3 12
出力例 2
224489796 214285714 559523809
Score : 600 points
Problem Statement
We have a sequence of k numbers: d_0,d_1,...,d_{k - 1}.
Process the following q queries in order:
- The i-th query contains three integers n_i, x_i, and m_i. Let a_0,a_1,...,a_{n_i - 1} be the following sequence of n_i numbers: \[ \begin{aligned} a_j = \begin{cases} x_i & ( j = 0 ) \\ a_{j - 1} + d_{(j - 1)~\textrm{mod}~k} & ( 0 < j \leq n_i - 1 ) \end{cases}\end{aligned} \] Print the number of j~(0 \leq j < n_i - 1) such that (a_j~\textrm{mod}~m_i) < (a_{j + 1}~\textrm{mod}~m_i).
Here (y~\textrm{mod}~z) denotes the remainder of y divided by z, for two integers y and z~(z > 0).
Constraints
- All values in input are integers.
- 1 \leq k, q \leq 5000
- 0 \leq d_i \leq 10^9
- 2 \leq n_i \leq 10^9
- 0 \leq x_i \leq 10^9
- 2 \leq m_i \leq 10^9
Input
Input is given from Standard Input in the following format:
k q d_0 d_1 ... d_{k - 1} n_1 x_1 m_1 n_2 x_2 m_2 : n_q x_q m_q
Output
Print q lines.
The i-th line should contain the response to the i-th query.
Sample Input 1
3 1 3 1 4 5 3 2
Sample Output 1
1
For the first query, the sequence {a_j} will be 3,6,7,11,14.
- (a_0~\textrm{mod}~2) > (a_1~\textrm{mod}~2)
- (a_1~\textrm{mod}~2) < (a_2~\textrm{mod}~2)
- (a_2~\textrm{mod}~2) = (a_3~\textrm{mod}~2)
- (a_3~\textrm{mod}~2) > (a_4~\textrm{mod}~2)
Thus, the response to this query should be 1.
Sample Input 2
7 3 27 18 28 18 28 46 1000000000 1000000000 1 7 1000000000 2 10 1000000000 3 12
Sample Output 2
224489796 214285714 559523809