Recursive sandwiches P53666


pdf   zip


Nowadays there are sandwiches of almost any ingredient. A crazy chef has just discovered recursion, so he is considering making sandwiches of sandwiches (of sandwiches ...). Since thinking in three dimensions is somehow difficult, he first wants to study the following two-dimensional model for making rectangular sandwiches.

Square pieces, with height 1 and length 1, correspond to ingredients; rectangular pieces, with height 1 and length ℓ (for any natural number ℓ ≥ 2), correspond to slices of bread. Then, a recursive sandwich (RS) is defined by these rules:

  1. Any single ingredient is a RS.
  2. Let h ≥ 1, ℓ ≥ 2, and let S be any sequence R1, …, Rn of RS’s where n ≥ 2, and such that height(Ri) = h for every 1 ≤ in, and ∑i=1n length(Ri) = ℓ. Then
    1. The result of placing a 1 × ℓ slice at the bottom of S is a RS.
    2. The result of placing a 1 × ℓ slice at the top of S and another 1 × ℓ slice at the bottom of S is a RS.
  3. There are no RSs other than those constructable from rules 1, 2(a) and 2(b).

These are some examples of recursive sandwiches:

And these are some examples of wrong sandwiches:

Write a program to tell if some given sandwiches follow the rules of the crazy chef or not.


Input consists of several cases. Every case begins with the name of the sandwich, followed by its height H, its length L, and its number of pieces m. Then follow m triples of integer numbers r, c and ℓ describing every piece: (r, c) is the position of the left square of the piece; ℓ is the length of the piece. Assume 1 ≤ H ≤ 20 and 1 ≤ L ≤ 100. The lower-left position of a sandwich is (1, 1). The sum of the areas of the pieces is exactly H × L, and every position in [1,H] × [1,L] is covered by a piece.

(The sandwich aaa in the sample input is the second of the recursive sandwiches given as example. The sandwich bbb is the fourth of the wrong sandwiches.)


For every given sandwich, tell if it is a recursive sandwich or not.

Public test cases
  • Input

    2 2 3
    2 1 1
    2 2 1
    1 1 2
    3 1 3
    1 1 1
    2 1 1
    3 1 1


    aaa is a recursive sandwich
    bbb is NOT a recursive sandwich
  • Information
    Salvador Roura
    Official solutions
    User solutions
    Tercer Concurs de Programació de la UPC - Final