AtCoder Beginner Contest 154

A - Remaining Balls

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100 点

問題文

文字列 S の書かれたボールが A 個、文字列 T の書かれたボールが B 個あります。
高橋君は、文字列 U の書かれたボールを 1 個選んで捨てました。
文字列 S,T の書かれたボールがそれぞれ何個残っているか求めてください。

制約

S,T,U は英小文字のみからなる文字列
S,T の長さは 1 以上 10 以下
S \not= T
S=U または T=U
1 \leq A,B \leq 10
A,B は整数

入力

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

S T
A B
U

出力

答えを空白区切りで出力せよ。

入力例 1

red blue
3 4
red

出力例 1

2 4

高橋君は red が書かれたボールを 1 つ選んで捨てました。
文字列 S,T が書かれたボールは、それぞれ 2,4 個残っています。

入力例 2

red blue
5 5
blue

出力例 2

5 4

高橋君は blue が書かれたボールを 1 つ選んで捨てました。
文字列 S,T が書かれたボールは、それぞれ 5,4 個残っています。

Score : 100 points

Problem Statement

We have A balls with the string S written on each of them and B balls with the string T written on each of them.
From these balls, Takahashi chooses one with the string U written on it and throws it away.
Find the number of balls with the string S and balls with the string T that we have now.

Constraints

S, T, and U are strings consisting of lowercase English letters.
The lengths of S and T are each between 1 and 10 (inclusive).
S \not= T
S=U or T=U.
1 \leq A,B \leq 10
A and B are integers.

Input

Input is given from Standard Input in the following format:

S T
A B
U

Output

Print the answer, with space in between.

Sample Input 1

red blue
3 4
red

Sample Output 1

2 4

Takahashi chose a ball with red written on it and threw it away. Now we have two balls with the string S and four balls with the string T.

Sample Input 2

red blue
5 5
blue

Sample Output 2

5 4

Takahashi chose a ball with blue written on it and threw it away. Now we have five balls with the string S and four balls with the string T.

B - I miss you...

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 200 点

問題文

文字列 S が与えられます。S のすべての文字を x で置き換えて出力してください。

制約

S は英小文字のみからなる文字列
S の長さは 1 以上 100 以下

入力

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

出力

S のすべての文字を x で置き換えて出力せよ。

入力例 1

sardine

出力例 1

xxxxxxx

sardine のすべての文字を x で置き換えると xxxxxxx となります。

入力例 2

xxxx

出力例 2

xxxx

入力例 3

gone

出力例 3

xxxx

Score : 200 points

Problem Statement

Given is a string S. Replace every character in S with x and print the result.

Constraints

S is a string consisting of lowercase English letters.
The length of S is between 1 and 100 (inclusive).

Input

Input is given from Standard Input in the following format:

Output

Replace every character in S with x and print the result.

Sample Input 1

sardine

Sample Output 1

xxxxxxx

Replacing every character in S with x results in xxxxxxx.

Sample Input 2

xxxx

Sample Output 2

xxxx

Sample Input 3

gone

Sample Output 3

xxxx

C - Distinct or Not

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

整数列 A_1, A_2, ..., A_N が与えられます。この整数列のどの 2 つの要素も互いに異なるならば YES を、そうでないなら NO を出力してください。

制約

2 ≤ N ≤ 200000
1 ≤ A_i ≤ 10^9
入力は全て整数

入力

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

N
A_1 ... A_N

出力

整数列のどの 2 つの要素も互いに異なるならば YES を、そうでないなら NO を出力せよ。

入力例 1

5
2 6 1 4 5

出力例 1

YES

どの 2 つの要素も互いに異なります。

入力例 2

6
4 1 3 1 6 2

出力例 2

NO

2 番目の要素と 4 番目の要素が同じです。

入力例 3

2
10000000 10000000

出力例 3

NO

Score : 300 points

Problem Statement

Given is a sequence of integers A_1, A_2, ..., A_N. If its elements are pairwise distinct, print YES; otherwise, print NO.

Constraints

2 ≤ N ≤ 200000
1 ≤ A_i ≤ 10^9
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 ... A_N

Output

If the elements of the sequence are pairwise distinct, print YES; otherwise, print NO.

Sample Input 1

5
2 6 1 4 5

Sample Output 1

YES

The elements are pairwise distinct.

Sample Input 2

6
4 1 3 1 6 2

Sample Output 2

NO

The second and fourth elements are identical.

Sample Input 3

2
10000000 10000000

Sample Output 3

NO

D - Dice in Line

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

N 個のサイコロが左から右に一列に並べてあります。左から i 番目のサイコロは 1 から p_i までの p_i 種類の目がそれぞれ等確率で出ます。

隣接する K 個のサイコロを選んでそれぞれ独立に振ったとき、出る目の合計の期待値の最大値を求めてください。

制約

1 ≤ K ≤ N ≤ 200000
1 ≤ p_i ≤ 1000
入力で与えられる値は全て整数

入力

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

N K
p_1 ... p_N

出力

隣接する K 個のサイコロを選んで振ったときに出る目の合計の期待値の最大値を出力せよ。

なお、想定解答との絶対誤差または相対誤差が 10^{-6} 以下であれば正解として扱われる。

入力例 1

5 3
1 2 2 4 5

出力例 1

7.000000000000

左から 3 番目、4 番目、5 番目のサイコロを振った時、出る目の合計の期待値は 7 となり、これが最大です。

入力例 2

4 1
6 6 6 6

出力例 2

3.500000000000

どのサイコロを選んで振っても、出る目の期待値は 3.5 です。

入力例 3

10 4
17 13 13 12 15 20 10 13 17 11

出力例 3

32.000000000000

Score : 400 points

Problem Statement

We have N dice arranged in a line from left to right. The i-th die from the left shows p_i numbers from 1 to p_i with equal probability when thrown.

We will choose K adjacent dice, throw each of them independently, and compute the sum of the numbers shown. Find the maximum possible value of the expected value of this sum.

Constraints

1 ≤ K ≤ N ≤ 200000
1 ≤ p_i ≤ 1000
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K
p_1 ... p_N

Output

Print the maximum possible value of the expected value of the sum of the numbers shown.

Your output will be considered correct when its absolute or relative error from our answer is at most 10^{-6}.

Sample Input 1

5 3
1 2 2 4 5

Sample Output 1

7.000000000000

When we throw the third, fourth, and fifth dice from the left, the expected value of the sum of the numbers shown is 7. This is the maximum value we can achieve.

Sample Input 2

4 1
6 6 6 6

Sample Output 2

3.500000000000

Regardless of which die we choose, the expected value of the number shown is 3.5.

Sample Input 3

10 4
17 13 13 12 15 20 10 13 17 11

Sample Output 3

32.000000000000

E - Almost Everywhere Zero

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

1 以上 N 以下の整数であって、 10 進法で表したときに、0 でない数字がちょうど K 個あるようなものの個数を求めてください。

制約

1 \leq N < 10^{100}
1 \leq K \leq 3

入力

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

N
K

出力

条件を満たす数の個数を出力せよ。

入力例 1

100
1

出力例 1

条件を満たす数は次の 19 個です。

1,2,3,4,5,6,7,8,9,10,20,30,40,50,60,70,80,90,100

入力例 2

25
2

出力例 2

条件を満たす数は次の 14 個です。

11,12,13,14,15,16,17,18,19,21,22,23,24,25

入力例 3

314159
2

出力例 3

入力例 4

9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
3

出力例 4

117879300

Score : 500 points

Problem Statement

Find the number of integers between 1 and N (inclusive) that contains exactly K non-zero digits when written in base ten.

Constraints

1 \leq N < 10^{100}
1 \leq K \leq 3

Input

Input is given from Standard Input in the following format:

N
K

Output

Print the count.

Sample Input 1

100
1

Sample Output 1

The following 19 integers satisfy the condition:

1,2,3,4,5,6,7,8,9,10,20,30,40,50,60,70,80,90,100

Sample Input 2

25
2

Sample Output 2

The following 14 integers satisfy the condition:

11,12,13,14,15,16,17,18,19,21,22,23,24,25

Sample Input 3

314159
2

Sample Output 3

Sample Input 4

9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
3

Sample Output 4

117879300

F - Many Many Paths

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

2 次元平面があります。この平面上に立っているすぬけ君は、一回の操作で x 軸正の方向に 1 もしくは y 軸正の方向に 1 移動することができます。

また、以下のように関数 f(r,c) を定義します。

f(r,c) := (すぬけ君が点 (0,0) から点 (r,c) まで上記の操作を繰り返して到達する経路の個数)

整数 r_1, r_2, c_1, c_2 が与えられます。 r_1 ≤ i ≤ r_2 かつ c_1 ≤ j ≤ c_2 を満たす全ての整数の組 (i,j) に対する f(i,j) の総和を求め、 (10^9+7) で割った余りを計算してください。

制約

1 ≤ r_1 ≤ r_2 ≤ 10^6
1 ≤ c_1 ≤ c_2 ≤ 10^6
入力はすべて整数

入力

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

r_1 c_1 r_2 c_2

出力

f(i,j) の総和を (10^9+7) で割った余りを出力せよ。

入力例 1

1 1 2 2

出力例 1

例えば、点 (0,0) から点 (1,1) までの経路は、(0,0) → (0,1) → (1,1) と (0,0) → (1,0) → (1,1) の 2 通りあるので、 f(1,1)=2 です。

同様に、f(1,2)=3, f(2,1)=3, f(2,2)=6 なので、求める総和は 14 です。

入力例 2

314 159 2653 589

出力例 2

602215194

Score : 600 points

Problem Statement

Snuke is standing on a two-dimensional plane. In one operation, he can move by 1 in the positive x-direction, or move by 1 in the positive y-direction.

Let us define a function f(r, c) as follows:

f(r,c) := (The number of paths from the point (0, 0) to the point (r, c) that Snuke can trace by repeating the operation above)

Given are integers r_1, r_2, c_1, and c_2. Find the sum of f(i, j) over all pair of integers (i, j) such that r_1 ≤ i ≤ r_2 and c_1 ≤ j ≤ c_2, and compute this value modulo (10^9+7).

Constraints

1 ≤ r_1 ≤ r_2 ≤ 10^6
1 ≤ c_1 ≤ c_2 ≤ 10^6
All values in input are integers.

Input

Input is given from Standard Input in the following format:

r_1 c_1 r_2 c_2

Output

Print the sum of f(i, j) modulo (10^9+7).

Sample Input 1

1 1 2 2

Sample Output 1

For example, there are two paths from the point (0, 0) to the point (1, 1): (0,0) → (0,1) → (1,1) and (0,0) → (1,0) → (1,1), so f(1,1)=2.

Similarly, f(1,2)=3, f(2,1)=3, and f(2,2)=6. Thus, the sum is 14.

Sample Input 2

314 159 2653 589

Sample Output 2

602215194