Državno natjecanje iz informatike 2018. / Prva podskupina (1. i 2. razred) - 2. zadatak

Veliko je finale kulinarskog TV showa “Tri, dva, jedan, kukaj”, nasljednika popularnog showa “DisasterChef”. Svaki natjecatelj doveden je u kuhinju novootvorenog restorana “Uma Gurman”, u nekim krugovima poznatog i kao “Kod Kreše”. U kuhinji se nalazi \(N\) različitih sorti ljutih papričica od kojih natjecatelj treba skuhati što više raznolikih jela i ponuditi ih gostima restorana. Jelo može sadržavati bilo koji skup papričica. Prema pravilima showa, jela \(A\) i \(B\) proglašavaju se dovoljno različitima ako zadovoljavaju sljedeće uvjete:

\(1\). Sadrže međusobno različit broj sorti papričica, tj. u jelu \(A\) ili u jelu \(B\) nalazi se strogo više ljutih okusa nego u drugom jelu.

\(2\). Postoji barem jedna sorta papričica u jelu \(A\) koje nema u jelu B.

\(3\). Postoji barem jedna sorta papričica u jelu \(B\) koje nema u jelu A.

Vaš je zadatak pomoći natjecatelju showa i pronaći što veći broj jela koji je moguće skuhati od \(N\) sorti papričica, tako da su svaka dva od tih jela dovoljno različita. Za detalje pogledajte sekciju Bodovanje.

Ulazni​ podaci

U jedinom retku nalazi se prirodan broj \(N ( 2 \leq N \leq 1000 )\), broj sorti ljutih papričica. Papričice su označene brojevima od \(1\) do N.

Izlazni podaci

Svako jelo ispišite u zaseban redak kao niz papričica koji ga sačinjava odvojenih razmakom.

Papričice se ne smiju ponavljati unutar pojedinog jela, ali njihov redoslijed nije bitan. Nije bitan ni redoslijed ispisanih jela.

Bodovanje

Broj osvojenih bodova u test podatku ovisi o broju skuhanih jela. Ako ste skuhali \(K\) jela, a najveći mogući broj jela u tom test podatku iznosi M, tada za taj test podatak osvajate \(5\) * (K / M) bodova (od mogućih \(5 )\), zaokruženo na niži cijeli broj. Ako vaše rješenje ne zadovoljava tražene uvjete, osvaja nula bodova bez obzira na broj jela.

U test podatcima ukupno vrijednima \(50 \%\) bodova bit će \(N \leq 64\).

Primjeri test​ podataka

Ulaz

3

Izlaz

1
2 3

Ulaz

5

Izlaz

1 2 3 4
1 3 5
2 5