A - Beginner

実行時間制限: 2 sec / メモリ制限: 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
B - Digits

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 200

問題文

整数 NK 進数で表したとき、何桁になるかを求めてください。

注記

K 進表記については、Wikipedia「位取り記数法」を参照してください。

制約

  • 入力は全て整数である。
  • 1 \leq N \leq 10^9
  • 2 \leq K \leq 10

入力

入力は以下の形式で標準入力から与えられる。

N K

出力

整数 NK 進数で表したとき、何桁になるかを出力せよ。


入力例 1

11 2

出力例 1

4

112 進数で表記すると 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
C - Rally

実行時間制限: 2 sec / メモリ制限: 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 = 12 番目の人が消費する体力は (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
D - Bouquet

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 400

問題文

あかりさんは n 種類の花を 1 本ずつ持っています。

あかりさんは、これらの花から 1 本以上を選び、花束を作ろうとしています。

ただし、あかりさんは ab2 つの数を苦手としていて、いずれかと一致するような本数の花からなる花束は作ることができません。

あかりさんが作ることのできる花束は何種類あるでしょうか。

(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).

E - Roaming

実行時間制限: 2 sec / メモリ制限: 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
F - Modularness

実行時間制限: 2 sec / メモリ制限: 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)yz で割った余りを表します。

制約

  • 入力は全て整数である。
  • 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