Получение нуля

Заметим, что 32768=215
, а потому мы можем сделать любое значение равным 0
 умножив его на два 15
 раз, так как (𝑣⋅215)mod215=0
. А потому ответ для каждого 𝑎𝑖
 не превосходит 15
.

Далее заметим, что всегда есть оптимальный ответ, имеющий вид: сначала прибавим единицу 𝑐𝑛𝑡𝐴𝑑𝑑
 раз, а потом умножим на два 𝑐𝑛𝑡𝑀𝑢𝑙
 раз — и 𝑐𝑛𝑡𝐴𝑑𝑑+𝑐𝑛𝑡𝑀𝑢𝑙
 будет минимальным ответом. Другими словами, давайте просто переберем все 𝑐𝑛𝑡𝐴𝑑𝑑≤15
 и 𝑐𝑛𝑡𝑀𝑢𝑙≤15
 и проверим, что (𝑣+𝑐𝑛𝑡𝐴𝑑𝑑)⋅2𝑐𝑛𝑡𝑀𝑢𝑙mod32768=0
. Ответ — это минимальное 𝑐𝑛𝑡𝐴𝑑𝑑+𝑐𝑛𝑡𝑀𝑢𝑙
 среди них.

Чтобы доказать, что выгодно сначала прибавлять, а только потом умножать, заметим, что невыгодно прибавлять более одного раза после умножения (𝑣→2𝑣→2𝑣+2
 можно заменить на 𝑣→𝑣+1→2(𝑣+1)
). А потому будет не более одного +1
 между двумя ⋅2
. Однако, невыгодно делать +1
 даже один раз, потому что нам в конечном итоге нужно сделать так, чтобы 𝑣
 делился на 215
, а +1
 ломает делимость.

Существуют и другие подходы к решению данной задачи: например, так как 𝑎𝑖<32768
 вы можете написать bfs, чтобы найти кратчайшие пути от 0
 ко всем 𝑎𝑖
.