Indian Computing Olympiad

Training Material

Dynamic Programming→Phidias (IOI 2004)

Phidias is a sculptor who has a large rectangular slab of marble of size W×L (1 ≤ W,L ≤ 600). He wants to cut out rectangular tiles of specific sizes (a1,b1), (a2,b2) … (ak,bk). He is willing to take as many of each type as are available. The marble slab has a pattern and so tiles cannot be rotated. This means that it is not acceptable to produce a tile of (bi,ai) instead of (ai,bi).

To cut a slab of marble, he can can make a full horizontal or vertical cut across the slab at an integer point.

After making a sequence of cuts, Phidias will arrive at some pieces of marble that are wasted — they cannot be cut down to any of the desired tiles.

Find a sequence of cuts that will minimize the wastage.