Темы --> Информатика --> Алгоритмы
    Задачи на моделирование(78 задач)
    Арифметические алгоритмы(240 задач)
    Алгоритмы поиска(155 задач)
    Алгоритмы сортировки(194 задач)
    Динамическое программирование(355 задач)
    Алгоритмы на графах(319 задач)
    Перебор(154 задач)
    Игры и выигрышные стратегии(33 задач)
    Вычислительная геометрия(216 задач)
    Эвристические методы(30 задач)
    Алгоритмы на строках(45 задач)
    Пересечение множеств(10 задач)
    Жадный алгоритм(71 задач)
    Теория расписаний(5 задач)
    Обработка текста(31 задач)
    Дата и время(14 задач)
---> 1657 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 263 264 265 266 267 268 269 >> Отображать по:
#111527
Туда и обратно
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

В сказочной стране, столицей которой является Изумрудный Город, всего N городов. Некоторые города соединены дорогой, целиком вымощеной желтым кирпичем. Элли нужно добраться из города на границе в Изумрудный Город и затем вернуться обратно. Чтобы не было скучно, ей хочется добираться туда и обратно разным маршрутом (а именно так, чтобы ни одна из дорог не была и на маршруте туда и на маршруте обратно). Поскольку зря тратить время она не собирается, то для каждого пути она хочет выбрать самый короткий вариант.

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

Все города пронумерованы натуральными числами от 1 до N, город на границе имеет номер K, Изумрудный Город имеет номер N.

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

В первой строке содержатся три числа: N, K и M (1 ≤ N ≤ 100, 1 ≤ K < N, ), где N -– количество городов в Сказочной стране, K – номер города, из которого Элли начинает путешествие, M – количество дорог, мощеных желтым кирпичем. В следующих M строках вводятся по три числа – номера городов, соединенных дорогой из желтого кирпича и длина этой дороги.

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

В первой строке выведите -1, если желание Элли неосуществимо. В противном случае в первой строке выведите два числа: длину пути туда и длину пути обратно, а в следующих двух строках: номера городов на пути туда и на пути обратно в том порядке, в котором она будет их проходить.

Примеры тестов

Входные данные
4 1 6
1 4 3
2 4 2
2 3 1
1 2 5
1 3 6
4 3 8
Выходные данные
3 7
1 4 
4 2 1
Входные данные
4 1 0
Выходные данные
-1

#111528
Шоколад
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

В целях увеличения продаж фирма "Новый русский шоколад" приняла решение разбивать каждую плитку на дольки в форме прямоугольников 1 × 2 и уголков (квадрат 2 × 2 с вырезанной угловой клеткой), а не на скучные квадратики 1 × 1. При этом долек другой формы на плитке шоколада быть не должно. Через некоторое время узор на плитке будет меняться на другой (но по-прежнему состоящий только из прямоугольников 1 × 2 и уголков), через некоторое время – еще на другой и так далее. Директору фирмы "Новый русский шоколад" захотелось узнать, а сколько всего существует способов разбить плитку шоколада на такие дольки? Помогите ему найти ответ.

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

В одной строке вводятся два натуральных числа n и m – ширина и длина плитки (1 ≤ n, m ≤ 9).

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

Выведите одно целое число – количество способов разбить плитку шоколада размером n × m на прямоугольники 1 × 2 и уголки (и прямоугольник и уголок можно поворачивать, долек другой формы на плитке быть не должно).

Примеры тестов

Входные данные
2 3
Выходные данные
5
Входные данные
3 3
Выходные данные
8

#111529
простое ЕГЭ
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

С целью упрощения ЕГЭ по литературе, было решено оставить в нем вопросы только с ответами «да» или «нет». Бланк ответов представляет клетчатое поле из N строк и M столбцов, в котором каждая клеточка соответствует своему вопросу. Ученику необходимо один раз перечеркнуть по диагонали те клеточки, которые, по его мнению, соответствуют вопросам с ответом «нет» (перечеркивать можно по любой из двух диагоналей). При этом во избежание ошибок при сканировании, никакие две диагонали не должны "сливаться", то есть иметь общий конец.

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

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

Даны два натуральных числа - количество строк N и количество столбцов M. Количество вопросов в варианте не превосходит 100, то есть 1 ≤ N·M ≤ 100.

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

Выведите одно число – максимальное количество вопросов с ответом «нет», которое можно включить в вариант.

Примеры тестов

Входные данные
1 2
Выходные данные
2
Входные данные
3 3
Выходные данные
6

#111540
Компоненты связности
  
ограничение по времени на тест
3.0 second;
ограничение по памяти на тест
256 megabytes

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

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

Во входном файле записано два числа \(N\) и \(M\) (0 < \(N\) ≤ 100000, 0 ≤ \(M\) ≤ 100000). В следующих \(M\) строках записаны по два числа \(i\) и \(j\) (1 ≤ \(i\), \(j\) ≤ \(N\)), которые означают, что вершины \(i\) и \(j\) соединены ребром.

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

В первой строчке выходного файла выведите количество компонент связности. Далее выведите сами компоненты связности в следующем формате: в первой строке количество вершин в компоненте, во второй - сами вершины в произвольном порядке.

Примеры
Входные данные
6 4
3 1
1 2
5 4
2 3
Выходные данные
3
3
1 2 3 
2
4 5 
1
6
#111541
Баобаб
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

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

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

В первой строке входного файла содержится одно натуральное число \(N\) (\(N\) ≤ 100) - количество вершин в графе. Далее в \(N\) строках по \(N\) чисел - матрица смежности графа: в \(i\)-ой строке на \(j\)-ом месте стоит 1, если вершины \(i\) и \(j\) соединены ребром, и 0, если ребра между ними нет. На главной диагонали матрицы стоят нули. Матрица симметрична относительно главной диагонали.

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

Вывести "YES", если граф является деревом, и "NO" иначе.

Примеры
Входные данные
6
0 1 1 0 0 0
1 0 1 0 0 0
1 1 0 0 0 0
0 0 0 0 1 0
0 0 0 1 0 0
0 0 0 0 0 0
Выходные данные
NO
Входные данные
3
0 1 0
1 0 1
0 1 0
Выходные данные
YES
Страница: << 263 264 265 266 267 268 269 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест