Плюсануть
Поделиться
Класснуть
Запинить


Условие задачи Прогресс
ID 33650. Гомер Симпсон
Темы: Задача о рюкзаке   

Обеденный перерыв Гомера Симпсона составляет T миллисекунд. Один гамбургер Гомер съедает за N миллисекунд, один чизбургер - за M. Какое количество гамбургеров и чизбургеров нужно съесть, чтобы потраченное время было как можно больше, не превышая T. При равенстве потраченного времени необходимо максимизировать суммарное количество съеденных гамбургеров и чизбургеров.

Ограничения: 1 <=M, N, T, <= 1000000 , все числа целые.

Входные данные
В первой строке находятся три числа - M, N и T, разделённые пробелами.

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

Ввод Вывод
1 2 1000 1000
2 1 1000 1000
3 6 1000 333 1

ID 33086. 0-1 рюкзак: наибольший вес
Темы: Задача о рюкзаке   

Дано N золотых слитков массой m1, …, mN. Ими наполняют рюкзак, который выдерживает вес не более M. Какую наибольшую массу золота можно унести в таком рюкзаке?
 
Входные данные: 
- в первой строке вводится натуральное число N, не превышающее 100 и натуральное число M, не превышающее 10000;
- во второй строке вводятся N натуральных чисел mi, не превышающих 100.
 
Выходные данные: выведите одно целое число - наибольшую возможную массу золота, которую можно унести в данном рюкзаке.
 

 

Примеры
Входные данные Выходные данные
1
2 3195
38 41
79

ID 33087. 0-1 рюкзак: минимум предметов
Темы: Задача о рюкзаке   

Дано N предметов массой m1, …, mN. Ими наполняют рюкзак, который выдерживает вес не более M. Как набрать вес в точности M, используя как можно меньше предметов?
 
Входные данные:
- в первой строке вводится натуральное число N, не превышающее 100 и натуральное число M, не превышающее 10000;
- во второе строке вводятся N натуральных чисел mi, не превышающих 100.
 
Выходные данные: выведите наименьшее необходимое число предметов или 0, если набрать данный вес невозможно.
 

 

Примеры
Входные данные Выходные данные
1
1 5968
18
0

ID 33081. Задача о рюкзаке с восстановлением ответа
Темы: Задача о рюкзаке   

Дано N предметов массой m1, …, mN и стоимостью c1, …, cN соответственно. 
Ими наполняют рюкзак, который выдерживает вес не более M. Определите набор предметов, который можно унести в рюкзаке, имеющий наибольшую стоимость.
 
Входные данные: 
- в первой строке вводится натуральное число N, не превышающее 100 и натуральное число M, не превышающее 10000;
- во второй строке вводятся N натуральных чисел mi, не превышающих 100;
- в третьей строке вводятся N натуральных чисел сi, не превышающих 100.
 
Выходные данные: выведите номера предметов (числа от 1 до N), которые войдут в рюкзак наибольшей стоимости (по одному номеру в строке).
 

 

Примеры
Входные данные Выходные данные
1
4 6
2 4 1 2
7 2 5 1
1
3
4

ID 33105. Копилка
Темы: Задача о рюкзаке   

Задан вес E пустой копилки и вес F копилки с монетами. В копилке могут находиться монеты N видов, для каждого вида известна ценность Pi и вес Wi одной монеты. Найти минимальную и максимальную суммы денег, которые могут находиться в копилке.

Входные данные
В первой строке находятся числа E и (1 <= E <= F <= 10000). Во второй - число (1<= N <= 500). В следующих N строках - по два числа, Pi и Wi (1 <= Pi <= 50000, 1 <= Wi <= 10000). Все числа целые.

Выходные данные
Выводятся два числа через пробел - минимальная и максимальная суммы. Если копилка не может иметь точно заданный вес при условии, что она наполнена монетами заданных видов, - вывести "This is impossible.".

 

ID 33088. Гирьки
Темы: Задача о рюкзаке   

Дан набор гирь массой1, …, mN. Можно ли их разложить на две чаши весов, чтобы они оказались в равновесии?
 
Входные данные:
- в первой строке вводится натуральное число N, не превышающее 100;
- во второе строке вводятся N натуральных чисел mi, не превышающих 100.
 
Выходные данные: выведите YES или NO.
 

 

Примеры
Входные данные Выходные данные
1 1
17
NO
2 2
19 19
YES

ID 33104. Сдача - 1
Темы: Задача о рюкзаке   

Покупатель хочет приобрести товар стоимостью S рублей. У него есть N банкнот номиналом P1, P2, ..., PN рублей. У продавца есть M банкнот номиналом Q1, Q2, ..., QM. рублей. Определите, смогут ли они рассчитаться.
 
Входные данные: 
- в первой строке задается сумма S;
- во второй строке - число N;
- в третьей строке  - N чисел P1, P2, ..., PN;
- в четвертой строке - число M;
- в пятой строке - M чисел Q1, Q2, ..., QM.
Количество банкнот у продавца и покупателя и их номиналы не превосходят 100.
 
Выходные данные: если продавец сможет рассчитаться с покупателем, выведите номиналы банкнот, которые покупатель отдает продавцу и которые он получает в качестве сдачи. Выводите число со знаком “+”, если банкноту соответствующего номинала покупатель отдает продавцу и со знаком “-”, если покупатель получает эту банкноту на сдачу. Номиналы банкнот разделяйте пробелом.
Если они не могут рассчитаться, выведите строку Impossible.
 

 

Примеры
Входные данные Выходные данные
1
10
3
3 9 14
2
6 2
-2 +9 +3
2
100
3
74 35 8
2
19 6
Impossible

ID 38366. Снова ка-штаны
Темы: Задача о рюкзаке   

В этой задаче, как и в задаче B, Петя снова собирает своего M-лапого Зверя на прогулку (однако количество лап у Зверя в этой задаче может быть до 1000). Снова ему мама оставила N штанов, имеющих соответственно K1, K2, …, KN штанин. Однако тетерь Петя хочет надеть на Зверя штаны так, чтобы выполнялись следующие условия:

  • на каждой лапе была надета хотя бы одна штанина (гарантируется, что это всегда возможно),
  • количество штанин, надетых на самую «утепленную» лапу, должно как можно меньше отличаться от количества штанин, надетых на самую легко одетую лапу (когда количество штанов, одетых на разные лапы, сильно отличается, Зверь испытывает дискомфорт),
  • в отличие от задачи B Петя не обязан надеть на Зверя все имеющиеся штаны — какие-то из них можно оставить дома.
Как и раньше, любые штаны можно надевать на любой набор лап. В частности, нельзя несколько штанин одних и тех же штанов надеть на одну и ту же лапу Зверя.

Помогите Пете – напишите программу, которая для каждой лапы укажет, сколько штанин должно быть на нее надето.

Входные данные
Вводится сначала число M, а затем число N (1 ≤ M ≤ 1000, 1 ≤ N ≤ 100). Далее вводятся N чисел Ki, обозначающих число штанин у оставленных мамой штанов (1 ≤ Ki ≤ M). Сумма всех Ki не меньше, чем M.

Выходные данные
Выведите M строк, в i-ой строке должно быть выведено количество штанин, надетых на i-ю лапу. Если искомых ответов несколько, то выведите любой из них.
 
Примеры
Входные данные Выходные данные Пояснение
1 4 3
1 2 3
1
1
1
1
Первые штаны надеты на лапу 1;
вторые штаны не используем;
третьи штаны надеты на лапы 2, 3 и 4.
Таким образом, на всех лапах по 1 штанине.
2 4 2
3 2
2
1
1
1
Первые штаны надеты на лапы 1, 2 и 3;
вторые штаны надеты на лапы 1 и 4.
Таким образом, количество штанов на самой «утепленной» лапе (это лапа номер 1) – 2, а на остальных лапах по одной штанине, т.е. количество штанин на разных лапах отличается на один. Нетрудно заметить, что в этом примере нельзя одеть зверя так, чтобы на всех лапах было поровну штанин, поэтому этот ответ является оптимальным.

ID 47675. Кристаллы максимуса
Темы: Динамическое программирование    Динамическое программирование: последовательности    Задача о рюкзаке   

Максимус очень любит коллекционировать кристаллы. Среди всех кристаллов у него есть один самый любимый с магической силой равной n. Также у него есть коллекция совершенных кристаллов. Совершенный кристалл - это кристалл, магическая сила которого равна квадрату натурального числа.
У Максимуса выдался свободный вечер, и он задумался: сколько нужно ему совершенных кристаллов, чтобы сумма их магических сил равнялась бы магической силе его любимого кристалла?
Квадратом натурального числа является число, которое получается умножением натурального числа на себя. Например, 1, 4 и 9 - это квадраты натуральных чисел, а 2, 3 и 5 - нет.
Ваша задача - помочь Максимусу найти минимальное количество совершенных кристаллов, сумма магических сил которых равна n.

Входные данные
Программа получает на вход натуральное число n (n < 104).

Выходные данные
Выведите ответ на задачу.
 
 

Примеры
Входные данные Выходные данные Примечание
1
12
3
12 = 4 + 4 + 4
2 13 2 13 = 4 + 9

ID 47743. Сумма фишек
Темы: Динамическое программирование    Задача о рюкзаке    Задача о рюкзаке   

Алиса и Громозека играют в фишки по следюущим правилам. Громозека загадывает определенное число, а Алиса должна использовать свои фишки, чтобы составить сумму, равную этому числу. У Алисы есть фишки, на каждой из которых записано определенное число. Алиса имеет неограниченный запас фишек с каждым числом. Если Алиса сможет составить нужную сумму, используя свои фишки, она победит.
Ваша задача - определить, сможет ли Алиса победить Громозеку и если да, то сколько различных комбинаций у нее есть для достижения победы. Если Алиса не сможет победить Громозеку, то вы должны вывести число 0.

Входные данные
Программа получает в первой строке два числа: n - количество различных чисел, которые записаны на фишках, num - число, которое загадал Громозека. Во второй строке записаны n различных чисел ci - числа, каждое из которых может быть записано на фишке. На каждой фишке записано только одно число из набора чисел ci. При этом, количество фишек с числом ci не ограниченно. Все фишки с одинаковым числом, считаются одинаковыми. Другими словами, комбинация фишек 2+1 и 1+2 считается одной комбинацией. 


Ограничения

  • 1 <= n <= 300
  • 1 <= ci <= 5000
  • Все значения ci уникальны.
  • 0 <= num <= 5000

Выходные данные
Выведите одно число - количество комбинаций, которым Алиса может выиграть Громозеку. Если Алиса не может выиграть, то выведите на экран 0.

Примечание
В первом примере есть 4 способа набрать сумму, равную 5:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

 

ID 47744. Айвен собирает кристаллы
Темы: Динамическое программирование    Задача о рюкзаке   

Юный волшебник Айвен отправляется в волшебный лес, чтобы набрать  волшебных кристаллов. Каждый кристалл, растущий в данном лесу, обладает своей массой. Айвен имеет рюкзак, который может выдержать определенный вес M. Айвен хочет использовать свой рюкзак по максимуму и набрать  кристаллов такое количество, чтобы суммарно их вес равнялся в точности весу, который может выдержать его рюкзак. 
Вам стали известны массы кристаллов, которые растут в волшебном лесу. Выведите "YES",  если Айвен сможет набрать кристаллов суммарным весом ровно M, иначе выведите "NO".


Входные данные
В первой строке вводится натуральное число N, не превышающее 100 и натуральное число M, не превышающее 104. Во второй строке вводятся N натуральных чисел mi, не превышающих 100.

Выходные данные
Выведите YES или NO.
 

ID 47745. 0-1 Рюкзак
Темы: Задача о рюкзаке   

Дано N предметов массой m1, …, mN и стоимостью c1, …, cN соответственно.

Ими наполняют рюкзак, который выдерживает вес не более M. Какую наибольшую стоимость могут иметь предметы в рюкзаке?

Входные данные
В первой строке вводится натуральное число N, не превышающее 100 и натуральное число M, не превышающее 10000. Во второй строке вводятся N натуральных чисел mi, не превышающих 100. Во третьей строке вводятся N натуральных чисел сi, не превышающих 100.

Выходные данные
Выведите наибольшую стоимость рюкзака.

ID 47747. Весы
Темы: Задача о рюкзаке   

Если в продаже нет стандартного набора гирь, измерение массы становится большой проблемой. Ваш набор содержит n гирь массой 1 грамм, 4 грамма, 16 грамм, ..., 4n - 1 грамм. Кроме того, у вас есть две чаши весов. Чтобы взвесить объект, надо положить его на левую чашу весов и поставить некоторые гири на левую и правую чашу для достижения равновесия. Требуется найти, сколько целых масс в диапазоне [1; m ] возможно измерить, используя весы и данный набор гирь.

Входные данные
В единственной строке содержаться 2 целых числа m и n (1 ≤ n , m ≤ 109 ) .

Выходные данные
Выведите одно число - количество масс, которые можно измерить с помощью этих гирь.

ID 47748. Сдача - 2
Темы: Задача о рюкзаке   

Покупатель хочет приобрести товар стоимостью S рублей. У него есть N банкнот номиналом P1, P2, ..., PN рублей. У продавца есть M банкнот номиналом Q1, Q2, ..., QM. рублей. Определите, смогут ли они рассчитаться.

Входные данные
Программа получает на вход сумму S. Далее идет число N затем P1, P2, ..., PN. Далее идет число M, затем Q1, Q2, ..., QM.Количество банкнот у продавца и покупателя и их номиналы не превосходят 100.

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

Если они не могут рассчитаться, выведите число -1.

ID 47749. Гирьки: три кучки одного размера
Темы: Задача о рюкзаке   

Дан набор гирек массой m1, …, mN. Разделите его на три кучки равной масссы, содержащие равное число гирек.

Входные данные
Первая строка входных данных содержит натуральное число N, не превышающее 18. Далее идет N натуральных чисел mi, не превышающих 100.

Выходные данные
Программа должна вывести номера гирек для каждого из наборов в три строки или строчку No solution, если решения не существует.

ID 47780. Гирьки: четыре кучки
Темы: Задача о рюкзаке   

Дан набор гирек массой m1, …, mN. Можно ли их разделить на четыре кучки равной массы?

Входные данные
Первая строка входных данных содержит натуральное число N, не превышающее 14. Далее идет N натуральных чисел mi, не превышающих 100.

Выходные данные
Программа должна вывести номера гирек для каждого из наборов в четыре строки или строчку No solution, если решения не существует.

ID 47938. Строковые артефакты
Темы: Задача о рюкзаке   

Команда исследователей-археологов, отправилась в затерянный храм на поиски древних артефактов. На каждом артефакте записана строка, состоящая из символов "0" и "1". Археологи узнали, что выйти из храма с артефактами можно только в том случае, если суммарное количество нулей в строках, записанных на всех, взятых с собой артефактах, будет не больше m, а суммарное количество единиц не больше n. Исследователи хотят унести как можно больше артефактов. Ваша задача определить, какое максимальное количество артефактов исследователи-археологи смогут унести. 

Входные данные
Первая строка содержит целое число k - количество артефактов в храме. Далее идут k строк si; в i-й строке записана строка с i-го артефакта, состоящая из "0" и "1".
На k+2 строке записаны 2 числа: m и n
 

Ограничения

  • 1 <= k <= 600
  • 1 <= длина si <= 100
  • si состоит только из цифр '0' and '1'.
  • 1 <= m, n <= 100



Выходные данные
Выведите ответ на задачу.

Пояснения к тестовым примерам
В первом тестовом примере наибольшим подмножеством, содержащим не более пяти 0 и не более трех 1, является {"10", "0001", "1", "0"}, поэтому ответ - 4.
Другие допустимые, но меньшие подмножества  {"0001", "1"} и {"10", "1", "0"}.
Подмножества {"111001"} является недопустимым, так как содержит четыре 1, что больше n.