День 4. Старшая группа


Чтобы посмотреть этот PDF файл с форматированием и разметкой, скачайте его и откройте на своем компьютере.
HD0401. Обход в глубину


Дан неориентированный невзвешенный граф. Для него вам необходимо найти количество вершин,


лежащих в одной компоненте связности с данной вершиной.

Формат входных данных


В первой строке заданы два числа: N и S (1 <= N <= 100; 1 <= S

<= N), где N
-

количество


вершин графа, а S
-

заданная вершина. В следующих N строках записано по N чисел
-


матрица смежности графа, в которой 0 означает отсутствие ребра между вершинами,


а 1
-

его наличие. Гарантируется, то на главной диагонали матриц
ы всегда стоят


всегда нули.

Формат выходных данных


Вывести одно целое число
-

искомое количество.

Пример:

Ввод

Вывод

3 1


0 1 0


1 0 0


0 0 0

2


HD0402. Путь


В неориентированном графе требуется найти минимальный путь между двумя вершинами.

Формат входных данных


В первой строке записано сначала число N
-

количество вершин в графе (1<=N<=100).


Затем записана матрица смежности (0 обозначает отсутствие ребра, 1
-

наличие ребра).


Затем записаны номера двух вершин
-

начальной и конечной.

Формат

выходных данных


В выходной файл выведите сначала L
-

длину кратчайшего пути (количество ребер,


которые нужно пройти), а затем L+1 число
-

путь от одной вершины до другой,


заданный своими вершинами. Если пути не существует, выведите одно число
-
1.

Приме
р:

Ввод

Вывод

5


0 1 0 0 1


1 0 1 0 0


0 1 0 0 0


0 0 0 0 0


1 0 0 0 0


3 5

3


3 2 1 5




HD0403. Дерево?


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


является ли этот граф деревом.

Формат входных данных


Cначала записано число N
-

количество вершин графа (от 1 до 100). Далее записана матрица


смежности размером N*N, в которой 1 обозначает наличие ребра, 0
-

его отсутствие.


Матрица симметрична относительно главной диагонали.

Формат в
ыходных данных


Выведите сообщение YES, если граф является деревом, и NO в противном случае

Пример:

Ввод

Вывод

3


0 1 0


1 0 1


0 1 0

YES


HD0404. Получи дерево


Дан связный неориентированный граф без петель и кратных ребер. Разрешается удалять из него


ребра. Требуется получить дерево.

Формат входных данных


Заданы два числа
-

N (от 1 до 100) и M
-

количество вершин и ребер графа соответственно.


Далее идет M пар чисел, задающих ребра. Гарантируется, что граф связный.

Формат выходных данных


Выведите N
-
1 пару чисел
-

ребра, которые войдут в дерево. Ребра можно выводить в любом порядке.

Пример:

Ввод

Вывод

4 4


1 2


2 3


3 4


4 1

1 2


2 3


3 4


HD0405. Один конь


На шахматной доске NxN в клетке (x1,y1) стоит голодный шахматный конь. Он хочет попасть


в клетку (x2,y2), где растет вкусная шахматная трава. Какое наименьшее количество


ходов он должен для этого сделать?

Формат входных данных


Входной поток содержит пять чисел: N,x1,y1,x2,y2 (5 <= N <= 20, 1 <= x1,y1,x2,y2 <= N).


Левая верхняя клетка доски имеет координаты (1,1), правая нижняя
-

(N,N).

Формат выходных данных


Первая строка должна содержать единственное число K
-

наименьшее необ
ходимое число


ходов коня. В каждой из следующих K+1 строк должно быть записано 2 числа
-

координаты


очередной клетки в пути коня.

Пример:

Ввод

Вывод

5


1 1


3 1

2


1 1


2 3


3 1


HD0406. Трискаидекадомино


Каждые 13 лет в тринадцатой системы Центавра на тринадцатой планете решается судьба вселенной.
Представители нашей вселенной сражаются в беспощадной битве с представителями тринадцатой
параллельной вселенной. На этих соревнованиях нашу вселенную представля
ют великие умы из созвездия
Гиагинской Евгений и Сергей. Для победы нашим героям необходимо сыграть в трискаидекадомино.
Участникам выдали N доминошек, на которых нанесены числа от 1 до 13. Евгений и Сергей должны выложить
эти доминошки в несколько рядов,
но если вражеская сборная сможет выложить доминошки в меньшее
количество рядов, то вселенная будет повержена. Доминошки разрешается класть рядом, если на
соприкасающихся гранях нанесены одинаковые числа. Найдите минимальное количество рядов, в которые
можн
о выложить данный набор доминошек. Доминошки могут повторяться.

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

В первой строке дано число N(1≤N≤1000)


количество доминошек. В следующих N строках идет описание
доминошек: по два числа в строке


номера на домимношках.

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

Выве
дите единственное число


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

Пример

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

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

7

1 5

2 5

2 7

5 7

13 10

13 12

6 12

2




HD0407. Банкет


На банкет были приглашены N Очень Важных Персон (ОВП). Были поставлены 2 стола. Столы


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


заключается в том, что некоторые ОВП не ладят друг с другом и не могут сидеть за одним


столом. Вас попросили определить, возможно ли всех ОВП рассадить за двумя столами.

Формат входных данных


В первой строке дано два числа: N и M (1 <= N,M <= 100), где N

-

количество ОВП,


а M
-

количество пар ОВП, которые не могут сидеть за одним столом.


В следующих M строках записано по 2 числа
-

пары ОВП, которые не могут сидеть за одним


столом.

Формат выходных данных


Если способ рассадить ОВП существует, то выведит
е YES в первой строке и номера ОВП,


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


в первой и единственной строке выведите NO.

Пример:

Ввод

Вывод

3 2


1 2


1 3

YES


2 3


HD0408. Вирусы


На поле размером

N
*
N

расположено

M

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


Ввод

В первой строке запи
саны два числа

N

(1 ≤

N

≤ 100) и

M

(1 ≤

M

≤ 10). Каждая из следующих

M

строк
содержит по два числа
-

координаты вируса на поле. Все числа целые, координаты по величине не
превосходят размеров поля. Левая нижняя клетка поля имеет координаты (1, 1).

Вывод

В
первую и единственную строку выведите одно число
-

искомое наименьшее количество ходов.


Ввод 1

Ввод 2

2 1

2 1

58 4

46 22

20 26

38 30

23 37

Вывод 1

Вывод 2

2

48




HD0409. Занятие 13
-
го марта


13 марта, на занятиях по программированию Миша рассказывал что
-
то о графах. Он просил обратить
внимание на следующую задачу: «Пусть дан неориентированный граф c N вершинами, где каждое ребро
имеет вес 0 или 1. Найти кратчайшее расстояние от вершины 1 до ве
ршины N» . Все были так увлечены
программированием, что никто не обратил внимание. Теперь Миша просит не только обратить внимание, но и
решить эту задачу.

Исходные данные

Первая строка содержит два числа N(2≤N≤10000) и M(0≤M≤100000), где N


число вершин в

графе, а M


число вершин в графе. В следующих M строках находится по три числа u,v и s, которые описывают ребра. u и
v(1≤ u,v ≤N)


соединяемые вершины. s


вес ребра(0 или 1).

Результат

Выведите единственное число


кратчайшее расстояние от вершины 1 до

вершины N. Если кратчайшего
расстояния нет


вывести
-
1.

Пример

исходные данные

результат

5 6

1 2 1

1 3 0

1 4 1

2 5 1

2 3 0

4 5 1

1


HD0410. Ралли


Миша не очень любит компьютерные игры, но в игру "Ралли" он играет с удовольствием. Игра происходит на
поле из NxM квадратиков. Необходимо проехать из клетки с координатами (1,1) в клетку с координатами
(N,M) за минимальное количество шагов. Перемещаться м
ожно только в соседние по горизонтали или
вертикали клетки. При этом на игровом поле есть непроходимые места, на которые заезжать нельзя.
Казалось бы, простая задача. Но ведь вы знаете, что машина не ездят на воздухе, им нужен бензин. У нашей
машины бак об
ъемом K литров, стартует она с полным баком. Конечно, не всегда можно добраться с K
литрами бензина до финиша, но в некоторых клетках есть заправочные станции, которые заливают 5 литров
бензина в бак. Заправка 5
-
ти литров происходит в тот момент, когда вы
заехали на клетку с заправкой.
Заправляться на одной и той же заправке можно неограниченное количество раз. Но запомните, что каждый
ход машина должна перемещаться на одну клетку. И естественно, нельзя залить бензина больше, чем объем
бака. Ваша программа
должна найти минимальное количество шагов, которые должен сделать игрок для
проезда из клетки (1,1) в клетку (N,M). Если проехать не получится, то выведите "
-
1".

У карты следующая легенда:

"*"
-

область, в которой можно ездить;

"#"
-

область, в которой нел
ьзя ездить;

"X"
-

область, в которой заливается 5 литров бензина.

Формат входных данных.


В первой строке находится три числа: N(1находится карта игры, в каждой строке по M символов.

Формат выходных д
анных.


В единственнй строке вывести "
-
1", если нельзя проехать до места назначения. Если проехать можно, то
выведите количество ходов, которое нужно сделать.

Примеры

Ввод

Вывод

9 5 2

**X**

*****

**X**

*****

X*X**

*****

X****

*****

X*X**

16

5 5 1

*XX**

**XX*

***X*

**###

*****

-
1



Приложенные файлы

  • pdf 26690910
    Размер файла: 327 kB Загрузок: 0

Добавить комментарий