Темы --> Информатика --> Алгоритмы --> Теория расписаний
---> 4 задач <---
Источники
    Личные олимпиады(925 задач)
    Командные олимпиады(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 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест