Recursive sandwiches P53666


Statement
 

pdf   zip

html

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

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.)

Output

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

Public test cases
  • Input

    aaa
    2 2 3
    2 1 1
    2 2 1
    1 1 2
    
    bbb
    3 1 3
    1 1 1
    2 1 1
    3 1 1
    

    Output

    aaa is a recursive sandwich
    bbb is NOT a recursive sandwich
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++
    Event
    Tercer Concurs de Programació de la UPC - Final
    Date
    2005-09-28