| Codeforces Round 564 (Div. 2) |
|---|
| Закончено |
Nauuo — девочка, которая любит играть в шахматы.
Однажды она сама придумала игру, для которой нужны $$$n$$$ шахматных фигур на доске $$$m\times m$$$. Строки и столбцы пронумерованы целыми числами от $$$1$$$ до $$$m$$$. Обозначим клетку на пересечении $$$r$$$-й строки и $$$c$$$-го столбца как $$$(r,c)$$$.
Цель игры — расставить на доске $$$n$$$ шахматных фигур, пронумерованных целыми числами от $$$1$$$ до $$$n$$$. Пусть $$$i$$$-я фигура находится в клетке $$$(r_i,\,c_i)$$$. Должно соблюдаться следующее правило: для каждой пары фигур $$$i$$$ и $$$j$$$ должно выполняться $$$|r_i-r_j|+|c_i-c_j|\ge|i-j|$$$. Здесь $$$|x|$$$ обозначает абсолютное значение числа $$$x$$$.
Вскоре Nauuo поняла, что иногда она не сможет найти решение игры, ведь доска может быть слишком маленькой.
Она хочет найти самую маленькую шахматную доску, на которой можно правильно расставить $$$n$$$ фигур.
Nauuo также интересует, как следует расставлять фигуры на доске. Можете ли вы помочь ей?
В первой строке записано единственное целое число $$$n$$$ ($$$1\le n\le 1000$$$) — количество шахматных фигур для игры.
Выведите одно целое число — минимальное значение $$$m$$$, где $$$m$$$ это длина стороны подходящей шахматной доски.
В $$$i$$$-й из следующих $$$n$$$ строк выведите два целых числа $$$r_i$$$ и $$$c_i$$$ ($$$1\le r_i,c_i\le m$$$) — координаты $$$i$$$-й шахматной фигуры.
Если существует несколько подходящих ответов, вы можете вывести любой.
2
2 1 1 1 2
4
3 1 1 1 3 3 1 3 3
В первом примере вы не можете расставить фигуры на доске $$$1\times1$$$ без нарушения описанных правил. Но вы можете расставить их на доске $$$2\times2$$$ следующим образом:
Во втором примере вы не можете расставить фигуры на доске $$$2\times2$$$ без нарушения описанных правил. Например, если вы расставите их следующим образом:
то $$$|r_1-r_3|+|c_1-c_3|=|1-2|+|1-1|=1$$$, $$$|1-3|=2$$$, $$$1<2$$$, а также $$$|r_1-r_4|+|c_1-c_4|=|1-2|+|1-2|=2$$$, $$$|1-4|=3$$$, $$$2<3$$$, это нарушает правило.
Однако вы можете расставить их на доске $$$3\times3$$$ следующим образом:
