実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
非負整数 x に対し定義される関数 f(x) は以下の条件を満たします。
- f(0) = 1
- 任意の正整数 k に対し f(k) = k \times f(k-1)
このとき、 f(N) を求めてください。
制約
- N は 0 \le N \le 10 を満たす整数
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを整数として出力せよ。
入力例 1
2
出力例 1
2
f(2) = 2 \times f(1) = 2 \times 1 \times f(0) = 2 \times 1 \times 1 = 2 です。
入力例 2
3
出力例 2
6
f(3) = 3 \times f(2) = 3 \times 2 = 6 です。
入力例 3
0
出力例 3
1
入力例 4
10
出力例 4
3628800
Score : 100 points
Problem Statement
A function f(x) defined for non-negative integer x satisfies the following conditions:
- f(0) = 1;
- f(k) = k \times f(k-1) for all positive integers k.
Find f(N).
Constraints
- N is an integer such that 0 \le N \le 10.
Input
The input is given from Standard Input in the following format:
N
Output
Print the answer as an integer.
Sample Input 1
2
Sample Output 1
2
We have f(2) = 2 \times f(1) = 2 \times 1 \times f(0) = 2 \times 1 \times 1 = 2.
Sample Input 2
3
Sample Output 2
6
We have f(3) = 3 \times f(2) = 3 \times 2 = 6.
Sample Input 3
0
Sample Output 3
1
Sample Input 4
10
Sample Output 4
3628800
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
0 以上 9 以下の整数 A, B が与えられます。
0 以上 9 以下の整数であって A + B と等しくないものをいずれかひとつ出力してください。
制約
- 0 \leq A \leq 9
- 0 \leq B \leq 9
- A + B \leq 9
- A, B は整数
入力
入力は以下の形式で標準入力から与えられる。
A B
出力
0 以上 9 以下の整数であって A + B と等しくないものをいずれかひとつ出力せよ。
入力例 1
2 5
出力例 1
2
A = 2, B = 5 のとき A + B = 7 です。したがって、0, 1, 2, 3, 4, 5, 6, 8, 9 のいずれかを出力すると正解となります。
入力例 2
0 0
出力例 2
9
入力例 3
7 1
出力例 3
4
Score: 100 points
Problem Statement
You are given two integers A and B, each between 0 and 9, inclusive.
Print any integer between 0 and 9, inclusive, that is not equal to A + B.
Constraints
- 0 \leq A \leq 9
- 0 \leq B \leq 9
- A + B \leq 9
- A and B are integers.
Input
The input is given from Standard Input in the following format:
A B
Output
Print any integer between 0 and 9, inclusive, that is not equal to A + B.
Sample Input 1
2 5
Sample Output 1
2
When A = 2, B = 5, we have A + B = 7. Thus, printing any of 0, 1, 2, 3, 4, 5, 6, 8, 9 is correct.
Sample Input 2
0 0
Sample Output 2
9
Sample Input 3
7 1
Sample Output 3
4
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
正の整数 N が与えられます。
N=2^x3^y を満たす整数 x,y が存在するなら Yes 、そうでなければ No と出力してください。
制約
- 1\leq N\leq10^{18}
- N は整数
入力
入力は以下の形式で標準入力から与えられる。
N
出力
条件を満たす整数 x,y が存在するなら Yes 、そうでなければ No と 1 行に出力せよ。
入力例 1
324
出力例 1
Yes
x=2,y=4 とすると、2^x3^y=2^23^4=4\times81=324 となるため条件を満たします。
よって、Yes と出力してください。
入力例 2
5
出力例 2
No
どのような整数 x,y をとっても 2^x3^y=5 とすることはできません。
よって、No と出力してください。
入力例 3
32
出力例 3
Yes
x=5,y=0 とすると、2^x3^y=32\times1=32 となるため、Yes と出力してください。
入力例 4
37748736
出力例 4
Yes
Score : 200 points
Problem Statement
You are given a positive integer N.
If there are integers x and y such that N=2^x3^y, print Yes; otherwise, print No.
Constraints
- 1\leq N\leq10^{18}
- N is an integer.
Input
The input is given from Standard Input in the following format:
N
Output
Print a single line containing Yes if there are integers x and y that satisfy the condition, and No otherwise.
Sample Input 1
324
Sample Output 1
Yes
For x=2,y=4, we have 2^x3^y=2^23^4=4\times81=324, so the condition is satisfied.
Thus, you should print Yes.
Sample Input 2
5
Sample Output 2
No
There are no integers x and y such that 2^x3^y=5.
Thus, you should print No.
Sample Input 3
32
Sample Output 3
Yes
For x=5,y=0, we have 2^x3^y=32\times1=32, so you should print Yes.
Sample Input 4
37748736
Sample Output 4
Yes
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
おもり 1, おもり 2, \dots, おもり N の N 個のおもりがあります。おもり i の重さは A_i です。
以下の条件を満たす正整数 n を 良い整数 と呼びます。
- \bf{3} 個以下 の異なるおもりを自由に選んで、選んだおもりの重さの和を n にすることができる。
W 以下の正整数のうち、良い整数は何個ありますか？
制約
- 1 \leq N \leq 300
- 1 \leq W \leq 10^6
- 1 \leq A_i \leq 10^6
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N W A_1 A_2 \dots A_N
出力
答えを出力せよ。
入力例 1
2 10 1 3
出力例 1
3
おもり 1 のみを選ぶと重さの和は 1 になります。よって 1 は良い整数です。
おもり 2 のみを選ぶと重さの和は 3 になります。よって 3 は良い整数です。
おもり 1 とおもり 2 を選ぶと重さの和は 4 になります。よって 4 は良い整数です。
これら以外に良い整数は存在しません。また、1,3,4 のいずれも W 以下の整数です。よって答えは 3 個になります。
入力例 2
2 1 2 3
出力例 2
0
W 以下の良い整数は存在しません。
入力例 3
4 12 3 3 3 3
出力例 3
3
良い整数は 3,6,9 の 3 個です。
たとえばおもり 1, おもり 2, おもり 3 を選ぶと重さの和は 9 になるので、9 は良い整数です。
12 は良い整数 ではない ことに注意してください。
入力例 4
7 251 202 20 5 1 4 2 100
出力例 4
48
Score : 200 points
Problem Statement
There are N weights called Weight 1, Weight 2, \dots, Weight N. Weight i has a mass of A_i.
Let us say a positive integer n is a good integer if the following condition is satisfied:
- We can choose at most 3 different weights so that they have a total mass of n.
How many positive integers less than or equal to W are good integers?
Constraints
- 1 \leq N \leq 300
- 1 \leq W \leq 10^6
- 1 \leq A_i \leq 10^6
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N W A_1 A_2 \dots A_N
Output
Print the answer.
Sample Input 1
2 10 1 3
Sample Output 1
3
If we choose only Weight 1, it has a total mass of 1, so 1 is a good integer.
If we choose only Weight 2, it has a total mass of 3, so 3 is a good integer.
If we choose Weights 1 and 2, they have a total mass of 4, so 4 is a good integer.
No other integer is a good integer. Also, all of 1, 3, and 4 are integers less than or equal to W. Therefore, the answer is 3.
Sample Input 2
2 1 2 3
Sample Output 2
0
There are no good integers less than or equal to W.
Sample Input 3
4 12 3 3 3 3
Sample Output 3
3
There are 3 good integers: 3, 6, and 9.
For example, if we choose Weights 1, 2, and 3, they have a total mass of 9, so 9 is a good integer.
Note that 12 is not a good integer.
Sample Input 4
7 251 202 20 5 1 4 2 100
Sample Output 4
48
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
高橋くんは数直線上に N 個のプレゼントを置きました。そのうち i 個目のプレゼントは座標 A_i に置かれました。
あなたは数直線上の長さ M の半開区間 [x,x+M) を選び、そこに含まれるプレゼントを全て獲得します。
より詳しくは、以下の手順でプレゼントを獲得します。
- まず、実数 x をひとつ選択する。
- その後、プレゼントのうち置かれている座標が x \le A_i < x+M を満たすものを全て獲得する。
最大でいくつのプレゼントを獲得することができますか?
制約
- 入力は全て整数
- 1 \le N \le 3 \times 10^5
- 1 \le M \le 10^9
- 0 \le A_i \le 10^9
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 A_2 \dots A_N
出力
答えを整数として出力せよ。
入力例 1
8 6 2 3 5 7 11 13 17 19
出力例 1
4
例えば、半開区間 [1.5,7.5) を指定します。
このとき、座標 2,3,5,7 にある 4 つのプレゼントを全て獲得することができ、これが獲得可能な最大の個数です。
入力例 2
10 1 3 1 4 1 5 9 2 6 5 3
出力例 2
2
同一の座標に複数のプレゼントが置いてあることもあります。
入力例 3
10 998244353 100000007 0 1755647 998244353 495 1000000000 1755648 503 1755649 998244853
出力例 3
7
Score : 300 points
Problem Statement
Takahashi has placed N gifts on a number line. The i-th gift is placed at coordinate A_i.
You will choose a half-open interval [x,x+M) of length M on the number line and acquire all the gifts included in it.
More specifically, you acquire gifts according to the following procedure.
- First, choose one real number x.
- Then, acquire all the gifts whose coordinates satisfy x \le A_i < x+M.
What is the maximum number of gifts you can acquire?
Constraints
- All input values are integers.
- 1 \le N \le 3 \times 10^5
- 1 \le M \le 10^9
- 0 \le A_i \le 10^9
Input
The input is given from Standard Input in the following format:
N M A_1 A_2 \dots A_N
Output
Print the answer as an integer.
Sample Input 1
8 6 2 3 5 7 11 13 17 19
Sample Output 1
4
For example, specify the half-open interval [1.5,7.5).
In this case, you can acquire the four gifts at coordinates 2,3,5,7, the maximum number of gifts that can be acquired.
Sample Input 2
10 1 3 1 4 1 5 9 2 6 5 3
Sample Output 2
2
There may be multiple gifts at the same coordinate.
Sample Input 3
10 998244353 100000007 0 1755647 998244353 495 1000000000 1755648 503 1755649 998244853
Sample Output 3
7