Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
A \times B を求めてください。
制約
- 1 \leq A \leq 100
- 1 \leq B \leq 100
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
A B
出力
値 A \times B を整数として出力せよ。
入力例 1
2 5
出力例 1
10
2 \times 5 = 10 です。
入力例 2
100 100
出力例 2
10000
Score : 100 points
Problem Statement
Compute A \times B.
Constraints
- 1 \leq A \leq 100
- 1 \leq B \leq 100
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
A B
Output
Print the value A \times B as an integer.
Sample Input 1
2 5
Sample Output 1
10
We have 2 \times 5 = 10.
Sample Input 2
100 100
Sample Output 2
10000
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
N 個の整数 A_1,...,A_N が与えられます。
A_1 \times ... \times A_N を求めてください。
ただし、結果が 10^{18} を超える場合は、代わりに -1
を出力してください。
制約
- 2 \leq N \leq 10^5
- 0 \leq A_i \leq 10^{18}
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
N A_1 ... A_N
出力
値 A_1 \times ... \times A_N を整数として出力せよ。ただし、この値が 10^{18} を超える場合は、代わりに -1
を出力せよ。
入力例 1
2 1000000000 1000000000
出力例 1
1000000000000000000
1000000000 \times 1000000000 = 1000000000000000000 です。
入力例 2
3 101 9901 999999000001
出力例 2
-1
101 \times 9901 \times 999999000001 = 1000000000000000001 ですが、これは 10^{18} を超えるので、代わりに -1
を出力します。
入力例 3
31 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6 2 6 4 3 3 8 3 2 7 9 5 0
出力例 3
0
Score : 200 points
Problem Statement
Given N integers A_1, ..., A_N, compute A_1 \times ... \times A_N.
However, if the result exceeds 10^{18}, print -1
instead.
Constraints
- 2 \leq N \leq 10^5
- 0 \leq A_i \leq 10^{18}
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A_1 ... A_N
Output
Print the value A_1 \times ... \times A_N as an integer, or -1
if the value exceeds 10^{18}.
Sample Input 1
2 1000000000 1000000000
Sample Output 1
1000000000000000000
We have 1000000000 \times 1000000000 = 1000000000000000000.
Sample Input 2
3 101 9901 999999000001
Sample Output 2
-1
We have 101 \times 9901 \times 999999000001 = 1000000000000000001, which exceeds 10^{18}, so we should print -1
instead.
Sample Input 3
31 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6 2 6 4 3 3 8 3 2 7 9 5 0
Sample Output 3
0
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
A \times B の小数点以下を切り捨て、結果を整数として出力してください。
制約
- 0 \leq A \leq 10^{15}
- 0 \leq B < 10
- A は整数
- B は小数第 2 位まで与えられる
入力
入力は以下の形式で標準入力から与えられる。
A B
出力
答えを整数として出力せよ。
入力例 1
198 1.10
出力例 1
217
198 \times 1.10 = 217.8 なので、小数点以下を切り捨てて答えは 217 となります。
入力例 2
1 0.01
出力例 2
0
入力例 3
1000000000000000 9.99
出力例 3
9990000000000000
Score : 300 points
Problem Statement
Compute A \times B, truncate its fractional part, and print the result as an integer.
Constraints
- 0 \leq A \leq 10^{15}
- 0 \leq B < 10
- A is an integer.
- B is a number with two digits after the decimal point.
Input
Input is given from Standard Input in the following format:
A B
Output
Print the answer as an integer.
Sample Input 1
198 1.10
Sample Output 1
217
We have 198 \times 1.10 = 217.8. After truncating the fractional part, we have the answer: 217.
Sample Input 2
1 0.01
Sample Output 2
0
Sample Input 3
1000000000000000 9.99
Sample Output 3
9990000000000000
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
正の整数 N が与えられます。 N に対して、以下の操作を繰り返し行うことを考えます。
- はじめに、以下の条件を全て満たす正の整数 z を選ぶ。
- ある素数 p と正の整数 e を用いて、 z=p^e と表せる
- N が z で割り切れる
- 以前の操作で選んだどの整数とも異なる
- N を、N/z に置き換える
最大で何回操作を行うことができるか求めてください。
制約
- 入力はすべて整数である。
- 1 \leq N \leq 10^{12}
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを整数として出力せよ。
入力例 1
24
出力例 1
3
例えば、次のように操作を行うことで、 3 回操作を行うことができます。
- z=2 (=2^1) とする。( 操作後、 N=12 となる。)
- z=3 (=3^1) とする。( 操作後、 N=4 となる。 )
- z=4 (=2^2) とする。( 操作後、 N=1 となる。 )
入力例 2
1
出力例 2
0
一度も操作を行うことができません。
入力例 3
64
出力例 3
3
例えば、次のように操作を行うことで、 3 回操作を行うことができます。
- z=2 (=2^1) とする。( 操作後、 N=32 となる。)
- z=4 (=2^2) とする。( 操作後、 N=8 となる。 )
- z=8 (=2^3) とする。( 操作後、 N=1 となる。 )
入力例 4
1000000007
出力例 4
1
例えば、次のように操作を行うことで、 1 回操作を行うことができます。
- z=1000000007 (=1000000007^1) とする。( 操作後、 N=1 となる。 )
入力例 5
997764507000
出力例 5
7
Score : 400 points
Problem Statement
Given is a positive integer N. Consider repeatedly applying the operation below on N:
- First, choose a positive integer z satisfying all of the conditions below:
- z can be represented as z=p^e, where p is a prime number and e is a positive integer;
- z divides N;
- z is different from all integers chosen in previous operations.
- Then, replace N with N/z.
Find the maximum number of times the operation can be applied.
Constraints
- All values in input are integers.
- 1 \leq N \leq 10^{12}
Input
Input is given from Standard Input in the following format:
N
Output
Print the maximum number of times the operation can be applied.
Sample Input 1
24
Sample Output 1
3
We can apply the operation three times by, for example, making the following choices:
- Choose z=2 (=2^1). (Now we have N=12.)
- Choose z=3 (=3^1). (Now we have N=4.)
- Choose z=4 (=2^2). (Now we have N=1.)
Sample Input 2
1
Sample Output 2
0
We cannot apply the operation at all.
Sample Input 3
64
Sample Output 3
3
We can apply the operation three times by, for example, making the following choices:
- Choose z=2 (=2^1). (Now we have N=32.)
- Choose z=4 (=2^2). (Now we have N=8.)
- Choose z=8 (=2^3). (Now we have N=1.)
Sample Input 4
1000000007
Sample Output 4
1
We can apply the operation once by, for example, making the following choice:
- z=1000000007 (=1000000007^1). (Now we have N=1.)
Sample Input 5
997764507000
Sample Output 5
7
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
N 個の整数 X_1, X_2, \cdots, X_N があり、A_i \leq X_i \leq B_i であることがわかっています。 X_1, X_2, \cdots, X_N の中央値として考えられる値はいくつあるか求めてください。
注記
X_1, X_2, \cdots, X_N の中央値は次のように定義されます。X_1, X_2, \cdots, X_N を昇順に並び替えたものを x_1, x_2, \cdots, x_N とします。
- N が奇数のとき、中央値は x_{(N+1)/2}
- N が偶数のとき、中央値は (x_{N/2} + x_{N/2+1}) / 2
制約
- 2 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq B_i \leq 10^9
- 入力はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N A_1 B_1 A_2 B_2 : A_N B_N
出力
答えを出力せよ。
入力例 1
2 1 2 2 3
出力例 1
3
-
X_1 = 1, X_2 = 2 のとき中央値は \frac{3}{2} です。
-
X_1 = 1, X_2 = 3 のとき中央値は 2 です。
-
X_1 = 2, X_2 = 2 のとき中央値は 2 です。
-
X_1 = 2, X_2 = 3 のとき中央値は \frac{5}{2} です。
よって、中央値として考えられる値は \frac{3}{2}, 2, \frac{5}{2} の 3 つです。
入力例 2
3 100 100 10 10000 1 1000000000
出力例 2
9991
Score : 500 points
Problem Statement
There are N integers X_1, X_2, \cdots, X_N, and we know that A_i \leq X_i \leq B_i. Find the number of different values that the median of X_1, X_2, \cdots, X_N can take.
Notes
The median of X_1, X_2, \cdots, X_N is defined as follows. Let x_1, x_2, \cdots, x_N be the result of sorting X_1, X_2, \cdots, X_N in ascending order.
- If N is odd, the median is x_{(N+1)/2};
- if N is even, the median is (x_{N/2} + x_{N/2+1}) / 2.
Constraints
- 2 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq B_i \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A_1 B_1 A_2 B_2 : A_N B_N
Output
Print the answer.
Sample Input 1
2 1 2 2 3
Sample Output 1
3
-
If X_1 = 1 and X_2 = 2, the median is \frac{3}{2};
-
if X_1 = 1 and X_2 = 3, the median is 2;
-
if X_1 = 2 and X_2 = 2, the median is 2;
-
if X_1 = 2 and X_2 = 3, the median is \frac{5}{2}.
Thus, the median can take three values: \frac{3}{2}, 2, and \frac{5}{2}.
Sample Input 2
3 100 100 10 10000 1 1000000000
Sample Output 2
9991
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
長さ N の正整数列 A_1, A_2, \ldots, A_N と正の整数 S が与えられます。
集合\{1, 2, \ldots , N \} の空でない部分集合 T について、f(T) を以下のように定めます。
- T の空でない部分集合 \{x_1, x_2, \ldots , x_k \} であって、 A_{x_1}+A_{x_2}+\cdots +A_{x_k} = S をみたすものの個数
T として考えられる集合は 2^N-1 通りありますが、そのすべてに対する f(T) の和を求めてください。ただし、答えは非常に大きくなることがあるので、998244353 で割ったあまりを出力してください。
制約
- 入力は全て整数である。
- 1 \leq N \leq 3000
- 1 \leq S \leq 3000
- 1 \leq A_i \leq 3000
入力
入力は以下の形式で標準入力から与えられる。
N S A_1 A_2 ... A_N
出力
f(T) の和を 998244353 で割ったあまりを出力せよ。
入力例 1
3 4 2 2 4
出力例 1
6
それぞれ以下のように計算できて、その和は 6 です。
- f(\{1\}) = 0
- f(\{2\}) = 0
- f(\{3\}) = 1 ( \{3\} の 1 つ)
- f(\{1, 2\}) = 1 ( \{1, 2\} の 1 つ)
- f(\{2, 3\}) = 1 ( \{3\} の 1 つ)
- f(\{1, 3\}) = 1 ( \{3\} の 1 つ)
- f(\{1, 2, 3\}) = 2 ( \{1, 2\}, \{3\} の 2 つ)
入力例 2
5 8 9 9 9 9 9
出力例 2
0
入力例 3
10 10 3 1 4 1 5 9 2 6 5 3
出力例 3
3296
Score : 600 points
Problem Statement
Given are a sequence of N positive integers A_1, A_2, \ldots, A_N and another positive integer S.
For a non-empty subset T of the set \{1, 2, \ldots , N \}, let us define f(T) as follows:
- f(T) is the number of different non-empty subsets \{x_1, x_2, \ldots , x_k \} of T such that A_{x_1}+A_{x_2}+\cdots +A_{x_k} = S.
Find the sum of f(T) over all 2^N-1 subsets T of \{1, 2, \ldots , N \}. Since the sum can be enormous, print it modulo 998244353.
Constraints
- All values in input are integers.
- 1 \leq N \leq 3000
- 1 \leq S \leq 3000
- 1 \leq A_i \leq 3000
Input
Input is given from Standard Input in the following format:
N S A_1 A_2 ... A_N
Output
Print the sum of f(T) modulo 998244353.
Sample Input 1
3 4 2 2 4
Sample Output 1
6
For each T, the value of f(T) is shown below. The sum of these values is 6.
- f(\{1\}) = 0
- f(\{2\}) = 0
- f(\{3\}) = 1 (One subset \{3\} satisfies the condition.)
- f(\{1, 2\}) = 1 (\{1, 2\})
- f(\{2, 3\}) = 1 (\{3\})
- f(\{1, 3\}) = 1 (\{3\})
- f(\{1, 2, 3\}) = 2 (\{1, 2\}, \{3\})
Sample Input 2
5 8 9 9 9 9 9
Sample Output 2
0
Sample Input 3
10 10 3 1 4 1 5 9 2 6 5 3
Sample Output 3
3296