Темы --> Информатика --> Алгоритмы --> Жадный алгоритм
---> 17 задач <---
Источники --> Личные олимпиады --> Всероссийская олимпиада школьников
    Муниципальный этап(80 задач)
    Окружная олимпиада(18 задач)
    Региональный этап(109 задач)
    Заключительный этап(97 задач)
Страница: 1 2 3 4 >> Отображать по:
#16
Приключение
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Теплым весенним днем группа из N школьников-программистов гуляла в окрестностях города Кисловодска. К несчастью, они набрели на большую и довольно глубокую яму. Как это случилось — непонятно, но вся компания оказалась в этой яме.

Глубина ямы равна H. Каждый школьник знает свой рост по плечи hi и длину своих рук li. Таким образом, если он, стоя на дне ямы, поднимет руки, то его ладони окажутся на высоте hi + li от уровня дна ямы. Школьники могут, вставая друг другу на плечи, образовывать вертикальную колонну. При этом любой школьник может встать на плечи любого другого школьника. Если под школьником i стоят школьники j1, j2, …, jk, то он может дотянуться до уровня hj1 + hj2 + … + hjk + hi + li.

Если школьник может дотянуться до края ямы (то есть hj1 + hj2 + … + hjk + hi + li ≥ H), то он может выбраться из нее. Выбравшиеся из ямы школьники не могут помочь оставшимся.

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

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

В первой строке входных данных задается натуральное число N (1 ≤ N ≤ 2000) — количество школьников, попавших в яму.

Далее в N строках содержится по два целых числа: рост i-го школьника по плечи hi (1 ≤ hi ≤ 105) и длина его рук li (1 ≤ li ≤ 105).

В последней строке указано целое число — глубина ямы H (1 ≤ H ≤ 105).

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

В первой строке выведите K — максимальное количество школьников, которые смогут выбраться из ямы. Если K > 0, то во второй строке в произвольном порядке выведите их номера, разделяя их пробелами. Школьники нумеруются с единицы в том порядке, в котором они заданы во входных данных. Если существует несколько решений, выведите любое.

Примечание

Решение, дающее правильный ответ только при N ≤ 100; H, hi, li ≤ 1000, будет оцениваться из 70 баллов.

Примеры
Входные данные
1
239 239
566
Выходные данные
0
Входные данные
3
1 2
1 2
4 1
7
Выходные данные
2
2 1
#17
Автобусы
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

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

Автобусная сеть страны охватывает N городов, занумерованных целыми числами от 1 до N.

Идеальное расписание содержит M ежедневных рейсов, i-й рейс начинается в городе Fi в момент времени Xi и заканчивается в некотором другом городе Gi в момент времени Yi. Продолжительность каждого рейса ненулевая и строго меньше 24 часов. Рейс i выполняется одним из автобусов, находящихся в момент времени Xi в городе Fi.

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

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

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

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

В первой строке задаются целые числа N и М (1 ≤ N, M ≤ 100 000) — количество городов и рейсов автобусов соответственно.

В каждой из следующих M строк содержится описание рейса автобуса: номер города отправления Fi, время отправления Xi, номер города назначения Gi (Fi ≠ Gi), время прибытия Yi, отделенные друг от друга одним пробелом. Время прибытия и отправления задается в формате HH:MM, где HH — часы от 00 до 23, MM — минуты от 00 до 59.

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

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

Примеры
Входные данные
4 6
1 10:00 2 12:00
1 10:00 3 09:00
3 12:00 4 23:00
2 11:00 4 13:00
4 12:00 1 11:00
4 12:00 1 10:30
Выходные данные
8
#20
Уроки физкультуры
  

Сегодня в 5-А классе праздник — урок физкультуры. Традиционно ребята в это время после небольшой разминки играют в футбол. Коля очень любит футбол, но сегодня, проходя мимо учительской, он случайно услышал, что несколько самых сильных школьников из 5-А во время урока физкультуры должны помочь разгружать новые парты. Что же делать? Ведь Коля предпочитает поиграть в футбол!

В голове Коли моментально созрел план. Коля знает, что в 5-А классе N школьников. Он хочет воспользоваться тем, что учитель физкультуры Иван Петрович на уроках вместо обычной расстановки школьников в шеренгу по росту практикует расстановку «по силе». Для этого Иван Петрович сначала расставляет N школьников по росту, а затем (N – 1) раз проходит вдоль шеренги слева направо, каждый раз начиная с самого левого (первого) школьника и заканчивая предпоследним школьником справа. Проходя мимо школьника, который стоит на i-м месте (1 ≤ i ≤ N – 1), Иван Петрович просит его помериться силой с соседом справа, который стоит на (i + 1)-м месте. Если школьник, стоящий левее, оказывается сильнее своего соседа справа, то они меняются местами. Если же силы школьников оказываются равны, либо слева стоит более слабый школьник, то школьники остаются на своих местах. После этого Иван Петрович просит помериться силой школьников, стоящих на местах (i + 1) и (i + 2), и т. д., заканчивая каждый проход школьниками, которые стоят на местах (N – 1) и N. При любом сравнении «по силе» все школьники, включая Колю, показывают свою реальную силу, так как не хотят прослыть слабаками.

Для увеличения шансов поиграть в футбол, Коля хотел бы оказаться как можно левее в получившейся шеренге. Силу каждого из своих одноклассников он знает. По предыдущим занятиям Коля заметил, что если присесть «завязывать шнурки» при каком-либо из проходов учителя, то Иван Петрович во время такого прохода не будет просить Колю мериться силой ни с соседом слева, ни с соседом справа, и, тем более, не будет просить мериться силой соседей Коли, так как они не стоят рядом. Однако, чтобы сохранить силы для игры в футбол, Коля не может присесть более k раз.

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

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

В первой строке входных данных задаются три целых числа: N — число школьников в классе, p — место Коли в шеренге по росту, и k — количество приседаний, которое Коля может сделать, не потеряв при этом способность играть в футбол (2 ≤ N ≤ 100 000, 1 ≤ p ≤ N, 1 ≤ k ≤ N – 1).

Во второй строке задаются целые числа a1, a2, ..., aN (1 ≤ ai ≤ 109). Число ai показывает силу школьника, который стоит на i-м месте по росту. Школьник, который стоит на i-м месте в расстановке по росту, сильнее школьника, который стоит j-м месте в расстановке по росту, если ai > aj.

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

В первой строке выведите самую левую позицию в шеренге, в которой может оказаться Коля после построения школьников «по силе». Во второй строке выведите любую из возможных стратегий Коли, приводящую к этому результату. Стратегия выводится в виде строки из (N – 1) символов, j-й символ этой строки должен быть равен символу «+», если на j-м проходе Коле необходимо присесть, и символу «-» — в противном случае.

Примечание

Решения, корректно работающие при N ≤ 3000, будут оцениваться, исходя из 70 баллов.

Примеры
Входные данные
10 5 6
10 1 8 3 6 5 4 7 2 9
Выходные данные
5
---++++++
#22
Ударим мостом по бездорожью
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

Профиль Уральских гор задается ломаной (x1, y1), (x2, y2), …, (xN, yN), для координат вершин которой верны неравенства x1 < x2 < … < xN. Начальные и конечные точки профиля расположены на уровне моря (y1 = yN = 0).

На горном профиле заданы две различные точки A и B, между которыми требуется проложить дорогу. Эта дорога будет проходить по склонам гор и проектируемому горизонтальному мосту, длина которого не должна превышать L. Оба конца моста находятся на горном профиле. Дорога заходит на мост с одного конца и выходит с другого. Мост не может содержать точек, расположенных строго под ломаной (строительство тоннелей не предполагается).

Возможные примеры расположения моста

1

Невозможное расположение моста

2

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

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

Первая строка входных данных содержит два целых числа N и L — количество вершин ломаной (2 ≤ N ≤ 100 000) и максимальную длину моста (1 ≤ L ≤ 106) соответственно. Вторая строка  содержит координаты точки A, третья строка — координаты точки B. Точки A и B различны.

Последующие N строк содержат координаты вершин ломаной (x1, y1), (x2, y2), …, (xN, yN). Координаты вершин ломаной, а также точек A и B, задаются парой целых чисел, не превосходящих по абсолютному значению 106. Гарантируется, что x1 < x2 < … < xN и y1 = yN = 0, а также, что точки A и B принадлежат ломаной.

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

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

В примере в первой строке указана длина дороги от точки A до точки B с учётом построенного моста. Её не нужно выводить.

Примечание

Решения, корректно работающие при N ≤ 2000, будут оцениваться, исходя из 80 баллов.

Примеры
Входные данные
5 3
1 1
3 1
-1 0
0 2
2 0
4 2
5 0
Выходные данные
2.000000000
1.00000 1.00000
3.00000 1.00000
#23
То березка, то рябина…
  

В целях улучшения ландшафтной архитектуры и экологической обстановки управление городского хозяйства разработало проект программы озеленения центрального проспекта. Согласно проекту, с одной стороны проспекта планируется высадить в ряд деревья K различных видов, для чего были закуплены саженцы деревьев, причем i-го вида было закуплено ai саженцев.

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

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

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

В первой строке вводятся два целых числа: K — количество различных видов деревьев (1 ≤ K ≤ 100 000), и P — требуемое количество подряд идущих деревьев разных видов (2 ≤ P ≤ K). Последующие K строк  входных данных содержат целые числа ai, задающие количество закупленных саженцев деревьев i-го вида  (1 ≤ ai ≤ 109), по одному числу в каждой строке.

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

Выведите единственное число — максимальное количество деревьев, посадка которых в ряд в некотором порядке достигает эстетического совершенства.

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