AtCoder Beginner Contest 044

A - Tak and Hotels (ABC Edit)

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 100 点

問題文

1 軒のホテルがあります。このホテルの宿泊費は、次のようになっています。

最初の K 泊までは、1 泊あたり X 円
K+1 泊目以降は、1 泊あたり Y 円

高橋君は、このホテルに N 泊連続で宿泊することにしました。高橋君の宿泊費は合計で何円になるか求めてください。

制約

1 \leq N, K \leq 10000
1 \leq Y < X \leq 10000
N,\,K,\,X,\,Y はいずれも整数である

入力

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

N
K
X
Y

出力

高橋君の宿泊費の合計金額を表す整数を出力せよ。

入力例 1

出力例 1

宿泊費は次のようになります。

1 泊目は 10000 円
2 泊目は 10000 円
3 泊目は 10000 円
4 泊目は 9000 円
5 泊目は 9000 円

したがって、合計は 48000 円です。

入力例 2

出力例 2

Score : 100 points

Problem Statement

There is a hotel with the following accommodation fee:

X yen (the currency of Japan) per night, for the first K nights
Y yen per night, for the (K+1)-th and subsequent nights

Tak is staying at this hotel for N consecutive nights. Find his total accommodation fee.

Constraints

1 \leq N, K \leq 10000
1 \leq Y < X \leq 10000
N,\,K,\,X,\,Y are integers.

Input

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

N
K
X
Y

Output

Print Tak's total accommodation fee.

Sample Input 1

Sample Output 1

The accommodation fee is as follows:

10000 yen for the 1-st night
10000 yen for the 2-nd night
10000 yen for the 3-rd night
9000 yen for the 4-th night
9000 yen for the 5-th night

Thus, the total is 48000 yen.

Sample Input 2

Sample Output 2

B - Beautiful Strings

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 200 点

問題文

w を、英小文字のみからなる文字列とします。 w が以下の条件を満たすならば、w を美しい文字列と呼ぶことにします。

どの英小文字も、w 中に偶数回出現する。

文字列 w が与えられます。w が美しい文字列かどうか判定してください。

制約

1 \leq |w| \leq 100
w は英小文字 (a-z) のみからなる文字列である

入力

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

出力

w が美しい文字列ならば Yes を、それ以外の場合は No を出力せよ。

入力例 1

abaccaba

出力例 1

Yes

a が 4 回、b が 2 回、c が 2 回、それ以外の英小文字が 0 回出現します。

入力例 2

hthth

出力例 2

No

Score : 200 points

Problem Statement

Let w be a string consisting of lowercase letters. We will call w beautiful if the following condition is satisfied:

Each lowercase letter of the English alphabet occurs even number of times in w.

You are given the string w. Determine if w is beautiful.

Constraints

1 \leq |w| \leq 100
w consists of lowercase letters (a-z).

Input

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

Output

Print Yes if w is beautiful. Print No otherwise.

Sample Input 1

abaccaba

Sample Output 1

Yes

a occurs four times, b occurs twice, c occurs twice and the other letters occur zero times.

Sample Input 2

hthth

Sample Output 2

No

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

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

入力例 2

3 8
6 6 9

出力例 2

入力例 3

8 5
3 6 2 8 7 6 5 9

出力例 3

入力例 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

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

Sample Input 3

8 5
3 6 2 8 7 6 5 9

Sample Output 3

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

入力例 2

87654
138

出力例 2

入力例 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

Sample Input 2

87654
138

Sample Output 2

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