Страница: << 139 140 141 142 143 144 145 >> Отображать по:

#112101

Темы: [Перебор с отсечением]

Источники: [ Личные олимпиады, Московская олимпиада школьников, 6-9 классы, 2014, Задача D ]

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

Построенная пандорианцами железная дорога представляет собой прямой отрезок, проходящий в непосредственной близости от 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 ₁ , M ₁ — время в пути между первым и вторым водопадами, H ₂ , M ₂ — между вторым и третьим и так далее. Гарантируется, что время, затрачиваемое на дорогу между любыми двумя соседними водопадами, строго положительно, не превосходит одних пандорианских суток и записано корректно: 0 ≤ H _i ≤ H , 0 ≤ M _i < M .

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

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

Примечание

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

Тесты 1–2. Тесты из условия, оцениваемые в ноль баллов.
Тесты 3–17. В тестах этой группы H = 24 , M = 60 и N ≤ 1000 . Эта группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.
Тесты 18–38. В тестах этой группы H ≤ 80 , M ≤ 100 , N ≤ 100000 . Эта группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.
В тестах этой группы дополнительные ограничения отсутствуют. Эта группа оценивается в 40 баллов. Решение будет тестироваться на тестах этой группы offline, т. е. после окончания тура. Тесты в этой группе оцениваются независимо.

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

Примеры

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

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

12 0

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

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

Impossible

#112102

Макемакеанские пирамиды (CD)

Источники: [ Личные олимпиады, Московская олимпиада школьников, 6-9 классы, 2014, Задача E ]

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

Для постройки пирамид на Макемаке были завезены и расставлены в ряд N каменных блоков различных типов. Всего существует 9 типов блоков. Тип блока определяется его размером: самые большие блоки имеют тип 9 , а самые маленькие — 1 . Правильная пирамида должна состоять из поставленных друг на друга блоков, причем сверху обязательно должен быть блок типа 1 , а каждый блок должен стоять на блоке следующего по величине типа.

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

Разработайте стратегию постройки пирамид, при которой неиспользованных блоков останется как можно меньше.

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

В первой строке задано целое число N — количество завезенных блоков ( 1 ≤ N ≤ 100 000 ).

Во второй строке даны N целых чисел от 1 до 9 — типы блоков в том порядке, в котором они стоят в ряду, перечисленные слева направо.

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

Выведите минимально возможное число неиспользованных блоков.

Примечание

Во втором примере можно построить только две пирамиды высотой 1.

В третьем примере можно из стоящих в середине блоков 1 2 построить пирамиду высотой 2, а из оставшихся блоков — пирамиду высотой 5.

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

Тесты 1–3. Тесты из условия, оцениваются в ноль баллов.
Тесты 4–18. В тестах этой группы 1 ≤ N ≤ 2000 . Тесты в этой группе оцениваются независимо. Каждый успешно пройденный тест оценивается в 4 балла.
Тесты 19–28. В тестах этой группы 1 ≤ N ≤ 100 000 . Решение будет тестироваться на тестах этой группы offline, т. е. после окончания тура. Тесты в этой группе оцениваются независимо. Каждый успешно пройденный тест оценивается в 4 балла.

Примеры

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

3
3 1 2

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

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

4
2 1 3 1

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

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

7
1 2 3 1 2 4 5

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

#112328

Киноакадемия

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Заключительный этап, 2014, 2 тур, Киноакадемия ] [ Личные олимпиады, Всероссийская олимпиада школьников, Заключительный этап, 2014, 2 тур, Задача A ]

В финал конкурса Киноакадемии вышли \(n\) лучших кинофильмов 2014 года. В конкурсе награждаются фильмы в двух номинациях: лучшая режиссура и лучший сценарий. По правилам конкурса в каждой номинации должен быть награжден ровно один фильм, причём в разных номинациях — разные фильмы.

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

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

Формат входного файла

В первой строке входного файла задано целое число n — количество кинофильмов, участвующих в финале конкурса Киноакадемии. В следующих n строках содержатся по три целых числа \(a_i\) , \(b_i\) , \(c_i\) — уровень ликования, если \(i\)-й фильм не выиграет ни в одной из номинаций, уровень ликования, если этот фильм выиграет в номинации на лучшую режиссуру, и уровень ликования, если этот фильм выиграет в номинации на лучший сценарий.

Формат выходного файла

Первая строка выходного файла должна содержать одно число — наибольший возможный суммарный уровень ликования. Вторая строка должна содержать два целых числа — номера фильмов-победителей в номинациях лучшая режиссура и лучший сценарий соответственно. Фильмы нумеруются натуральными числами от 1 до \(n\). Если оптимальных способов выбора награждаемых фильмов несколько, можно вывести любой из них.

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

Подзадача 1

2 <= \(n\) <= 100

1 <= \(a_i\), \(b_i\), \(c_i\) <= \(10^5\)

Подзадача оценивается в 20 баллов

Подзадача 2

2 <= \(n\) <= 2000

1 <= \(a_i\), \(b_i\), \(c_i\) <= \(10^5\)

Подзадача оценивается в 25 баллов

Подзадача 3

2 <= \(n\) <= \(10^5\)

1 <= \(a_i\), \(b_i\), \(c_i\) <= \(10^9\)

Подзадача оценивается в 55 баллов

Пояснение к примеру

В приведенном примере наибольший суммарный уровень ликования равен 3 + 5 + 9 = 17.

Примеры

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

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

17
2 3

#112329

Магистраль "Урал"

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Заключительный этап, 2014, 2 тур, Задача C ]

Планируется строительство новой магистрали «Урал». Долговечность автомагистрали зависит от пластов пород, залегающих под ней. Пластом называется геологическое тело, состоящее из одной горной породы.

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

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

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

Формат входного файла

Первая строка входного файла содержит целое число \(n\) — количество пластов. Пласты пронумерованы целыми числами от 1 до \(n\) в произвольном порядке.

В \(i\)-й из следующих \(n\) строк содержатся целые числа \(l_i\) и \(r_i\) (0 <= \(l_i\) < \(r_i\) <= \(10^9\) ) — расстояния от начала магистрали до точек, под которыми начинается и заканчивается \(i\)-й пласт.

В следующей строке записано целое число \(m\) — количество скважин, в которых проводилось бурение. Следующие \(m\) строк описывают результаты бурения: в каждой строке сначала указаны два целых числа \(x\) (0 <= \(x\) <= \(10^9\) ) и \(k\) (0 <= \(k\) <= \(n\)) — расстояние от начала магистрали до скважины и количество обнаруженных в данной скважине пластов, затем — целые числа \(s_1\); \(s_2\), ..., \(s_k\) — номера пробуренных пластов, перечисленные в порядке залегания сверху вниз. Скважины перечислены в порядке возрастания расстояния \(x\).

Гарантируется, что решение существует.

Формат выходного файла

Первая строка выходного файла должна содержать n целых чисел \(p_1\); \(p_2\), ..., \(p_n\), описывающих возможный порядок залегания пластов сверху вниз. Среди чисел \(p_1\), \(p_2\), ..., \(p_n\) каждый номер пласта должен встретиться ровно один раз. При этом пласт с номером \(p_j\) не должен нигде проходить выше пластов с номерами \(p_1\), ..., p_j-1 или ниже пластов с номерами p_j+1, ..., \(p_n\)

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

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

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

Подзадача 1

1 <= \(n\), \(m\) <= 1000

Каждая скважина пересекает все пласты, залегающие под ней

Подзадача оценивается в 20 баллов

Подзадача 2

1 <= \(n\), \(m\) <= 1000

Подзадача оценивается в 20 баллов

Подзадача 3

1 <= \(n\), \(m\) <= 30000

Суммарное количество пластов, найденных при бурении скважин, не более \(10^6\).

Подзадача оценивается в 20 баллов

Подзадача 4

1 <= \(n\), \(m\) <= \(10^5\)

Суммарное количество пластов, найденных при бурении скважин, не более \(10^5\).

Подзадача оценивается в 20 баллов

Подзадача 5

1 <= \(n\), \(m\) <= \(10^5\)

Суммарное количество пластов, найденных при бурении скважин, не более \(10^6\).

Подзадача оценивается в 20 баллов

Примеры

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

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

2 1 3 4

#112330

Здоровое питание

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Заключительный этап, 2014, 2 тур, Задача B ]

План студенческого городка некоторого университета представляет собой квадрат \(n\) x \(n\), в каждой клетке которого расположено здание. Здания соединены переходами, если они расположены в клетках, имеющих общую сторону. В левом верхнем углу квадрата расположено студенческое общежитие. В правом нижнем углу расположен учебный корпус.

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

Руководство университета заинтересовалось разнообразием питания студентов, покупающих продукты в автоматах по ходу движения. Для каждого автомата A_i,j планируется найти кратчайший путь из общежития в учебный корпус, проходящий через этот автомат и содержащий как можно больше автоматов, торгующих тем же самым продуктом, что и автомат A_i,j. Количество таких автоматов на этом пути называется избыточностью автомата A_i,j. При этом автомат A_1,1 находится в общежитии, а автомат A_n,n — в учебном корпусе.

Требуется написать программу, которая по информации о продуктах, продаваемых автоматами, для каждого из чисел в диапазоне от 1 до 2n - 1 определяет число автоматов с таким значением избыточности.

Формат входного файла

Первая строка входного файла содержит целое число n (2 <= \(n\) <= 1500). Следующие \(n\) строк содержат по \(n\) чисел в каждой. В \(i\)-й из этих строк \(j\)-е число соответствует номеру продукта, продающегося в автомате A _{i, j}. Номера продуктов находятся в диапазоне от 1 до \(n^2\).

Формат выходного файла

Выходной файл должен содержать (2n - 1) целых чисел - количество автоматов с избыточностями 1, 2, ..., 2n - 1 соответственно

Система оценивания

Для проверки решений этой задачи используются 50 тестов. Тесты оцениваются независимо. Каждый тест оценивается в 2 балла. Значения n в тестах жюри приведены в следующей таблице.

Примеры

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

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

0 0 9 0 0

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

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

2 4 9 0 0 1 1 8 0

Страница: << 139 140 141 142 143 144 145 >> Отображать по:

Выбрано

Отменить

Добавить в контест