e-olymp 982. Связность

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

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

В первой строке заданы количество вершин [latex]n[/latex] и ребер [latex]m[/latex] в графе соответственно [latex](1 \leq n \leq 100, 1 \leq m \leq 10000)[/latex]. Каждая из следующих m строк содержит по два числа [latex]u_i[/latex] и [latex]v_i[/latex] [latex](1 \leq u_i, v_i \leq n);[/latex]  каждая такая строка означает, что в графе существует ребро между вершинами [latex]u_i[/latex] и [latex]v_i[/latex].

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

Выведите «YES», если граф является связным и «NO» в противном случае.

Тесты

Тесты, взятые с e-olymp.com

Test Input Output
1 3 2
1 2
3 2
YES
2 3 1
1 3
NO

Мои тесты

Test Input Output
1 4 2
1 2
3 4
NO
2 4 5
1 2
2 1
2 4
2 4
4 2
NO
3 5 4
1 2
5 1
3 5
4 3
YES

Код программы

Алгоритм

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

Код программы

Засчитанное решение на сайте e-olymp.com

e-olymp 6127. Очередь неограниченного размера

Задача

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

push n

Добавить в очередь число n (значение n задается после команды). Программа должна вывести ok.

pop

Удалить из очереди первый элемент. Программа должна вывести его значение.

front

Программа должна вывести значение первого элемента, не удаляя его из очереди.

size

Программа должна вывести количество элементов в очереди.

clear

Программа должна очистить очередь и вывести ok.

exit

Программа должна вывести bye и завершить работу.

Размер очереди должен быть ограничен только размером доступной оперативной памяти. Перед исполнением операций front и popпрограмма должна проверять, содержится ли в очереди хотя бы один элемент. Если во входных данных встречается операция frontилиpop, и при этом очередь пуста, то программа должна вместо числового значения вывести строку error.

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

Описаны в условии. См. также пример входных данных.

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

Описаны в условии. См. также пример выходных данных.

Тесты 

Входные данные Выходные данные:
1 push 1
front
exit
ok
1
bye
2 size
push 1
size
push 2
size
push 3
size
exit
0
ok
1
ok
2
ok
3
bye

Код программы:

Алгоритм решения:

Каждый элемент (узел) очереди состоит из информационной части (его значение) и адресной. В адресную часть первого элемента записываем адрес следующего элемента и т.д., тем самым мы создаем порядок следования элементов в очереди, связывая их между собой. При добавлении или удалении элемента мы соответственно изменяем размер очереди, который изначально равен нулю, а также меняем позиции указателей на начало и конец очереди. В условии задачи сказано, что если во входных данных встречается операция front или  pop, и при этом очередь пуста, то программа должна вместо числового значения вывести строку error. Поэтому создаем исключительную ситуацию для проверки наличия в очереди хотя бы одного элемента.

Ссылка на засчитанное решение на e-olymp
Ссылка на условие задачи
Ссылка на решение задачи на ideone.com

 

 

 

e-olymp 6125. Простая очередь

Задача

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

  • push n — Добавить в очередь число n (значение n задается после команды). Программа должна вывести ok.
  • pop — Удалить из очереди первый элемент. Программа должна вывести его значение.
  • front — Программа должна вывести значение первого элемента, не удаляя его из очереди.
  • size — Программа должна вывести количество элементов в очереди.
  • clear — Программа должна очистить очередь и вывести ok.
  • exit — Программа должна вывести bye и завершить работу.

Гарантируется, что набор входных команд удовлетворяет следующим требованиям: максимальное количество элементов в очереди в любой момент не превосходит 100, все команды pop и front корректны, то есть при их исполнении в очереди содержится хотя бы один элемент.

Данную задачу также можно найти здесь.

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

Описаны в условии. Смотрите также тесты, расположенные ниже.

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

Описаны в условии. Смотрите также тесты, расположенные ниже.

Тесты

Входные данные Выходные данные
1 push 123
size
push -5
pop
exit
ok
1
ok
123
bye
2 push 1
push 2
front
push 42
pop
exit
ok
ok
1
ok
1
bye
3 push 1
push 2
pop
pop
size
exit
ok
ok
1
2
0
bye

Код

Ход решения

Реализуем абстрактный тип данных очередь, который отвечает принципу FIFO («первый вошёл – первый вышел») с помощью массива. Очередь имеет начало и конец, на которые указывают соответственно start и finish. Изначально очередь является пустой, поэтому start = 0, finish = 0. При добавлении нового элемента в очередь записываем его в конец. finish при этом увеличиваем на единицу. Извлекаемый же элемент берём в начале очереди, после чего start++. Если необходимо получить значение начала очереди, не извлекая его, воспользуемся функцией front(), возвращающей значение первого элемента. Для получения размера очереди используем функцию size(), которая возвращает разницу между концом и началом очереди. Если очередь нужно очистить, то приравниваем finish и start к нулю.

 

Ссылка на засчитанное решение находится здесь.

Код на сайте ideone.com находится здесь.

e-olymp 1061. Покраска лабиринта

Сорокина Полина
Сорокина Полина

Latest posts by Сорокина Полина (see all)

Задача e-olimp 1061.

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

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

В первой строке находится число N, затем идут N строк по N символов: точка обозначает пустой сегмент, решетка — сегмент со стеной.

3N33, размер сегмента 3×3, высота стен 3 метра.

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

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

Пример

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

. . . . .

. . . # #

. . # . .

. . # # #

. . . . .

198

C++:

Java:

Для решения задачи я использовала алгоритм поиска в ширину: начиная с левой верхней клетки, которая гарантированно пуста, проверяю все смежные с ней и заношу их в план проверки. Для каждой клетки считаю количество пустых смежных клеток и получаю число стен рядом с ней. Чтобы было удобно проверять смежные клетки на пустоту, я сделала «стену» вокруг данного лабиринта. После проверки клетки отмечаю, что она просмотрена.

Так как в условии не гарантируется, что есть проход от левой верхней до правой нижней клетки, проверяю, посещена ли последняя. Если нет, снова запускаю поиск, начиная с неё.

Засчитанное решение.

Задача на Ideone:
C++
Java

e-olimp 4847. Очередь с приоритетами

Швандт Максим Альбертович
Швандт Максим Альбертович

Latest posts by Швандт Максим Альбертович (see all)

Условие: Реализуйте структуру «очередь с приоритетами», поддерживающую следующие операции:

  1. Добавление элемента в очередь.
  2. Удаление из очереди элемента с наибольшим приоритетом.
  3. Изменение приоритета для произвольного элемента, находящегося в очереди.

Тесты:

input data output data
add eight 8 <вывод не предусмотрен>
add three 3 <вывод не предусмотрен>
add eleven 11 <вывод не предусмотрен>
add one 1 <вывод не предусмотрен>
add five 5 <вывод не предусмотрен>
add neun 9 <вывод не предусмотрен>
add forteen 14 <вывод не предусмотрен>
add six 6 <вывод не предусмотрен>
add ten 10 <вывод не предусмотрен>
add twelve 12 <вывод не предусмотрен>
add fifteen 15 <вывод не предусмотрен>
add seven 7 <вывод не предусмотрен>
add thirteen 13 <вывод не предусмотрен>
change eleven 1100 <вывод не предусмотрен>
change eleven 1101 <вывод не предусмотрен>
change one 111 <вывод не предусмотрен>
pop eleven 1101
pop one 111
pop fifteen 15
pop forteen 14
pop thirteen 13
pop twelve 12
pop ten 10
pop neun 9
pop eight 8
pop seven 7
pop six 6
pop five 5
pop three 3
pop error

Код программы:

Компилировать под Gnu C++ 4.7.1

План программы:

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

Задача решалась в два этапа, сначала был написан вариант с упорядоченным списком, который позволял мгновенный pop, но add и change не удовлетворили тестам на скорость т.к. основывались на поиску путем перебора. Было приято решение использовать алгоритм поиска в двоичном дереве, учитывая, что условия задачи позволяли большой объем памяти.

 

Текущий вариант основывается шаблонном классе, реализующем двоичное дерево. Очередь содержит два объекта – дерево со строковыми ключами для хранения Id и дерево с числовыми ключами для хранения приоритетов. Каждый узел дерева Id указывает на узел дерева приоритетов. Это позволяет немедленно получить приоритет данного Id без поиска, что необходимо для операции change. В свою очередь, каждый узел дерева приоритетов указывает на узлы дерева Id с данным приоритетом. Это позволяет немедленно определить какой Id надо удалять при выполнении pop. Для обслуживания нескольких Id с равным приоритетом пришлось ввести еще один шаблонный класс – список.

 

Краткое описание операций

  • Add
    1. Находим или добавляем узел дерева Id (ситуацию если он есть игнорируем по условию задачи)
    2. Находим или добавляем узел дерева приоритетов
    3. Для узла дерева Id устанавливаем указатель на узел дерева приоритетов
    4. Для узла дерева приоритетов добавляем в его список узел дерева Id

 

  • Pop
    1. Находим узел дерева приоритетов с максимальным ключом
    2. Удаляем из списка найденного узла первый попавшийся указатель на узел дерева Id, если список
    3. Если список уже пуст, удаляем узел дерева приоритетов

 

  • Change
    1. Находим узел дерева Id (ситуацию если его нет игнорируем по условию задачи)
    2. Берем узел дерева приоритетов, на который указывает узел Id и удаляем из его списка этот узел Id (т.к. приоритет уже будет новый), если список оказался пуст, удаляем также узел приоритета
    3. Находим или добавляем узел дерева приоритетов с новым приоритетом и устанавливаем связь с узлом Id как в случае добавления.

 

Ссылка: http://ideone.com/FROADt

e-olimp 2510. Сортировка очередями

Іванов Вячеслав Володимирович
Іванов Вячеслав Володимирович

Latest posts by Іванов Вячеслав Володимирович (see all)

e-olimp 2510. Сортировка очередями

Постановка задачи

Рассматривается специальное устройство, содержащее входной поток, выходной поток и k очередей, пронумерованных числами от [latex]1[/latex] до [latex]k[/latex].

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

Программа должна содержать ровно [latex]2n[/latex] операций, каждая из которых либо читает число из входного потока и добавляет его в одну из очередей, либо извлекает число из одной из очередей и выводит его в выходной поток.

Алгоритм решения

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

Реализация:

Ideone: http://ideone.com/X37iWg
Засчитанное решение: http://www.e-olimp.com/solutions/1935453

Детали реализации:

В коде программы активно используется библиотека [latex]algorithm[/latex] и анонимные функции,
объявленные по месту использования (внутри соответствующих методов), что позволяет минимизировать число лишних сущностей
и сделать реализацию более декларативной.

  1. find_if() — найти первый элемент участка контейнера, удовлетворяющий логическому условию. Принимает итераторы
    на левую и правую границу интересующего участка, а также унарное логическое условие. Возвращает итератор на интересующий
    элемент или итератор на область за пределами участка, если условие не выполнилось ни разу.
  2. min_element() — найти минимальный элемент на заданном участке контейнера. Принимает итераторы на левую и правую
    границу интересующего участка и двухместный предикат, задающий отношение порядка. Возвращает итератор на интересующий
    элемент или за на область за пределами участка, если условие не выполнилось ни разу (пустой контейнер, некорректный порядок).