Темы --> Информатика --> Алгоритмы
    Задачи на моделирование(78 задач)
    Арифметические алгоритмы(240 задач)
    Алгоритмы поиска(155 задач)
    Алгоритмы сортировки(194 задач)
    Динамическое программирование(355 задач)
    Алгоритмы на графах(319 задач)
    Перебор(154 задач)
    Игры и выигрышные стратегии(33 задач)
    Вычислительная геометрия(216 задач)
    Эвристические методы(30 задач)
    Алгоритмы на строках(45 задач)
    Пересечение множеств(10 задач)
    Жадный алгоритм(71 задач)
    Теория расписаний(5 задач)
    Обработка текста(31 задач)
    Дата и время(14 задач)
---> 8 задач <---
Источники --> Личные олимпиады --> Московская олимпиада школьников --> 6-9 классы
    2011(5 задач)
    2012(5 задач)
    2013(5 задач)
    2014(5 задач)
    2015(5 задач)
    2016(5 задач)
Страница: << 1 2 Отображать по:
#111508
Кружки в Маховниках
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Маленький Петя очень любит компьютеры и хочет научиться программировать.

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

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

Перед тем как сесть составлять порядок посещения кружков, Петя внимательно перечитал условия обучения и обнаружил ещё один важный пункт. Оказывается, для привлечения школьников, во всех кружках действует система поощрения учеников конфетами. Это означает, что по окончании очередного кружка ученику выдают несколько коробок конфет, всё больше и больше с каждым пройденным кружком. С другой стороны, в каждом кружке количество конфет в коробке своё, зависящее от сложности курса. Более конкретно — за прохождение i-го по счёту кружка, если этот кружок идёт в общем списке под номером j, ученику выдают аж Ni - 1·j конфет — такие щедрые люди программисты.

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

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

В первой строке входного файла содержится целое число N (1 ≤ N ≤ 100 000) — количество кружков в Маховниках.

В последующих N строках идут описания входных требований кружков, в порядке их следования в общем списке. В i-ой строке сначала записано целое число ki (0 ≤ ki ≤ N - 1) — количество кружков, в которых нужно отучиться перед записью в i-й кружок, а потом ki номеров этих кружков.

Сумма ki не превосходит 200 000.

Гарантируется, что возможно посетить все эти кружки в некотором порядке, не нарушая условия посещения.

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

Выведите N номеров, разделённых пробелами — порядок, в котором Пете надо посещать кружки, чтобы съесть как можно больше конфет.

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

Входные данные
6
1 2
0
1 2
3 1 2 5
1 2
4 1 3 4 5
Выходные данные
2 1 3 5 4 6

Примечание

Пояснение к примеру. Посещая кружки в указанном порядке, Петя получит 60·2 + 61·1 + 62·3 + 63·5 + 64·4 + 65·6 = 2 + 6 + 108 + 1080 + 5184 + 46656 = 53036 конфет.

#112099
Воды слонам!
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Кроме Земли, пандорианцы уже много тысячелетий исследуют и другие планеты. Большой интерес для них в прошлом представляла планета Арракис. К сожалению, с началом исследований на Земле финансирование исследований на Арракисе было существенно урезано, и местным агентам-исследователям пришлось искать дополнительные источники дохода.

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

Изначально пандорианцы обладают запасом золота в 10 золотых слитков. Они решили в один из дней года купить на все это золото воды, а в какой-то последующий день продать всю купленную воду и получить прибыль за счет разницы стоимости. К примеру, если бы стоимость воды в день покупки составляла 1 литр за 4 золотых слитка, а стоимость воды в день продажи – 1 литр за 6 золотых слитков, то пандорианцы могли бы получить купить \(\frac{10}{4}=2.5\) литра воды, а продать они эту воду смогут за \(2.5 \times 6=15\) золотых слитков. Таким образом, прибыль пандорианцев составила бы \(15-10=5\) золотых слитков. Конечно же, пандорианцы хотят максимизировать свой доход в результате этих махинаций. Помогите им выбрать оптимальные дни для покупки и продажи воды!

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

В первой строке задано целое число 2 ≤ N ≤ 100 000 — количество дней в году на планете Арракис.

Во второй строке заданы N целых положительных чисел a i ( 1 ≤ i ≤ N , 1 ≤ a i ≤ 5000 ), задающих стоимость воды на Арракисе в день i .

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

Выведите два целых числа: первое число — номер дня, в который стоит купить воду, второе число — номер дня, в который следует воду продать. Дни нумеруются с единицы. Если оптимальных пар дней для покупки/продажи несколько, то выведите любую из них.

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

Примеры
Входные данные
6
10 3 5 3 11 9
Выходные данные
2 5
Входные данные
4
5 5 5 5
Выходные данные
0 0
#112101
Паровозик из Морошково (BC)
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

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

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

В первой строке через пробел вводятся два натуральных числа: количество часов в одних сутках ( H ) и минут в одном часу ( M ) на Пандоре ( 1 ≤ H , M ≤ 500 ).

Следующая строка содержит четыре целых числа, описывающих время начала ( H s , M s ) и конца ( H f , M f ) светового дня ( 0 ≤ H s , H f < H ; 0 ≤ M s , M f < M ). При этом либо H s < H f , либо H s = H f и M s < M f (гарантируется, что день начинается раньше, чем заканчивается). Если паровозик проезжает мимо водопада ровно в H s часов M s минут или ровно в H f часов M f минут, то считается, что он проехал мимо водопада днём.

Третья строка содержит одно натуральное число N — количество водопадов, рядом с которыми проезжает паровозик ( 1 ≤ N ≤ 100 000 ).

В следующих N - 1 строках вводятся по 2 целых числа H i и M i , описывающих продолжительность временных интервалов для проезда между соседними водопадами: H 1 , M 1 — время в пути между первым и вторым водопадами, H 2 , M 2 — между вторым и третьим и так далее. Гарантируется, что время, затрачиваемое на дорогу между любыми двумя соседними водопадами, строго положительно, не превосходит одних пандорианских суток и записано корректно: 0 ≤ H i ≤ H , 0 ≤ M i < M .

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

Если составить подходящее расписание невозможно, то в качестве ответа выведите одно слово « Impossible » (без кавычек). Иначе выведите два числа H 0 и M 0 , разделённые пробелом, описывающие любое подходящее время проезда паровозика рядом с первым водопадом.

Примечание

Тесты к этой задаче состоят из четырех групп.

  • Тесты 1–2. Тесты из условия, оцениваемые в ноль баллов.

  • Тесты 3–17. В тестах этой группы H = 24 , M = 60 и N ≤ 1000 . Эта группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.

  • Тесты 18–38. В тестах этой группы H ≤ 80 , M ≤ 100 , N ≤ 100000 . Эта группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.

  • В тестах этой группы дополнительные ограничения отсутствуют. Эта группа оценивается в 40 баллов. Решение будет тестироваться на тестах этой группы offline, т. е. после окончания тура. Тесты в этой группе оцениваются независимо.

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

Примеры
Входные данные
24 60
8 0 22 0
6
6 0
21 0
19 0
12 0
10 0
Выходные данные
12 0
Входные данные
24 60
8 17 20 10
2
11 59
Выходные данные
Impossible
Страница: << 1 2 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест