0188. Hobbit's Party

Input file name: input.txt
Output file name: output.txt
Time limit: 250 ms
Memory limit: 16 megabytes

Все знают, что хоббиты любят устраивать различные вечеринки и празднества. В Шире живет N (2 < N < 256) хоббитов. Они решили провести Грандиозный Праздник (ГП), длящийся несколько дней. На каждый день был составлен список приглашенных - некоторое непустое подмножество из всех жителей Шира. Для того, что бы всем было весело и никто не скучал, необходимо чтобы для любых двух разных дней (скажем А и В) ГП существовал бы хотя бы один хоббит, приглашенный как в день А, так и в день В. Однако, чтобы никто не поссорился для любых трех разных дней А, В, С не должно существовать хоббита, приглашенного в день А, В и С. Жители Шира заинтересованы в наибольшей продолжительности ГП. Ваша задача для данного числа N указать наибольшую продолжительность ГП и списки приглашенных на каждый день.

Формат входного файла

Во входном файле записано натуральное число N.

Формат выходного файла

В первой строке выходного файла выведите число K - наибольшую продолжительность ГП в днях. Далее в К строках выведите списки приглашенных (через пробел). Каждый список выводите на отдельной строке.

Пример:

input.txtoutput.txt
4 3 1 2 2 3 1 3


Source: Petrozavodsk Winter 2003. SaratovSU #3 Training Contest, Wednesday, February 05

Discuss       Submit a solution



Printable version