e-olymp 6122. Простой стек

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

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

Входные данные
Каждая строка содержит одну команду.

Выходные данные
Для каждой команды вывести в отдельной строке соответствующий результат.

Тесты

входные данные выходные данные
push 2 ok
push 3 ok
push 5 ok
baсk 5
sizе 3
pop 5
sizе 2
push 7 ok
pop 7
clear ok
size 0
exit bye

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

Решение задачи
Для каждой команды вводимой в программу реализуем функцию, которую она должна выполнять в стеке.

Ссылки

A303. Вычисления с хранением последовательности значений

Условие задачи

Даны действительные числа [latex]x_1,\;…,\;x_{200}[/latex], принадлежащие интервалу [latex](0, 1][/latex]. Полуинтервал разбивается на 100 равных частей. Вычислить [latex]p_1, …, p_{100}[/latex], где [latex]p_k = \frac{m_k}{2000}[/latex], а [latex]m_k[/latex] — количество заданных чисел, принадлежащих полуинтервалу [latex](0.01(k – 1), 0.01k] \ \ (k = 1, …, 100)[/latex].

Входные данные
Входной файл содержит 200 действительных чисел, принадлежащих интервалу [latex](0, 1][/latex].

Выходные данные
В выходной файл выведите 100 чисел [latex]p_k \ (k = 1, …, 100)[/latex].

Тесты

Входные данные Выходные данные
1
Последовательность [latex]\frac{1}{i}, \ i=1, …, 200[/latex] p[1]=0.067 p[2]=0.013 p[3]=0.006 p[4]=0.003 p[5]=0.002 p[6]=0.0015 p[7]=0.001 p[8]=0.001 p[9]=0.0005 p[10]=0.0005
p[11]=0.0005 p[12]=0 p[13]=0.0005 p[14]=0.0005 p[15]=0 p[16]=0 p[17]=0.0005 p[18]=0 p[19]=0 p[20]=0.0005
p[21]=0 p[22]=0 p[23]=0 p[24]=0 p[25]=0.0005 p[26]=0 p[27]=0 p[28]=0 p[29]=0 p[30]=0
p[31]=0 p[32]=0 p[33]=0.0005 p[34]=0 p[35]=0 p[36]=0 p[37]=0 p[38]=0 p[39]=0 p[40]=0
p[41]=0 p[42]=0 p[43]=0 p[44]=0 p[45]=0 p[46]=0 p[47]=0 p[48]=0 p[49]=0 p[50]=0.0005
p[51]=0 p[52]=0 p[53]=0 p[54]=0 p[55]=0 p[56]=0 p[57]=0 p[58]=0 p[59]=0 p[60]=0
p[61]=0 p[62]=0 p[63]=0 p[64]=0 p[65]=0 p[66]=0 p[67]=0 p[68]=0 p[69]=0 p[70]=0
p[71]=0 p[72]=0 p[73]=0 p[74]=0 p[75]=0 p[76]=0 p[77]=0 p[78]=0 p[79]=0 p[80]=0
p[81]=0 p[82]=0 p[83]=0 p[84]=0 p[85]=0 p[86]=0 p[87]=0 p[88]=0 p[89]=0 p[90]=0
p[91]=0 p[92]=0 p[93]=0 p[94]=0 p[95]=0 p[96]=0 p[97]=0 p[98]=0 p[99]=0 p[100]=0.0005

Код на языке C++:

Код на языке Java:

Решение задачи
Для сортировки чисел по полуинтервалам разделим каждое [latex]x_i[/latex] на [latex]0.01[/latex](т.е. умножим на 100) и округлим вправо. Заведём массив для подсчета количества чисел, принадлежащих полуинтервалам [latex](0.01(k – 1), 0.01k] \ \ (k = 1, …, 100)[/latex]. Выведем [latex]p_k \ (k = 1, …, 100)[/latex].

Условие задачи (стр. 127)
Код задачи на C++: Ideone
Код задачи на Java: Ideone

e-olymp 6128. Простой дек

Задача. Простой дек

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

push_front

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

push_back

Добавить (положить) в конец дека новый элемент. Программа должна вывести ok.

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

pop_back

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

front

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

back 

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

size

Вывести количество элементов в деке.

clear

Очистить дек (удалить из него все элементы) и вывести ok.

exit

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

Гарантируется, что количество элементов в деке в любой момент не превосходит 100. Все операции:

  • pop_front
  • pop_back
  • front
  • back

всегда корректны.

Объяснение: Количество элементов во всех структурах данных не превышает 10000, если это не указано особо.

Тесты

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

 push_back 3

push_back 14

size

clear

push_front 1

back

push_back 2

front

pop_back

size

pop_front

size

exit

 ok

ok

2

ok

ok

1

ok

1

2

1

1

0

bye

 2  size

push_back 8

push_front 4

size

front

back

push_back 3

pop_front

front

pop_back

back

exit

0

ok

ok

2

4

8

ok

4

8

3

8

bye

Решение

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

Реализация двусторонней очереди идет посредством векторов [latex]box1[/latex] и [latex]box2[/latex], поэтому нет необходимости делать проверку на переполнение. Команды [latex]push_front[/latex] и [latex]push_back[/latex] соответственно добавляют в концы векторов [latex]box1[/latex] и [latex]box2[/latex] элементы и увеличивают размер дека box_size (на единицу за каждый добавленный элемент). Рассмотрим команду [latex]front[/latex]. Проверяя присутствие элементов в [latex]box1[/latex] мы выводим последний элемент вектора, так как добавляли элемент с помощью [latex]push_front[/latex] в конец вектора [latex]box1[/latex]. Если же вектор [latex]box1[/latex] пуст, то выводим первый элемент вектора [latex]box2[/latex], который в случае пустого вектора [latex]box1[/latex] является первым элементом дека. Команда [latex]back[/latex] относительно [latex]front[/latex] с векторами работает инверсивно. Т.е. Проверяя присутствие элементов в [latex]box2[/latex] выводим последний элемент данного вектора. Если же вектор [latex]box2[/latex] пуст, то выводим первый элемент вектора [latex]box1[/latex] , который в случае пустого вектора [latex]box2[/latex] является последним элементом дека. С командами [latex]pop_front[/latex] и [latex]pop_back[/latex] работают идентично [latex]front[/latex] и [latex]back[/latex]. Отличие лишь в том, что команды [latex]pop[/latex] в дополнении к выводу элемента удаляют его, уменьшая размер дека [latex]box_size[/latex] (на единицу за каждый удаленный элемент). Команда [latex]size[/latex] выводит размер дека [latex]box_size[/latex]. Команда clear удаляет все элементы векторов [latex]box1[/latex], [latex]box2[/latex] и обнуляет размер дека. Команда [latex]exit[/latex] выводит «bye» и завершает работу программы. Команды принимаются из потока ввода посредством строки s.

Ссылка на код.

e-olymp.

 

6130. Дек неограниченного размера

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

push_front

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

push_back

Добавить (положить) в конец дека новый элемент. Программа должна вывести ok.

pop_front

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

pop_back

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

front

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

back

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

size

Вывести количество элементов в деке.

clear

Очистить дек (удалить из него все элементы) и вывести ok.

exit

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

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

Тесты

Входные данные Выходные данные
push_front 1 ok
push_back 9 ok
push_front 2 ok
push_back 3 ok
size 4
pop_front 2
pop_back 3
size 2
front 1
back 9
clear ok
size 0
back error
exit bye

Описание решения задачи:
Для решения данной задачи использовался двунаправленный линейный список. Каждый узел ДЛС содержит два поля указателей — на следующий и на предыдущий узел. Для этого в задаче была создана структура [latex]Node[/latex]. Указателем на адрес начала списка и конца, соответственно, выступают узлы [latex]head[/latex] и [latex]tail[/latex], изначально инициализированные нулем.

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

Условие задачи
Код задачи на с++
Засчитанное решение

A302. Количество различных цифр числа в его десятичной записи

Задача

Дано натуральное число [latex]N[/latex]. Сколько различных цифр встречается в его десятичной записи?

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

Натуральное число [latex]N[/latex].

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

Количество различных цифр [latex]sum[/latex].

Тесты

Входные данные Выходные данные
[latex]N[/latex] [latex]sum[/latex]
12345678900987654321 sum:10
302 sum:3

Код программы с использованием deque

 

Решение

Создадим дэк [latex]folder[/latex] в котором будем хранить различные цифры десятичной записи. Добавляем первую цифру числа [latex]N[/latex] в дэк и делим [latex]N[/latex] на [latex]10[/latex]. Следующие цифры мы будем добавлять после проверки на отсутствие таких же в [latex]folder[/latex], если цифры совпадают заканчиваем цикл. В конце выводим размер [latex]folder[/latex] который и является [latex]sum[/latex].

Код программы с использованием массива

Решение

Создадим массив [latex]folder[/latex] в котором будем хранить кол-во встреч для различных цифр десятичной записи в соответствующих позициях массива. Увеличиваем на один значения соответствующей позиции массива и делим [latex]N[/latex] на [latex]10[/latex]. Для определения [latex]sum[/latex] делаем цикл и проверяем ненулевые значения массива [latex]folder[/latex].

Ссылки

Ideone через deque;
Ideone через массив;
Условие задачи (стр. 126).

e-olymp 6128. Простой дек

Задача

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

  • push_front Добавить (положить) в начало дека новый элемент. Программа должна вывести ok.
  • push_back Добавить (положить) в конец дека новый элемент. Программа должна вывести ok.
  • pop_front Извлечь из дека первый элемент. Программа должна вывести его значение.
  • pop_back Извлечь из дека последний элемент. Программа должна вывести его значение.
  • front Узнать значение первого элемента (не удаляя его). Программа должна вывести его значение.
  • back Узнать значение последнего элемента (не удаляя его). Программа должна вывести его значение.
  • size Вывести количество элементов в деке.
  • clear Очистить дек (удалить из него все элементы) и вывести ok.
  • exit Программа должна вывести bye и завершить работу.

Гарантируется, что количество элементов в деке в любой момент не превосходит [latex]100[/latex]. Все операции:

pop_front,
pop_back,
front,
back
всегда корректны.

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

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

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

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

Тесты

Входные данные Выходные данные
push_back 3
push_front 14
size
clear
push_front 1
back
push_back 2
front
pop_back
size
pop_front
size
exit
ok
ok
2
ok
ok
1
ok
1
2
1
1
0
bye

Код программы на C++

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

Решение

Создадим массив [latex]folder[/latex] и целочисленные переменные [latex]start[/latex] и [latex]end[/latex] в качестве указателей на начало и конец нашего дека.

  • push_front  — сдвигаем указатель [latex]start[/latex] на [latex]1[/latex] назад, кладем значение в наш дек и выводим ok;
  • push_back  — кладем значение в наш дек, сдвигаем указатель [latex]end[/latex] на [latex]1[/latex] вперед и выводим ok;
  • pop_front  — выводим значение начала дека и перемещаем [latex]start[/latex] вперед на [latex]1[/latex];
  • pop_back  — перемещаем [latex]end[/latex] назад на [latex]1[/latex] и выводим значение конца дека;
  • front  — выводим значение начала дека;
  • back  — выводим значение перед [latex]end[/latex];
  • size  — отнимем от переменной [latex]end[/latex] переменную [latex]start[/latex];
  • clear  — приводим [latex]start[/latex] и [latex]end[/latex] к изначальным позициям;
  • exit  — выводим «bye» и заканчиваем программу.

Ссылки

Ideone C++
Ideone Java
решение e-olymp C++
решение e-olymp Java

e-olymp 1060. Линии

Задача взята с сайта e-olymp.com.

Условие задачи

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

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

В первой строке находится число [latex]n \left (2\leq n\leq 40 \right )[/latex], в каждой из следующих [latex]n[/latex] строк — по [latex]n[/latex] символов. Символом точки обозначена свободная клетка, латинской заглавной [latex]O[/latex] — шарик, [latex]@[/latex] — исходное положение шарика, который должен двигаться, латинской заглавной [latex]X[/latex] — конечное положение шарика.

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

В первой строке выводится [latex]Y[/latex], если движение возможно, или [latex]N[/latex], если нет. Если движение возможно далее следует [latex]n[/latex] строк по [latex]n[/latex] символов — как и на вводе, но [latex]X[/latex], а также все точки на пути заменяются плюсами.

Тесты

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

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

ideone.com

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

Решение

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

Затем, если клетка с конечным положением шарика достижима, необходимо восстановить кратчайший путь. Двигаясь от конечной позиции в начальную, на каждом шаге выбираем клетку значение которой на единицу меньше текущего положения, при этом символы в соответствующих клетках исходного лабиринта заменяем на символ [latex]+.[/latex]

e-olymp 1948. Топологическая сортировка

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

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

В первой строке содержатся количество вершин [latex]n[/latex] (1 ≤ [latex]n[/latex] ≤ 100000) и количество рёбер [latex]m[/latex] (1 ≤[latex]m[/latex] ≤ 100000) в графе. В следующих [latex]m[/latex] строках перечислены рёбра графа, каждое из которых задаётся парой чисел — номерами начальной и конечной вершины.

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

Вывести любую топологическую сортировку графа в виде последовательности номеров вершин. Если граф невозможно топологически отсортировать, то вывести -1.

Тесты:

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

Решение:

Описание решения:

Для решения данной задачи необходимо было воспользоваться алгоритмом топологической сортировки, посредством поиcка в глубину. Чтобы применить данный алгоритм, необходимо было проверить граф на ацикличность с помощью алгоритма поиска в глубину. Это было реализовано функцией [latex]cyclic[/latex], которая проходила по всему графу в поиске цикла. Если цикл был найден, то функция меняла значение переменной [latex]cycle_st[/latex]. Далее, если цикл был найден, то программа выводить -1, иначе применяется алгоритм топологической сортировки, реализованный в двух функциях:

и

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

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

Код решения на ideone.com.

e-olymp 6123. Стек с защитой от ошибок

Задача

Стек с защитой от ошибок

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

push n

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

pop

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

back

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

size

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

clear

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

exit

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

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

Команды для стека.

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

Соответствующие значения для каждой команды(см. выше).

Тесты

Последовательность Результат
1 push 2
back
pop
size
pop
push 1
size
exit
ok
2
2
0
error
ok
1
bye
2 push 3
push 1
push 5
size
pop
size
exit
ok
ok
ok
3
5
2
bye
3 back
push 9
pop
pop
exit
error
ok
9
error
bye
4 size
push 1
size
back
pop
exit
0
ok
1
1
1
bye

Код

Решение

Создаем структуру в которой реализуем все команды для стека с помощью функций и указателя([latex]cursor[/latex]). [latex]cursor[/latex] указывает на последний элемент в строке. Изначально [latex]cursor[/latex] равен 0, т.к. сначала стек пуст.

[latex]push n[/latex]  записывает в ячейку с номером [latex]cursor+1[/latex] элемент [latex]n[/latex].

[latex]size[/latex] возвращает [latex]cursor[/latex] т.е. размер стека.

[latex]pop[/latex] возвращает последний помещённый в стек элемент, то есть элемент с номером [latex]cursor-1[/latex], при этом удаляя его из стека. Если размер стека равен 0 то функция возвращает [latex]error[/latex].

[latex]back[/latex] возвращает последний помещённый в стек элемент, то есть элемент с номером [latex]cursor-1[/latex]. Если размер стека равен 0 то функция возвращает [latex]error[/latex].

[latex]clear[/latex] присваивает [latex]cursor[/latex] значение 0.

[latex]exit[/latex] выполняется с помощью оператора [latex]break[/latex], который заканчивает выполнение цикла, в который вводятся команды.

 

Ссылка на e-olymp.

Ссылка на ideone.

e-olymp 6124. Стек неограниченного размера

Задача

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

push n

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

pop

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

back

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

size

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

clear

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

exit

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

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

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

Описаны в условии.

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

Описаны в условии.

Тесты:

 ввод  вывод ввод вывод
push 7
clear
push 4
back
push 1151
back
pop
back
size
exit
ok
ok
ok
4
ok
1151
1151
4
1
bye
 push 2
push 7
back
pop
pop
back
push 1
back
pop
exit
ok
ok
7
7
2
error
ok
1
1
bye
pop
push 42
back
size
pop
size
push 17
push 19
push 24
back
size
clear
size
exit
error
ok
42
1
42
0
ok
ok
ok
24
3
ok
0
bye
back
size
clear
size
back
pop
push 2
pop
push 1
size
back
exit
error
0
ok
0
error
error
ok
2
ok
1
1
bye

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

Решение

В данном решении стек состоит из объектов, далее именуемых звеньями, каждый из которых состоит из массива, переменной, отвечающей свободному месту в массиве, ссылки на следующее звено. Кроме того, у звена есть метод для его создания, методы push и pop. В этих методах, кроме их прямой функции, отслеживается количество свободного места в звене. С этим всем работает сам стек. В самом стеке есть указатель на первое звено (звено, в которое был добавлен последний элемент, который все еще есть в стеке) и переменная S, отвечающая количеству элементов в стеке. Еще есть такие методы, как создание и удаление звена, а также все методы указанные в условии.  Создается звено, если нужно что-то добавить в стек и в текущих звеньях уже нет свободного места, а удаляется, если после извлечения чего-то из стека первое звено пустое (или при методе clear). Для этого и нужна переменная отвечающая свободному месту в звене.

Теперь немного о методах, указанных в условии. Во-первых, все методы, меняющие число элементов в стеке, соответственно влияют на переменную, этому числу отвечающую, а size ее просто возвращает. Методы push и pop непосредственно для выполнения своей функции обращаются к своим аналогам в первом звене. Методы pop и back проверяют в начале, не пуст ли стек, через переменную S. Back получает значение последнего элемента, работая непосредственно с массивом первого звена. exit вообще не создан, как метод, а обрабатывается непосредственно в функции Main().  Собственно, сама эта функция только принимает и обрабатывает через условные операторы запросы, а потому описывать ее нет смысла (см. код программы).

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

задача взята с сайта e-olymp

Ссылка на засчитанное решение

ссылка на код на ideone

 

AL6

Задача AL6

Условие

Дана конечная последовательность, состоящая из левых и правых скобок различных заданных типов. Как определить, можно ли добавить в нее цифры и знаки арифметических действий так, чтобы получилось правильное арифметическое выражение.

Тесты

Входные данные Выходные данные
1 ( NO
2 )) NO
3 [} NO
4 {} YES
5 (){}[] YES
6 ({[]}{}) YES
7 [({}())[] NO

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

Решение

Арифметическое выражение является правильным если каждой открывающей скобке соответствует единственная закрывающая. Что бы убедится в правильности выражения необходимо создать структуру [latex]stack[/latex], в которую поочередно записываются открывающиеся скобки. Если встречается закрывающая скобка того же типа, что и последняя открывающая, то они обе удаляются, так как не влияют на правильность выражения. Если же закрывающая скобка не соответствует типу последней открывающей, то такое арифметическое выражение не является правильным. Если после обработки всей последовательности в стеке не осталось элементов, то такое выражение является правильным. В случае отсутствия скобок выражение также правильное.

Ссылки

Код программы на ideone.com

Условие задачи

e-olimp 6129. Дек с защитой от ошибок

Задача:

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

push_front

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

push_back

Добавить (положить) в конец дека новый элемент. Программа должна вывести ok.

pop_front

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

pop_back

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

front

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

back

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

size

Вывести количество элементов в деке.

clear

Очистить дек (удалить из него все элементы) и вывести ok.

exit

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

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

 

 

Решенная задача на e-olimp

Код на ideone

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

 

 

 

AL15. Лабиринт

Условие

Матрица размера [latex]n*m[/latex] определяет некоторый лабиринт. B матрице элемент [latex]1[/latex] обозначает стену, а [latex]0[/latex] определяет свободное место. В первой строке матрицы определяются входы [latex]x_i[/latex], а в последней выходы [latex]y_i[/latex], [latex]i = 1, \ldots, k[/latex], [latex]k \leq n[/latex] которые должны быть нулевыми элементами.

Необходимо определить, можно ли:

а) провести [latex]k[/latex] человек от входа [latex]x_i[/latex] до выхода [latex]y_i[/latex] соответственно, [latex]i = 1, \ldots, k[/latex], таким образом, чтобы каждое свободное место посещалось не более одного раза.

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

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

Числа [latex]n[/latex] и [latex]m[/latex] определяющие кол-во строк и столбцов соответственно, [latex]1 \leq n, m \leq 10^4[/latex]. Количество входов [latex]k[/latex]  равно кол-ву выходов, [latex]1 \leq k \leq min(1000, n)[/latex]. Число [latex]k[/latex] не является частью входных данных (не подается на вход программы).

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

[latex]YES[/latex], если соответствующий набор маршрутов существует, [latex]NO[/latex] — в противном случае.

Замечания

  1. Легко заметить, что случай б) эквивалентен случаю а). Предположим, что [latex]k > 1[/latex] и мы провели первых [latex]i — 1[/latex] людей (возможно, никого) согласно условию а), [latex]1 \leq i < k[/latex]. Пусть человек под номером [latex]i[/latex] нарушил условие, например, вышел через выход с номером [latex]i + 1[/latex]. Тогда, т.к. его путь цельный и идет от самого первого ряда лабиринта до последнего, он образует «стену» из единичек, заблокировав выход [latex]i[/latex]. Тогда провести всех людей не возможно, ведь кол-ва входов и выходов равны. Следовательно, будем рассматривать как нашу задачу только случай а).
  2. Заполнение клеток каждого из пройденных маршрутов в матрице различными числами вместо единицы и функция

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

Тесты

№ теста Входные данные Выходные данные Пояснение (маршрут)
 1 6 8
1 0 1 0 1 1 0 1
1 0 1 0 0 0 0 1
1 0 1 1 0 0 1 1
1 0 0 0 0 0 0 1
1 0 0 1 1 0 0 1
1 0 0 1 1 1 0 1
 YES 1 a 1 b 1 1 c 1
1 a 1 b b c c 1
1 a 1 1 b c 1 1
1 a b b b c 0 1
1 a b 1 1 c c 1
1 a b 1 1 1 c 1
 2 5 7
1 0 0 0 1 1 0
0 0 0 0 0 0 0
0 0 0 0 0 1 1
0 0 0 0 0 0 0
0 0 0 1 1 1 0
YES 1 a b c 1 1 d
a a b c d d d
a b b c d 1 1
a b c c d d d
a b c 1 1 1 d
 3 7 7
1 1 0 0 1 1 1
0 0 0 0 0 0 0
0 0 0 0 0 0 0
1 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 1 0 0 0
1 1 1 1 0 1 0
YES 1 1 a b 1 1 1
a a a b 0 0 0
a a b b 0 0 0
1 a b b b b 0
a a a a a b 0
a a a 1 a b b
1 1 1 1 a 1 b
 4 5 5
0 1 0 1 0
0 0 0 0 0
0 0 0 0 0
0 0 1 0 0
0 1 0 1 0
 NO
 5 7 12
1 1 1 1 1 0 1 1 1 1 1 0
0 0 0 1 0 0 1 0 0 0 0 0
0 0 0 0 0 1 1 0 1 1 1 0
0 1 1 0 0 0 1 1 1 0 0 0
1 0 1 0 0 0 1 0 0 0 1 0
0 0 0 0 0 0 1 0 0 1 1 0
1 1 1 1 1 0 1 1 1 1 1 0
 YES 1 1 1 1 1 a 1 1 1 1 1 b
0 0 0 1 a a 1 0 0 0 0 b
0 0 0 a a 1 1 0 1 1 1 b
0 1 1 a 0 0 1 1 1 0 0 b
1 0 1 a 0 0 1 0 0 0 1 b
0 0 0 a a a 1 0 0 1 1 b
1 1 1 1 1 a 1 1 1 1 1 b
 6 3 6
1 1 1 1 1 0
0 0 0 0 0 0
1 0 1 1 1 1
 YES 1 1 1 1 1 a
0 a a a a a
1 a 1 1 1 1
 7 10 10
0 1 1 1 1 1 1 1 1 1
0 1 0 0 0 0 0 0 0 0
0 1 0 1 1 1 1 1 1 0
0 1 0 1 0 0 0 0 1 0
0 1 0 1 0 0 1 0 1 0
0 1 0 1 0 0 1 0 1 0
0 1 0 0 0 0 1 0 1 0
0 1 1 1 1 1 1 0 1 0
0 0 0 0 0 0 0 0 1 0
1 1 1 1 1 1 1 1 1 0
 YES a 1 1 1 1 1 1 1 1 1
a 1 a a a a a a a a
a 1 a 1 1 1 1 1 1 a
a 1 a 1 a a a a 1 a
a 1 a 1 a 0 1 a 1 a
a 1 a 1 a 0 1 a 1 a
a 1 a a a 0 1 a 1 a
a 1 1 1 1 1 1 a 1 a
a a a a a a a a 1 a
1 1 1 1 1 1 1 1 1 a
 8 10 10
0 1 1 1 1 1 1 1 1 1
0 1 0 0 0 0 0 0 0 0
0 1 0 1 1 1 1 1 1 0
0 1 0 1 0 0 0 0 1 0
0 1 0 1 1 0 1 0 1 0
0 1 0 1 0 1 1 0 1 0
0 1 0 0 0 0 1 0 1 0
0 1 1 1 1 1 1 0 1 0
0 0 0 0 0 0 0 0 1 0
1 1 1 1 1 1 1 1 1 0
 NO
 9 6 7
1 1 1 1 0 0 1
0 0 0 1 0 0 1
0 1 0 0 0 0 1
0 0 1 0 0 0 1
1 0 0 0 0 1 1
1 1 0 0 1 1 1
 YES 1 1 1 1 a b 1
a a a 1 a b 1
a 1 a a a b 1
a a 1 b b b 1
1 a a b 0 1 1
1 1 a b 1 1 1
 10 1 5
0 0 0 0 0
 YES a b c d e

Алгоритм

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

  1. Попытаться провести человека согласно описанной выше стратегии.
  2. В случае успеха, отметить все ячейки, пройденные ним, как недоступные. Иначе — будем кидать исключение, ловить которое будем непосредственно в основной функции, при поимке — выводим [latex]NO[/latex] и завершаем работу программы.

За поиск маршрута отвечают 2 функции. Функция

возвращает стек координат (пар чисел), представляющих собой маршрут человека, или кидает исключение в случае его отсутствия. Функция только создает стек, помещает в него первую вершину и запускает рекурсивную функцию

отвечающую непосредственно за поиск, из точки входа с направлением движения вниз (т.к. из входа первый шаг можно совершить только вниз). Алгоритм поиска маршрута:

  1. Находим, в какую клетку мы попали при данном направлении. Определим все направления как подходящие константы и будем получать направление по формуле [latex]dir / 10, dir \mod 10[/latex], первая координата — по вертикали, вторая — по горизонтали. Так, например, для [latex]down = 10[/latex] получим вектор [latex](1, 0)[/latex], соответствующий перемещению на одну ячейку вниз в матрице (для остальных направлений значения подобраны аналогично).
  2. Проверяем, можем ли мы находиться в этой ячейке, если нет (она занята или находится вне матрицы) — не ищем дальше, возвращаем [latex]false[/latex].
  3. Добавляем координаты ячейки в стек route, проверяем, является ли данная точка выходом, если да — завершаем поиск успешно ([latex]true[/latex]).
  4. Составим массив направлений, от наиболее до наименее приоритетных, в зависимости от предыдущего направления. Например, текущее направление было [latex]down[/latex], мы пришли сверху, лучше всего будет попробовать пойти влево, иначе снова вниз, иначе вправо, наверх нельзя (уже были):

    Для других направлений — рассуждения аналогичны.
  5. Поочередно вызовем поиск из новой точки в каждом из направлений в порядке приоритета, при нахождении пути оставшиеся направления (с меньшим приоритетом) не рассматриваем, возвращаем [latex]true[/latex].
  6. Если ни в одном из направлений нельзя попасть к выходу (тупик) — удаляем вершину из стека, возвращаем [latex]false[/latex].

Код

 

Ссылки

Код для тестирования на ideone.

e-olymp 4002. Down with cheating!

During the test, Professor Floyd noticed that some students exchanged notes. At first, he wanted to put a bad mark everyone, but that day the professor was in a good mood, therefore he decided to split all the students into two groups and put a bad mark to only those,who writting off.
The professor recorded all the pairs of students, who exchanged notes. You need to determine whether they can be divided into two groups, where student of one group exchange notes only with student of other group.

Input

There are two numbers in first line [latex]m[/latex] and [latex]n[/latex] — quantity of students and quantity of pairs, who exchanged notes. [latex](1 \le n \le 100[/latex], [latex]0 \le m \le n(n-1)/2)[/latex]. Further in [latex]m[/latex] lines there are description of student pairs: two different numbers, corresponding to the student serial number, who exchanged notes (numbering from [latex]1[/latex]). Each pair of students is listed only once.

Output

Print the answer to the Professor’s Floyd task. If it is possible to divide the students into two groups output «YES», or «NO» otherwise.

Test

Input Output
1 3 2
1 2
2 3
YES
2 3 3
1 2
1 3
2 3
NO
3 12 9
1 3
2 3
4 5
5 6
6 8
6 9
7 9
8 10
11 12
YES
4 12 10
1 3
2 3
4 5
5 6
6 8
6 9
7 9
8 9
8 10
11 12
NO

bipartite graph
Illustration for the test №3notBipartiteGraph
Illustration for the test №4
 

Algorithm

After reading the statement of the problem becomes clear that our goal is to determine whether it is possible to divide the graph into two sets in each of them there aren’t adjacent vertices — check whether the graph is bipartite.
For the implementation, we need a basic function
bool isBipartite(vector<int> *listOfVertices, int *colorOfVertices, int sourceVertex, int quantityOfVertex), that takes a graph (in this program as an array of vectors of adjacent vertices, but can be done similar implementation on the adjacency matrix), array of vertices’ colors, vertex, which we start checking, and the number of vertices.
To solve the problem we perform graph coloring. Naturally, we organize data reading process. And our next sequence of steps is:

  • Initially, we define all the vertices as WHITE — not processed.
  • Call the fucntion for the first vertex (in our numbering — zero).
  • Assign source vertex with one of the colors (for convenience in program we denote it as RED) — equivalent to the action that we put the vertex in the first of two sets.
  • Color all adjacent vertex with inverse color (in program it’s BLUE — has opposite to RED number value) — equivalent to the action that we put vertices in the second set.
  • Color all adjacent to the adjacent vertices with RED color —  we put them in the first set.
  • Repeat this until we have completed bypassing (for convenience we use queue)  — coloring of all connected vertices. But we can find adjacent vertices with same color that sygnalize that our graph cannot be colored with two color — so it isn’t bipartite.

It should be noted that the function implemented in such way works for only one connected component. Therefore, to check the disconnected graphs we must check  all vertices which color is white.

Code

 

Links

e-olymp 6128. Простой дек

Задача. Простой дек

Условие задачи

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

push_front

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

push_back

Добавить (положить) в конец дека новый элемент. Программа должна вывести ok.

pop_front

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

pop_back

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

front

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

back

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

size

Вывести количество элементов в деке.

clear

Очистить дек (удалить из него все элементы) и вывести ok.

exit

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

Гарантируется, что количество элементов в деке в любой момент не превосходит 100. Все операции:

  • pop_front,
  • pop_back,
  • front,
  • back

всегда корректны.

Объяснение: Количество элементов во всех структурах данных не превышает 10000, если это не указано особо.

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

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

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

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

Также условие задачи можно посмотреть здесь.

Тестирование

Входные данные Выходные данные
1. push_back 3
push_front 14
size
clear
push_front 1
back
push_back 2
front
pop_back
size
pop_front
size
exit
ok
ok
2
ok
ok
1
ok
1
2
1
1
0
bye
2. push_front 5
pop_front
size
push_back 3
push_front 10
back
pop_back
size
clear
front
exit
ok
5
0
ok
ok
3
3
1
ok
-1
bye
3. push_front 1
push_back 12
back
front
size
pop_front
size
exit
ok
ok
12
1
2
1
1
bye

Реализация

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

Реализуем двустороннюю очередь с помощью массива. Ввиду особенности структуры дека, необходимым является указание области, активной во время выполнения операций push_front, push_back, pop_front, pop_back, front и back. Это либо начало дека(переменная start), либо его конец(переменная end).
1. Перед выполнением операций push_front и push_back обязательной является проверка дека на заполненность и соответственно на пустоту. Таким образом, если размер дека равен максимально допустимому количеству элементов в структуре данных, программа выводит Full — ни одна из двух вышеупомянутых команд не выполняется. Аналогично, если размер дека равен нулю, увеличиваем его на единицу. Иначе: команды успешно выполняются с проверкой условий, представленных в коде программы. Программа выводит «ok».
2. Далее переходим к командам pop_front и pop_back. Здесь, как и в случае предыдущих операций, в первую очередь проверяем дек на пустоту. Если двусторонняя очередь не содержит элементов, то программа выводит -1. Важной также является проверка на равенство начала и конца дека, в этом случае нужно уменьшить размер структуры на единицу. Если дек содержит хотя бы один элемент, команды успешно выполняются и выводятся значения извлекаемых элементов.
3. Аналогично, перед выполнением команд front и back проверяем, содержит ли дек хотя бы один элемент. Если нет, выводится -1. Иначе: выводятся значения первого и последнего элемента соответственно.
4. Используем команду size, чтобы получить размер дека. Программа выводит количество элементов в деке.
5. Далее, с помощью команды clear удаляем из дека все элементы: присваиваем переменной _size(размер дека) и переменным start и end значение ноль. Программа выводит «ok».
6. Команда exit выводит «bye» — программа завершает работу.
Реализация вывода на экран всех требуемых значений происходит в теле функции main() с помощью строки s.

Для запроса на выполнение следует перейти по ссылке.

Ссылка на засчитанное решение на e-olymp.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 =