Problem: You have mined a large slab or marble from a quarry. For simp, suppose the marble slab is a rectangle measuring n centimeters in height and m centimeters in width. You want to cut the slab into smaller rectangles of integral pieces (i.e. every small rectangle piece should be a cm by b cm dimension for positive integers a and b) of various sizes. You have a marble saw that can make either horizontal or vertical cuts across any rectangular slab. At any time, you can query the spot price P[x, y] by an x cm by y cm marble rectangle in O(1)-time, for any positive integers x and y.
1
