Темы --> Информатика --> Алгоритмы --> Жадный алгоритм
---> 70 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 4 5 6 7 8 9 10 >> Отображать по:
ограничение по времени на тест
0.0 second;
ограничение по памяти на тест
0 megabytes

Магазины в рекламных целях часто устраивают распродажи. Так, например,одна из крупных сетей магазинов канцелярских товаров объявила два рекламных предложения: "купи $N$ одинаковых товаров и получи еще один товар бесплатно"и "купи $K$ товаров по цене $K-1$ товара".

Для проведения олимпиады организаторам требуется распечатать условия для участников, на что уходит очень много бумаги. Каждая пачка стоит $B$ рублей. Какое максимальное количество пачек бумаги можно приобрести на $A$ рублей, правильно используя рекламные предложения?

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

Во входном файле записаны целые числа $N$, $K$, $A$ и $B$ ($1\leq N\leq 100$, $2\leq K\leq 100$, $1\leq A \leq 10^9$, $1\leq B \leq 10^9$), разделенные пробелами.

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

Выведите одно целое число - максимальное количество пачек бумаги, которое смогут купить организаторы олимпиады.

Примечание

В первом примере, дважды используя второе рекламное предложение, можно купить 8 пачек бумаги, заплатив за 6.

Во втором примере рекламными предложениями воспользоваться нельзя.

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

Примеры
Входные данные
4 4 13 2
Выходные данные
8
Входные данные
3 4 8 3
Выходные данные
2
Входные данные
3 4 7 1
Выходные данные
9

Петя часто ездит на олимпиады, и потому у него накопилось много футболок. Все футболки он делит на три типа: белые, чёрные и цветные. Каждое утро он выбирает футболку и носит её весь день. Петя любит ходить только в свежих футболках, и поэтому, если он уже надевал одну, то следующий раз он наденет её только после стирки. Его мама не стирает вместе футболки разных типов (иначе они полиняют). Кроме того, мама соблюдает инструкции по оптимальной загрузке стиральной машинки, и для стирки ей требуется ровно $K$ футболок. При этом, конечно, стирать уже чистые футболки она не будет. Подразумевается, что мама стирает футболки сразу же, как ее об этом попросит Петя, и на следующий день он уже может их надевать.

Один из типов футболок Петя любит больше остальных, отчасти из-за того, что количество футболок этого типа позволяет носить только их. Но однажды Пете сказали, что он одевается не "по моде", на что Петя обиделся и поспорил, что он сможет $N$ дней одеваться модно. По моде, принятой в их школе, нельзя ходить два дня подряд в однотипной футболке и нельзя прийти в футболке того же типа ровно через неделю, после того как ты ее надел (например, два понедельника подряд). Школьная мода распространяется и на те дни, когда в школу ходить не надо.

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

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

Во входном файле содержатся пять целых чисел $N$, $W$, $B$, $C$ и $K$, разделенных пробелами - число дней, которые Петя должен носить футболки "по моде", количество белых, черных и цветных футболок, имеющихся у него соответственно, и количество грязных однотипных футболок, которое согласится стирать мама. Гарантируется, что хотя бы одно из чисел $W$, $B$, $C$ не меньше $K$.

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

В первой строке выходного файла выведите единственное слово YES или NO - ответ на вопрос задачи. Если ответ YES, то во второй строке выведите $N$ символов, где $i$-ый символ означает цвет футболки, которую Петя будет носить в $i$-ый день. Символ "W" означает белый цвет, "B" - черный, "C" - цветной.

Примечания

Во всех тестах $1 \le N \le 1\,000$, $1 \le K \le 1\,000$, $0 \le W \le 1\,000$, $0 \le B \le 1\,000$, $0 \le C \le 1\,000$. Тесты состоят из трёх групп.

  1. Тесты 1--3, из условия, оцениваются в 0 баллов.
  2. В тестах этой группы среди чисел $W$, $B$ и $C$ хотя бы одно равно нулю. Эта группа оценивается в 50 баллов, при этом баллы начисляются только при прохождении всех тестов группы (при этом прохождения всех тестов из условия не требуется).
  3. Offline-группа. Баллы за тесты этой группы начисляются только при прохождении всех тестов 1 группы. Некоторые тесты этой группы объединяются в подгруппы, баллы за каждую подгруппу ставятся только при прохождении всех тестов подгруппы

Примеры
Входные данные
2 5 0 4 1
Выходные данные
YES
WC
Входные данные
4 3 4 5 3
Выходные данные
YES
CWCW
Входные данные
10 3 2 1 3
Выходные данные
NO

Юные физики Евгений и Родион очень любят музыку, кроме того Родион умеет исполнять любое произведение при помощи бутылок с водой. У них есть $N$ бутылок бесконечной вместимости. В $i$-ой бутылке уже содержится $a_i$ мл воды. Также у них есть бочонок с $L$ мл воды, из которого можно переливать любой имеющийся объём воды в любую бутылку. Выливать воду из бутылок нельзя. После того как Евгений заканчивает все переливания, он больше не притрагивается к бутылкам, а Родион начинает играть мелодию.

Мелодия состоит из $M$ нот $b_1, b_2, \dots, b_M$, которые обязательно надо исполнять в заданном порядке. Ноту $b_i$ Родион сможет сыграть, если найдется бутылка с $b_i$ мл воды. Если очередную ноту он исполнить не может, то сильно огорчается и перестает играть. Евгений стремится наполнить бутылки таким образом, чтобы Родион играл как можно дольше. Помогите ребятам узнать, какое максимальное количество начальных нот данной мелодии сможет сыграть Родион при оптимальных действиях Евгения.

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

В первой строке входного файла содержатся три целых числа $N$, $M$, $L$ - количество бутылок, длина мелодии и объем бочонка соответственно. Во второй строке через пробел расположены $N$ чисел $a_i$ ($i = 1, 2, \dots N$) - количество мл в $i$-ой бутылке. В третьей строке - $M$ чисел $b_i$ ($i = 1, 2, \dots M$) - последовательность нот в мелодии (каждая музыкальная нота обозначается своим числом, одинаковые ноты - одинаковыми числами). Все числа целые и неотрицательные.

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

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

Примечания

Тесты состоят из четырёх групп.

  1. Тесты 1--3, из условия, оцениваются в 0 баллов.
  2. В тестах этой группы $1 \le N \le 100$, $1 \le M \le 100$, $0 \le a_i \le 1\,000$, $0 \le b_i \le 1\,000$, $0 \le L \le 10^6$. Эта группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.
  3. В тестах этой группы $1 \le N \le 1\,000$, $1 \le M \le 1\,000$, $0 \le a_i \le 10^6$, $0 \le b_i \le 10^6$, $0 \le L \le 10^9$. Эта группа также оценивается в 30 баллов, они начисляются только при прохождении всех тестов группы.
  4. Offline-группа, $1 \le N \le 10^5$, $1 \le M \le 10^5$, $0 \le a_i \le 10^6$, $0 \le b_i \le 10^6$, $0 \le L \le 10^9$. Баллы за тесты этой группы начисляются только при прохождении всех тестов 1-й и 2-й групп. Некоторые тесты этой группы объединяются в подгруппы, тесты за каждую подгруппу ставятся только при прохождении всех тестов подгруппы.
Примеры
Входные данные
6 8 179
4 9 23 15 43 7
3 10 14 7 3 8 7 3
Выходные данные
0
Входные данные
5 8 5
5 3 8 14 1
10 7 3 7 12 3 3 6
Выходные данные
4
Входные данные
2 2 4
6 13
8 10
Выходные данные
1

На прямой задано некоторое множество отрезков с целочисленными координатами концов [$L_i$, $R_i$]. Выберите среди данного множества подмножество отрезков, целиком покрывающее отрезок [0, $M$], ($M$ — натуральное число), содержащее наименьшее число отрезков.

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

В первой строке указана константа $M$ ($1 \leq M \leq 5000$). В каждой последующей строке записана пара чисел $L_i$ и $R_i$ ($|L_i|, |R_i| \leq 50000$), задающая координаты левого и правого концов отрезков. Список завершается парой нулей. Общее число отрезков не превышает 100 000.

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

В первой строке выходного файла выведите минимальное число отрезков, необходимое для покрытия отрезка [0; $M$]. Далее выведите список покрывающего подмножества, упорядоченный по возрастанию координат левых концов отрезков. Список отрезков выводится в том же формате, что и во входe. Завершающие два нуля выводить не нужно. Если покрытие отрезка [0, $M$] исходным множеством отрезков [$L_i$, $R_i$] невозможно, то следует вывести единственную фразу “No solution”.

Примеры
Входные данные
1
-1 0
-5 -3
2 5
0 0

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

Входные данные
1
-1 0
0 1
0 0
Выходные данные
1
0 1
ограничение по времени на тест
0.0 second;
ограничение по памяти на тест
0 megabytes

Высокое здание, состоящее из $N$ этажей, оснащено только одним лифтом. Парковка находится ниже фундамента здания, что соответствует одному этажу ниже первого. Этажи пронумерованы от $1$ до $N$ снизу вверх. Про каждый этаж известно количество человек, желающих спуститься на лифте на парковку. Пусть для i-го этажа эта величина равна $A_i$. Известно, что лифт не может перевозить более $C$ человек единовременно, а также то, что на преодоление расстояния в один этаж (не важно вверх или вниз) ему требуется $P$ секунд. Какое наибольшее количество человек лифт может перевезти на парковку за $T$ секунд, если изначально он находится на уровне парковки?

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

В первой строке входного файла содержатся целые числа $N$, $C$, $P$, $T$ ($1 \leq N \leq 100$, $1 \leq C \leq 10^9$, $1 \leq P \leq 10^9$, $1 \leq T \leq 10^9$). Вторая строка содержит последовательность $N$  целых чисел $A_1$, $A_2$, ..., $A_N$ ($0 \leq A_i \leq 10^9$). Сумма всех значений последовательности не превосходит $10^9$.

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

Выведите наибольшее количество человек, которое лифт успеет перевезти на парковку.

Примеры
Входные данные
4 5 2 15
0 1 2 3
Выходные данные
3
Входные данные
4 5 2 18
0 1 2 3
Выходные данные
5
Входные данные
3 2 1 9
1 1 1
Выходные данные
3

Страница: << 4 5 6 7 8 9 10 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест