Решение задачи Степени двойки с Codeforces
С пояснением   Просмотров: 160
Вам даны два положительных целых числа n и k. Представьте n как сумму ровно k степеней двойки.
Пояснение к задаче
Сначала давайте поймем, как мы можем получить минимальное количество степеней двойки, необходимых для того, чтобы представить n в виде их суммы. Мы можем воспользоваться двоичным представлением n: каждый бит в нем, равный 1, добавляет в ответ одно слагаемое.
Сначала, если количество слагаемых больше, чем k, то ответ NO. Окей, что нужно делать, если нам не хватает слагаемых? Каждое слагаемое x>1 может быть разбито на два слагаемых, равных x2. Давайте сохраним все слагаемые больше 1 где-нибудь (стек, массив, очередь, мультимножество, где вы хотите), будем выбирать любое слагаемое и разбивать его на два до тех пор, пока у нас не станет ровно k слагаемых. Если n≥k, то этот процесс точно когда-то закончится, потому что всегда найдется какое-то слагаемое для выбора до тех пор, пока они все не станут равны 1.