Description
P1) Suppose we have received a large rectangular marble slab of size W × H and we want to cut
the slab to obtain rectangular marble plates of sizes W1 × H1, W2 × H2, . . . , Wn × Hn. Any
piece of marble (the slab or the plates cut from it) can be cut either horizontally or vertically
into two rectangular plates with integral widths and heights, cutting completely through that
piece. This is the only way to cut pieces and pieces cannot be joined together.
Task Description Day-2
IOI 2004
Athens Version 1.1
Greece phidias
21.09.04 Page 1 of 2 phidias
Phidias
PROBLEM
Famous ancient Greek sculptor Phidias is making preparations to build another marvelous
monument. For this purpose he needs rectangular marble plates of sizes W1 × H1, W2 ×
H2, …, WN × HN.
Recently, Phidias has received a large rectangular marble slab. He wants to cut the slab to
obtain plates of the desired sizes. Any piece of marble (the slab or the plates cut from it) can
be cut either horizontally or vertically into two rectangular plates with integral widths and
heights, cutting completely through that piece. This is the only way to cut pieces and pieces
cannot be joined together. Since the marble has a pattern on it, the plates cannot be rotated:
if Phidias cuts a plate of size A × B then it cannot be used as a plate of size B × A unless A =
B. He can make zero or more plates of each desired size. A marble plate is wasted if it is
not of any of the desired sizes after all cuts are completed. Phidias wonders how to cut the
initial slab so that as little of it as possible will be wasted.
As an example, assume that in the figure below the width of the original slab is 21 and the
height of the original slab is 11, and the desired plate sizes are 10 × 4, 6 × 2, 7 × 5, and 15 ×
10. The minimum possible area wasted is 10, and the figure shows one sequence of cuts
with total waste area of size 10.
Your task is to write a program that, given the size of the original slab and the desired plate
sizes, calculates the minimum total area of the original slab that must be wasted.
INPUT
The input file name is phidias.in. The first line of input contains two integers: first W,
the width of the original slab, and then H, the height of the original slab. The second line
contains one integer N: the number of desired plate sizes. The following N lines contain the
desired plate sizes. Each of these lines contains two integers: first the width Wi and then the
height Hi of that desired plate size (1 ≤ i ≤ N).
OUTPUT
The output file name is phidias.out. The file is to contain one line with a single integer:
the minimum total area of the original slab that must be wasted.
10 4 10 4
6 2 6 2 6 2
7 5 7 5 7 5
Since the marble has a pattern on it, the plates cannot be rotated: if a plate of size A × B
is cut, then it cannot be used as a plate of size B × A unless A = B. We can make zero or
more plates of each desired size. A marble plate is wasted if it is not of any of the desired sizes
after all cuts are completed. The question is how to cut the initial slab so that as little of it
as possible will be wasted.
As an example, assume that original slab is 21 × 11 and the desired plate sizes are 10 × 4, 6 ×
2, 7 × 5, and 15 × 10. The minimum possible area wasted is 10, and the figure (below) shows
one sequence of cuts with total waste area of size 10. Design an algorithm that runs in time
polynomial in n, W, H that outputs the minimum possible waste area.
P2) Draw out a maximum s-t flow for the graph below, and the corresponding residual graph Gf .
What is the minimum cut that corresponds to this max flow?
s a b c t
d
e
8
3
3
2
4
1 3
3
2 1
3
4 5
P3) Given a directed graph G such that each edge has capacity c(e). Suppose that we have assigned
every node v a number r(v) if r(v) > 0 it means that v has a supply r(v) units of electricity
7-1
and if r(v) is negative it means v has a demand of −r(v) units of electricity. We want to see if
it possibly to route the supply and satisfy all demand while we respect the capacity of every
edge. Design an algorithm that runs in time polynomial in n and maxec(e) and outputs “yes”
if we can satisfy all demands and “no” otherwise. For example, you should output yes for the
left graph below and no for the right graph.
+3 0
−1 −2
2
1
1
2
+3 0
−1 −2
1
1
1
1
P4) Extra Credit: You are given an m × n array of real numbers. Suppose that the numbers in
each row add up to an integer and the numbers in each column add up to an integer. You want
to substitute each number A[i, j] with ⌊A[i, j]⌋ or ⌈A[i, j]⌉ such that the sum of the numbers in
each row and each column remain invariant. Design a polynomial time algorithm that outputs
the integer array.
For example, if the input is the left table you can output the right table. Note the sum of
numbers in each row (and each column) of the left table is the same as the sum of the numbers
of the same row (resp. the same column) in the right table.
0.4 0.1 1.5
0.6 1.9 0.5 ⇒
1 0 1
0 2 1
7-2
