Plafon függvény

A Fejlett Plafongyártó Vállalat (Advanced Ceiling Manufacturers, ACM) a Hihetetlenül Beomlásbiztos Plafonjai (Incredibly Collapse-Proof Ceiling, ICPC) új sorozatának tulajdonságait elemzi. Egy ilyen plafon n anyagrétegből áll, amelyek mindegyike különböző (pozitív egész számmal megadott) beomlás-ellenállási értékkel rendelkezik. Az ACM által tervezett vizsgálat veszi az egyes rétegek beomlás-ellenállási értékeit, eltárolja őket egy bináris keresőfában, majd ellenőrzi, hogy a kapott fa formája mutat-e bármilyen korrelációt a teljes szerkezet minőségével. Mert hát miért is ne mutatna?

Pontosabban fogalmazva: az ACM veszi az egyes rétegek beomlás-ellenállási értékeit a felső rétegtől az alsó rétegig haladva, és egyesével beszúrja őket egy fába. Egy v érték beszúrásának szabályai a következők:

• Ha a fa üres, legyen v a fa gyökere.
• Ha a fa nem üres, hasonlítsuk össze v-t a fa gyökerével. Ha v kisebb, szúrjuk be v-t a gyökér bal oldali részfájába, különben szúrjuk be v-t a jobb oldali részfába.

Az ACM néhány plafon prototípust szeretne bevizsgálni úgy, hogy megpróbálja beomlasztani őket. Az azonos formájú fákat eredményező plafon prototípusokat együtt szeretné vizsgálni.

Tegyük fel például, hogy az ACM öt plafon prototípust vizsgál, amelyek mindegyike három rétegből áll, ahogy az 1. példa bemenetben és az 1. ábrán látható. Az első prototípus felső rétegének a beomlás-ellenállási értéke 2, a középső rétegének 7, az alsó rétegének pedig 1. A második prototípus rétegeinek a beomlás-ellenállási értékei 3, 1 és 4 – mégis ez a két prototípus ugyanazt a faformát eredményezi, ezért az ACM együtt vizsgálja őket.

A feladatod, hogy adott protípusok esetén meghatározd, hogy hány különböző faformát eredményeznek.

1. ábra: Az 1. példa bemenetben látható plafon prototípusokból következő négy faforma.

A bemenet specifikációja

A bemenet számos tesztesetet tartalmaz. Minden teszteset első sorában két egész szám szerepel: n (1 ≤ n ≤ 50), amely a vizsgálandó plafon prototípusok számát, és k (1 ≤ k ≤ 20), amely az egyes prototípusokban lévő rétegek számát adja meg.

A következő n sor írja le a plafon prototípusokat. Ezek a sorok mind k különböző egész számot tartalmaznak (1 és 10⁶ között), amelyek egy konkrét plafon prototípus egyes rétegeinek a beomlás-ellenállási értékeit adják meg, felülről lefelé haladva.

A kimenet specifikációja

Minden tesztesetre egy sort kell a kimenetre írni, amely a különböző faformák számát tartalmazza.

Példa bemenet

1. 5 3
2. 2 7 1
3. 3 1 4
4. 1 5 9
5. 2 6 5
6. 9 7 3
7. 3 4
8. 3 1 2 40000
9. 3 4 2 1
10. 33 42 17 23

letöltés szöveges állományként

A példa bemenethez tartozó kimenet

1. 4
2. 2

letöltés szöveges állományként