| Автор: | В. Степанец, А. Кленин | Ограничение времени: | 1 сек | |
| Входной файл: | input.txt | Ограничение памяти: | 256 Мб | |
| Выходной файл: | output.txt | |||
| Максимальный балл: | 100 |
Автостоянка, находящаяся поблизости от улицы имени Г. Кантора, ограничена с севера и запада домами, а с востока и юга открыта в большое поле.
Чтобы упорядочить размещение автомобилей, владелец стоянки решил пронумеровать места на ней и выделить каждому клиенту номер и соответствующее место. Нумерацию решено производить так: месту в углу стоянки присвоен номер ноль, далее нумерация идёт по диагоналям в направлении с северо-востока на юго-запад.
| 0 | 1 | 3 | 6 | 10 | … |
| 2 | 4 | 7 | 11 | … | |
| 5 | 8 | 12 | … | ||
| 9 | 13 | … | |||
| 14 | … | ||||
| … |
Координаты каждого места на стоянке определяются числами (x; y), где x — количество мест, расположенных западнее данного, y — количество мест, расположенных севернее. Например, место номер 7 имеет координаты (2; 1).
Требуется написать программу, которая для каждого из N данных номеров мест определит их координаты.
N = 1
C ≤ 106
1 ≤ N ≤ 105
0 ≤ Ci ≤ 109
| № | Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|---|---|
| 1 | |
|
| 2 | |
|
Попробуем сначала решить обратную задачу: найти по координатам места его номер C(x, y). Заметим, что в последовательности номеров один элемент расположен на первой диагонали, два элемента на второй, … , x + y элементов на предпоследней и y элементов но последней, содержащей указанное место. Таким образом, номер места можно посчитать как C(x, y) = 1 + 2 + … + (x + y) + y
Теперь мы можем в цикле по диагоналям наращивать номер места до тех пор, пока он не превзойдёт указанного. Сложность такого решения составляет O(N × √max Ci)
Более эффективное решение можно получить, если использовать двоичный поиск или решить уравнение 2 × C = (x + y) × (x + y + 1).
Зная x + y = p, мы можем легко найти x и y:
y = C − p * (p + 1) / 2
x = p − y