| Автор: | Михаил Дворкин (Городская олимпиада школьников Санкт-Петербурга по информатике 2006) | Ограничение времени: | 2 сек | |
| Входной файл: | hyper.in | Ограничение памяти: | 64 Мб | |
| Выходной файл: | hyper.out |
Недавно Миша узнал о существовании многомерных пространств. В n-мерном пространстве точка задается набором из n вещественных координат. Миша сразу же догадался как измерить расстояние между двумя точками — расстояние между точками (x1, x2, …, xn) и (y1, y2, …, yn) равно sqrt((x1 − y1)2 + (x2 − y2)2 + … + (xn − yn)2).
Для начала он стал исследовать отрезки. Отрезок, соединяющий точки (x1, x2, …, xn) и (y1, y2, …, yn) — это множество точек с координатами (λ x1 + (1 − λ)y1, λ x2 + (1 − λ)y2, …, λ xn + (1 − λ)yn), где λ ∈ [0,1].
Миша называет точку с целочисленными координатами видимой, если на отрезке, соединяющем эту точку с началом координат (точкой, все координаты которой равны нулю), не лежит других целочисленных точек. Например, в двумерном пространстве точка (2, 1) является видимой, а точка (2, 2) — нет, во втором случае соответствующий отрезок содержит точку (1, 1).
Теперь Мишу заинтересовал вопрос — а в пространстве какой минимальной размерности существует видимая точка, расстояние от которой до начала координат равно sqrt(l). Также его интересует, а сколько видимых точек в пространстве этой размерности находятся на расстоянии sqrt(l) от начала координат. Помогите ему решить эту задачу.
Входной файл содержит целое число l.
На первой строке выходного файла выведите n — минимальную размерность пространства, в которой существует искомая точка. На второй строке выведите n целых чисел — координаты любой такой точки. На третьей строке выведите количество таких точек в пространстве размерности n.
| № | Входной файл (hyper.in) |
Выходной файл (hyper.out) |
|---|---|---|
| 1 | |
|