---> 91 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 3 4 5 6 7 8 9 >> Отображать по:
ограничение по времени на тест
0.0 second;
ограничение по памяти на тест
0 megabytes

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

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

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

На вход сначала подается число n — количество ульев ($1 \leq n \leq 200$).

Введем координаты так, что дом Бена будет располагаться в точке (0, 0). В следующих $n$ строках входных данных записаны координаты ульев в саду Бена. Они не превосходят $10000$ по абсолютному значению. Никакие два улья не совпадают, и нет ульев, расположенных в точке (0, 0). Будем считать, что они пронумерованы от $1$ до $n$.

Следующие $n$ строк описывают дорожки — каждая дорожка описывается номерами объектов, которые она соединяет. Дом Бена имеет номер 0.

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

Выведите два числа — номера объектов, которые надо соединить дополнительной дорожкой. Если требуемой прямой дорожки, сокращающей общий путь Бена не существует, то выведите –1.

Примеры
Входные данные
3
1 0
1 1
0 1
0 2
1 2
1 3
Выходные данные
0 3
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

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

Разрешается в некоторых квадратах построить водостоки. Когда на каком-то квадрате строят водосток, то вся вода, которая раньше скапливалась в этом квадрате, будет утекать в водосток.

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

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

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

Во входном файле записаны сначала числа N и M, задающие размеры карты — натуральные числа, не превышающие 100. Далее идет N строк, по M чисел в каждой, задающих высоту квадратов карты над уровнем моря. Высота задается натуральным числом, не превышающим 10000. Считается, что квадраты, расположенные за пределами карты, имеют высоту 10001 (то есть вода никогда не утекает за пределы карты).

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

В выходной файл выведите минимальное количество водостоков, которое необходимо построить.

Примеры
Входные данные
4 4
1 2 4 1
2 4 4 4
1 4 3 2
1 2 3 2
Выходные данные
4
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes
Программа выводит номера посещенной вершины графа после вызова обхода в глубину. По результатам работы этой программы требуется восстановить граф и вывести его в виде списка ребер.

Недавно на кружке по программированию Петя узнал об обходе в глубину. Обход в глубину используется во многих алгоритмах на графах. Петя сразу же реализовал обход в глубину на своих любимых языках программирования Паскале и Си.

Паскаль

Си

var

   a: array [1..maxn, 1..maxn] of boolean;

  visited: array [1..maxn] of boolean;

 

procedure dfs(v: integer);

var

   i: integer;

begin

   writeln(v);

   visited[v] := true;

   for i := 1 to n do begin

     if a[v][i] and not visited[i] then begin

       dfs(i);

       writeln(v);

     end;

   end;

end;

 

procedure graph_dfs;

var

   i: integer;

begin

   for i := 1 to n do

     if not visited[i] then

       dfs(i);

end;

int a[maxn + 1][maxn + 1];

int visited[maxn + 1];

 

void dfs(int v) {

   printf("%d\n", v);

   visited[v] = 1;

   for (int i = 1; i <= n; i++) {

     if ((a[v][i] != 0) && (visited[i] == 0)) {

       dfs(i);

       printf("%d\n", v);

     }

   }

}

 

void graph_dfs() {

   for (int i = 1; i <= n; i++) {

     if (visited[i] == 0) {

       dfs(i);

     }

  }

}

Петина программа хранит граф с использованием матрицы смежности в массиве a (вершины графа пронумерованы от 1 до n). В массиве visited помечается, в каких вершинах обход в глубину уже побывал.

Петя запустил процедуру graph_dfs для некоторого неориентированного графа G с n вершинами и сохранил ее вывод. А вот сам граф потерялся. Теперь Пете интересно, какое максимальное количество ребер могло быть в графе G. Помогите ему выяснить это!

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

Первая строка входного файла содержит два целых числа: n и l количество вершин в графе и количество чисел в выведенной последовательности (1 ≤ n ≤ 300, 1 ≤ l ≤ 2n − 1). Следующие l строк по одному числу вывод Петиной программы. Гарантируется, что существует хотя бы один граф, запуск программы Пети на котором приводит к приведенному во входном файле выводу.

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

На первой строке выходного файла выведите одно число m максимальное возможное количество ребер в графе.

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

Примеры
Входные данные
6 10
1
2
3
2
4
2
1
5
6
5
Выходные данные
6
1 2
1 3
1 4
2 3
2 4
5 6
ограничение по времени на тест
0.0 second;
ограничение по памяти на тест
0 megabytes

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

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

Во входном файле записано сначала число N — количество городов (1≤N≤1000). Затем записано число M — количество дорог (1≤M≤100000). Далее идет M пар чисел, задающих дороги (каждая дорога описывается номерами городов, которые она соединяет). Не бывает дорог из некоторого города в тот же город. Между двумя городами может быть несколько дорог. Гарантируется, что до введения одностороннего движения можно было попасть из любого города в любой другой.

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

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

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

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

На шахматный турнир в Нью-Васюках съехалось 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

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