Темы --> Информатика --> Алгоритмы
    Задачи на моделирование(78 задач)
    Арифметические алгоритмы(240 задач)
    Алгоритмы поиска(155 задач)
    Алгоритмы сортировки(194 задач)
    Динамическое программирование(355 задач)
    Алгоритмы на графах(319 задач)
    Перебор(154 задач)
    Игры и выигрышные стратегии(33 задач)
    Вычислительная геометрия(216 задач)
    Эвристические методы(30 задач)
    Алгоритмы на строках(45 задач)
    Пересечение множеств(10 задач)
    Жадный алгоритм(71 задач)
    Теория расписаний(5 задач)
    Обработка текста(31 задач)
    Дата и время(14 задач)
---> 1657 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 318 319 320 321 322 323 324 >> Отображать по:
#113807
Хоккей
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Совсем скоро начнётся чемпионат Хорватии по хорватскому хоккею. В хорватском хоккее каждая игра длится по M минут и в каждый момент времени на поле находятся ровно 6 игроков. Так как игра может длиться очень долго, не все игроки могут находится на поле на протяжении всей игры. Поэтому каждая команда привезла на чемпионат большое число запасных игроков.

Сегодня мы будем помогать Анте, тренеру команды Загреба. Анте привёз N игроков на чемпионат, причём у каждого игрока есть своя сила p i и своя выносливость d i . Для каждого игрока известно, что его «суммарное игровое время» не превышает величину его выносливости. «Суммарное игровое время» игрока — это суммарное количество времени, которое игрок провёл на поле. То есть, если игрок сначала провёл на поле X минут, а потом Y минут, то его «суммарное игровое время» равно X + Y минут.

В каждой момент времени у команды есть её сила — сумма сил всех шестерых игроков, находящихся на поле. Общая сила команды Z — это сумма сил команды во все минуты игры. То есть, если игра длилась 3 минуты и в первую минуту сила команды была 15 , во вторую — 12 , а в третью — 14 , то общая сила команды — 15 + 12 + 14 = 41 . Анте знает, что чтобы победить, надо максимизировать общую силу команды. Но Анте — не очень талантливый тренер, поэтому он просит вас помочь ему составить оптимальное расписание выхода команд, чтобы Z было максимально. Гарантируестя, что можно составить расписание так, чтобы в каждый момент на поле было по 6 игроков.

Обратите внимание, что в хорватском хоккее все игроки могут заменять друг друга, и вратаря нет, ведь так игра становиться гораздо веселее.

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

В первой строке вводится 2 числа M и N ( 1 ≤ M ≤ 5·10 5 , 6 ≤ N ≤ 5·10 5 ) — длительность матча в минутах и число игроков у команды соответственно.

В каждой из следующих N строк даны по 2 числа p i и d i ( 1 ≤ p i ≤ 10 5 , 1 ≤ d i ≤ M ) — сила и выносливость i -го игрока.

Все игроки пронумерованы от 1 до N в порядке, данном во входных данных.

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

В первой строке выведите Z — максимальную возможную общую силу команды.

Во второй строке выведите 6 чисел — номера игроков, которые должны выйти на поле с самого начала.

В третей строке выведите B — число замен. Обратите внимание, что число замен не должно превосходить 3· N .

В следующих B строках выведите по 3 числа X , Y , Z ( 1 ≤ X < M , 1 ≤ Y , Z ≤ N ), описывающие замену игрока Y на игрока Z в момент времени X . Обратите внимание, что можно проводить несколько замен в один момент времени, но не допускается выход в игру на нулевое время (т.е. выход в игру и замена в один момент времени или наоборот).

Если существует несколько ответов, выведите любой.

Система оценки

Тесты к этой задаче состоят из трёх групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов некоторых из предыдущих групп. Обратите внимание, что прохождение тестов из условия (обозначается «У») не всегда обязательно для принятия на проверку.

Примеры
Входные данные
200 6
3 200
4 200
5 200
6 200
7 200
8 200
Выходные данные
6600
6 5 4 3 2 1 
0
Входные данные
9 9
10 3
9 3
13 9
5 3
15 9
100 9
3 6
2 6
1 6
Выходные данные
1260
6 5 3 1 7 8 
4
3 8 9
3 1 2
6 7 8
6 2 4
Входные данные
3 9
100 3
100 3
100 3
100 3
100 2
100 1
50 1
30 2
1 1
Выходные данные
1610
1 2 3 4 5 7 
2
1 7 8
2 5 6
#113809
Простыни
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
512 megabytes

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

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

Мы можем представлять двор Дональда как бесконечную систему координат, а простыни - как прямоугольники, параллельные осям координат. Выстрелы Кима могут быть представлены как точки в этой системе.

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

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

Первая строка ввода содержит два числа - количество простынь N ( 1 ≤ N ≤ 80000 ), и количество шаров M ( 1 ≤ M ≤ 80 000 ).

i -я из следующих N строк содержит четыре числа: координаты нижнего левого угла A i , B i ( 1 ≤ A i , B i ≤ 10 9 ) и верхнего правого угла C i , D i , ( 1 ≤ C i , D i ≤ 10 9 ) i -й простыни.

j -я из следующих M строк содержит три числа, где X j , Y j ( 1 ≤ X j , Y j ≤ 10 9 ) - координаты j -го выстрела Кима и K j ( 1 ≤ K j ≤ 10 9 ) - цвет j -го пейнтбольного шара.

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

i -я из N выходных строк должна содержать количество цветов на i -м листе.

Система оценки

Тесты к данной задаче состоят из трёх групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов необходимых групп.

Примеры
Входные данные
2 2
1 1 3 3
5 6 10 10
3 3 1
5 1 2
Выходные данные
1
0
Входные данные
3 3
1 1 7 7
2 2 6 6
3 3 5 5
4 4 1
2 6 2
4 7 3
Выходные данные
3
2
1
Входные данные
1 3
1 1 7 7
2 6 2
4 7 3
4 4 1
Выходные данные
3
#113811
ЗигЗаг
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Зиг и Заг играют в игру. Зиг говорит букву, а Заг — слово. Но слово не простое, а такое, что начинается с буквы Зига. Но и это не всё. Слово это должно быть в специальном списке слов, а из всех таких должно оно быть произнесено наименьшее число раз. А из всех слов из списка, начинающихся с буквы Зига, которые были произнесены минимальное число раз Заг должен взять лексикографический минимальное. Загу сложно. Помогите Загу.

Вам дан список S из k разрешённых слов. Так же вам даны буквы Зига за первые n ходов. На каждую из этих ходов найдите слово, которое Заг должен сказать.

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

В первой строке ввода содержится 2 числа k и n ( 1 ≤ k ≤ 10 5 , 1 ≤ n ≤ 10 5 ) — число слов в списке и число ходов.

В следующих k строках даны различные слова из списка, по одному в строке. Каждое из слов имеет длину не более 21 символа.

В следующих n строках даны буквы Зига, по одной в строке. Буквы даны в том порядке, в котором Зиг своими ходами их называет.

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

Выведите n строк, в i -й — то слово, которое Заг должен ответить на ход Зига. Гарантируется, что Заг всегда может сделать ход.

Система оценки

Решения, работающие при n ≤ 500 и k ≤ 500 будут оцениваться в 60 балов.

Примеры
Входные данные
4 5
zagreb
split
zadar
sisak
z
s
s
z
z
Выходные данные
zadar
sisak
split
zagreb
zadar
Входные данные
5 3
london
rim
pariz
moskva
sarajevo
p
r
p
Выходные данные
pariz
rim
pariz
Входные данные
1 3
zagreb
z
z
z
Выходные данные
zagreb
zagreb
zagreb
#113812
Доктор
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
128 megabytes

Домагой смотрит на руку Мате, играя в очень упрощённую версию игры «Ханаби». Для простоты скажем, что Мате держит в руке N карт, пронумерованных числами 1, 2, ..., N в каком-то фиксированном порядке (каждое из чисел от 1 до N соответствует ровно одной карте). Как и в настоящей игре, Мате не может менять порядок карт.

Домагой указывает Мате на подотрезок последовательности карт, после чего Мате «разворачивает» этот отрезок карт.

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

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

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

В первой строке вводится единственное число N — число кард в руке Мате ( 1 ≤ N ≤ 5·10 5 ). Во второй строке вводятся N различных целых чисел от 1 до N — карты в руке Мате в том порядке, в котором Домагой видит их.

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

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

Система оценки

Программа, верно работающая на тестах, в которых N ≤ 500 , оценивается в 30 баллов. Программа, верно работающая на тестах, в которых N ≤ 5 000 , оценивается в 60 баллов.

Примеры
Входные данные
4
3 2 1 4
Выходные данные
3 1
Входные данные
2
1 2
Выходные данные
1 1
Входные данные
7
3 6 5 7 4 1 2
Выходные данные
6 1
#113813
Небоскрёбы
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
128 megabytes

Вы когда-нибудь мечтали стать главным героем компьютерной игры? Главный герой этой истории, Бранимир, мечтает сейчас именно об этом.

Мир в мечте Бранимира состоит из N небоскребов, пронумерованных слева направо. Для i -го небоскреба, известна его высота H i и количество золотых монет G i на крыше этого небоскреба. Игра начинается с прыжка на любой из небоскребов и состоит из нескольких ходов. На каждом ходу Бранимир может прыгнуть на любой небоскрёб, находящийся справа от него, но так, чтобы высота нового небоскрёба была не меньше того небоскрёба, на котором сейчас сидит Бранимир. Оказавшись на крыше небоскреба, Бранимир собирает все золотые монеты на ней. Бранимир может закончить игру после любого количества шагов (возможно, нулевого), но он должен собрать не менее K золотых монет, чтобы перейти на следующий уровень.

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

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

Первая строка содержит 2 натуральных числа N и K ( 1 ≤ N ≤ 40 , 1 ≤ K ≤ 4·10 10 ) — число небоскрёбов и количество монет, которые надо набрать соответственно.

Следующие N строк содержат информацию о небоскрёбах. В i -й строке даны 2 числа H i и G i ( 1 ≤ H i , G i ,  ≤ 10 9 ) — высота и количество монет на i -м небоскрёбе.

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

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

Система оценки

Решение, корректно работающее при n ≤ 20 будет оцениваться в 40 баллов.

Примеры
Входные данные
4 6
2 1
6 3
7 2
5 6
Выходные данные
3
Входные данные
2 7
4 6
3 5
Выходные данные
0
Входные данные
4 15
5 5
5 12
6 10
2 1
Выходные данные
4
Страница: << 318 319 320 321 322 323 324 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест