Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
H 行 W 列の白色のマス目があります。
あなたは h 個の行と w 個の列を選び、選んだ行または列に含まれるマス目を全て黒色で塗りつぶします。
白色のマス目はいくつ残るでしょうか。
なお、残る白色のマス目の数は行や列の選び方によらないことが証明できます。
制約
- 入力は全て整数である。
- 1 \leq H, W \leq 20
- 1 \leq h \leq H
- 1 \leq w \leq W
入力
入力は以下の形式で標準入力から与えられる。
H W h w
出力
残る白色のマス目の数を出力せよ。
入力例 1
3 2 2 1
出力例 1
1
3 行 2 列の白色のマス目があり、2 行と 1 列を選んで黒色で塗りつぶしたとき、白色のマス目は必ず 1 個だけ残ります。
入力例 2
5 5 2 3
出力例 2
6
入力例 3
2 4 2 4
出力例 3
0
Score : 100 points
Problem Statement
There are H rows and W columns of white square cells.
You will choose h of the rows and w of the columns, and paint all of the cells contained in those rows or columns.
How many white cells will remain?
It can be proved that this count does not depend on what rows and columns are chosen.
Constraints
- All values in input are integers.
- 1 \leq H, W \leq 20
- 1 \leq h \leq H
- 1 \leq w \leq W
Input
Input is given from Standard Input in the following format:
H W h w
Output
Print the number of white cells that will remain.
Sample Input 1
3 2 2 1
Sample Output 1
1
There are 3 rows and 2 columns of cells. When two rows and one column are chosen and painted in black, there is always one white cell that remains.
Sample Input 2
5 5 2 3
Sample Output 2
6
Sample Input 3
2 4 2 4
Sample Output 3
0
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
N 個のソースコードがあり、i 個目のソースコードの特徴は A_{i1}, A_{i2}, ..., A_{iM} の M 個の整数で表されます。
また、整数 B_1, B_2, ..., B_M と 整数 C が与えられます。
A_{i1} B_1 + A_{i2} B_2 + ... + A_{iM} B_M + C > 0 のときに限り、i 個目のソースコードはこの問題に正答するソースコードです。
N 個のソースコードのうち、この問題に正答するソースコードの個数を求めてください。
制約
- 入力は全て整数である。
- 1 \leq N, M \leq 20
- -100 \leq A_{ij} \leq 100
- -100 \leq B_i \leq 100
- -100 \leq C \leq 100
入力
入力は以下の形式で標準入力から与えられる。
N M C B_1 B_2 ... B_M A_{11} A_{12} ... A_{1M} A_{21} A_{22} ... A_{2M} \vdots A_{N1} A_{N2} ... A_{NM}
出力
N 個のソースコードのうち、この問題に正答するソースコードの個数を出力せよ。
入力例 1
2 3 -10 1 2 3 3 2 1 1 2 2
出力例 1
1
以下のように 2 個目のソースコードのみがこの問題に正答します。
- 3 \times 1 + 2 \times 2 + 1 \times 3 + (-10) = 0 \leq 0 なので 1 個目のソースコードはこの問題に正答しません。
- 1 \times 1 + 2 \times 2 + 2 \times 3 + (-10) = 1 > 0 なので 2 個目のソースコードはこの問題に正答します。
入力例 2
5 2 -4 -2 5 100 41 100 40 -3 0 -6 -2 18 -13
出力例 2
2
入力例 3
3 3 0 100 -100 0 0 100 100 100 100 100 -100 100 100
出力例 3
0
全て Wrong Answer です。あなたのソースコードは含めません。
Score : 200 points
Problem Statement
There are N pieces of source code. The characteristics of the i-th code is represented by M integers A_{i1}, A_{i2}, ..., A_{iM}.
Additionally, you are given integers B_1, B_2, ..., B_M and C.
The i-th code correctly solves this problem if and only if A_{i1} B_1 + A_{i2} B_2 + ... + A_{iM} B_M + C > 0.
Among the N codes, find the number of codes that correctly solve this problem.
Constraints
- All values in input are integers.
- 1 \leq N, M \leq 20
- -100 \leq A_{ij} \leq 100
- -100 \leq B_i \leq 100
- -100 \leq C \leq 100
Input
Input is given from Standard Input in the following format:
N M C B_1 B_2 ... B_M A_{11} A_{12} ... A_{1M} A_{21} A_{22} ... A_{2M} \vdots A_{N1} A_{N2} ... A_{NM}
Output
Print the number of codes among the given N codes that correctly solve this problem.
Sample Input 1
2 3 -10 1 2 3 3 2 1 1 2 2
Sample Output 1
1
Only the second code correctly solves this problem, as follows:
- Since 3 \times 1 + 2 \times 2 + 1 \times 3 + (-10) = 0 \leq 0, the first code does not solve this problem.
- 1 \times 1 + 2 \times 2 + 2 \times 3 + (-10) = 1 > 0, the second code solves this problem.
Sample Input 2
5 2 -4 -2 5 100 41 100 40 -3 0 -6 -2 18 -13
Sample Output 2
2
Sample Input 3
3 3 0 100 -100 0 0 100 100 100 100 100 -100 100 100
Sample Output 3
0
All of them are Wrong Answer. Except yours.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
栄養ドリンクにレーティング上昇効果があると聞いた高橋くんは、M 本の栄養ドリンクを買い集めることにしました。
栄養ドリンクが売られている店は N 軒あり、i 軒目の店では 1 本 A_i 円の栄養ドリンクを B_i 本まで買うことができます。
最小で何円あれば M 本の栄養ドリンクを買い集めることができるでしょうか。
なお、与えられる入力では、十分なお金があれば M 本の栄養ドリンクを買い集められることが保証されます。
制約
- 入力は全て整数である。
- 1 \leq N, M \leq 10^5
- 1 \leq A_i \leq 10^9
- 1 \leq B_i \leq 10^5
- B_1 + ... + B_N \geq M
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 B_1 A_2 B_2 \vdots A_N B_N
出力
M 本の栄養ドリンクを買い集めるのに必要な最小の金額を出力せよ。
入力例 1
2 5 4 9 2 4
出力例 1
12
12 円あれば 1 軒目の店で 1 本、2 軒目の店で 4 本の栄養ドリンクを購入し、合計 5 本の栄養ドリンクを買い集めることができます。一方、11 円以下では 5 本の栄養ドリンクを買い集めることができません。
入力例 2
4 30 6 18 2 5 3 10 7 9
出力例 2
130
入力例 3
1 100000 1000000000 100000
出力例 3
100000000000000
出力が 32 ビット整数型におさまらないことがあります。
Score : 300 points
Problem Statement
Hearing that energy drinks increase rating in those sites, Takahashi decides to buy up M cans of energy drinks.
There are N stores that sell energy drinks. In the i-th store, he can buy at most B_i cans of energy drinks for A_i yen (the currency of Japan) each.
What is the minimum amount of money with which he can buy M cans of energy drinks?
It is guaranteed that, in the given inputs, a sufficient amount of money can always buy M cans of energy drinks.
Constraints
- All values in input are integers.
- 1 \leq N, M \leq 10^5
- 1 \leq A_i \leq 10^9
- 1 \leq B_i \leq 10^5
- B_1 + ... + B_N \geq M
Input
Input is given from Standard Input in the following format:
N M A_1 B_1 A_2 B_2 \vdots A_N B_N
Output
Print the minimum amount of money with which Takahashi can buy M cans of energy drinks.
Sample Input 1
2 5 4 9 2 4
Sample Output 1
12
With 12 yen, we can buy one drink at the first store and four drinks at the second store, for the total of five drinks. However, we cannot buy 5 drinks with 11 yen or less.
Sample Input 2
4 30 6 18 2 5 3 10 7 9
Sample Output 2
130
Sample Input 3
1 100000 1000000000 100000
Sample Output 3
100000000000000
The output may not fit into a 32-bit integer type.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
f(A, B) を A, A+1, ..., B の排他的論理和としたとき、f(A, B) を求めてください。
排他的論理和とは
整数 c_1, c_2, ..., c_n のビットごとの排他的論理和 y は、以下のように定義されます。
- y を二進表記した際の 2^k (k \geq 0) の位の数は、c_1, c_2, ..., c_n のうち、二進表記した際の 2^k の位の数が 1 となるものが奇数個ならば 1、偶数個ならば 0 である。
例えば、3 と 5 の排他的論理和は 6 です(二進数表記すると: 011
と 101
の排他的論理和は 110
です)。
制約
- 入力は全て整数である。
- 0 \leq A \leq B \leq 10^{12}
入力
入力は以下の形式で標準入力から与えられる。
A B
出力
f(A, B) を計算し、出力せよ。
入力例 1
2 4
出力例 1
5
2, 3, 4 は 2 進数でそれぞれ 010
, 011
, 100
です。
これらの排他的論理和は 101
であり、これを 10 進数表記にすると 5 になります。
入力例 2
123 456
出力例 2
435
入力例 3
123456789012 123456789012
出力例 3
123456789012
Score : 400 points
Problem Statement
Let f(A, B) be the exclusive OR of A, A+1, ..., B. Find f(A, B).
What is exclusive OR?
The bitwise exclusive OR of integers c_1, c_2, ..., c_n (let us call it y) is defined as follows:
- When y is written in base two, the digit in the 2^k's place (k \geq 0) is 1 if, the number of integers among c_1, c_2, ...c_m whose binary representations have 1 in the 2^k's place, is odd, and 0 if that count is even.
For example, the exclusive OR of 3 and 5 is 6. (When written in base two: the exclusive OR of 011
and 101
is 110
.)
Constraints
- All values in input are integers.
- 0 \leq A \leq B \leq 10^{12}
Input
Input is given from Standard Input in the following format:
A B
Output
Compute f(A, B) and print it.
Sample Input 1
2 4
Sample Output 1
5
2, 3, 4 are 010
, 011
, 100
in base two, respectively.
The exclusive OR of these is 101
, which is 5 in base ten.
Sample Input 2
123 456
Sample Output 2
435
Sample Input 3
123456789012 123456789012
Sample Output 3
123456789012