#1223

Темы: [Обход в глубину]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, Московская областная олимпиада, 2007, Задача C ]

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

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

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

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

Первая строка содержит два целых числа: N (0 < N ≤ 1000) — число игроков, и M (0 < M ≤ 10⁶) — число сыгранных на турнире партий. Следующие N строк содержат по одному целому неотрицательному числу A_i(0 < A_i ≤ 10⁶) — рейтинг i-го игрока. Затем идет M строк с результатами партий (ничейные партии не приводятся, одни и те же игроки могли играть между собой несколько раз). Каждая строка состоит из номеров двух игроков через пробел: это значит, что в данной партии игрок, номер которого идет в строке первым, победил второго игрока. Все входные данные корректны.

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

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

Примеры

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

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

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

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

#1227

Радио «Байтик»

Темы: [Обход в глубину] [Бинарный поиск по ответу] [Многоугольники. Выпуклые оболочки]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, Московская областная олимпиада, 2007, Задача G ]

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

Радиостанция «Байтик» планирует транслировать свои программы в стране Флатландия. Министерство связи Флатландии выдало радиостанции лицензию на вещание на двух различных частотах.

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

Все передатчики, установленные на вышках, должны, согласно инструкции министерства, иметь одну и ту же мощность. Чтобы программы радиостанции могли приниматься на как можно большей территории, мощность передатчиков должна быть как можно большей. С другой стороны, необходимо, чтобы прием передач был качественным на всей территории Флатландии. Прием передач считается качественным, если не существует такого участка ненулевой площади, на который радиоволны радиостанции «Байтик» приходят на одной частоте одновременно с двух вышек.

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

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

Первая строка содержит число N — количество вышек (3 ≤ N ≤ 1200). Последующие N строк содержат по два целых числа — координаты вышек. Координаты заданы в километрах и не превышают 10⁴ по модулю. Все точки, в которых расположены вышки, различны. Все числа в строках разделены пробелом.

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

В первой строке выводится вещественное число — искомая мощность передатчиков. Во второй строке выводятся N чисел, где i-е число должно быть равно 1, если соответствующий передатчик должен вещать на первой частоте, и 2, если на второй. Ответ должен быть выведен с точностью, не меньшей 10^–8.

Примеры

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

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

0.707106781186548
1 2 2 1

#1928

Производство деталей

Темы: [Рекурсия] [Обход в глубину]

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

Предприятие «Авто-2010» выпускает двигатели для известных во всём мире автомобилей. Двигатель состоит ровно из $n$ деталей, пронумерованных от 1 до $n$, при этом деталь с номером $i$ изготавливается за $p_i$ секунд. Специфика предприятия «Авто-2010» заключается в том, что там одновременно может изготавливаться лишь одна деталь двигателя. Для производства некоторых деталей необходимо иметь предварительно изготовленный набор других деталей.

Генеральный директор «Авто-2010» поставил перед предприятием амбициозную задачу — за наименьшее время изготовить деталь с номером 1, чтобы представить её на выставке.

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

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

Первая строка входного файла содержит число $n$ ($1\le n\le100000$) — количество деталей двигателя. Вторая строка содержит $n$ натуральных чисел $p_1,p_2, \ldots,p_n$, определяющих время изготовления каждой детали в секундах. Время для изготовления каждой детали не превосходит $10^9$ секунд.

Каждая из последующих $n$ строк входного файла описывает характеристики производства деталей. Здесь $i$-я строка содержит число деталей $k_i$, которые требуются для производства детали с номером $i$, а также их номера. В $i$-й строке нет повторяющихся номеров деталей. Сумма всех чисел $k_i$ не превосходит 200000.

Известно, что не существует циклических зависимостей в производстве деталей.

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

В первой строке выходного файла должны содержаться два числа: минимальное время (в секундах), необходимое для скорейшего производства детали с номером 1 и число $k$ деталей, которые необходимо для этого произвести. Во второй строке требуется вывести через пробел $k$ чисел — номера деталей в том порядке, в котором следует их производить для скорейшего производства детали с номером 1.

Примеры

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

3
100 200 300
1 2
0
2 2 1

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

300 2
2 1

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

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

5 2
2 1

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

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

9 3
3 2 1

#111495

Столицы

Темы: [Динамическое программирование на графах] [Обход в глубину]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, 2013, 2 день, Задача D ]

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

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

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

Требуется написать программу, которая по количеству городов в Триландии и описанию дорог находит количество троек городов, которые могут быть столицами.

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

Первая строка входного файла содержит два разделенных пробелом целых числа: количество городов в Триландии n и требуемое время в пути между столицами d ($3 \leq n \leq 10^5$, $1 \leq d < n$). Каждая из последующих (n – 1) строк содержит описание одной дороги: пару разделенных пробелом различных целых чисел $a_i$ и $b_i$ — номера городов, которые соединены двусторонней дорогой ($1 \leq a_i \leq n$, $1 \leq b_i \leq n$, $a_i \ne b_i$). Каждая пара городов соединена не более чем одной дорогой.

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

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

Пояснения к тестам

В первом примере существует единственный способ выбрать три столицы: города под номерами 2, 3 и 4. Рисунок, соответствующий первому примеру, приведен ниже.

$\text{[math]}$

Во втором примере существует четыре варианта выбора трёх столиц из четверки городов: 2, 3, 4 и 5. Можно также выбрать столицами города с номерами 1, 6 и 7. Рисунок, соответствующий второму примеру, приведен ниже.

$\text{[math]}$

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

Правильные решения для тестов, в которых 3 ≤ n ≤ 50, будут оцениваться из 20 баллов.

Правильные решения для тестов, в которых 3 ≤ n ≤ 500, будут оцениваться из 40 баллов.

Правильные решения для тестов, в которых 3 ≤ n ≤ 5000, будут оцениваться из 60 баллов.

Примеры

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

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

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

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

#113441

Размещение данных

Темы: [Мосты] [Алгоритмы на графах] [Обход в глубину]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, 2017, 1 день, Задача C ]

Телекоммуникационная сеть крупной IT-компании содержит n серверов, пронумерованных от 1 до $n$. Некоторые пары серверов соединены двусторонними каналами связи, всего в сети m каналов. Гарантируется, что сеть серверов устроена таким образом, что по каналам связи можно передавать данные с любого сервера на любой другой сервер, возможно с использованием одного или нескольких промежуточных серверов.

Множество серверов $A$ называется отказоустойчивым, если при недоступности любого канала связи выполнено следующее условие. Для любого не входящего в это множество сервера $X$ существует способ передать данные по остальным каналам на сервер $X$ хотя бы от одного сервера из множества $A$.

На рис. 1 показан пример сети и отказоустойчивого множества из серверов с номерами 1 и 4. Данные на сервер 2 можно передать следующим образом. При недоступности канала между серверами 1 и 2 — с сервера 4, при недоступности канала между серверами 2 и 3 — с сервера 1. На серверы 3 и 5 при недоступности любого канала связи можно по другим каналам передать данные с сервера 4.

В рамках проекта группе разработчиков компании необходимо разместить свои данные в сети. Для повышения доступности данных и устойчивости к авариям разработчики хотят продублировать свои данные, разместив их одновременно на нескольких серверах, образующих отказоустойчивое множество. Чтобы минимизировать издержки, необходимо выбрать минимальное по количеству серверов отказоустойчивое множество. Кроме того, чтобы узнать, насколько гибко устроена сеть, необходимо подсчитать количество способов выбора такого множества, и поскольку это количество способов может быть большим, необходимо найти остаток от деления этого количества способов на число $10^9 + 7$.

Требуется написать программу, которая по заданному описанию сети определяет следующие числа: $k$ — минимальное количество серверов в отказоустойчивом множестве серверов, $c$ — остаток от деления количества способов выбора отказоустойчивого множества из $k$ серверов на число $10^9 + 7$

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

Первая строка входного файла содержит целые числа $n$ и $m$ — количество серверов и количество каналов связи соответственно ($2 \le n \le 200000$, $1 \le m \le 200000$). Следующие $m$ строк содержат по два целых числа и описывают каналы связи между серверами. Каждый канал связи задается двумя целыми числами: номерами серверов, которые он соединяет.

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

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

Выведите два целых числа, разделенных пробелом: $k$ — минимальное число серверов в отказоустойчивом множестве серверов, $c$ — количество способов выбора отказоустойчивого множества из $k$ серверов, взятое по модулю $10^9 + 7$

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

В приведенном примере отказоустойчивыми являются следующие множества из двух серверов: {1, 3}, {1, 4}, {1, 5}.

Описание подзадач и системы оценивания

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

Примеры

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

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

2 3

Страница: 1 Отображать по: