Codeforces Rd.126

[navyblue]

Подписался на рассылку от этих ребят, там регулярно устраиваются соревнования - за 2 часа с лишком надо решить несколько задач по программированию. Иногда принимаю вызов, только для того, чтобы познать всю глубину своего невежества.

Вчера, наконец, сошлись звёзды за долгое время и я принял участие в одном из раундов и снова был посрамлён. За два часа я прочитал три задачи из шести, понял, хоть примерно, как решать одну из них, но и ту не решил за отведённое время.

Заметил, что победители все пишут на C++ - для таких задач он реально быстрее Питона, но мне это неважно :)

Приведу эту задачку, чтобы не быть голословным:



Предположим, у вас есть целое число V. За одну операцию вы можете:

• либо присвоить v=(v+1) mod 32768
• либо присвоить v=(2⋅v) mod 32768

Вам заданы nn целых чисел a1,a2,…,an. Какое минимальное количество операций необходимо, чтобы сделать каждое ai равным 0?

Входные данные

В первой строке задано одно целое число n (1≤n≤32768) - количество чисел.

Во второй строке заданы n целых чисел a1,a2,…,an (0≤ai<32768).

Выходные данные

Выведите n чисел: i-е число должно равняться минимальному количеству операций, чтобы сделать ai равным 0.

Примечание

Рассмотрим несколько ai:

• a1=19. Вы можете, сначала, увеличить его на единицу и получить 20, а потом умножить его на два 13 раз. Вы получите 0 за 1+13=14 шагов.
• a2=32764. Вы можете увеличить число на единицу 44 раза: 32764→32765→32766→32767→0.
• a3=10240. Вы можете умножить его на два 44 раза: 10240→20480→81920→163840→0.
• a4=49. Вы можете умножить его на два 15 раз.

Отдельно изложу свой путь к решению и само решение:



По сути, надо посчитать, за какое минимальное число шагов можно из числа 0≤a<32768 сделать число, кратное 32768, используя операции +1 и х2.

Число 32768 - это 2^15, так что у нас один из способов найти решение - прибавить по единичке к a, чтобы получить одну из степеней двойки, и дальше домножать на 2 до 32768.

Вот только над этим алгоритмом я провозился больше часа, а это не всегда самое оптимальное решение.

Есть ещё варианты прибавлением 1 довести число до степени двойки, помноженное на 10, 100 или 1000 и уже это число домножать до 327680, 3276800 или 32768000, соответственно.

Над ними я провозился ещё почти час, время заканчивалось, но остался ещё вариант - тупо домножать число 15 раз на 2, чтобы получить умножение на 32768 - иногда этот вариант получается короче.

И вот из всех этих шагов надо выбрать минимальное число - это и будет ответ в каждом случае.

Здесь я изложил своё решение и правильное решение:

gist.github.com/BuslaySt/9aa81d8e8bef235d27ce649f13d9c432