Темы --> Информатика --> Алгоритмы --> Алгоритмы на графах
    Кратчайшие пути в графе(116 задач)
    Обход в глубину(100 задач)
    Способы задания графа(54 задач)
    Минимальный каркас(12 задач)
    Потоки(21 задач)
    Паросочетания(17 задач)
    Эйлеров цикл(9 задач)
    Деревья(16 задач)
---> 74 задач <---
Источники --> Личные олимпиады
    Олимпиады сайта(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 задач)
Страница: << 3 4 5 6 7 8 9 >> Отображать по:
#1316
Школы
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Во взвешенном графе необходимо найти два минимальных остовных дерева.

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

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

Известна стоимость соединения между некоторыми парами школ. Мэр города решил выбрать одну из двух наиболее экономичных схем электроснабжения (стоимость схемы равняется сумме стоимостей соединений пар школ).

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

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

В первой строке входного файла находятся два натуральных числа, разделенных пробелом:N (3 ≤ N ≤ 100), количество школ в городе, и M – количество возможных соединений между ними. В каждой из последующих M строк находятся по три числа: Ai, Bi, Ci, разделенных пробелами, где Ci – стоимость прокладки линии электроснабжения (1 ≤ Ci ≤ 300) от школы Ai до школы Bi (i=1,2,…,N).

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

В единственной строке выходного файла должны содержаться два натуральных числа S1 и S2, разделенных пробелом – две наименьшие стоимости схем (S1 ≤ S2). S1=S2 тогда и только тогда, когда существует несколько схем надежного электроснабжения наименьшей стоимости.

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

Примеры
Входные данные
5 8
1 3 75
3 4 51
2 4 19
3 2 95
2 5 42
5 4 31
1 2 9
3 5 66
Выходные данные
110 121
#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


#1355
Векторы
  

На плоскости задано множество точек (x, y), где x, y – целые числа, 1≤x≤M, 1≤y≤N. Из каждой точки выходит ровно один из следующих векторов: (-1,-1), (-1,0), (-1,1), (0,1), (1,1), (1,0), (1,-1), (0,-1). Каждый вектор соединяет одну целочисленную точку плоскости с другой. Например, если из точке (2, 5) выходит вектор (1, 1), то он соединяет эту точку с (3, 6), но не наоборот.

Последовательность из двух и более точек плоскости a1, a2,…, ak назовем циклом, если каждая точка ai соединена вектором с ai+1 (1≤i≤k-1), и ak соединена вектором с a1. Циклы считаются разными если они отличаются хотя бы одной вершиной.

Напишите программу, которая по информации о векторах, выходящих из точек плоскости, находит количество различных циклов.

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

Первая строка входного файла содержит два целых числа N (1≤N≤100) и M (1≤M≤100). Каждая из последующих N строк, содержит M пар чисел (т.е. 2≤M чисел). Пара x, которая находится в строке y, задает вектор в точке (x, y).

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

Единственная строка выходного файла должна содержать целое число – количество циклов, образованных векторами.

Примеры
Входные данные
2 4 
-1 1 -1 1 -1 0 0 1
1 0 1 0 0 -1 0 -1
Выходные данные
2
#1386
Праздничные открытки
  

Петя с Васей решили поздравить всех своих одноклассниц с Международным Женским Днем. Важной частью любого праздника являются открытки. Купив их достаточно, друзья сели писать пожелания. Подписанные открытки они складывали на специальный стол, расчерченный в квадратную клетку параллельно краям стола так, что длина и ширина его составляли N и M клеток соответственно. По удивительному совпадению каждая открытка была размером точь-в-точь с две клетки стола. Петя настоял на том, чтобы класть подписанные поздравления строго по линиям сетки — горизонтально или вертикально, накрывая одной открыткой ровно две клетки.

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

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

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

В первой строке входного файла записаны два целых числа N и M (1 ≤ N, M ≤ 700) — длина и ширина стола. Гарантируется, что хотя бы одно из N, M четное. Будем считать, что все открытки занумерованы числами от 1 до NM. Следующие 2N строк содержат по M чисел: первые N строк описывают нижний слой, следующие N строк — верхний слой. Число k в i-й строке j-м столбце нижнего или верхнего слоя означает наличие на этой позиции одной из половинок открытки номер k.

Гарантируется, что входные данные корректны, то есть что каждое число 1 до NM встречается ровно два раза, и эти вхождения находятся на соседних позициях, при этом они могут находиться как в одном слое, так и в разных. Кроме того, если две открытки покрывают одни и те же клетки, то одна из них находится обеими половинками снизу, а другая — сверху.

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

В выходной файл запишите единственное слово NO, если не существует способа извлечь половину открыток нужным образом. В противном случае в первую строку выведите YES, во вторую — последовательность из NM/2 номеров открыток, которые надо достать, в правильном порядке. У каждой из них на момент извлечения хотя бы одна из половинок должна находиться сверху. Если искомых последовательностей несколько, выведите любую из них.

Частичные ограничения

Первая группа состоит из тестов, в которых произведение NM ≤ 24.

Вторая группа состоит из тестов, в которых N, M ≤ 100.

Примеры
Входные данные
2 2
1 1
3 2
4 2
4 3
Выходные данные
YES
4
2
Входные данные
2 3
1 1 4
2 3 4
2 6 5
3 6 5
Выходные данные
YES
2
6
5
#1637
Домино
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

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

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

В первой строке входного файла содержится одно целое число \(M\) (0≤\(M\)≤100), которое соответствует максимально возможному количеству точек на половинке костяшки. Во второй строке записано одно целое число \(N\), равное количеству костяшек, удаленных из полного набора. Каждая \(і\)-я из последующих \(N\) строк содержит по два числа \(A_i\) и \(B_і\). Это количества точек на половинках \(i\)-й удалённой костяшки.

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

Единственная строка выходного файла должна содержать одно целое число \(L\) – минимальное количество цепочек.

Примеры
Входные данные
7
2
7 5
3 4
Выходные данные
2
Страница: << 3 4 5 6 7 8 9 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест