Темы --> Информатика --> Алгоритмы --> Алгоритмы на графах --> Обход в глубину
    Компоненты сильной связности(3 задач)
    Мосты(2 задач)
    Применение обхода в глубину(3 задач)
    Топологическая сортировка(2 задач)
    Точки сочленения(1 задач)
---> 9 задач <---
Источники --> Личные олимпиады --> Всероссийская олимпиада школьников
    Муниципальный этап(80 задач)
    Окружная олимпиада(18 задач)
    Региональный этап(109 задач)
    Заключительный этап(97 задач)
Страница: 1 2 >> Отображать по:
#21
Электрички на перегонах не меняют
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

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

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

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

1

4 станции, 3 перегона: 1-4, 2-4, 3-4

Маршруты: 1-4-2, 2-4-3, 3-4-1.


Ответ: решения нет

2

5 станций, 4 перегона: 1-5, 2-5, 3-5, 4-5

Маршруты: 1-5-2, 2-5-3, 3-5-4, 4-5-1.


Ответ: решение есть; например, следующее: номер станции: 1 2 3 4 5

тарифный номер: 1 4 1 5 3


Замечание: тарифные номера разных станций могут совпадать.
Входные данные

В первой строке входных данных содержатся два целых числа: N — количество станций (2 ≤ N ≤ 100 000), и M — количество перегонов между ними (1 ≤ M ≤ N – 1). В последующих M строках записаны пары целых чисел a, b (a ≠ b, 1 ≤ a ≤ N, 1 ≤ b ≤ N), означающие наличие перегона между станциями a и b. За ними в отдельной строке записано единственное целое положительное число K — количество маршрутов электричек. В последующих K строках идут описания маршрутов электричек, по одному на строке. Каждое описание представляет собой последовательность целых чисел — номеров всех станций маршрута в порядке одного из двух возможных направлений следования электрички. Описание маршрута заканчивается числом 0.

Все номера станций в описании маршрута различны. Количество станций в каждом маршруте не менее двух. Любые две последовательные станции в маршруте каждой электрички соединены перегоном. Суммарное количество станций в описаниях всех маршрутов не превосходит 200 000. Могут быть станции и перегоны, через которые не проходит ни одна электричка.

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

В первую строку  выведите «NO», если искомого назначения тарифных номеров не существует. В противном случае в первую строку выведите «YES», а в следующей строке — N целых положительных чисел, где i-е число — тарифный номер i-й станции. Тарифный номер каждой станции должен находиться в диапазоне от 1 до N.

Если существует несколько решений, необходимо вывести любое из них.

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

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

  • Группа 1 (20 баллов): N, K <= 20
  • Группа 2 (30 баллов): N, K <= 2000
  • Группа 3 (50 баллов): без дополнительных ограничений
Примеры
Входные данные
6 5
1 2
5 2 
5 6
4 5
3 2
6
1 2 0
5 6 0
3 2 1 0
5 2 3 0
4 5 2 0
6 5 4 0
Выходные данные
YES
2 3 4 1 2 3
#1223
Авторитетное сообщество
  

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

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

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

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

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

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

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

Примеры
Входные данные
2 1
1
1
1 2
Выходные данные
1
Входные данные
6 6 
1
1
1
5 
6
1
6 1
1 2
2 3
3 4
4 5
3 4
Выходные данные
9
#1227
Радио «Байтик»
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

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

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

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

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

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

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

Примеры
Входные данные
4
0 0
0 1
1 0
1 1
Выходные данные
0.707106781186548
1 2 2 1
#1337
Компьютерная сеть
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

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

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

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

Организаторам олимпиады поручено разместить компьютеры в зале соревнований. При размещении должны выполняться следующие условия:

1.Компьютеры размещаются на плоскости в точках с целочисленными координатами.

2.Координаты компьютеров x и y лежат в диапазоне 0 ≤ x, y ≤ 106.

3.Никакие два компьютера не располагаются в одной точке.

4.Кабели являются отрезками прямых.

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

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

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

В первой строке входного файла содержатся числа N и M — количество компьютеров и количество кабелей в схеме (1 ≤ N ≤ 100 000, 0 ≤ M ≤ 200 000). В последующих M строках содержатся пары чисел, разделенных пробелами. Каждая такая пара описывает один кабель, числа представляют собой номера соединенных компьютеров. Компьютеры пронумерованы от 1 до N. Никакая пара не встречается дважды, и никакой кабель не соединяет компьютер с самим собой.

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

Выходной файл должен содержать N строк. Строка с номером i должна содержать координаты i-го компьютера, разделенные пробелом. Сначала выводится координата x, затем y. Разрешается вывести любой вариант размещения компьютеров, при котором выполняются условия 1–5.

Примечания

Решения, корректно работающие при отсутствии циклов, будут оцениваться из 40 баллов.

Решения, корректно работающие при наличии только одного цикла, будут оцениваться из 60 баллов.

Пример входных и выходных данных

Ввод

 Вывод

13 14

11 12

11 13

1 3

3 5

5 8

8 9

8 6

6 3

4 6

4 2

6 10

10 11

10 7

7 4

1 0

3 0

1 1

3 1

0 2

2 2

4 2

1 3

1 4

3 3

3 4

2 5

4 5


#1928
Производство деталей
  
ограничение по времени на тест
4.0 second;
ограничение по памяти на тест
64 megabytes

Предприятие «Авто-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
Входные данные
2
2 3
1 2
0
Выходные данные
5 2
2 1
Входные данные
4
2 3 4 5
2 3 2
1 3
0
2 1 3
Выходные данные
9 3
3 2 1
Страница: 1 2 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест