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

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

Помогите Глебу выбрать день начала подготовки к экзаменам.

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

Первая строка выходных данных содержит число экзаменов n (1 ≤ n ≤ 50 000). Следующие строки описывают экзамены. Каждое описание состоит из трех строк. Первая строка – это название экзамена (строка, содержащая только латинские буквы, длиной не более 10). Вторая строка – дата экзамена в формате dd.mm.yyyy. Третья строка содержит величину ti для этого экзамена (1 ≤ ti ≤ 100 000). Все экзамены проходят от 01.01.1900 до 31.12.2100. Не забудьте, что високосными считаются годы, которые делятся на 4 и не делятся на 100 или которые делятся на 400.

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

Выведите в формате dd.mm.yyyy, когда Глеб самое позднее сможет приступить к подготовке к экзаменам. Если расписание не позволяет подготовиться к каждому из экзаменов, то выведите слово Impossible.

Примеры
Входные данные
3
Philosophy
29.06.2005
1
Algebra
30.06.2005
3
Physics
02.07.2005
10
Выходные данные
27.06.2005
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

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

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

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

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

Все работы пронумерованы числами от 1 до T, где T = K1 + ... + KN, первые K1 работ относятся к первому предмету, следующие K2 ко второму предмету и т.д.

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

В первой строке входных данных содержится одно число N — количество предметов (1 ≤ N ≤ 500). Далее содержатся числа Ki — число лабораторных работ по соответствующему предмету (1 ≤ Ki ≤ 100).

В следующей строке содержится T целых чисел pj — времена выполнения соответствующих работ (1 ≤ pj ≤ 10 000).

В последней строке содержится T целых чисел wj, обозначающих коэффициенты сложности соответствующих работ (1 ≤ wj ≤ 10 000).

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

(student.in, student.out) В первой строке выведите одно число — искомую минимальную величину взяток. В следующей строке выведите перестановку чисел от 1 до T, обозначающих порядок выполнения работ в оптимальном расписании. Помните, что Вася сначала должен изучить какой-то один предмет целиком, а только потом приступить к следующему и также изучать его целиком. В случае, если существует несколько решений, выведите любое из них.

Примеры тестов

Входные данные
1
5
1 2 3 4 5
5 4 3 2 1
Выходные данные
70
1 2 3 4 5
Входные данные
2
2 2
1 1 2 2
1 1 2 2
Выходные данные
23
1 2 3 4

ограничение по времени на тест
0.25 second;
ограничение по памяти на тест
256 megabytes

Для хранения двух агрессивных жидкостей $A$ и $B$ используется емкость с многослойной перегородкой, которая изготавливается из имеющихся $N$ листов. Для каждого листа $i$ ($i$ = 1, ..., $N$) известно время его растворения жидкостью $A$ - $a_i$ и жидкостью $B$ - $b_i$. Растворение перегородки каждой из жидкостей происходит последовательно лист за листом, с постоянной скоростью по толщине листа. Требуется спроектировать такую перегородку, время растворения которой было бы максимальным.

В первой строке входного файла записано число $N$ (1 ≤ $N$ ≤ 256). В каждой из последующих N строк содержатся два положительных вещественных числа $a_i$ и $b_i$, разделенные пробелом.

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

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

Примеры
Входные данные
4
1 2
1 2
0.5 1.5
7 3.5
Выходные данные
6.00000000
4 2 1 3 
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

В первой строке число n — количество горшочков с золотом — и число t — время исчезновения (в минутах) одного из них ( 2 ≤ n , t ≤ 100 ). В следующей строке n чисел — координаты горшочков в метрах. Все числа различны и по абсолютной величине не превосходят 100. Координаты горшочков даны в порядке возрастания. В следующей строке записан номер горшочка, который исчезнет через t минут.

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

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

Примеры
Входные данные
5 5
1 4 9 16 25
2
Выходные данные
24
1 2 3 4 5 
Входные данные
6 4
1 2 3 6 8 25
5
Выходные данные
31
5 1 2 3 4 6 
ограничение по времени на тест
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 — число замен. Обратите внимание, что число замен не должно превосходить N .

В следующих B строках выведите по 3 числа X , Y , Z ( 1 ≤ X < M , 1 ≤ Y , Z N ), описывающие замену игрока A на игрока B в момент времени 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

Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест