Специалисты из лаборатории нанотехнологий Уральского федерального
университета занимаются
созданием вычислителя, работающего на уровне отдельных атомов. Недавно они
узнали, что если правильно расположить на плоскости n атомов
тантала, то можно построить на их основе квантовый компьютер, обладающий
недостижимыми ранее характеристиками.
К сожалению, теория описывает только некоторые физические характеристики системы
атомов, но не их конфигурацию в целом. Физики должны вычислить,
как именно нужно расположить атомы, чтобы добиться желаемого
эффекта. Сканирующий туннельный микроскоп, который физики используют для своих опытов,
может поместить атом тантала только в точки, координаты которых выражены целым
числом нанометров, по модулю не превышающим 106.
Чтобы определить координаты атомов, учёные обратились за помощью к
вам. Они избавились от лишней физической информации и предоставили вам
только квадраты расстояний между всеми парами атомов.
Исходные данные
Первая строка содержит единственное целое число n — общее количество атомов
(2 ≤ n ≤ 100). Далее в n строках записана матрица aij
размера n × n. Число aij равно требуемому квадрату расстояния
между атомами с номерами i и j (0 ≤ aij ≤ 109;
aij = aji; aii = 0). Все aij целые.
Результат
Если существует ответ, удовлетворяющий данной матрице квадратов
расстояний, выведите n строк. i-я строка должна содержать два целых
числа, по модулю не превосходящих 106 — координаты i-го атома.
Если существует несколько возможных ответов, выведите любой из них.
Если разместить атомы требуемым образом невозможно, выведите «Impossible».
Примеры
исходные данные | результат |
---|
3
0 1 4
1 0 1
4 1 0
| 0 0
1 0
2 0
|
3
0 1 5
1 0 1
5 1 0
| Impossible
|
3
0 1 0
1 0 1
0 1 0
| 5 -5
5 -4
5 -5
|
Автор задачи: Сергей Пупырев (подготовка — Иван Бурмистров)
Источник задачи: Открытый командный чемпионат УрФУ по программированию — 2011