0226. Гири

Input file name:	weights.in
Output file name:	weights.out
Time limit:	2 s
Memory limit:	256 megabytes

Ваня, Сережа и Дима любят физические нагрузки. Больше всего им нравится поднимать тяжести. Ребята очень давно начали заниматься гиревым спортом и уже собрали набор гирь для тренировок. Этот набор состоит из n гирь с различными целыми весами от 1 до n.

Совсем недавно ребята нашли новый спортивный зал и решили перенести туда все свои гири. Так как им очень нравится их поднимать, то каждому хочется нести как можно больший вес. Но ребята очень честные, и весь вес решили распределить поровну. Помогите спортсменам разделить набор из n гирь с весами 1, 2, …, n на три равные по весу части.

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

Входной файл содержит единственное целое число n (1 ≤ n ≤ 100,000) – количество гирь.

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

Выведите для каждого спортсмена набор гирь, который ему нужно перенести в новый спортивный зал. Наборы выводятся следующим образом. В первой строке выведите количество гирь в наборе. Далее, во второй строке через пробел выведите веса гирь.

Если разбить все гири на три равных по весу множества нельзя, выведите <<Impossible>>.

Если существует несколько решений, можно вывести любое.

Пример:

weights.in	weights.out
6	2 3 4 2 5 2 2 1 6
3	Impossible

Source: Командное школьное первенство Республики Карелия по программированию, 30 октября 2011.

Discuss       Submit a solution