ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Фильтр
Сложность с по   Класс с по  
Выбрано 2 задачи
Версия для печати
Убрать все задачи

Максимальное время работы на одном тесте: 1 секунда

Максимальный объем используемой памяти: 64 мегабайта

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

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

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

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

Формат входных данных

В первой строке входного файла c.in записаны два целых числа 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).

Формат выходных данных

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

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

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

Примеры

c.in

c.out

2 14

7 9 6 10

7 8 6 10

88

10 4

1 20

1 1 1 1

-1

Вниз   Решение


Докажите тождество Гаусса  φ(d ) = n. Определение функции φ(n) см. в задаче 60758.

Вверх   Решение

Задачи

Страница: 1 2 3 4 >> [Всего задач: 18]      



Задача 35349

Тема:   [ Симметрические системы. Инволютивные преобразования ]
Сложность: 2+
Классы: 8,9

Решить систему уравнений:
    xy = 1,
    yz = 2,
    zx = 8.

Прислать комментарий     Решение

Задача 35641

Темы:   [ Симметрические системы. Инволютивные преобразования ]
[ Квадратные уравнения и системы уравнений ]
Сложность: 3
Классы: 8,9,10

Существуют ли три различных действительных числа, каждое из которых в сумме с произведением двух оставшихся дает одно и то же число?

Прислать комментарий     Решение

Задача 76440

Темы:   [ Симметрические системы. Инволютивные преобразования ]
[ Симметрические многочлены ]
[ Методы решения задач с параметром ]
Сложность: 3
Классы: 8,9,10

Решить систему:
   x + y + z = a,
   x
² + y² + z² = a²,
   x³ + y³ + z³ = a³.

Прислать комментарий     Решение

Задача 97861

Темы:   [ Симметрические системы. Инволютивные преобразования ]
[ Симметрия и инволютивные преобразования ]
[ Алгебраические неравенства (прочее) ]
Сложность: 3
Классы: 8,9,10

Найти все решения системы уравнений:   (x + y)³ = z,  (y + z)³ = x,  (z + x)³ = y.

Прислать комментарий     Решение

Задача 97966

Темы:   [ Симметрические системы. Инволютивные преобразования ]
[ Системы алгебраических нелинейных уравнений ]
[ Монотонность и ограниченность ]
Сложность: 3
Классы: 8,9,10

Автор: Тутеску Л.

Решите систему уравнений:
   (x3 + x4 + x5)5 = 3x1,
   (x4 + x5 + x1)5 = 3x2,
   (x5 + x1 + x2)5 = 3x3,
   (x1 + x2 + x3)5 = 3x4,
   (x2 + x3 + x4)5 = 3x5.

Прислать комментарий     Решение

Страница: 1 2 3 4 >> [Всего задач: 18]      



© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .