Задача №114649. Экскурс в историю биологии
Сегодня на уроке ботаники учительница рассказала вам про открытие нового растительного вида, которым почти сто лет назад известный биолог Джон Хопкрофт произвёл фурор в биологии. Надземная часть этого дерева ничем не примечательна, но корневая система подчиняется строгим математическим законам:
- она распространяется вниз от ствола дерева, никогда не загибаясь вверх;
- в некоторых точках \(p\) она разветвляется : в эту точку сверху входит один корень, а вниз исходит \(k_p\) корней, \(k_p>1\). Хопкрофт открыл свойство скупости , согласно которому во всех таких точках \(k_p\) равно двум или трём, и предположил, что это ограничение вызвано эволюционным механизмом для сокращения конкуренции за питательные вещества между соседними ответвлениями корня и преимущественного распространения вширь и вглубь;
- самой верхней точкой разветвления является низ ствола дерева Хопкрофта, и это единственная точка, в которой корневая система соединяется с надземной частью. Она тоже удовлетворяет свойству скупости;
- в некоторых точках она заканчивается и дальше вниз не распространяется, такие точки называется корневыми окончаниями ;
- она обладает свойством равномерности : на кратчайшем пути от любого корневого окончания до ствола располагается равное количество точек разветвления; это количество называется глубиной корня. Низ ствола в этом количестве учитывается.
Учительница рассказала, что, когда несколько лет назад в городе был ураган, одно такое дерево было вырвано с корнем, и она имела возможность лично убедиться в выполнении свойств скупости и равномерности, а также пересчитала корневые окончания — их было ровно \(n\). Другие ученики не поверили, что ураган смог вырвать настолько сложный корень из земли, не повредив его, но вы посчитали, что если глубина корня невелика, то такое вполне возможно. Чтобы разобраться в ситуации, вам захотелось для начала найти структуру корня дерева Хопкрофта с \(n\) корневыми окончаниями и наименьшей возможной глубиной.
В единственной строке находится одно целое число \(n\) (\(2 \le n \le 200\,000\)) — требуемое количество корневых окончаний.
Можно показать, что для любого \(n\) требуемый корень действительно существует. Предположим, что суммарно в нём \(k\) точек разветвления. Обозначим различными целыми числами от 1 до \(n+k\) все точки разветвления и корневые окончания так, чтобы низу ствола соответствовало число 1. В первой строке выведите число \(n+k\), в каждой из следующих \(n+k-1\) строк выведите через пробел пары целых чисел, означающие все соединения между этими \(n+k\) точками: пара \({a\;b}\) означает, что на пути корня между точками \(a\) и \(b\) нет точек разветвления (кроме, возможно, самих \(a\) и \(b\)). И сами пары, и числа в парах можно выводить в любом порядке. Не выводите никакое число в паре с самим собой, не выводите дважды одну и ту же пару (как в одинаковом порядке, так и в разном). Ваш набор пар должен описывать структуру любого корня дерева Хопкрофта с \(n\) окончаниями, низом ствола, пронумерованным единицей, и наименьшей глубиной.
Тесты к этой задаче состоят из трёх групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов предыдущих групп.
| Дополнительные ограничения | |||
| Группа | Баллы | \(n\) | Комментарий |
| 0 | 0 | – | Тесты из условия. |
| 1 | 13 | \(n \leq 12\) | |
| 2 | 35 | \(n \leq 200\) | |
| 3 | 52 | – |
8
12 6 1 12 4 12 1 2 10 10 5 8 12 1 10 6 3 7 10 9 6 6 11