Задача E. Дополнения
Задачу добавил: alef
Успешно сдано решений: 11
Кондрат так и не понял, как Рагнар показал ему карту порталов. Он видел ее, мог разглядывать в деталях, пока Рагнар говорил о том, как устроен вход и выход из зазеркального города. Но, когда Рагнар закончил свой рассказ, карта исчезла.
— Как же я отсюда выберусь, если у меня нет карты?
— Так пока ты не собираешься возвращаться. Чтобы посмотреть на город и на людей, карта не нужна. Потом придешь сюда, — Рагнар исчез также неожиданно, как и появился.
Кондрат действительно хотел еще побродить по городу. После встречи с Рагнаром он почему-то совершенно успокоился. Он выбирал более людные и широкие улицы и спустя некоторое время оказался на местном базаре. Местные ценники его несколько удивили: в них встречались красные и синие цифры. Кондрат отметил про себя, что все числа на ценниках начинаются с красных цифр, но больше никакой закономерности уловить не смог. Но на одном из прилавков он увидел довольно странный ценник. Надписи на чужом языке он не понимал, но в этом случае смысл был ясен: купи два товара и получи скидку.
Кондрат выяснил, что в зазеркальном городе в ходу уравновешенная система счисления с основанием K (K — нечетное целое положительное число). В такой системе счисления используются цифры от –(K – 1) / 2 до (K – 1) / 2. Положительные цифры обозначаются красным цветом, а отрицательные — синим. Заметим, что всякое число имеет в такой системе счисления однозначное представление, которое в развернутом виде может быть записано следующим образом:
где aj — это цифра, стоящая на позиции #j, если считать справа налево (младшая цифра имеет номер 0).
Кондрат хочет научиться переводить целые числа из десятичной системы счисления в систему счисления, используемую в зазеркальном городе. Ваша задача — написать программу, которая будет это делать
Формат входного файла input.txt
Первая строка — два целых числа K и N (2 < K < 20, 1 ≤ N ≤ 105) через пробел. K — основание системы счисления (гарантируется, что K — нечетное) и N — количество чисел в десятичной системе счисления, которые Кондрат хотел бы перевести в систему счисления используемую в зазеркальном городе.
Каждая из следующих N строк содержит по одному целому числу в десятичной системе счисления. Все числа не более 109 и не менее –109
Формат выходного файла output.txt
Выходной файл содержит N строк. В каждой из строк без пробелов записаны цифры соответствующего числа в уравновешенной K-ичной системе счисления в том порядке, в котором они образуют число. Красные цифры записываются обычным образом, а перед синими цифрами ставится знак минус.
Пример входного файла — 1
3 8
1
2
0
-1
-2
22
100
121
Пример выходного файла — 1
1
1-1
0
-1
-11
1-111
11-101
11111
Пример входного файла — 2
5 6
10
121
-724
4096
55
-2
Пример выходного файла — 2
20
10-11
-1-1101
12-2-1-11
210
-2