Рюкзак для пика Ленина


Отправить решение Решать в редакторе

Сложность: 85%
Очки: 100 (частичный балл)
Ограничение по времени: 3.0s
Ограничение по памяти: 256M

Автор:
Типы задач
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

Пик Ленина (7134 м) на границе Кыргызстана и Таджикистана — один из самых популярных семитысячников мира. Базовый лагерь экспедиций стоит на поляне Ачик-Таш на Памире, куда альпинисты добираются из Оша по Памирскому тракту.

Фотография
Пик Ленина, вид со стороны села Сары-Могол. Фото: Nihongarden, CC BY-SA 3.0, Wikimedia Commons

Альпинист Эмиль собирает рюкзак для штурма вершины. На выбор у него n предметов снаряжения; предмет i весит w[i] граммов и имеет полезность v[i] (опытные гиды оценили, насколько он повышает шансы на успех). Рюкзак выдержит не более W граммов, а чтобы штурм разрешили, суммарная полезность взятых предметов должна быть не меньше V.

Эмиль хочет знать, сколько у него вариантов. Найдите количество подмножеств предметов (в том числе пустое), у которых суммарный вес не больше W, а суммарная полезность не меньше V.

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

В первой строке — три целых числа n, W, V (1 ≤ n ≤ 40, 0 ≤ W, V ≤ 4 · 10¹⁶).

В каждой из следующих n строк — два целых числа w[i] и v[i] (1 ≤ w[i] ≤ 10¹⁵, 0 ≤ v[i] ≤ 10¹⁵).

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

Выведите одно целое число — количество подходящих подмножеств.

Пример 1

Вход:

4 10 7
5 4
4 3
3 3
6 5

Выход:

4

Пояснение

Подходят наборы {1, 2} (вес 9, полезность 7), {1, 3} (8 и 7), {2, 4} (10 и 8) и {3, 4} (9 и 8).

Система оценивания

Подзадача Баллы Дополнительные ограничения
1 20 n ≤ 16
2 25 V = 0 и все v[i] = 0
3 55 без дополнительных ограничений

Баллы за подзадачу начисляются, только если пройдены все её тесты.

Примечание

Ответ может достигать 2⁴⁰ — используйте 64-битные целые числа.


Комментарии

Еще нет ни одного комментария.