Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 150 点
問題文
実数 X が小数点以下第 3 位まで与えられます。
実数 X を以下の条件を満たすように出力してください。
- 小数点以下の部分について、末尾に
0を付けない - 末尾に過剰な小数点を付けない
制約
- 0 \le X < 100
- X は小数点以下第 3 位まで与えられる
入力
入力は以下の形式で標準入力から与えられる。
X
出力
答えを出力せよ。
入力例 1
1.012
出力例 1
1.012
1.012 はそのまま出力しても構いません。
入力例 2
12.340
出力例 2
12.34
12.340 を末尾に 0 を付けずに出力すると 12.34 となります。
入力例 3
99.900
出力例 3
99.9
99.900 を末尾に 0 を付けずに出力すると 99.9 となります。
入力例 4
0.000
出力例 4
0
0.000 を末尾に 0 や過剰な小数点を付けずに出力すると 0 となります。
Score : 150 points
Problem Statement
A real number X is given to the third decimal place.
Print the real number X under the following conditions.
- The decimal part must not have trailing
0s. - There must not be an unnecessary trailing decimal point.
Constraints
- 0 \le X < 100
- X is given to the third decimal place.
Input
The input is given from Standard Input in the following format:
X
Output
Output the answer.
Sample Input 1
1.012
Sample Output 1
1.012
1.012 can be printed as it is.
Sample Input 2
12.340
Sample Output 2
12.34
Printing 12.340 without the trailing 0 results in 12.34.
Sample Input 3
99.900
Sample Output 3
99.9
Printing 99.900 without the trailing 0s results in 99.9.
Sample Input 4
0.000
Sample Output 4
0
Printing 0.000 without trailing 0s or an unnecessary decimal point results in 0.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
a+b+c \leq S かつ a \times b \times c \leq T を満たす非負整数の組 (a,b,c) はいくつありますか？
制約
- 0 \leq S \leq 100
- 0 \leq T \leq 10000
- S, T は整数である。
入力
入力は以下の形式で標準入力から与えられる。
S T
出力
条件を満たす非負整数の組 (a,b,c) の個数を出力せよ。
入力例 1
1 0
出力例 1
4
条件を満たす非負整数の組 (a,b,c) は (0,0,0), (0,0,1), (0,1,0), (1,0,0) の 4 つです。
入力例 2
2 5
出力例 2
10
入力例 3
10 10
出力例 3
213
入力例 4
30 100
出力例 4
2471
Score : 200 points
Problem Statement
How many triples of non-negative integers (a, b, c) satisfy a+b+c \leq S and a \times b \times c \leq T?
Constraints
- 0 \leq S \leq 100
- 0 \leq T \leq 10000
- S and T are integers.
Input
Input is given from Standard Input in the following format:
S T
Output
Print the number of triples of non-negative integers (a,b,c) satisfying the conditions.
Sample Input 1
1 0
Sample Output 1
4
The triples (a,b,c) satisfying the conditions are (0,0,0), (0,0,1), (0,1,0), and (1,0,0) ― there are four of them.
Sample Input 2
2 5
Sample Output 2
10
Sample Input 3
10 10
Sample Output 3
213
Sample Input 4
30 100
Sample Output 4
2471
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
長さ N の数列 A=(A_1,\ldots,A_N) が与えられます。
1\leq i,j \leq N である組 (i,j) であって、A_i-A_j=X となるものが存在するかどうか判定してください。
制約
- 2 \leq N \leq 2\times 10^5
- -10^9 \leq A_i \leq 10^9
- -10^9 \leq X \leq 10^9
- 入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N X A_1 \ldots A_N
出力
1\leq i,j \leq N である組 (i,j) であって、A_i-A_j=X となるものが存在するとき Yes、存在しないとき No と出力せよ。
入力例 1
6 5 3 1 4 1 5 9
出力例 1
Yes
A_6-A_3=9-4=5 です。
入力例 2
6 -4 -2 -7 -1 -8 -2 -8
出力例 2
No
A_i-A_j=-4 となる組 (i,j) は存在しません。
入力例 3
2 0 141421356 17320508
出力例 3
Yes
A_1-A_1=0 です。
Score : 300 points
Problem Statement
You are given a sequence of N numbers: A=(A_1,\ldots,A_N).
Determine whether there is a pair (i,j) with 1\leq i,j \leq N such that A_i-A_j=X.
Constraints
- 2 \leq N \leq 2\times 10^5
- -10^9 \leq A_i \leq 10^9
- -10^9 \leq X \leq 10^9
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N X A_1 \ldots A_N
Output
Print Yes if there is a pair (i,j) with 1\leq i,j \leq N such that A_i-A_j=X, and No otherwise.
Sample Input 1
6 5 3 1 4 1 5 9
Sample Output 1
Yes
We have A_6-A_3=9-4=5.
Sample Input 2
6 -4 -2 -7 -1 -8 -2 -8
Sample Output 2
No
There is no pair (i,j) such that A_i-A_j=-4.
Sample Input 3
2 0 141421356 17320508
Sample Output 3
Yes
We have A_1-A_1=0.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
1 以上 N 以下の整数からなる集合が M 個あり、順に S_1, S_2, \dots, S_M と呼びます。
S_i は C_i 個の整数 a_{i, 1}, a_{i, 2}, \dots, a_{i, C_i} からなります。
M 個の集合から 1 個以上の集合を選ぶ方法は 2^M-1 通りあります。
このうち、次の条件を満たす選び方は何通りありますか？
- 1 \leq x \leq N を満たす全ての整数 x に対して、選んだ集合の中に x を含む集合が少なくとも 1 個存在する。
制約
- 1 \leq N \leq 10
- 1 \leq M \leq 10
- 1 \leq C_i \leq N
- 1 \leq a_{i,1} \lt a_{i,2} \lt \dots \lt a_{i,C_i} \leq N
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M
C_1
a_{1,1} a_{1,2} \dots a_{1,C_1}
C_2
a_{2,1} a_{2,2} \dots a_{2,C_2}
\vdots
C_M
a_{M,1} a_{M,2} \dots a_{M,C_M}
出力
問題文の条件を満たす集合の選び方の数を出力せよ。
入力例 1
3 3 2 1 2 2 1 3 1 2
出力例 1
3
入力で与えられている集合はそれぞれ S_1 = \lbrace 1, 2 \rbrace, S_2 = \lbrace 1, 3 \rbrace, S_3 = \lbrace 2 \rbrace です。
問題文の条件を満たす集合の選び方は次の 3 通りです。
- S_1, S_2 を選ぶ。
- S_1, S_2, S_3 を選ぶ。
- S_2, S_3 を選ぶ。
入力例 2
4 2 2 1 2 2 1 3
出力例 2
0
問題文の条件を満たす選び方が存在しない場合もあります。
入力例 3
6 6 3 2 3 6 3 2 4 6 2 3 6 3 1 5 6 3 1 3 6 2 1 4
出力例 3
18
Score : 300 points
Problem Statement
There are M sets, called S_1, S_2, \dots, S_M, consisting of integers between 1 and N.
S_i consists of C_i integers a_{i, 1}, a_{i, 2}, \dots, a_{i, C_i}.
There are (2^M-1) ways to choose one or more sets from the M sets.
How many of them satisfy the following condition?
- For all integers x such that 1 \leq x \leq N, there is at least one chosen set containing x.
Constraints
- 1 \leq N \leq 10
- 1 \leq M \leq 10
- 1 \leq C_i \leq N
- 1 \leq a_{i,1} \lt a_{i,2} \lt \dots \lt a_{i,C_i} \leq N
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N M
C_1
a_{1,1} a_{1,2} \dots a_{1,C_1}
C_2
a_{2,1} a_{2,2} \dots a_{2,C_2}
\vdots
C_M
a_{M,1} a_{M,2} \dots a_{M,C_M}
Output
Print the number of ways to choose sets that satisfy the conditions in the Problem Statement.
Sample Input 1
3 3 2 1 2 2 1 3 1 2
Sample Output 1
3
The sets given in the input are S_1 = \lbrace 1, 2 \rbrace, S_2 = \lbrace 1, 3 \rbrace, S_3 = \lbrace 2 \rbrace.
The following three ways satisfy the conditions in the Problem Statement:
- choosing S_1, S_2;
- choosing S_1, S_2, S_3;
- choosing S_2, S_3.
Sample Input 2
4 2 2 1 2 2 1 3
Sample Output 2
0
There may be no way to choose sets that satisfies the conditions in the Problem Statement.
Sample Input 3
6 6 3 2 3 6 3 2 4 6 2 3 6 3 1 5 6 3 1 3 6 2 1 4
Sample Output 3
18
Time Limit: 3 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
高橋君は N 種類の硬貨をそれぞれ何枚か持っており、 具体的には、1\leq i\leq N について A_i 円硬貨を B_i 枚持っています。
高橋君が現在持っている硬貨を用いて、（お釣りが出ないように）ちょうど X 円を支払うことができるか判定してください。
制約
- 1\leq N\leq 50
- 1\leq X\leq 10^4
- 1\leq A_i\leq 100
- 1\leq B_i\leq 50
- A_i はすべて異なる。
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N X A_1 B_1 A_2 B_2 \vdots A_N B_N
出力
高橋君が現在持っている硬貨を用いてちょうど X 円を支払うことができる場合は Yes を、
できない場合は No を出力せよ。
入力例 1
2 19 2 3 5 6
出力例 1
Yes
高橋君は 2 円硬貨を 3 枚、5 円硬貨を 6 枚持っています。
このうち、2 円硬貨を 2 枚、5 円硬貨を 3 枚用いることでちょうど 2\times 2+5\times 3=19 円を支払うことができます。
よって、Yes を出力します。
入力例 2
2 18 2 3 5 6
出力例 2
No
持っている硬貨をどのように組み合わせてもちょうど 18 円を支払うことはできません。
よって、No を出力します。
入力例 3
3 1001 1 1 2 1 100 10
出力例 3
Yes
1 枚も使用しない硬貨が存在しても構いません。
Score : 400 points
Problem Statement
Takahashi has N kinds of coins; specifically, for 1\leq i\leq N, he has B_i coins worth A_i yen (the currency in Japan) each.
Determine if Takahashi can pay exactly X yen (without change) with the coins he currently has.
Constraints
- 1\leq N\leq 50
- 1\leq X\leq 10^4
- 1\leq A_i\leq 100
- 1\leq B_i\leq 50
- A_i are pairwise distinct.
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N X A_1 B_1 A_2 B_2 \vdots A_N B_N
Output
Print Yes if Takahashi can pay exactly X yen with the coins he currently has;
print No otherwise.
Sample Input 1
2 19 2 3 5 6
Sample Output 1
Yes
Takahashi has three 2-yen coins and six 5-yen coins.
He can use two 2-yen coins and three 5-yen coins to pay exactly 2\times 2+5\times 3=19 yen.
Thus, Yes should be printed.
Sample Input 2
2 18 2 3 5 6
Sample Output 2
No
There is no combination of the coins that he can use to pay exactly 18 yen.
Thus, No should be printed.
Sample Input 3
3 1001 1 1 2 1 100 10
Sample Output 3
Yes
He need not use all kinds of coins.