Темы --> Информатика --> Алгоритмы --> Алгоритмы на графах --> Обход в глубину
    Компоненты сильной связности(3 задач)
    Мосты(2 задач)
    Применение обхода в глубину(3 задач)
    Топологическая сортировка(2 задач)
    Точки сочленения(1 задач)
---> 33 задач <---
Источники --> Личные олимпиады
    Олимпиады сайта(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 задач)
Страница: 1 2 3 4 5 6 7 >> Отображать по:
#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
#487
Монополия
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

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

В результате небольшого исследования Иванушка установил, между какими компаниями существует взаимное доверие (причем всегда если компания доверяет компании B, то компания B доверяет компании A).

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

Напишите программу, которая определит, какое максимальное число компаний может объединить Иванушка под своим началом.

Будем считать, что Иванушка — честный предприниматель и он никогда не подтасовывает рассылаемые им списки.

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

В первой строке входных данных содержится число N — количество фирм (1≤N≤2000). Далее идут N чисел, описывающих ответ фирмы на первое предложение Иванушки (1 — согласие, 0 — отказ). Далее задается число M (0≤M≤200000) — количество пар компаний, между которыми существует доверие. Далее следуют M пар чисел, задающих номера фирм, между которыми существует взаимное доверие (числа в паре не могут быть одинаковыми). Любая пара компаний упоминается в этом списке не более одного раза.

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

Выведите  одно число — максимальное число фирм, которое сможет купить Иванушка.

Примеры
Входные данные
7
1 0 0 0 0 0 1
6
1 2
1 3
1 4
4 5
5 6
2 5
Выходные данные
4
Входные данные
3
0 0 0
0
Выходные данные
0
#493
Формула - 3
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Топологическая сортировка

В ежегодном чемпионате Флатландии (которая, естественно, является плоским миром) по космическим гонкам "Формула-3" участвуют N космических скутеров, имеющие форму треугольников. До начала гонок скутеры занимают положение в стартовой зоне согласно результатам жеребьевки.

1

Скутеры стартуют строго по порядку. Каждый скутер,получив команду «старт», уезжает в положительном направлении оси Ox. Следующий скутер стартует лишь тогда, когда предыдущий покинет стартовую зону. Скутеры уезжают строго параллельно оси Ox, скутеры в стартовой зоне не поворачивают и не разворачиваются.

Естественно, что если в момент старта на пути скутера окажется другой скутер, то произойдет авария (даже если скутер заденет лишь угол другого скутера своим углом).

Для уменьшения опасности столкновения скутеров на старте строго соблюдается следующее правило: прямые, параллельные оси Ox и пересекающие какой-то скутер, должны в совокупности пересекать не более 100 других скутеров (прямая, проходящая через одну точку скутера также считается прямой, пересекающей скутер). Например, на приведенном рисунке прямые, параллельные Ox и пересекающие скутер 2, проходят через 2 других скутера (1 и 3), а прямые, проходящие через скутер 1, проходят только через один другой скутер (номер 2).

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

Помогите Главному Судье — напишите программу, которая определит какой-нибудь порядок старта скутеров, чтобы аварии не произошло.

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

В первой строке вводится натуральное число N( 1 ≤ N ≤ 30 000).

В каждой из следующих N строк содержится по 6 чисел: x1, y1, x2, y2, x3, y3 – координаты трех вершин скутера на старте, целые числа, не превосходящие по модулю 106. В начальный момент скутеры не задевают друг друга.

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

Выведите через пробел N чисел – номера скутеров в том порядке, в котором они могут стартовать. Если решений несколько, выведите одно любое из них. Если решений нет, выведите одно число -1.

Примечание: первый тест соответствует приведенному рисунку. Ответ 2 3 1 в этом тесте также является правильным

Примеры
Входные данные
3
1 19 3 9 6 15
5 6 10 2 10 12
1 1 6 1 3 7
Выходные данные
Входные данные
3
0 1 -2 1 -1 -1
5 6 10 2 10 12
1 1 6 1 3 7


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

                            
                                


                        

                    

                    

                        

                            

                                #497
                            

                            

                                Автобусы
                            

                              
                
                            

                                
                                
                            


                        

                        

                                

                                

                                    

                                        
ограничение по времени на тест

                                        1.0 second;
                                    
                                        
ограничение по памяти на тест

                                        64 megabytes
                                    

                                

                            
                            

   




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



Автобусное сообщение в столице устроено следующим образом. Есть N автобусных остановок, в частности, возле каждой станции метро расположено по остановке. Между N – 1 парой остановок постоянно курсируют автобусы, время движения от одной остановки до другой – 1 минута. Временем ожидания и пересадки можно пренебречь. Автобусное сообщение в столице организовано так, что от любой автобусной остановки до любой другой можно добраться на автобусах (возможно, с пересадками).


   


   

    

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




В первой строке входных данных содержатся два числа N и M – количество автобусных остановок и станций метро соответственно (2 ≤ N ≤ 50 000, 1 ≤ M ≤ 1 000, M < N).




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



В следующих N – 1 строках записано по два числа – номера автобусных остановок, между которыми курсирует автобус. (Автобус ходит в обоих направлениях. Каждый маршрут указан один раз.)



   


   

    

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



Выведите два числа – сначала наибольшее время за которое кто-то будет и после строительства добираться на работу, а затем номер автобусной остановки, рядом с которой следует построить новую станцию метро. (Строить можно возле тех автобусных остановок, возле которых еще нет станций метро). Если решений несколько, выведите одно из них.



Подзадачи и система оценки


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


Подзадача 1 (40 баллов)


В этой подзадаче \(N \leq 2000\)


Подзадача 2 (60 баллов)


Дополнительные ограничения отсутствуют.








                            
Примеры
Входные данные
8 2
1 2
1 2
1 3
1 4
2 5
2 6
6 7
6 8

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

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

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


                            
                                


                        

                    

                    

                        

                            

                                #556
                            

                            

                                Мехико
                            

                              
                
                            

                                
                                
                            


                        

                        

                                

                                

                                    

                                        
ограничение по времени на тест

                                        1.0 second;
                                    
                                        
ограничение по памяти на тест

                                        16 megabytes
                                    

                                

                            
                            

   

    

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



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



В какой-то момент короли городов решили упорядочить товароперевозки. Они разработали маршрут товароперевозок, который соединяет все города вокруг озера. Маршрут удовлетворяет следующим условиям:



*Он начинается в каком-либо городе, проходит через каждый прибрежный город и заканчивается в городе, отличном от того, в котором он начался.

*Маршрут проходит через каждый город ровно один раз.

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

*Маршрут состоит из отрезков прямых, каждый из которых соединяет два последовательно посещаемых города маршрута.

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






На рисунке показано озеро и города вокруг него. Тонкие и жирные линии отрезков обозначают коммерческие соглашения между городами. Жирные линии показывают маршрут грузоперевозок, начинающийся в городе 2 и заканчивающийся в городе 5.




Этот маршрут нигде не имеет самопересечений. Но если построить маршрут, идущий из города 2 в город 6, затем в город 5, а затем в город 1, то он будет неправильным, поскольку имеет самопересечения.



Города нумеруются целыми числами от 1 до \(c\) по направлению часовой стрелки.

    

   


   

    

     Задание
    

    

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

   








    

     Ограничения
    

    


3 ≤ \(c\) ≤ 1000, \(c\) – число городов вокруг озера
    

   





    

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

    

		На вход Вашей программы поступают данные в следующем формате:



СТРОКА 1: Содержит целое число \(c\).


СТРОКА 2: Содержит целое число \(n\) – количество коммерческих соглашений.


СЛЕДУЮЩИЕ \(n\) СТРОК: Каждая строка описывает одно коммерческое соглашение (одно соглашение описывается один раз). В строке задаются два целых числа, разделенных пробелами, которые соответствуют номерам городов, заключивших между собой коммерческое соглашение.
    

   



   

    

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

    

		Если возможно построить маршрут товароперевозок, выведите c строк, в каждой из которых записано целое число. Эти числа представляют собой порядок посещения городов по маршруту товароперевозок. Если невозможно построить маршрут товароперевозок, удовлетворяющий всем указанным требованиям, выведите одну строку, содержащую отрицательное целое число -1.
    


   






    

     Замечание
    

    

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


   







    

     Оценивание
    

    

		Ряд тестов с общей суммой 30 баллов будет удовлетворять следующим ограничениям:


3 ≤ \(m\) ≤ 10 

3 ≤ \(n\) ≤ 10 

    


   

 

 

                            
Примеры
Входные данные
7
9
1 4
5 1
1 7
5 6
2 3
3 4
2 6
4 6
6 7

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


                            
                                


                        

                    

                

                
        

            Страница: 
                    1
                    2
                    3
                    4
                    5
                    6
                    7
                >>
            Отображать по:
            
        

    
            

        

        
    
    

    

        

            
Выбрано
:
            
Отменить
|
            
Добавить в контест