A - White Cells

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
B - Can you solve this?

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.
C - Energy Drink Collector

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.
D - XOR World

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