Темы --> Информатика --> Алгоритмы
    Задачи на моделирование(78 задач)
    Арифметические алгоритмы(240 задач)
    Алгоритмы поиска(155 задач)
    Алгоритмы сортировки(194 задач)
    Динамическое программирование(355 задач)
    Алгоритмы на графах(319 задач)
    Перебор(154 задач)
    Игры и выигрышные стратегии(33 задач)
    Вычислительная геометрия(216 задач)
    Эвристические методы(30 задач)
    Алгоритмы на строках(45 задач)
    Пересечение множеств(10 задач)
    Жадный алгоритм(71 задач)
    Теория расписаний(5 задач)
    Обработка текста(31 задач)
    Дата и время(14 задач)
---> 405 задач <---
Источники --> Личные олимпиады
    Олимпиады сайта(17 задач)
    Школьная личная олимпиада ФМШ №2007 г. Москвы(7 задач)
    Золотая середина (Новосибирск)(10 задач)
    Нижегородская олимпиада школьников(42 задач)
    Московская олимпиада школьников(168 задач)
    Индивидуальная олимпиада по информатике и программированию (ИОИП)(22 задач)
    Открытая олимпиада школьников(173 задач)
    Украинские олимпиады(61 задач)
    Республиканская олимпиада школьников (Беларусь)(6 задач)
    Жаутыковские олимпиады(8 задач)
    Всероссийская олимпиада школьников(304 задач)
    Международные олимпиады(32 задач)
    Central European Olympiad in Informatics (4 задач)
    Интернет-олимпиады(2 задач)
    COCI(36 задач)
    Турнир Архимеда(36 задач)
    Baltic Olympiad in Informatics(10 задач)
Страница: << 53 54 55 56 57 58 59 >> Отображать по:
#3333
Бизнес
  
ограничение по времени на тест
3.0 second;
ограничение по памяти на тест
256 megabytes

В государстве Древоландия есть \(N\) крупных городов, соединенных \(N - 1\) двухсторонними дорогами, причем из любого города можно добраться по этим дорогам до любого другого города. Экономика страны находится в зачаточном состоянии, а Владислав - один из первых бизнесменов в этой стране. В данный момент он подумывает о том, чтобы перевозить крупные партии товаров из одного города в другой.

Совсем недавно на дорогах страны появились \(M\) полицейских постов (они могут быть не на каждой дороге, и их может быть несколько на одной дороге). Все посты разбиты на \(P\) категорий, на одной дороге бывают посты только различных категорий. Полицейские очень любят переписываться с коллегами своей категории, а электронной почты в стране еще не существует, поэтому для передачи писем они используют проезжающих. Проезжая пост категории \(i\) без письма для полицейских этой категории, Владислав обязательно берет на посту письмо. Проезжая через очередной пост категории \(i\), Владислав обязательно отдает это письмо, причем новое письмо на этом посту он не получает. К концу поездки у Владислава не должно остаться ни одного письма.

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

Для любой дороги Владислав знает, сколько разбойников и странников находится на ней в первый год его предпринимательства, и сколько новых будут появляться каждый год (это фиксированные числа, свои для каждой дороги). Владиславу также известно расположение всех полицейских постов и категория каждого их них. Заниматься бизнесом он планирует в течение \(K\) лет.

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

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

В первой строке входного файла содержатся три целых числа \(N\), \(M\) и \(K\). В следующей \((N - 1)\) строке идут описания каждой из дорог. Дорога сначала описывается четырьмя целыми числами \(S_i\), \(F_i\) - номера городов, которые эта дорога соединяет (\(1 \le S_i \le N\), \(1 \le F_i \le N\)), \(A_i\) - число странников на этой дороге в первый год, \(B_i\) - число разбойников на этой дороге в первый год, \(C_i\), \(D_i\) - ежегодные прирост числа странников и числа разбойников соответственно. Затем идет число \(E_i\) - количество постов на этой дороге, а после него \(E_i\) различных натуральных чисел, не превосходящих 20, обозначающих категории постов. Все числа целые и неотрицательные.

Гарантируется, что общее количество всех постов равно \(M\), а также что в течение этих \(K\) лет количество как странников, так и разбойников на каждой дороге не превзойдет \(10\,000\).

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

Выведите \(K\) чисел - максимальную прибыль, которую можно получить в каждый из \(K\) годов (в том числе отрицательную для убыточных годов). В случае, если в какой-то из годов нет ни одного маршрута, на котором Владислав мог бы передать все врученные ему письма, выведите "Sadness!" (без кавычек).

Примечания

Тесты состоят из четырех групп.

  1. Тесты 1--3, из условия, они оцениваются в 0 баллов.
  2. В тестах этой группы \(1 \le N \le 1\,000\), \(1 \le M \le 1\,000\), \(1 \le K \le 10\). Эта группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.
  3. В тестах этой группы \(1 \le N \le 30\,000\), \(1 \le M \le 30\,000\), \(1 \le K \le 10\). Эта группа также оценивается в 30 баллов, они начисляются только при прохождении всех тестов группы.
  4. Offline-группа, \(1 \le N \le 100\,000\), \(1 \le M \le 100\,000\), \(1 \le K \le 50\). Баллы за тесты этой группы начисляются только при прохождении всех тестов 1-й и 2-й групп. Каждый тест оценивается независимо от других.
Примеры
Входные данные
2 2 2
2 1 7 1 6 10 2 1 2
Выходные данные
Sadness!
Sadness!
Входные данные
5 5 10
3 2 2 4 8 4 0
4 1 3 10 8 7 2 2 1
4 5 6 8 8 10 2 1 2
1 3 2 5 6 1 1 1
Выходные данные
-2
2
6
10
14
18
22
26
30
34
Входные данные
14 14 2
1 3 48 28 23 0 1 1
4 5 25 20 25 7 1 4
3 2 23 16 100 50 1 4
11 9 179 2 57 54 1 2
13 7 30 4 27 23 1 2
10 1 23 6 63 70 2 4 1
3 8 17 7 10 5 0
12 13 34 17 43 67 1 4
4 3 10 4 1 6 1 2
6 1 23 11 38 38 2 2 4
9 8 50 13 0 0 1 1
8 13 43 15 18 19 1 2
10 14 14 40 50 1 1 2
Выходные данные
67
111
#3334
Проходной балл
  

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

  1. Призеры олимпиады прошлого года приглашаются на заключительный этап вне зависимости от набранных ими в первом туре баллов.
  2. Все участники, набравшие не меньше баллов, чем установленный жюри проходной балл, проходят во второй тур.
  3. Если в каком-либо из регионов ни один участник по первым двум правилам во второй тур не прошел, то на заключительный этап приглашается участник из этого региона, набравший в нем максимальное количество баллов (это не касается регионов, от которых участников не было).
  4. На второй тур можно пригласить не более \(M\) участников.

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

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

В первой строке входного файла содержатся три целых числа \(N\), \(M\) и \(R\) - число участников первого тура, максимально возможное число участников второго тура и число регионов, из которых могли быть участники (\(1 \le M < N\)). Далее в \(N\) строках содержатся результаты каждого из участников. Каждая строка состоит из четырех целых чисел. Сначала идет \(id\) - уникальный идентификатор участника (\(1 \le id \le N\)), далее номер региона \(region\), в котором данный участник учится (\(1 \le region \le R\)), затем \(score\) - число баллов, набранных участником, четвертое число равно 1, если участник является призером олимпиады прошлого года, и 0 - в противном случае.

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

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

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

Примечания

Тесты состоят из четырёх групп. Во всех тестах \(0 \le score \le 10^9\).

  1. Тест 1 из условия, оценивается в 0 баллов.
  2. В тестах этой группы все числа на входе не превосходят 1000. Эта группа оценивается в 30 баллов, при этом баллы начисляются только при прохождении всех тестов группы.
  3. В тестах этой группы \(1 \le R \le M \le 10\,000\), \(M < N \le 100\,000\). Эта группа также оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.
  4. В тестах этой группы, \(1 \le R \le M < N \le 100\,000\). Баллы за тесты этой группы начисляются только при прохождении всех тестов 1-й и 2-й групп. Каждый из тестов оценивается независимо от других.
Примеры
Входные данные
9 6 5
6 1 799 0
2 4 995 0
1 4 989 1
7 2 538 0
5 4 984 0
8 2 1000 0
3 2 998 0
4 2 823 1
9 1 543 0
Выходные данные
985
#3335
Лыжные гонки
  

Во время лыжных соревнований \(N\) спортсменов стартуют с интервалом в 1 минуту. Скорость каждого лыжника на дистанции постоянна: \(i\)-й лыжник преодолевает 1 км за \(w_i\) минут. Длина трассы равна \(L\) км. Считается, что \(i\)-й лыжник обогнал \(j\)-го (совершил обгон), если он стартовал позже \(j\)-го, а пришёл к финишу раньше него. Подсчитайте суммарное число совершённых во время гонки обгонов.

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

Первая строка входного файла содержит два целых числа \(N\) и \(L\). Во второй строке через пробел расположены \(N\) целых чисел \(w_i\).

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

Выведите единственное число - суммарное количество обгонов.

Примечания

Во всех тестах \(1 \le L \le 10^9\), \(1 \le w_i \le 10^9\) при \(i = 1, 2, \dots, N\). Тесты состоят из трёх групп.

  1. Тесты 1 и 2 из условия, оцениваются в 0 баллов.
  2. В тестах этой группы \(1 \le N \le 10\,000\), эти тесты оцениваются в 50 баллов, при этом баллы начисляются только при прохождении всех тестов группы.
  3. Off-line группа, \(1 \le N \le 500\,000\). При этом баллы за тесты этой группы ставятся только тогда, когда программа проходит все тесты предыдущей группы. Если программа не проходит хотя бы один из тестов группы 1, то баллы за тесты группы 2 не ставятся. Тесты этой группы оцениваются независимо друг от друга.
Примеры
Входные данные
2 1
20 19
Выходные данные
0
Входные данные
5 3
3 6 2 4 1
Выходные данные
7
#3336
Волейбол
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

В одной Очень Известной Летней Школе наиболее популярным видом спорта является волейбол. Для каждого из \(N\) школьников известно его умение играть в волейбол. Перед началом занятий школьников необходимо распределить между двумя тренерами.

Тренеры сочли справедливым следующий алгоритм разделения на две группы. Сначала они выбирают два целых числа \(p\), \(q\) (\(0 < p \le q \le N\)). Затем первый берет себе \(p\) лучших школьников, после чего оба тренера, начиная со второго, берут по очереди по \(q\) лучших школьников из оставшихся, пока их количество не меньше \(q\). В конце очередной тренер просто берет всех оставшихся.

Оба тренера заинтересованы в наиболее справедливом распределении школьников между группами. Поэтому они стремятся найти такие \(p\) и \(q\), чтобы разница суммарных умений между двумя группами школьников оказалась минимальной. При этом, вообще говоря, не обязательно, чтобы количество школьников в каждой из групп было одинаковым.

Помогите тренерам подобрать такие "справедливые" значения \(p\) и \(q\) (\(0 < p \le q \le N\)), при которых разница в суммарных умениях образованных групп школьников по абсолютной величине будет минимальна.

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

В первой строке входного файла записано единственное целое число \(N\). Во второй строке содержатся \(N\) неотрицательных целых чисел, не превосходящих \(10^9\) - умения школьников играть в волейбол.

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

Выведите искомые целые значения \(p\) и \(q\) (\(0 < p \le q \le N\)). Если искомых пар несколько, то выведите любую из них.

Примечания

Тесты состоят из четырёх групп.

  1. Тест 1, из условия, оценивается в 0 баллов.
  2. В тестах этой группы \(2 \le N \le 300\). Эта группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.
  3. В тестах этой группы \(2 \le N \le 2\,000\). Эта группа также оценивается в 30 баллов, они начисляются только при прохождении всех тестов группы.
  4. Offline-группа, \(1 \le N \le 100\,000\). Баллы за тесты этой группы начисляются только при прохождении всех тестов 1-й и 2-й групп. Тесты этой группы оцениваются независимо друг от друга.

Примеры
Входные данные
8
5 3 3 3 3 3 7 1
Выходные данные
1 2
#3337
Забор
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

На одну Очень Известную Планету упал метеорит. Метеорит в атмосфере распался на \(N\) кусков, каждый из которых упал в свою точку.

Чтобы куски метеорита не были испорчены любопытными туристами, для проведения научных исследований решили построить один забор, которым огородить не менее \(K\) кусков метеорита. Естественно, что забор должен быть минимально возможной длины, и внутри него должны оказаться любые \(K\) (или больше) кусков метеорита (кусок считается лежащим внутри забора как когда он лежит строго внутри, так и когда забор проходит непосредственно через него).

Конечно, ученые хотят огородить как можно больше кусков, но как всегда, все упирается в деньги. Главный бухгалтер решил составить такую таблицу: для каждого \(K\) от 1 до \(N\) определить, какой минимальной длины нужно построить забор, чтобы внутри него оказалось не менее \(K\) кусков метеорита. Помогите ему.

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

В первой строке входного файла записано единственное целое число \(N\). В каждой из следующих \(N\) строк записано по паре целых чисел, по модулю не превосходящих \(1\,000\) - координаты точек, куда упали куски метеорита. Никакие два куска не упали в одну и ту же точку.

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

Выведите \(N\) чисел, \(i\)-е (\(1 \le i \le N\)) должно быть равно минимальной длине забора, внутри которого окажется не менее \(K\) кусков метеорита. Выведенный ответ будет сравниваться с правильным с точностью до \(10^{-6}\).

Примечания

Тесты состоят из четырёх групп.

  1. Тесты 1--2, из условия, оцениваются в 0 баллов.
  2. В тестах этой группы \(1 \le N \le 16\). Эта группа оценивается в 30 баллов, при этом баллы начисляются только при прохождении всех тестов группы.
  3. В тестах этой группы \(1 \le N \le 30\). Эта группа также оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.
  4. Offline-группа. Баллы за тесты этой группы начисляются только при прохождении всех тестов 1-й и 2-й групп. Тесты объединяются в подгруппы, каждая из которых оценивается в 10 баллов, баллы за каждую подгруппу начисляются только при прохождении всех тестов подгруппы. Подгруппы соответствуют ограничениям \(N \le 40\), \(N \le 60\), \(N \le 80\), \(N \le 100\).

Примеры
Входные данные
4
0 0
0 1
1 0
1 1
Выходные данные
0.000000000
2.000000000
3.414213562
4.000000000
Входные данные
3
1 1
0 0
2 0
Выходные данные
0.000000000
2.828427125
4.828427125
Страница: << 53 54 55 56 57 58 59 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест