Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 






Задача 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


Сдать задачу

Задать вопрос жюри по этой задаче