printРабочее место участника

printЗадачи

1657. Нанокристалл

Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Сверхсекретный завод, расположенный высоко в горах, занимается изготовлением новейших систем контроля торсионных полей — нанокристаллов. Нанокристалл состоит из нескольких атомов, некоторые из которых попарно связаны сверхпрочными торсионными связями.
Нанокристалл стабилен, если между любыми двумя его атомами можно построить соединяющую их цепочку связей, возможно с использованием других атомов. Например, нанокристалл `X` из четырех атомов `A`, `B`, `C` и `D`, в котором между собой связаны пары `A-B`, `A-C`, `B-C` и `B-D`, стабилен. Если же, например, в нанокристалле из данных четырех атомов связаны только пары `A-B` и `C-D`, то кристалл нестабилен, поскольку, например, `A` и `C` не соединены никакой цепочкой связей.
Для любой пары атомов стабильного нанокристалла определена их взаимная удаленность — минимальная длина цепочки из связей, которая их соединяет. Например, рассмотрим описанный выше нанокристалл `X`. Взаимная удаленность атомов `A` и `B` равна единице (они соединены напрямую), а взаимная удаленность `C` и `D` равна двум (они соединены цепочками `C-B-D` и `C-A-B-D`, длина кратчайшей цепочки равна двум).
Важнейшей характерикой стабильного нанокристалла является его емкость. Емкость нанокристалла равна сумме взаимных удаленностей всех пар его атомов. Например, емкость нанокристалла `X` равна 8.
Недавно на завод поступил заказ — разработать стабильный нанокристалл заданной емкости `c`. При этом как число атомов в нанокристалле, так и число связей может быть произвольным. Помогите ученым разработать такой кристалл!
Ввод
Входной файл содержит целое число `c` (`1\ ≤\ c\ ≤\ 10\ 000`).
Ввод
На первой строке выходного файла выведите два целых числа `n` и `m` — количество атомов и связей в разработанном нанокристалле, соответственно. Будем считать, что атомы нанокристалла пронумерованы от 1 до `n`. Следующие `m` строк должны содержать по два целых числа — пары атомов, которые следует соединить торсионными связями. Если решений несколько, выведите любое.
Если искомого нанокристалла не существует, выведите на первой выходного файла строке два нуля.

Пример ввода 1

8

Пример вывода 1

4 4
1 2
1 3
2 3
2 4

Пример ввода 2

2

Пример вывода 2

0 0
Источник: V Всероссийская командная олимпиада школьников по программированию, 2004
loading