Темы --> Информатика --> Алгоритмы --> Алгоритмы на графах --> Кратчайшие пути в графе --> Обход в ширину
    0-1 BFS(3 задач)
---> 20 задач <---
Источники --> Личные олимпиады
    Олимпиады сайта(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 >> Отображать по:
#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
#1653
Бусинки
  
ограничение по времени на тест
0.3 second;
ограничение по памяти на тест
64 megabytes

Маленький мальчик делает бусы. У него есть много пронумерованных бусинок. Каждая бусинка имеет уникальный номер – целое число в диапазоне от 1 до N. Он выкладывает все бусинки на полу и соединяет бусинки между собой произвольным образом так, что замкнутых фигур не образуется. Каждая из бусинок при этом оказывается соединенной с какой-либо другой бусинкой.
Требуется определить, какое максимальное количество последовательно соединенных бусинок присутствует в полученной фигуре (на рисунке эти бусинки выделены темным цветом).

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

В первой строке – количество бусинок 1≤N≤2500. В последующих N-1 строках по два целых числа – номера, соединенных бусинок.

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

Вывести одно число – искомое количество бусинок.

Пример

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

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

7

4 5

6 7

7 4

7 2

1 3

4 1

5
#1668
Блохи
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Блохи сидят на клетках шахматного поля и ходят конем. Должны собраться в одной из клеток. Определить сумму длин кратчайших путей.

На клеточном поле, размером \(N\)x\(M\) (2 ≤ \(N\), \(M\) ≤ 250) сидит \(Q\) (0 ≤ \(Q\) ≤ 10000) блох в различных клетках. "Прием пищи" блохами возможен только в кормушке - одна из клеток поля, заранее известная. Блохи перемещаются по полю странным образом, а именно, прыжками, совпадающими с ходом обыкновенного шахматного коня. Длина пути каждой блохи до кормушки определяется как количество прыжков. Определить минимальное значение суммы длин путей блох до кормушки или, если собраться блохам у кормушки невозможно, то сообщить об этом. Сбор невозможен, если хотя бы одна из блох не может попасть к кормушке.

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

В первой строке входного файла находится 5 чисел, разделенных пробелом: \(N\), \(M\), \(S\), \(T\), \(Q\). \(N\), \(M\) - размеры доски (отсчет начинается с 1); \(S\), \(T\) - координаты клетки - кормушки (номер строки и столбца соответственно), \(Q\) - количество блох на доске. И далее \(Q\) строк по два числа - координаты каждой блохи.

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

Содержит одно число - минимальное значение суммы длин путей или -1, если сбор невозможен.

Примеры
Входные данные
2 2 1 1 1
2 2
Выходные данные
-1
#1748
Задача из ЕГЭ
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Вася, решая задачи демо-версии ЕГЭ, дошел до задачи B5, которая звучит так.

«У исполнителя Калькулятор две команды:

· прибавь 3

· умножь на 4

Выполняя первую из них, Калькулятор прибавляет к числу на экране 3, а выполняя вторую, умножает его на 4.»

Далее в задаче требовалось получить из числа 3 число 57 не более, чем за 6 команд. Однако Вася заинтересовался, как можно для произвольных чисел \(a\) и \(b\) построить программу наименьшей длины получения числа \(b\) из числа \(a\).

Напишите программу, которая по заданным числам \(a\) и \(b\) вычислит наименьшее количество команд Калькулятора, которое нужно, чтобы получить из \(a\) число \(b\).

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

Вводятся два натуральных числа, не превышающих 1000 — \(a\) и \(b\).

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

Выведите наименьшее число команд, которое нужно, чтобы получить из \(a\) число \(b\). Если число \(b\) получить нельзя, выведите –1 (минус 1).

Примеры
Входные данные
3 57
Выходные данные
5
Входные данные
43 57
Выходные данные
-1
Входные данные
10 10
Выходные данные
0
#1939
Эвакуация
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

Сначала вводятся два натуральных числа \(N\), \(K\) (\(1\) ≤ \(N\) ≤ 100000, \(1\) ≤ \(K\) ≤ \(N\)) — количество бункеров и количество выходов соответственно.

Далее через пробел записаны \(K\) различных чисел от \(1\) до \(N\), обозначающих номера бункеров, в которых расположены выходы.

Потом идёт число \(M\) (1 ≤ \(M\) ≤ 100000) — количество туннелей. Далее вводятся M пар чисел – номера бункеров, соединенных туннелем. По каждому из туннелей можно двигаться в обе стороны. В организации не существует туннелей, ведущих из бункера в самого себя, зато может существовать более одного туннеля между парой бункеров.

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

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

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