C - Tak and Cards

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 300 点

問題文

高橋君は、N 枚のカードを持っています。 i \, (1 \leq i \leq N) 番目のカードには、整数 x_i が書かれています。 高橋君は、これらのカードの中から 1 枚以上を選び、 選んだカードに書かれた整数の平均をちょうど A にしたいと考えています。 そのようなカードの選び方が何通りあるか求めてください。

制約

  • 1 \leq N \leq 50
  • 1 \leq A \leq 50
  • 1 \leq x_i \leq 50
  • N,\,A,\,x_i はいずれも整数である

部分点

  • 1 \leq N \leq 16 を満たすデータセットに正解した場合は、200 点が与えられる。

入力

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

N A
x_1 x_2 ... x_N

出力

書かれた整数の平均がちょうど A となるようなカードの選び方の総数を出力せよ。

入力例 1

4 8
7 9 8 9

出力例 1

5
  • 平均が 8 となるカードの選び方は、以下の 5 通りです。
    • 3 枚目のカードのみを選ぶ。
    • 1 枚目と 2 枚目のカードを選ぶ。
    • 1 枚目と 4 枚目のカードを選ぶ。
    • 1 枚目、2 枚目および 3 枚目のカードを選ぶ。
    • 1 枚目、3 枚目および 4 枚目のカードを選ぶ。

入力例 2

3 8
6 6 9

出力例 2

0

入力例 3

8 5
3 6 2 8 7 6 5 9

出力例 3

19

入力例 4

33 3
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3

出力例 4

8589934591
  • 答えは 32 ビット整数型に収まらない場合があります。

Score : 300 points

Problem Statement

Tak has N cards. On the i-th (1 \leq i \leq N) card is written an integer x_i. He is selecting one or more cards from these N cards, so that the average of the integers written on the selected cards is exactly A. In how many ways can he make his selection?

Constraints

  • 1 \leq N \leq 50
  • 1 \leq A \leq 50
  • 1 \leq x_i \leq 50
  • N,\,A,\,x_i are integers.

Partial Score

  • 200 points will be awarded for passing the test set satisfying 1 \leq N \leq 16.

Input

The input is given from Standard Input in the following format:

N A
x_1 x_2 ... x_N

Output

Print the number of ways to select cards such that the average of the written integers is exactly A.

Sample Input 1

4 8
7 9 8 9

Sample Output 1

5
  • The following are the 5 ways to select cards such that the average is 8:
    • Select the 3-rd card.
    • Select the 1-st and 2-nd cards.
    • Select the 1-st and 4-th cards.
    • Select the 1-st, 2-nd and 3-rd cards.
    • Select the 1-st, 3-rd and 4-th cards.

Sample Input 2

3 8
6 6 9

Sample Output 2

0

Sample Input 3

8 5
3 6 2 8 7 6 5 9

Sample Output 3

19

Sample Input 4

33 3
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3

Sample Output 4

8589934591
  • The answer may not fit into a 32-bit integer.
D - Digit Sum

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 500 点

問題文

2 以上の整数 b および 1 以上の整数 n に対し、関数 f(b,n) を次のように定義します。

  • n < b のとき f(b,n) = n
  • n \geq b のとき f(b,n) = f(b,\,{\rm floor}(n / b)) + (n \ {\rm mod} \ b)

ここで、{\rm floor}(n / b) は n / b を超えない最大の整数を、 n \ {\rm mod} \ b は n を b で割った余りを表します。

直感的に言えば、f(b,n) は、n を b 進表記したときの各桁の和となります。 例えば、

  • f(10,\,87654)=8+7+6+5+4=30
  • f(100,\,87654)=8+76+54=138

などとなります。

整数 n と s が与えられます。 f(b,n)=s を満たすような 2 以上の整数 b が存在するか判定してください。 さらに、そのような b が存在するならば、その最小値を求めてください。

制約

  • 1 \leq n \leq 10^{11}
  • 1 \leq s \leq 10^{11}
  • n,\,s はいずれも整数である

入力

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

n
s

出力

f(b,n)=s を満たす 2 以上の整数 b が存在するならば、そのような b の最小値を出力せよ。 そのような b が存在しないならば、代わりに -1 を出力せよ。

入力例 1

87654
30

出力例 1

10

入力例 2

87654
138

出力例 2

100

入力例 3

87654
45678

出力例 3

-1

入力例 4

31415926535
1

出力例 4

31415926535

入力例 5

1
31415926535

出力例 5

-1

Score : 500 points

Problem Statement

For integers b (b \geq 2) and n (n \geq 1), let the function f(b,n) be defined as follows:

  • f(b,n) = n, when n < b
  • f(b,n) = f(b,\,{\rm floor}(n / b)) + (n \ {\rm mod} \ b), when n \geq b

Here, {\rm floor}(n / b) denotes the largest integer not exceeding n / b, and n \ {\rm mod} \ b denotes the remainder of n divided by b.

Less formally, f(b,n) is equal to the sum of the digits of n written in base b. For example, the following hold:

  • f(10,\,87654)=8+7+6+5+4=30
  • f(100,\,87654)=8+76+54=138

You are given integers n and s. Determine if there exists an integer b (b \geq 2) such that f(b,n)=s. If the answer is positive, also find the smallest such b.

Constraints

  • 1 \leq n \leq 10^{11}
  • 1 \leq s \leq 10^{11}
  • n,\,s are integers.

Input

The input is given from Standard Input in the following format:

n
s

Output

If there exists an integer b (b \geq 2) such that f(b,n)=s, print the smallest such b. If such b does not exist, print -1 instead.

Sample Input 1

87654
30

Sample Output 1

10

Sample Input 2

87654
138

Sample Output 2

100

Sample Input 3

87654
45678

Sample Output 3

-1

Sample Input 4

31415926535
1

Sample Output 4

31415926535

Sample Input 5

1
31415926535

Sample Output 5

-1
E - Tak and Hotels

Time Limit: 3 sec / Memory Limit: 256 MB

配点 : 700 点

問題文

N 軒のホテルが一直線上に並んでいます。i \, (1 \leq i \leq N) 番目のホテルは、座標 x_i に位置しています。

旅行者である高橋君には、次の 2 つの信念があります。

  • 高橋君の 1 日の移動距離は L を超えない。
  • 高橋君は野宿をしない。すなわち、1 日の終わりには必ずいずれかのホテルにいなければならない。

Q 個のクエリが与えられます。j\,(1 \leq j \leq Q) 番目のクエリとして、異なる 2 つの整数 a_j,\,b_j が与えられます。 各クエリについて、前述の信念をともに守った上で、高橋君が a_j 番目のホテルから b_j 番目のホテルに移動するために必要な最小日数を求めてください。 なお、高橋君が a_j 番目のホテルから b_j 番目のホテルに移動できることは保証されます。

制約

  • 2 \leq N \leq 10^5
  • 1 \leq L \leq 10^9
  • 1 \leq Q \leq 10^5
  • 1 \leq x_i < x_2 < ... < x_N \leq 10^9
  • x_{i+1} - x_i \leq L
  • 1 \leq a_j,b_j \leq N
  • a_j \neq b_j
  • N,\,L,\,Q,\,x_i,\,a_j,\,b_j はいずれも整数である

部分点

  • N \leq 10^3 および Q \leq 10^3 を満たすデータセットに正解した場合は、200 点が与えられる。

入力

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

N
x_1 x_2 ... x_N
L
Q
a_1 b_1
a_2 b_2
:
a_Q b_Q

出力

出力は Q 行からなる。 j \, (1 \leq j \leq Q) 行目には、高橋君が a_j 番目のホテルから b_j 番目のホテルに移動するために必要な最小日数を表す整数を出力せよ。

入力例 1

9
1 3 6 13 15 18 19 29 31
10
4
1 8
7 3
6 7
8 5

出力例 1

4
2
1
2

1 つ目のクエリでは、次のように行動することで、1 番目のホテルから 8 番目のホテルへ 4 日間で移動することができます。

  • 1 日目には、1 番目のホテルから 2 番目のホテルへ移動する。この日の移動距離は 2 である。
  • 2 日目には、2 番目のホテルから 4 番目のホテルへ移動する。この日の移動距離は 10 である。
  • 3 日目には、4 番目のホテルから 7 番目のホテルへ移動する。この日の移動距離は 6 である。
  • 4 日目には、7 番目のホテルから 8 番目のホテルへ移動する。この日の移動距離は 10 である。

Score : 700 points

Problem Statement

N hotels are located on a straight line. The coordinate of the i-th hotel (1 \leq i \leq N) is x_i.

Tak the traveler has the following two personal principles:

  • He never travels a distance of more than L in a single day.
  • He never sleeps in the open. That is, he must stay at a hotel at the end of a day.

You are given Q queries. The j-th (1 \leq j \leq Q) query is described by two distinct integers a_j and b_j. For each query, find the minimum number of days that Tak needs to travel from the a_j-th hotel to the b_j-th hotel following his principles. It is guaranteed that he can always travel from the a_j-th hotel to the b_j-th hotel, in any given input.

Constraints

  • 2 \leq N \leq 10^5
  • 1 \leq L \leq 10^9
  • 1 \leq Q \leq 10^5
  • 1 \leq x_i < x_2 < ... < x_N \leq 10^9
  • x_{i+1} - x_i \leq L
  • 1 \leq a_j,b_j \leq N
  • a_j \neq b_j
  • N,\,L,\,Q,\,x_i,\,a_j,\,b_j are integers.

Partial Score

  • 200 points will be awarded for passing the test set satisfying N \leq 10^3 and Q \leq 10^3.

Input

The input is given from Standard Input in the following format:

N
x_1 x_2 ... x_N
L
Q
a_1 b_1
a_2 b_2
:
a_Q b_Q

Output

Print Q lines. The j-th line (1 \leq j \leq Q) should contain the minimum number of days that Tak needs to travel from the a_j-th hotel to the b_j-th hotel.

Sample Input 1

9
1 3 6 13 15 18 19 29 31
10
4
1 8
7 3
6 7
8 5

Sample Output 1

4
2
1
2

For the 1-st query, he can travel from the 1-st hotel to the 8-th hotel in 4 days, as follows:

  • Day 1: Travel from the 1-st hotel to the 2-nd hotel. The distance traveled is 2.
  • Day 2: Travel from the 2-nd hotel to the 4-th hotel. The distance traveled is 10.
  • Day 3: Travel from the 4-th hotel to the 7-th hotel. The distance traveled is 6.
  • Day 4: Travel from the 7-th hotel to the 8-th hotel. The distance traveled is 10.
F - Best Representation

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 900 点

問題文

x を長さ 1 以上の文字列とします。 いかなる文字列 y および 2 以上の整数 k に対しても、 y を k 回繰り返した文字列が x と異なるならば、 x を良い文字列であると呼ぶことにします。 例えば、a, bbc, cdcdc などは良い文字列ですが、 aa, bbbb, cdcdcd などは良い文字列ではありません。

w を長さ 1 以上の文字列とします。 m 項からなる列 F=(\,f_1,\,f_2,\,...,\,f_m) について、 次の条件がともに満たされるならば、F を w の良い表現と呼ぶことにします。

  • すべての i \, (1 \leq i \leq m) について、f_i は良い文字列である。
  • f_1,\,f_2,\,...,\,f_m をこの順に連結すると w になる。

例えば、w=aabb の場合、w の良い表現は次の 5 つとなります。

  • (aabb)
  • (a,abb)
  • (aab,b)
  • (a,ab,b)
  • (a,a,b,b)

文字列 w の良い表現のうち、項数 m が最小であるものを、 w の最良表現と呼ぶことにします。 例えば、w=aabb の最良表現は (aabb) の 1 つのみとなります。

文字列 w が与えられます。次の 2 つを求めてください。

  • w の最良表現の項数
  • w の最良表現の総数を 1000000007 \, (=10^9+7) で割った余り

なお、w に対し、良い表現が存在することは保証されます。

制約

  • 1 \leq |w| \leq 500000 \, (=5 \times 10^5)
  • w は英小文字 (a-z) のみからなる文字列である

部分点

  • 1 \leq |w| \leq 4000 を満たすデータセットに正解した場合は、400 点が与えられる。

入力

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

w

出力

出力は 2 行からなる。

  • 1 行目に、w の最良表現の項数を出力せよ。
  • 2 行目に、w の最良表現の総数を 1000000007 で割った余りを出力せよ。

入力例 1

aab

出力例 1

1
1

入力例 2

bcbc

出力例 2

2
3
  • この入力に対しては、項数が 2 の最良表現が以下の 3 通り存在します。
    • (b,cbc)
    • (bc,bc)
    • (bcb,c)

入力例 3

ddd

出力例 3

3
1

Score : 900 points

Problem Statement

Let x be a string of length at least 1. We will call x a good string, if for any string y and any integer k (k \geq 2), the string obtained by concatenating k copies of y is different from x. For example, a, bbc and cdcdc are good strings, while aa, bbbb and cdcdcd are not.

Let w be a string of length at least 1. For a sequence F=(\,f_1,\,f_2,\,...,\,f_m) consisting of m elements, we will call F a good representation of w, if the following conditions are both satisfied:

  • For any i \, (1 \leq i \leq m), f_i is a good string.
  • The string obtained by concatenating f_1,\,f_2,\,...,\,f_m in this order, is w.

For example, when w=aabb, there are five good representations of w:

  • (aabb)
  • (a,abb)
  • (aab,b)
  • (a,ab,b)
  • (a,a,b,b)

Among the good representations of w, the ones with the smallest number of elements are called the best representations of w. For example, there are only one best representation of w=aabb: (aabb).

You are given a string w. Find the following:

  • the number of elements of a best representation of w
  • the number of the best representations of w, modulo 1000000007 \, (=10^9+7)

(It is guaranteed that a good representation of w always exists.)

Constraints

  • 1 \leq |w| \leq 500000 \, (=5 \times 10^5)
  • w consists of lowercase letters (a-z).

Partial Score

  • 400 points will be awarded for passing the test set satisfying 1 \leq |w| \leq 4000.

Input

The input is given from Standard Input in the following format:

w

Output

Print 2 lines.

  • In the first line, print the number of elements of a best representation of w.
  • In the second line, print the number of the best representations of w, modulo 1000000007.

Sample Input 1

aab

Sample Output 1

1
1

Sample Input 2

bcbc

Sample Output 2

2
3
  • In this case, there are 3 best representations of 2 elements:
    • (b,cbc)
    • (bc,bc)
    • (bcb,c)

Sample Input 3

ddd

Sample Output 3

3
1