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

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

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

В первой строке входных данных содержатся два числа: N и S (1 ≤ N ≤ 100; 1 ≤ SN), где N – количество вершин графа, а S – заданная вершина. В следующих N строках записано по N чисел – матрица смежности графа, в которой 0 означает отсутствие ребра между вершинами, а 1 – его наличие. Гарантируется, что на главной диагонали матрицы всегда стоят нули.

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

Выведите одно целое число – искомое количество вершин.

Примеры
Входные данные
3 1
0 1 1
1 0 0
1 0 0
Выходные данные
3
ограничение по времени на тест
0.0 second;
ограничение по памяти на тест
0 megabytes
Максимальное время работы на одном тесте: 5 секунд

В галактике "Milky Way" на планете "Neptune" есть N городов, некоторые из которых соединены дорогами. Император "Maximus" галактики "Milky Way" решил провести инвентаризацию дорог на планете "Neptune". Но, как оказалось, он не силен в математике, поэтому он просит вас сосчитать количество дорог.

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

В первой строке  задается число N (0 ≤ N ≤ 100). В следующих N строках содержится по N чисел, каждое из которых является единичкой или ноликом. Причем, если в позиции (i,j) квадратной матрицы стоит единичка, то i-ый и j-ый города соединены дорогами, а если нолик, то не соединены.

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

Выведите одно число – количество дорог на планете "Neptune".

Примеры
Входные данные
5
0 1 0 0 0 
1 0 1 1 0 
0 1 0 0 0 
0 1 0 0 0 
0 0 0 0 0 
Выходные данные
3
ограничение по времени на тест
0.0 second;
ограничение по памяти на тест
0 megabytes
Максимальное время работы на одном тесте: 5 секунд

В подземелье M тоннелей и N перекрестков, каждый тоннель соединяет какие-то два перекрестка. Мышиный король решил поставить по светофору в каждом тоннеле перед каждым перекрестком. Напишите программу, которая посчитает, сколько светофоров должно быть установлено на каждом из перекрестков. Перекрестки пронумерованы числами от 1 до N.

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

Первая строка входных данных содержит два числа N и M (0 < N ≤ 100, 0 ≤ MN*(N – 1)/2). В каждой из следующих M строк записаны по два числа i и j (1 ≤ i,jN), которые означают, что перекрестки i и j соединены тоннелем.

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

Требуется вывести N чисел: k-ое число означает количество светофоров на k-ом перекрестке.

Примечание. Можно считать, что любые два перекрестка соединены не более, чем одним тоннелем. Нет тоннелей от перекрестка i до него самого.

Примеры
Входные данные
7 10
5 1
3 2
7 1
5 2
7 4
6 5
6 4
7 5
2 1
5 3
Выходные данные
3 3 2 2 5 2 3 
ограничение по времени на тест
0.0 second;
ограничение по памяти на тест
0 megabytes
Максимальное время работы на одном тесте: 5 секунд

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

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

В  первой строке входных данных содержится число N (0 < N ≤ 100) – количество холмов. Далее идет матрица смежности, описывающая наличие мостов между холмами (1 – мост есть, 0 – нет). После матрицы смежности идёт пустая строка, и в последней строке записано N чисел, обозначающих цвет холмов: 1 – красный; 2 – синий; 3 – зеленый.

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

Выведите одно число – количество "плохих" мостов.

Примеры
Входные данные
7
0 1 0 0 0 1 1 
1 0 1 0 0 0 0 
0 1 0 0 1 1 0 
0 0 0 0 0 0 0 
0 0 1 0 0 1 0 
1 0 1 0 1 0 0 
1 0 0 0 0 0 0 

1 1 1 1 1 3 3 
Выходные данные
4
ограничение по времени на тест
0.0 second;
ограничение по памяти на тест
0 megabytes
Максимальное время работы на одном тесте: 1 секунда

Штирлиц ехал на машине, увидел голосующего Бормана, и проехал мимо. Через некоторое время он снова увидел голосующего Бормана, и снова проехал мимо. Вскоре он опять увидел голосующего Бормана.
 - Издевается! - подумал Борман.
 - Кольцевая! - догадался Штирлиц.

В городе N площадей. Любые две площади соединены между собой ровно одной дорогой с двусторонним движением. В этом городе живет Штирлиц. У Штирлица есть хобби - он любит воскресным утром выйти из дома, сесть в машину, выбрать какой-нибудь кольцевой маршрут, проходящий ровно по трем площадям (то есть сначала он едет с какой-то площади на какую-то другую, потом - на третью, затем возвращается на начальную, и опять едет по этому маршруту). Он воображает, что где-то на этом пути стоит Борман. И так вот ездит Штирлиц все воскресенье, пока голова не закружится, и радуется...

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

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

В первой строке задается  число N (3 <= N <= 100). В последующих строках содержится матрица NxN расстояний между площадями (число в позиции i,j обозначает длину дороги, соединяющей i-ую и j-ую площади). Все числа в матрице (кроме стоящих на главной диагонали) - натуральные, не превышающие 1000. Матрица симметрична относительно главной диагонали, на главной диагонали стоят 0.

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

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

Примеры
Входные данные
5
0 1 9 9 2
1 0 9 9 9
9 9 0 9 9
9 9 9 0 9
2 9 9 9 0
Выходные данные
1 2 5

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