a, b, c > 0  и  abc = 1.  Известно, что   a + b + c > ¹/_a + ¹/_b + ¹/_c.  Докажите, что ровно одно из чисел a, b, c больше 1.

   Решение

На вашем диске в каталоге DATA содержатся 10 файлов, которые имеют названия THEATER.D01, THEATER.D02, : , THEATER.D10, следующего формата.

Создайте 10 выходных файлов THEATER.S01, THEATER.S02, : , THEATER.S10 в вашем каталоге на дискете. Эти файлы должны содержать ответы для соответствующих входных файлов.

   Решение

а) Пусть  , и  — произвольные углы, причем сумма любых двух из них меньше  180^o. На сторонах треугольника ABC внешним образом построены треугольники  A₁BC, AB₁C и ABC₁, имеющие при вершинах A, B и C углы  , и . Докажите, что прямые AA₁, BB₁ и CC₁ пересекаются в одной точке.
б) Докажите аналогичное утверждение для треугольников, построенных на сторонах треугольника ABC внутренним образом.

   Решение

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

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

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

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

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

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

В первой строке входного файла c.in записаны два целых числа N и L (1 £ N £ 100, 0 £ L £ 100). В каждой из последующих N строк находится описание магазина номер i - 4 целых числа P_i, R_i, Q_i, F_i (1 £ Q_i £ P_i £ 1000, 1 £ R_i £ 100, 0 £ F_i £ 100).

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

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

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

   Решение

Тема:    [ Динамическое программирование (прочее) ]

Сложность: 3 Классы: 8,9,10,11 Название задачи: Маскарад.

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

Условие

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

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

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

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

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

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

В первой строке входного файла c.in записаны два целых числа N и L (1 £ N £ 100, 0 £ L £ 100). В каждой из последующих N строк находится описание магазина номер i - 4 целых числа P_i, R_i, Q_i, F_i (1 £ Q_i £ P_i £ 1000, 1 £ R_i £ 100, 0 £ F_i £ 100).

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

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

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

Решение

Тесты и проверяющая программа

Найдем способ определять минимальное количество денег, необходимое для того, чтобы купить S метров ткани, используя магазины с 1-го по K-й (обозначим эту величину A[S][K]). Покажем, как вычислить A[S][K], если мы уже знаем значения A[s][k] для всех s £ S, k < K.

Пусть в оптимальном плане по закупке S метров ткани в магазинах с 1-го по K-й в магазине номер K было куплено t метров ткани (t может принимать значения от 0 до min{S, F[K]}). Тогда A[S][K] = Cost(K, t) + A[S-t][K-1]. Здесь Cost(K, t) - стоимость закупки t метров ткани в магазине K. Значит

A[S][K] = (Cost(K, t) + A[S-t][K-1] (*).

Тогда ровно L метров ткани можно купить за A[L][N] бурлей. Заметим, что иногда бывает выгодно покупать более L метров ткани, т.к. когда начинают работать скидки, суммарная стоимость может получиться меньше, поэтому значение A[L][N] вычислить недостаточно. Ответом на поставленную задачу будет

A[S][N]) (**).

То есть в общем случае возникает задача нахождения минимума в бесконечной последовательности значений A[S][N] для S ³ L. Однако в нашей задаче на S в (**) можно наложить ограничение сверху. Дело в том, что стоимость ткани всегда положительна, поэтому если мы согласно оптимальному плану закупок уже купили в первых K магазинах не менее L метров ткани, то во всех остальных магазинах (с (K + 1)-го по N-й) ткань закупаться уже не будет. Значит S £ S_max = L + (F[i]) - 1.

Будем хранить все значения A[S][K] в двухмерном массиве A[0..S_max,1..N]. Для заполнения этого массива по формулам (*)необходимы начальные значения. Ими в нашем решении будет столбец A[S][1] (стоимость покупки S метров ткани в первом магазине), значения элементов которого предлагается задать явным образом. В случае, если в первом магазине нет S метров ткани, элементу A[S][1] нужно присвоить значение, равное "бесконечности" (в программе бесконечность представляет собой какое-нибудь достаточно большое число, заведомо превосходящее ответ, для данной задачи подойдет число 10⁶). Вычислим остальные элементы массива по формулам (*) в порядке неуменьшения K, а при равных K - в порядке увеличения S.

Для вычисления требуемого в задаче еще и плана закупок ткани, вместе с заполнением массива A будем заполнять дополнительный массив D[S][K], элементами которого будут значения t из формул (*), на которых достигаются соответствующие минимальные значения. С помощью массива D несложно восстановить весть план закупок.

Общее время работы данного алгоритма - O(F_maxS_maxN). На полный балл задачу решили 12 человек, еще несколько участников, фактически решив задачу, не поняли из условия, что ткани можно покупать больше, чем требуется, если это окажется выгодным.

Источники и прецеденты использования