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

Робот движется по полю, которое состоит из N клеток, выстроенных в ряд. На каждой из клеток находится кубик определенного цвета.

До начала движения робот находится на первой клетке поля и не держит ни одного кубика. Находясь на клетке, робот может выполнить не более одного раза каждую из следующих операций: (1) положить кубик того же цвета, который лежит на текущей клетке; (2) поднять с клетки тот кубик, который находился там сначала. После этого робот перемещается на следующую клетку или останавливается, если текущая клетка последняя в поле.

Одновременно робот может держать не более K кубиков. На момент остановки робот не должен держать ни одного кубика.

Напишите программу, которая по информации о цвете кубиков и ограничении на количество кубиков, которое может держать робот, определяет максимальное общее количество кубиков, которое робот может перенести с места на место, двигаясь по полю.

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

Первая строка входного файла содержит символьную строку длинны N (1N≤1000). Строка состоит из маленьких букв латинского алфавита. Каждая буква соответствует клетке поля и определяет цвет кубика, который находится в этой клетке. Вторая строка содержит ограничение на количество кубиков, которое одновременно может держать робот K (1K≤25).

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

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

Подзадачи и система оценки

Баллы за эту задачу будут начислены если ваше решение проходит все тесты

Примеры
Входные данные
rgbbggrmcm
2
Выходные данные
4
ограничение по времени на тест
0.0 second;
ограничение по памяти на тест
0 megabytes

Системный администратор вспомнил, что давно не делал архива пользовательских файлов. Однако, объем диска, куда он может поместить архив, может быть меньше чем суммарный объем архивируемых файлов.

Известно, какой объем занимают файлы каждого пользователя.

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

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

сначала вводится число $S$ – размер свободного места на диске (натуральное, не превышает 10000), затем следует число $N$ – количество пользователей (натуральное, не превышает 100), после этого идет $N$ чисел - объем данных каждого пользователя (натуральное, не превышает 1000).

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

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

Примеры
Входные данные
100 2
200
50
Выходные данные
1
Входные данные
100 3
50
30
50
Выходные данные
2
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Вводится новый авиарейс между городами $A$ и $B$. Самолет будет лететь строго по прямой, соединяющей эти города. На протяжении всего пути необходимо, чтобы за самолетом могли наблюдать с земли при помощи радаров. Однако, радиус действия радаров ограничен, и равен $R$. Хуже того, радарные станции имеются только в определенных точках (например, других населенных пунктах). Руководство авиакомпании желает выяснить: можно ли следить за самолетом на протяжении всего пути из $A$ в $B$. Если это возможно, то каким минимальным количеством уже имеющихся радаров можно для этого обойтись. Самолет, находящийся на границе действия радара является видимым, то есть если расстояние от радара до самолета точно равно $R$, то считается что радар еще действует.

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

сначала вводятся координаты точек $A$ и $B$ (целые числа, по модулю не превышают 1000), затем вводится число $N$ (натуральное, не превышает 20) – количество уже построенных радаров, затем следует число $R$ – радиус действия радара (натуральное, не превышает 1000). Затем вводится $N$ пар чисел – координаты уже построенных радаров (целые, по модулю не превышают 1000). Наличие радаров в городах $A$ и $B$ возможно, но необязательно.

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

выведите минимальное количество радаров, которое надо задействовать для сопровождения самолета на всем пути. Если сопровождение имеющимися средствами невозможно – выведите число -1.

Примеры
Входные данные
0 0 1 1
1 1
5 5
Выходные данные
-1
Входные данные
0 0 10 0
3 5
0 0
5 0
10 0
Выходные данные
1
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
263 megabytes

Василиса Премудрая с Иваном-царевичем сбежали от морского царя. Царь немедленно выслал погоню. Уже совсем близко стук копыт, а верный конь Василисы устал нести двоих седоков... Единственное, что спасёт беглецов — чудо!

Сохраняя хладнокровие, Василиса решает в уме сложную задачу. Она хочет сотворить между собой и преследователями волшебный лес. Этот лес будет представлять собой $n$ рядов деревьев, идущих строго с запада на восток. В каждом ряду будет также $n$ деревьев, образующих вместе $n$ рядов, идущих строго с севера на юг. Более того, суммарная высота деревьев в $i$-м ряду с запада на восток должна составлять ровно $a_i$ метров, а суммарная высота деревьев в $j$-м ряду с севера на юг — ровно $b_j$ метров. Наконец, высота каждого дерева должна выражаться целым числом метров. Сотвори такой лес — и преследователи будут без толку плутать по нему, пока волшебство не ослабнет и лес не исчезнет.

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

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

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

В первой строке входного файла задано целое число $n$ ($2 \le n \le 1000$). Во второй строке заданы $n$ целых чисел $a_1, a_2, \ldots, a_n$ через пробел — сумма высот деревьев в рядах, идущих с запада на восток ($0 \le a_i \le 10^6$). В третьей строке заданы $n$ целых чисел $b_1, b_2, \ldots, b_n$ через пробел — сумма высот деревьев в рядах, идущих с севера на юг ($0 \le b_j \le 10^6$).

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

Если сотворить волшебный лес с данными параметрами невозможно, выведите «NO» в первой строке выходного файла. Иначе в первой строке выведите «YES», а в следующих $n$ строках по $n$ целых неотрицательных чисел через пробел в каждой — высоты деревьев. Сумма чисел в $i$-й из последних $n$ строк должна равняться $a_i$, а сумма чисел в $j$-м столбце должна равняться $b_j$. Максимальное число в ответе должно быть минимально возможным. Если правильных ответов несколько, можно выводить любой из них.

Примеры
Входные данные
2
1 3
2 2
Выходные данные
YES
1 0 
1 2 
Входные данные
2
1 3
2 4
Выходные данные
NO
ограничение по времени на тест
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

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