Разбор задачи «Энергоячейки склада»

Идея задачи

У нас есть числа от 1 до L. Для каждого числа x известна его энергетическая ценность — это значение младшего установленного бита, то есть lowbit(x).

Например:

• lowbit(1) = 1
• lowbit(6) = 2
• lowbit(12) = 4
• lowbit(16) = 16

Нужно выбрать несколько различных чисел от 1 до L так, чтобы сумма их значений lowbit была ровно S.

Если это возможно, нужно вывести любой подходящий набор чисел.

Что такое lowbit(x)

В двоичной записи число x содержит несколько битов. Нас интересует самый правый бит, равный 1.

Например:

• 10 = 1010₂, младший установленный бит равен 2
• 12 = 1100₂, младший установленный бит равен 4
• 40 = 101000₂, младший установленный бит равен 8

Очень полезная формула:

x & -x

Она как раз и вычисляет значение младшего установленного бита числа x.

Переформулируем задачу

У каждого числа x есть свой «вклад» в сумму — это lowbit(x).

Значит, задача сводится к следующему:

• есть числа от 1 до L;
• каждое число можно взять не более одного раза;
• у каждого числа есть вес lowbit(x);
• нужно набрать ровно сумму S.

На первый взгляд это похоже на задачу о выборе подмножества. Но здесь есть важная структура: значение lowbit(x) всегда является степенью двойки.

Главное наблюдение

Если мы хотим как можно быстрее набрать сумму S, то выгодно брать числа с большим значением lowbit.

Например, если у нас осталось набрать 8, то число с lowbit = 8 обычно выгоднее, чем восемь чисел с lowbit = 1.

Поэтому естественная идея такая:

• идём по числам от L вниз к 1;
• для каждого числа считаем lowbit(x);
• если это значение не больше оставшейся суммы, берём число в ответ.

То есть используем жадный алгоритм.

Почему перебор идёт с конца

Если идти от больших чисел к меньшим, мы раньше встречаем числа с более крупными значениями lowbit.

Например:

• у числа 16 значение lowbit = 16;
• у числа 12 значение lowbit = 4;
• у числа 10 значение lowbit = 2;
• у числа 7 значение lowbit = 1.

Большие вклады удобнее использовать первыми. Тогда остаток суммы уменьшается быстрее.

Жадный алгоритм

Пусть rest — сумма, которую нам ещё нужно набрать.

Тогда делаем так:

1. Изначально rest = S.
2. Перебираем x от L до 1.
3. Вычисляем b = lowbit(x).

4. Если b <= rest, то:

   • добавляем число x в ответ;
   • уменьшаем rest на b.

5. После перебора:

   • если rest = 0, ответ найден;
   • иначе решения нет.

Разберём пример

Пусть:

S = 5, L = 6

Посчитаем значения:

• 1 -> 1
• 2 -> 2
• 3 -> 1
• 4 -> 4
• 5 -> 1
• 6 -> 2

Идём с конца:

• 6, lowbit = 2, берём, осталось 3
• 5, lowbit = 1, берём, осталось 2
• 4, lowbit = 4, уже не помещается
• 3, lowbit = 1, берём, осталось 1
• 2, lowbit = 2, не помещается
• 1, lowbit = 1, берём, осталось 0

Получили один из возможных ответов: 6 5 3 1.

Их вклад:

• 2 + 1 + 1 + 1 = 5

Это корректный ответ.

Обрати внимание: ответ не обязан быть минимальным по количеству чисел. Нам нужно просто найти любой корректный набор.

Почему жадность работает

Докажем идею более аккуратно.

Когда мы рассматриваем очередное число x, его вклад равен степени двойки. Если этот вклад не превосходит оставшейся суммы, то брать его безопасно.

Почему?

Потому что:

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

Фактически мы всегда стараемся забрать максимально выгодный доступный вклад, не превышающий остаток.

Если после просмотра всех чисел остаток всё ещё положителен, значит среди доступных чисел уже нельзя собрать точную сумму. Следовательно, ответа не существует.

Как вычислять lowbit

На C++

int lowbit = x & -x;

На Python

lowbit = x & -x

Это работает благодаря двоичному представлению отрицательных чисел.

Пошаговый план решения

1. Считать S и L.
2. Создать пустой массив ответа.

3. Для всех x от L до 1:

   • вычислить x & -x;
   • если значение не больше оставшейся суммы, добавить x в ответ.
4. Если в конце остаток не равен нулю, вывести -1.
5. Иначе вывести количество выбранных чисел и сами числа.

Реализация на C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int s, l;
    cin >> s >> l;

    vector<int> ans;

    for (int x = l; x >= 1; --x) {
        int lowbit = x & -x;
        if (lowbit <= s) {
            s -= lowbit;
            ans.push_back(x);
        }
    }

    if (s != 0) {
        cout << -1 << '\n';
    } else {
        cout << ans.size() << '\n';
        for (int x : ans) {
            cout << x << ' ';
        }
        cout << '\n';
    }

    return 0;
}

Реализация на Python

import sys


def main():
    data = sys.stdin.read().split()
    s = int(data[0])
    l = int(data[1])

    ans = []

    for x in range(l, 0, -1):
        lowbit = x & -x
        if lowbit <= s:
            s -= lowbit
            ans.append(x)

    if s != 0:
        print(-1)
    else:
        print(len(ans))
        print(*ans)


if __name__ == "__main__":
    main()

Оценка сложности

Мы один раз проходим по всем числам от L до 1.

Значит:

• время работы — O(L);
• память — O(L) в худшем случае, если в ответ попадёт много чисел.

При ограничениях задачи такое решение проходит без проблем.

Частые ошибки

1. Пытаться искать минимальное количество чисел

В задаче это не требуется. Подойдёт любой корректный набор.

2. Забыть, что числа должны быть различными

Мы перебираем каждое число ровно один раз, поэтому автоматически соблюдаем это условие.

3. Неправильно понимать lowbit

lowbit(x) — это не количество единичных битов и не старший бит. Это именно значение младшего установленного бита.

Например:

• у 12 = 1100₂ ответ 4, а не 2;
• у 10 = 1010₂ ответ 2.

4. Пугаться, что жадность может выбрать «не те» числа

Здесь жадность работает именно из-за особой структуры вкладов: все они равны степеням двойки.

Небольшой итог

В этой задаче важно заметить две вещи:

• вклад каждого числа легко вычисляется как x & -x;
• из-за того, что все вклады — степени двойки, можно использовать жадный выбор.

После этого задача решается очень коротко:

• идём от L к 1;
• берём число, если его lowbit помещается в оставшуюся сумму;
• в конце проверяем, удалось ли набрать ровно S.

Это и есть основная идея решения.