Темы --> Информатика --> Алгоритмы --> Динамическое программирование --> Динамическое программирование: два параметра --> Задача о рюкзаке
---> 6 задач <---
Источники --> Личные олимпиады
    Олимпиады сайта(17 задач)
    Школьная личная олимпиада ФМШ №2007 г. Москвы(7 задач)
    Золотая середина (Новосибирск)(10 задач)
    Нижегородская олимпиада школьников(42 задач)
    Московская олимпиада школьников(168 задач)
    Индивидуальная олимпиада по информатике и программированию (ИОИП)(22 задач)
    Открытая олимпиада школьников(173 задач)
    Украинские олимпиады(61 задач)
    Республиканская олимпиада школьников (Беларусь)(6 задач)
    Жаутыковские олимпиады(8 задач)
    Всероссийская олимпиада школьников(304 задач)
    Международные олимпиады(32 задач)
    Central European Olympiad in Informatics (4 задач)
    Интернет-олимпиады(2 задач)
    COCI(36 задач)
    Турнир Архимеда(36 задач)
    Baltic Olympiad in Informatics(10 задач)
Страница: 1 2 >> Отображать по:
#992
Маскарад
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Есть N магазинов, для каждого из них задана цена метра, количество метров необходимых для "оптовой" покупки, цена метра при покупке оптом, а также имеющееся в магазине количество ткани. Необходимо купить L метров за минимальную цену (можно покупать в различных магазинах кусками).

По случаю введения больших новогодних каникул устраивается великий праздничный бал-маскарад. До праздника остались считанные дни, поэтому срочно нужны костюмы для участников. Для пошивки костюмов требуется L метров ткани. Ткань продается в N магазинах, в которых предоставляются скидки оптовым покупателям. В магазинах можно купить только целое число метров ткани. Реклама магазина номер i гласит "Мы с радостью продадим Вам метр ткани за Pi бурлей, однако если Вы купите не менее Ri метров, то получите прекрасную скидку — каждый купленный метр обойдется Вам всего в Qi бурлей". Чтобы воплотить в жизнь лозунг "экономика страны должна быть экономной", правительство решило потратить на закупку ткани для костюмов минимальное количество бурлей из государственной казны. При этом ткани можно купить больше, чем нужно, если так окажется дешевле. Ответственный за покупку ткани позвонил в каждый магазин и узнал, что:

1) реклама каждого магазина содержит правдивую информацию о ценах и скидках;

2) магазин номер i готов продать ему не более Fi метров ткани.

Ответственный за покупку очень устал от проделанной работы и поэтому поставленную перед ним задачу «закупить ткань за минимальные деньги» переложил на своих помощников. Напишите программу, которая определит, сколько ткани нужно купить в каждом из магазинов так, чтобы суммарные затраты были минимальны.

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

В первой строке входного файла записаны два целых числа N и L (1≤N≤100, 0≤L≤100). В каждой из последующих N строк находится описание магазина номер i — 4 целых числа Pi, Ri, Qi, Fi (1≤Qi≤Pi≤1000, 1≤Ri≤100, 0≤Fi≤100).

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

Первая строка выходного файла должна содержать единственное число — минимальное необходимое количество бурлей.

Во второй строке выведите N чисел, разделенных пробелами, где i-ое число определяет количество метров ткани, которое нужно купить в i-ом магазине. Если в i-ом магазине ткань покупаться не будет, то на i-ом месте должно стоять число 0. Если вариантов покупки несколько, выведите любой из них.

Если ткани в магазинах недостаточно для пошивки костюмов, выходной файл должен содержать единственное число -1.

Примеры
Входные данные
2 14
7 9 6 10
7 8 6 10
Выходные данные
88
10 4
Входные данные
1 20
1 1 1 1
Выходные данные
-1
#1225
Склад
  

На роботизированном складе имеется N отсеков, в которые робот может размещать грузы. Отсек с номером i имеет вместимость ci. Груз с номером i имеет размер si, поступает на склад в момент времени ai и забирается со склада в момент времени di.

Когда груз с номером i поступает на склад, робот сначала пытается найти отсек, в котором достаточно свободного места для размещения этого груза. Свободное место в пустом отсеке совпадает с его вместимостью. Если в отсеке с вместимостью c находится несколько грузов с суммарным размером d, то свободное место в этом отсеке равно c – d.

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

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

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

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

Первая строка содержит два целых числа: N — количество отсеков, и M — количество грузов (1 ≤ N ≤ 10, 1 ≤ M ≤100). Вторая строка содержит N целых чисел ci, определяющих вместимости отсеков (1 ≤ ci ≤ 109). Последующие M строк описывают грузы: каждый груз описывается тремя целыми числами: своим размером si, временем поступления на склад ai и временем, когда его забирают со склада di (1 ≤ si ≤ 109, 1 ≤ ai < di ≤ 1000, все времена во входном файле различны, грузы упорядочены по возрастанию времени поступления на склад). Все числа в строках разделены пробелом.

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

Выведите последовательность действий робота в том порядке, в котором они выполняются. Следуйте формату, приведенному в примере.

Возможны следующие сообщения:

put cargo X to cell Y — положить груз с номером X в отсек с номером Y;

move cargo X from cell Y to cell Z — переложить груз с номером X из отсека с номером Y в отсек с номером Z;

take cargo X from cell Y — достать груз с номером X из отсека с номером Y.

cargo X cannot be stored — если груз с номером X разместить невозможно.

Примеры
Входные данные
1 2
3
2 1 2
4 3 4
Выходные данные
put cargo 1 to cell 1
take cargo 1 from cell 1
cargo 2 cannot be stored
#1277
Несчастливые номера
  

Обычно автобусный билет с номером, состоящим из 6 цифр, считается счастливым, если сумма первых трех цифр его номера была равна сумме трех последних. Школьник Вася очень любил получать счастливые билеты, однако это случалось не так часто. Поэтому для себя он изменил определение счастливого билета. Счастливым он считал тот номер, сумма некоторых цифр которого равнялась сумме оставшихся цифр. В его представлении билет с номером 561743 счастливый, так как 5 + 1 + 4 + 3 = 6 + 7.

Вася вырос, но по привычке в номерах различных документов пытается найти признаки счастливого номера ☺. Для этого он расширил свое определение счастливого номера на n-значные номера лицевых счетов и других документов, состоящих из цифр от 0 до k (1 ≤ k ≤ 9). Номер документа он называет счастливым, если сумма некоторых цифр этого номера равняется сумме оставшихся. Остальные номера для него несчастливые. К сожалению, несмотря на расширенное понимание “счастья”, несчастливых номеров остается еще много...

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

Входной файл unlucky.in содержит описание нескольких видов номеров. Каждый вид номеров определяется значениями n и k. Для данного входного файла вы должны создать соответствующий ему выходной файл и отправить его на проверку жюри.

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

Входной файл содержит несколько пар значений n и k, каждая пара записана в отдельной строке.

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

Для каждой пары значений n и k входного файла выведите в соответствующей строке выходного файла искомое количество несчастливых билетов или 0, если такое число вам получить не удалось. Количество строк во входном и выходном файлах должно совпадать.

Примечание

За правильное решение задачи для каждого вида номеров вы получите 5 баллов. Так, представленный в примере выходной файл соответствует 15 баллам.

При сдаче на проверку выходного файла во время тура вы будете получать одно из двух сообщений:

  • Presentation Error — если файл не соответствует формату вывода. В этом случае файл не принимается на проверку.
  • Accepted — если файл формату вывода соответствует. В этом случае файл принимается на проверку. Проверка правильности ответов в выходном файле осуществляется только после окончания тура.
Содержание файла unlucky.in:
4 1
7 1
3 2
6 2
22 2
7 9
8 7
9 6
8 8
12 9
20 9
20 3
17 5
16 7
15 9
19 5
26 9
100 3
99 4
50 5
#1374
Снова ка-штаны
  
Требуется найти набор, остаток от деления которого на размер рюкзака минимален.

В этой задаче, как и в задаче 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. Первые штаны надеты на лапу 1;
вторые штаны не используем;
третьи штаны надеты на лапы 2, 3 и 4.
Таким образом, на всех лапах по 1 штанине.

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

Примеры
Входные данные
4 3
1 2 3
Выходные данные
1
1
1
1
Входные данные
4 2
3 2
Выходные данные
2
1
1
1
#1982
Петино путешествие
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Завтра Петя уезжает в кругосветное путешествие, в процессе которого собирается посетить N разных городов. Вспомнив о старинной традиции бросать монетки в фонтаны для того, чтобы когда-нибудь вернуться в это место, он решил запастись монетами заранее. Поскольку это всего лишь традиция, подумал Петя, то с него хватит оставить в каждом городе по одной копеечной монете – зачем тратиться зря?

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

С этими мыслями Петя решил прогуляться до продуктового магазина – купить в дорогу немного еды. Из всего ассортимента ему подходило M видов товара (количество товаров каждого вида неограниченно), стоимость i-го равна ai рублей bi копеек. И тут его осенило. Если покупать товары в правильной последовательности, то он довольно быстро сможет скопить так нужные ему N копеечных монет!

Процесс покупки в магазине устроен следующим образом. Петя может заказать любой набор из подходящих ему товаров (каждого товара Петя может взять сколько угодно единиц). После чего он платит за них и получает сдачу минимальным числом купюр и монет (любых монет и купюр в кассе также с избытком). Это означает, например, что если ему должны сдать 11 рублей и 98 копеек сдачи, то он получит купюру в 10 рублей, монеты в 1 рубль, 50 копеек, 4 монеты в 10 копеек, одну монету в 5 копеек и три копеечных монеты. При этом он волен вносить любую сумму (лишь бы она была не меньше требуемой для оплаты) и платить любым набором купюр и монет, имеющихся у него в распоряжении.

После этого Петя может ещё раз подойти к кассе, сделать заказ, расплатиться имеющимися наличными (можно использовать и полученные до этого со сдачей) и так далее сколько угодно раз.

Петя хочет потратить в этом магазине как можно меньше денег. Помогите ему найти оптимальный способ обретения не менее N копеечных монет с минимальными затратами.

Комментарий для нероссийских участников олимпиады.

В России используются монеты и купюры достоинством 1, 5, 10, 50 копеек и 1, 2, 5, 10, 50, 100, 500, 1000 и 5000 рублей. 1 рубль равен 100 копейкам.

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

Сначала вводятся целые числа N и M (0 ≤ N ≤ 108, 0 ≤ M ≤ 100) — количество городов, которые собирается посетить Петя, и количество подходящих ему видов товара. Далее идут M пар чисел ai, bi, обозначающих стоимость товара соответствующего типа (0 ≤ ai ≤ 100, 0 ≤ bi ≤ 99). Стоимость товара всегда больше нуля.

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

Если требуемое количество копеечных монет получить невозможно, выведите –1. Иначе выведите минимальную сумму, которую должен потратить Петя на покупку товаров, чтобы получить N однокопеечных монет.  Сумма должна быть выведена как два целых числа, задающих рубли и копейки (второе число обязано быть от 0 до 99).

Система оценки

Примеры
Входные данные
3 1
0 2
Выходные данные
0 2
Входные данные
4 2
1 2
0 4
Выходные данные
0 16
Входные данные
1 3
0 1
0 4
0 6
Выходные данные
0 1
Страница: 1 2 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест