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 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

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

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 6122. Простой стек

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

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

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

Тесты

Входные данные Выходные данные
1 push 2
push 3
push 5
back
size
pop
size
push 7
pop
clear
size
exit
ok
ok
ok
5
3
5
2
ok
7
ok
0
bye
2 push 7
size
push 1
pop
back
exit
push 4
pop
ok
1
ok
1
7
bye

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

Для запроса на выполнение нажать здесь.

Решение

Реализуем стек с помощью массива, указателя на на верхнюю незаполненную ячейку массива ([latex]cursor[/latex]) и функций, с помощью которых выполняются команды push, pop, back, size, clear:

  • функция push выполняет запись в ячейку с номером [latex]cursor[/latex] элемента [latex]n[/latex];
  • функция pop возвращает последний помещённый в стек элемент, то есть элемент с номером [latex]cursor-1[/latex], при этом удаляя его из стека;
  • функция back возвращает последний помещённый в стек элемент, то есть элемент с номером [latex]cursor-1[/latex], при этом не удаляя его из стека;
  • функция size возвращает значение [latex]cursor[/latex], то есть размер стека;
  • функция clear присваивает [latex]cursor[/latex] значение [latex]0[/latex].

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

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

e-olymp 1776. Рельсы

Ссылка на условие задачи: http://www.e-olymp.com/ru/problems/1776.

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

В городе PopPush находится известная железнодорожная станция. Страна, в котором находится город, невероятно холмистая. Станция была построена в прошлом веке. К сожалению, в то время средства для постройки были крайне ограничены, поэтому удалось построить только одну железнодорожную колею. Более того, выяснилось, что станция может быть только тупиковой (см. рисунок), и из-за отсутствия свободного места может иметь только одну колею.

Иллюстрация

Местная традиция гласит, что каждый поезд приходящий со стороны A продолжает свое движение в направлении B, при этом его вагоны перестанавливаются в некотором порядке. Предположим, что каждый поезд, приходящий из направления A, имеет n1000 вагонов, пронумерованных в возрастающем порядке 1, 2, …, n. Ответственный за реорганизацию вагонов должен знать, возможно ли перевезти их в направлении B в порядке a1, a2, …, an. Помогите ему написать программу, которая определит возможна ли такая перестановка вагонов. Вагоны можно отсоединять от поезда до того как они попадут на станцию и можно их отдельно передвигать пока все они не буду находиться в направлении B. На станции в любой момент времени может находиться любое количество вагонов. Но если вагон зашел на станцию, он уже не может вернуться на колею в направлении A, а также если он уже выехал в направлении B, то уже не может вернуться на станцию.

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

Состоит из нескольких тестов. Каждый тест кроме последнего описывает один поезд и возможно несколько требований для его реорганизации. Первая строка теста содержит целое число n. Каждая из следующих строк теста содержит перестановку 1, 2, …, n. Последняя строка блока содержит 0.
Последний тест состоит из единственной строки, содержащей 0.

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

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

Решение

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

Код программы: http://ideone.com/2p9seU.

A1048

Задача. Одним из наиболее часто встречающихся видов списка является стек-список, в котором все включения и исключения элементов делаются только на одном его конце — вершине стека. Механизм функционирования стека хорошо отражен в другом его названии — список типа «LIFO» (last in first out) -«последним вошел — первым вышел»).

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

Составить процедуры, реализующие операции занесения элемента в стек и удаления элемента из его вершины.

Тесты:

Ввод Вывод Комментарий
push 5push 7

pop

push 11

pop

exit

okok

7

ok

11

bye

Пройден
push 1pop

pop

push 15

pop

exit

ok1

error

ok

15

bye

Пройден
poppush 7

push 9

push 9

push 1

pop

pop

pop

pop

exit

errorok

ok

ok

ok

1

9

9

7

bye

Пройден

Решение:

В структуре stack, реализованной с помощью массива, опишем операции добавления элемента в стек и удаления элемента из его вершины.

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

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

С работой программы можно ознакомиться здесь.

e-olimp 4513. Сортировка вагонов — B

Сортировка вагонов — B

prb4513   К тупику со стороны пути 1 (см. рисунок) подъехал поезд. Разрешается отцепить от поезда один или сразу несколько первых вагонов и завезти их в тупик (при желании, можно даже завезти в тупик сразу весь поезд). После этого часть из этих вагонов вывезти в сторону пути 2. После этого можно завезти в тупик еще несколько вагонов и снова часть оказавшихся вагонов вывезти в сторону пути 2. И так далее (так, что каждый вагон может лишь один раз заехать с пути 1 в тупик, а затем один раз выехать из тупика на путь 2). Заезжать в тупик с пути 2 или выезжать из тупика на путь 1 запрещается. Нельзя с пути 1 попасть на путь 2, не заезжая в тупик.

Известно, в каком порядке изначально идут вагоны поезда. Требуется с помощью указанных операций сделать так, чтобы вагоны поезда шли по порядку (сначала первый, потом второй и т. д., считая от головы поезда, едущего по пути 2 в сторону от тупика). Напишите программу, определяющую, можно ли это сделать.

 

Технические условия

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

Вводится число [latex]N[/latex] — количество вагонов в поезде [latex]\left(1\leq N\leq100\right)[/latex]. Дальше идут номера вагонов в порядке от головы поезда, едущего по пути 1 в сторону тупика. Вагоны пронумерованы натуральными числами от [latex]1[/latex]  до [latex]N[/latex], каждое из которых встречается ровно один раз.

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

Если сделать так, чтобы вагоны шли в порядке от [latex]1[/latex]  до [latex]N[/latex], считая от головы поезда, когда поезд поедет по пути 2 из тупика, можно, выведите сообщение YES, если это сделать нельзя, выведите NO.

 

Код

Ссылка на код : № 4513 , ссылка на решение на e-olimp : http://www.e-olimp.com.ua/solutions/1935588

 

Стек, дек и очередь неограниченного размера

Задачи: Стек, Очередь и Дек

Решение:

Код для задачи на неограниченный стек:

Код для задачи на неограниченную очередь:

Код для задачи на неограниченный дек:

Засчитанные решения на сайте e-olimp: Стек, Очередь и Дек.

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

Однако в каждой задаче требовалось возможность использования всей оперативной памяти под структуру. В моем решении каждый элемент занимает втрое больше памяти (я подозреваю) чем обычный int, а значит всю оперативную память под числа я использовать не смогу. Тогда можно использовать заранее созданный массив достаточно большого размера, чтобы занять всю выделенную память в 256 мб. Но это не будет считаться «неограниченным» размером. А если использовать ту же структуру с Node, но вместо одного элемента хранить массив? Тогда информацию о следующем и предыдущем массиве нужно так-же хранить, как и с отдельными элементами. Вроде бы меньше памяти будет тратится на хранение дополнительной информации, НО никто не может точно сказать, какого размера массивы должны быть. Если они будут слишком маленькие — большой выгоды такой способ не принесет. Если они будут слишком большими, то есть шанс, что мы не покроем большой кусок памяти, что тоже не очень хорошо.

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

Поэтому я реализовал всё без массивов (хотя вариант с маленькими массивами имеет место быть).

e-olimp 693. Минимум в стеке

Задача e-olimp.com №693. На вход программы подается набор операций со стеком. Каждая операция состоит в добавлении или удалении элемента из стека. После выполнения каждой операции найдите наименьшее число, которое находится в стеке. Сложите все полученные числа и получите ответ. Если после некоторой операции стек оказался пуст, то ничего не прибавляйте к ответу. Если выполнить удаление невозможно, так как стек пуст, то не выполняйте его.

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

Входные данные генерируются в самой программе. На вход подаются параметры для генерации входной последовательности.

Первое число содержит количество операций [latex]n (1\leq n\leq10^{6})[/latex] со стеком. Затем следуют четыре неотрицательных целых числа [latex]a, b, c, x_{0}[/latex] не превосходящие [latex]10000[/latex].

Для получения входных данных генерируем последовательность [latex]x[/latex].

Первое число в генерируемой последовательности [latex]x_{1}[/latex]. Первое, а также каждое следующее число вычисляется из предыдущего по формуле:

[latex]x_{i}=\left(a\cdot x_{i-1}^{2} + b\cdot x_{i-1} + c\right)/100 \bmod{10^{6}}[/latex],

где ‘/‘ — операция целочисленного деления, а ‘[latex] \mod{}[/latex]’ — остаток от деления.

Если [latex]x_{i} \mod{5}<2[/latex], то необходимо удалить число из стека. В противном случае необходимо добавить в стек число [latex]x_{i}[/latex].

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

Выведите результирующую сумму.

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

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

 Пояснение решения

На мой взгляд сложность задачи состояла только в том, чтобы реализовать взятие минимального элемента из стека за [latex]O\left(1 \right)[/latex].

Для этого предполагается хранить в стеке не просто наши элементы, но и минимум в стеке на текущем шаге. Что для этого требовалось, так это не забывать кидать в стек обновлённые минимумы на каждом шаге. Так же помня о том, что стек может быть уже пуст, я изменяла результирующую сумму только в том случае, если в стеке был хотя бы один элемент.

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

Стек неограниченного размера

Реализуйте структуру данных «стек«. Напишите программу, содержащую описание стека и моделирующую работу стека, реализовав все указанные здесь методы.  Программа считывает последовательность команд и в зависимости от команды выполняет ту или иную операцию. После выполнения каждой команды программа должна вывести одну строчку. Возможные команды для программы:
push n
Добавить в стек число n (значение n задается после команды). Программа должна вывести ok.
pop
Удалить из стека последний элемент. Программа должна вывести его значение.
back
Программа должна вывести значение последнего элемента, не удаляя его из стека.
size
Программа должна вывести количество элементов в стеке.
clear
Программа должна очистить стек и вывести ok.
exit
Программа должна вывести bye и завершить работу.

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

Решение

Предлагается реализация стека через связные списки.

Положительные стороны:

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

Отрицательные стороны:

Конструктор срабатывает для каждого узла достаточно медленно, решение уступает в скорости связному списку массивов.
Ссылка на задачу. Ссылка на засчитанное решение.

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