Задача . C. Секрет

Самый Великий Секрет состоит из n слов, пронумерованных натуральными числами от 1 до n. Секрет требуется разделить между k Хранителями (пронумеруем их натуральными числами от 1 до k), i-ый Хранитель получает непустое множество слов c номерами из множества U_i = (u_i, 1, u_i, 2, ..., u_i, |Ui|). Здесь и далее будем подразумевать, что при записи элементов множества они перечисляются в порядке возрастания.

Скажем, что секрет надежно хранится, если выполняются следующие условия:

• для любых двух индексов i, j (1 ≤ i < j ≤ k) пересечение множеств U_i и U_j — пустое множество;
• объединение множеств U₁, U₂, ..., U_k — это множество (1, 2, ..., n);
• в каждом множестве U_i его элементы u_i, 1, u_i, 2, ..., u_i, |Ui| не образуют арифметическую прогрессию (в частности должно выполняться |U_i| ≥ 3).

Напомним, что элементы множества (u₁, u₂, ..., u_s) образуют арифметическую прогрессию, если существует такое число d, что для всех i (1 ≤ i < s) выполняется: u_i + d = u_i + 1. Например, элементы множеств (5), (1, 10) и (1, 5, 9) образуют арифметические прогрессии, а множеств (1, 2, 4) и (3, 6, 8) — не образуют.

Вам требуется найти разбиение множества слов на подмножества U₁, U₂, ..., U_k, чтобы секрет был надежно сохранен, либо указать, что искомого разбиения не существует.