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

13/12/2017 by Курьянов Павел

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

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

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

#include <iostream>
#include <cstring>
#include <stack>
using namespace std;


stack<int> s;
char str[100];
int n;
int main(void)
{
  while(scanf("%s",&str))
  {
    if (strcmp(str,"push") == 0)
    {
      cin>>n;;
      s.push(n);
      cout<<"ok"<<"\n";
    } else
    if (strcmp(str,"pop") == 0)
    {
       cout<<s.top()<<"\n";
      s.pop();
    } else
    if (strcmp(str,"back") == 0)
    {
       cout<<s.top()<<"\n";;
    } else
    if (strcmp(str,"size") == 0)
    {
       cout<<s.size()<<"\n";
    } else
    if (strcmp(str,"clear") == 0)
    {
      while(!s.empty()) 
    s.pop();
      cout<<"ok"<<"\n";
    } else
    {
      cout<<"bye"<<"\n";
      break;
    }
  }
  return 0;
}

#include <iostream>

#include <cstring>

#include <stack>

using namespace std;

stack<int> s;

char str[100];

int n;

int main(void)

{

while(scanf("%s",&str))

{

if (strcmp(str,"push") == 0)

{

cin>>n;;

s.push(n);

cout<<"ok"<<"\n";

} else

if (strcmp(str,"pop") == 0)

{

cout<<s.top()<<"\n";

s.pop();

} else

if (strcmp(str,"back") == 0)

{

cout<<s.top()<<"\n";;

} else

if (strcmp(str,"size") == 0)

{

cout<<s.size()<<"\n";

} else

if (strcmp(str,"clear") == 0)

{

while(!s.empty())

s.pop();

cout<<"ok"<<"\n";

} else

{

cout<<"bye"<<"\n";

break;

}

return 0;

}

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

Ссылки

Related Images:

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

10/12/2017 by Сытников Дан

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

Даны действительные числа [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++:

#include <iostream>
using namespace std;

int main() {
    int k = 0;
    double p[101] = {0};
    double x[200];
    for (int i = 0; i < 200; i++){
        cin >> x[i];
        k = (int)(x[i]*100.0 + 0.5);
        p[k]+=1;
    }
    for (int i = 1; i < 101; i++){
        cout << "p[" << i << "]=" << p[i]/2000.0 << " ";
        if (i%10 == 0) cout << "\n";
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int k = 0;

double p[101] = {0};

double x[200];

for (int i = 0; i < 200; i++){

cin >> x[i];

k = (int)(x[i]*100.0 + 0.5);

p[k]+=1;

}

for (int i = 1; i < 101; i++){

cout << "p[" << i << "]=" << p[i]/2000.0 << " ";

if (i%10 == 0) cout << "\n";

}

return 0;

}

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

import java.util.*;
import java.lang.*;
import java.io.*;
 
/* Name of the class has to be "Main" only if the class is public. */
class Ideone {
    public static void main (String[] args) throws java.lang.Exception {
        int k = 0;
        Scanner in = new Scanner(System.in);
        double[] x = new double[200];
        double[] p = new double[101];
        for (int i = 0; i < 200; i++) {
            x[i] = in.nextDouble();
            k = (int)(x[i]*100.0 + 0.5);
            p[k] += 1;
        }
        for (int i = 1; i < 101; i++) {
            System.out.println("p[" +i + "] = " + p[i]/2000.0);
        }
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */

class Ideone {

public static void main (String[] args) throws java.lang.Exception {

int k = 0;

Scanner in = new Scanner(System.in);

double[] x = new double[200];

double[] p = new double[101];

for (int i = 0; i < 200; i++) {

x[i] = in.nextDouble();

k = (int)(x[i]*100.0 + 0.5);

p[k] += 1;

}

for (int i = 1; i < 101; i++) {

System.out.println("p[" +i + "] = " + p[i]/2000.0);

}

Решение задачи
Для сортировки чисел по полуинтервалам разделим каждое [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

Related Images:

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

01/06/2016 by Максим Носов

Задача

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

Код

#include <iostream> 
using namespace std; 
struct stack {      //создаем структуру
    long long s[100]; 
    int cursor=0;   //указатель
    void push(long long n){  //задаем функцию для каждой из команд: push n, pop, back, size, clear
        s[cursor++]=n; 
    } 
    long long pop(){ 
        return s[--cursor]; 
    } 
    long long back(){ 
        return s[cursor-1]; 
    } 
    unsigned size(){ 
        return cursor; 
    } 
    void clear(){ 
        cursor=0; 
        s[cursor]=0; 
    } 
}; 
int main() { 
    stack x; 
    string b;    //задаем строку
    long long n; 
    while(cin>>b){   //читаем ее
        if(b=="push"){    //выполняем команды, которые встречаем в строке
            cin>>n; 
            x.push(n); 
            cout<<"ok"<<endl; 
        } 
        else if(b=="pop"){ 
            if(x.size()==0){
                cout<<"error"<<endl;
            }
            else
                cout<<x.pop()<<endl; 
        } 
        else if(b=="back"){ 
                if(x.size()==0){
                cout<<"error"<<endl;
            }
            else cout<<x.back()<<endl;  
        } 
        else if(b=="size"){ 
        cout<<x.size()<<endl; 
        } 
        else if(b=="clear"){ 
            x.clear(); 
            cout<<"ok"<<endl; 
        } 
        else if(b=="exit"){ 
            cout<<"bye"<<endl; 
            break; 
        } 
    } 
    return 0; 
}

#include <iostream>

using namespace std;

struct stack { //создаем структуру

long long s[100];

int cursor=0; //указатель

void push(long long n){ //задаем функцию для каждой из команд: push n, pop, back, size, clear

s[cursor++]=n;

}

long long pop(){

return s[--cursor];

}

long long back(){

return s[cursor-1];

}

unsigned size(){

return cursor;

}

void clear(){

cursor=0;

s[cursor]=0;

}

};

int main() {

stack x;

string b; //задаем строку

long long n;

while(cin>>b){ //читаем ее

if(b=="push"){ //выполняем команды, которые встречаем в строке

cin>>n;

x.push(n);

cout<<"ok"<<endl;

}

else if(b=="pop"){

if(x.size()==0){

cout<<"error"<<endl;

}

else

cout<<x.pop()<<endl;

}

else if(b=="back"){

if(x.size()==0){

cout<<"error"<<endl;

}

else cout<<x.back()<<endl;

}

else if(b=="size"){

cout<<x.size()<<endl;

}

else if(b=="clear"){

x.clear();

cout<<"ok"<<endl;

}

else if(b=="exit"){

cout<<"bye"<<endl;

break;

}

return 0;

}

Решение

Создаем структуру в которой реализуем все команды для стека с помощью функций и указателя([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.

Related Images:

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

27/05/2016 by Станислав Коциевский

Задача

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

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

#include <iostream>
using namespace std;

const short int link_array_size = 30; //количество элементов в одном звене

struct link //звено списка
{
    int array [link_array_size]; //массив, элементы которого и являются элементами стека
    short int capacity; //свободное место в массиве
    link* next; //адресс следующего звена
    link () //создание звена
    {
        capacity = link_array_size;
    }
    void link_push (int n)
    {
        capacity--;
        array [capacity] = n; 
    }
    int link_pop ()
    {
        capacity++;
        return array[capacity-1]; 
    }
};

struct stack //сам стек
{
    link* head; //указатель на первое звено 
    int s; //количество элементов в стеке
    stack (link* h = NULL) // создание стека
    {
        head = h;
        s = 0;
    }
    void add_link() //добавление звена
    {
        link* a = new link;
        a->next = head;
        head = a;
    }
    void destroy_link() //удаление звена 
    {
        link * a = head;
        head = a->next;
        delete a;
    }
    void push (int n)
    {
        if ((head == NULL)||(head->capacity == 0))
        {
            add_link();
        }
        head->link_push(n);
        s++;
    }
    int pop ()
    {
        if (s>0)
        {
            int n = (head->link_pop());
            if (head->capacity == link_array_size)
            {
            destroy_link();
            }
            s--;
            return n;
        }
        else
        {
            throw 0;
        }
    }
    int back()
    {
        if (s>0)
        {
            return head->array[head->capacity];
        }
        else
        {
            throw 0;
        }
    }
    int size()
    {
        return s;
    }
    void clear()
    {
        while (head!=NULL)
        {
            destroy_link();
        }
        s = 0;
    }
};

int main()
{
    string s;
    stack Q;
    while (cin>>s)
    {
        if (s == "push")
        {
            int n;
            cin>>n;
            Q.push(n);
            cout<<"ok"<<endl;
        }
        if (s == "pop")
        {
            try
            {
                cout<<Q.pop()<<endl;
            }
            catch (int e)
            {
                cout<<"error"<<endl;
            }
        }
        if (s == "back")
        {
            try
            {
                cout<<Q.back()<<endl;
            }
            catch (int e)
            {
                cout<<"error"<<endl;
            }
        }
        if (s == "size")
        {
            cout<<Q.size()<<endl;
        }
        if (s == "clear")
        {
            Q.clear();
            cout<<"ok"<<endl;
        }
        if (s == "exit")
        {
            cout<<"bye"<<endl;
            break;
        }
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

#include <iostream>

using namespace std;

const short int link_array_size = 30; //количество элементов в одном звене

struct link //звено списка

{

int array [link_array_size]; //массив, элементы которого и являются элементами стека

short int capacity; //свободное место в массиве

link* next; //адресс следующего звена

link () //создание звена

{

capacity = link_array_size;

}

void link_push (int n)

{

capacity--;

array [capacity] = n;

}

int link_pop ()

{

capacity++;

return array[capacity-1];

}

};

struct stack //сам стек

{

link* head; //указатель на первое звено

int s; //количество элементов в стеке

stack (link* h = NULL) // создание стека

{

head = h;

s = 0;

}

void add_link() //добавление звена

{

link* a = new link;

a->next = head;

head = a;

}

void destroy_link() //удаление звена

{

link * a = head;

head = a->next;

delete a;

}

void push (int n)

{

if ((head == NULL)||(head->capacity == 0))

{

add_link();

}

head->link_push(n);

s++;

}

int pop ()

{

if (s>0)

{

int n = (head->link_pop());

if (head->capacity == link_array_size)

{

destroy_link();

}

s--;

return n;

}

else

{

throw 0;

}

int back()

{

if (s>0)

{

return head->array[head->capacity];

}

else

{

throw 0;

}

int size()

{

return s;

}

void clear()

{

while (head!=NULL)

{

destroy_link();

}

s = 0;

}

};

int main()

{

string s;

stack Q;

while (cin>>s)

{

if (s == "push")

{

int n;

cin>>n;

Q.push(n);

cout<<"ok"<<endl;

}

if (s == "pop")

{

try

{

cout<<Q.pop()<<endl;

}

catch (int e)

{

cout<<"error"<<endl;

}

if (s == "back")

{

try

{

cout<<Q.back()<<endl;

}

catch (int e)

{

cout<<"error"<<endl;

}

if (s == "size")

{

cout<<Q.size()<<endl;

}

if (s == "clear")

{

Q.clear();

cout<<"ok"<<endl;

}

if (s == "exit")

{

cout<<"bye"<<endl;

break;

}

return 0;

}

Решение

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

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

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

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

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

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

Related Images:

AL6

26/05/2016 by Андрей Яроцкий

Задача AL6

Условие

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

Тесты

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

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

#include <iostream>
#include <string>
#include <cstring>
#include <cmath>
using namespace std;
 
struct stack{
        char *bkt = new char;
        int cur;
        stack(){cur = 0;}
        void push(char x){
            bkt[cur++] = x;
        }
        void pop(){
            cur--;
        }
        char back(){
            return bkt[cur-1];
        }
        int size(){
            return cur;
        }
};
 
int main() {
    string brace;
    cin >> brace;
    stack x;
    if(brace[0] == '(' || brace[0] == '{' || brace[0] == '[') x.push(brace[0]); //Правильное выражение начинается только с открывающей скобки
    else{
        if(brace == "") cout << "YES";//Выражение без скобок также првильное
        else cout << "NO";
        return 0;
    }
    for(int i = 1; i < brace.length(); i++){
        if(brace[i] == '(' || brace[i] == '{' || brace[i] == '['){ //Любую открывающую скобку добавляем в стек
            x.push(brace[i]);
        }
        else if(abs(brace[i] - x.back()) < 3 && x.size() != 0){//Модуль разницы скобок одного типа меньше трех
            x.pop();
        }
        else{
            cout << "NO";
            return 0;
        }
    }
    if(x.size() == 0) cout << "YES";//Правильное арифметическое выражение получим при пустом стэке
    else cout << "NO";
    return 0;
}

#include <iostream>

#include <string>

#include <cstring>

#include <cmath>

using namespace std;

struct stack{

char *bkt = new char;

int cur;

stack(){cur = 0;}

void push(char x){

bkt[cur++] = x;

}

void pop(){

cur--;

}

char back(){

return bkt[cur-1];

}

int size(){

return cur;

}

};

int main() {

string brace;

cin >> brace;

stack x;

if(brace[0] == '(' || brace[0] == '{' || brace[0] == '[') x.push(brace[0]); //Правильное выражение начинается только с открывающей скобки

else{

if(brace == "") cout << "YES";//Выражение без скобок также првильное

else cout << "NO";

return 0;

}

for(int i = 1; i < brace.length(); i++){

if(brace[i] == '(' || brace[i] == '{' || brace[i] == '['){ //Любую открывающую скобку добавляем в стек

x.push(brace[i]);

}

else if(abs(brace[i] - x.back()) < 3 && x.size() != 0){//Модуль разницы скобок одного типа меньше трех

x.pop();

}

else{

cout << "NO";

return 0;

}

if(x.size() == 0) cout << "YES";//Правильное арифметическое выражение получим при пустом стэке

else cout << "NO";

return 0;

}

Решение

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

Ссылки

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

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

Related Images:

AL15. Лабиринт

11/04/2016 by Сплошнов Кирилл

Условие

Матрица размера [latex]n\times 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 \leqslant 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 \leqslant n, m \leqslant 10^4[/latex]. Количество входов [latex]k[/latex] равно кол-ву выходов, [latex]1 \leqslant k \leqslant \min(1000, n)[/latex]. Число [latex]k[/latex] не является частью входных данных (не подается на вход программы).

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

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

Замечания

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

C++

void print(int n, int m, int** matrix)

1

void print(int n, int m, int** matrix)

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

Тесты

№ теста	Входные данные	Выходные данные	Пояснение (маршрут)
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

Алгоритм

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

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

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

stack<pair<int,int>> findRoute(int n, int m, int** matrix, int begin)

1	stack<pair<int,int>> findRoute(int n, int m, int** matrix, int begin)

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

bool search(int n, int m, int** matrix, stack<pair<int,int>>& route, int dir)

1	bool search(int n, int m, int** matrix, stack<pair<int,int>>& route, int dir)

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

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

C++

priorityDirs = new int[3]{left, down, right};

42

priorityDirs = new int[3]{left, down, right};

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

Код

#include <iostream>
#include <stack>
#include <utility>
#define down 10
#define left -1
#define right 1
#define up -10
using namespace std;

void print(int n, int m, int** matrix)
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (matrix[i][j] == 0 || matrix[i][j] == 1)
                cout << matrix[i][j] << " ";
            else
                cout << (char)matrix[i][j] << " ";
        }
        cout << endl;
    }
}

bool search(int n, int m, int** matrix, stack<pair<int,int>>& route, int dir)
{
    pair<int, int> npos = make_pair(dir / 10 + route.top().first, dir % 10 + route.top().second);
    if (npos.first < 0 || npos.first >= n || npos.second < 0 || npos.second >= m || matrix[npos.first][npos.second] != 0)
        return false;
    else
    {
        route.push(npos);
        matrix[npos.first][npos.second] = 1; //чтобы при построении маршрута нельзя было вернутся в предыдущие вершины
        if (npos.first == n - 1)
            return true;
        else
        {
            int* priorityDirs;
            switch (dir)
            {
                case down:
                    priorityDirs = new int[3]{left, down, right};
                    break;
                case left:
                    priorityDirs = new int[3]{left, down, up};
                    break;
                case right:
                    priorityDirs = new int[3]{down, right, up};
                    break;
                case up:
                    priorityDirs = new int[3]{left, right, up};
                    break;
            }
            bool found = true;
            for (int i = 0; i < 3; i++)
            {
                found = search(n, m, matrix, route, priorityDirs[i]);
                if (found)
                    return true;
            }
            matrix[npos.first][npos.second] = 0; //если ячейка не подходит, убираем ее из маршрута (освобождаем)
            route.pop();
            return false;
        }
    }
}

stack<pair<int,int>> findRoute(int n, int m, int** matrix, int begin)
{
    stack<pair<int,int>> route;
    route.push(make_pair(0, begin));
    if (n != 1 && !search(n, m, matrix, route, down)) //n != 1 для корректного ответа на тесты вида №10
        throw -1;
    return route;
}

int main() 
{
    ios::sync_with_stdio(false);
    int n, m;
    scanf("%d%d", &n, &m);
    int** matrix = new int*[n];
    for (int i = 0; i < n; i++)
        matrix[i] = new int[m];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            scanf("%d", &matrix[i][j]);
    bool possible = true;
    int symbol = -1; //определяет символ, которым будет отмечен маршрут человека при необходимости вывода лабиринта на экран
    for (int i = 0; i < m; i++)
    {
        if (matrix[0][i] == 0)
        {
            symbol++;
            try
            {
                stack<pair<int,int>> route = findRoute(n, m, matrix, i);
                while (!route.empty()) //вынимаем из стека координаты пройденных ячеек и отмечаем их в матрице
                {
                    pair<int, int> pos = route.top(); 
                    matrix[pos.first][pos.second] = 'a' + symbol; //для удобства при необходимости вывода маршрута
                    route.pop();
                }
            }
            catch (...)
            {
                possible = false;
                break;
            }
        }
    }
    cout << (possible ? "YES" : "NO") << endl;
    /*
    if (possible)
        print(n, m, matrix);
    */
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

#include <iostream>

#include <stack>

#include <utility>

#define down 10

#define left -1

#define right 1

#define up -10

using namespace std;

void print(int n, int m, int** matrix)

{

for (int i = 0; i < n; i++)

{

for (int j = 0; j < m; j++)

{

if (matrix[i][j] == 0 || matrix[i][j] == 1)

cout << matrix[i][j] << " ";

else

cout << (char)matrix[i][j] << " ";

}

cout << endl;

}

bool search(int n, int m, int** matrix, stack<pair<int,int>>& route, int dir)

{

pair<int, int> npos = make_pair(dir / 10 + route.top().first, dir % 10 + route.top().second);

if (npos.first < 0 || npos.first >= n || npos.second < 0 || npos.second >= m || matrix[npos.first][npos.second] != 0)

return false;

else

{

route.push(npos);

matrix[npos.first][npos.second] = 1; //чтобы при построении маршрута нельзя было вернутся в предыдущие вершины

if (npos.first == n - 1)

return true;

else

{

int* priorityDirs;

switch (dir)

{

case down:

priorityDirs = new int[3]{left, down, right};

break;

case left:

priorityDirs = new int[3]{left, down, up};

break;

case right:

priorityDirs = new int[3]{down, right, up};

break;

case up:

priorityDirs = new int[3]{left, right, up};

break;

}

bool found = true;

for (int i = 0; i < 3; i++)

{

found = search(n, m, matrix, route, priorityDirs[i]);

if (found)

return true;

}

matrix[npos.first][npos.second] = 0; //если ячейка не подходит, убираем ее из маршрута (освобождаем)

route.pop();

return false;

}

stack<pair<int,int>> findRoute(int n, int m, int** matrix, int begin)

{

stack<pair<int,int>> route;

route.push(make_pair(0, begin));

if (n != 1 && !search(n, m, matrix, route, down)) //n != 1 для корректного ответа на тесты вида №10

throw -1;

return route;

}

int main()

{

ios::sync_with_stdio(false);

int n, m;

scanf("%d%d", &n, &m);

int** matrix = new int*[n];

for (int i = 0; i < n; i++)

matrix[i] = new int[m];

for (int i = 0; i < n; i++)

for (int j = 0; j < m; j++)

scanf("%d", &matrix[i][j]);

bool possible = true;

int symbol = -1; //определяет символ, которым будет отмечен маршрут человека при необходимости вывода лабиринта на экран

for (int i = 0; i < m; i++)

{

if (matrix[0][i] == 0)

{

symbol++;

try

{

stack<pair<int,int>> route = findRoute(n, m, matrix, i);

while (!route.empty()) //вынимаем из стека координаты пройденных ячеек и отмечаем их в матрице

{

pair<int, int> pos = route.top();

matrix[pos.first][pos.second] = 'a' + symbol; //для удобства при необходимости вывода маршрута

route.pop();

}

catch (...)

{

possible = false;

break;

}

cout << (possible ? "YES" : "NO") << endl;

if (possible)

print(n, m, matrix);

return 0;

}

Ссылки

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

Related Images:

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

20/03/2016 by Таня Корнилова

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

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

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

#include <iostream>
#include <string>
using namespace std;
#define SIZE 100

struct stack {
    int storage[SIZE];
    int cursor = 0; // указатель на верхнюю незаполненную ячейку
    void push (int n) {
        storage[cursor] = n;
        cursor++;
    }
    int pop () {
        return storage[--cursor];
    }
    int back () {
        return storage[cursor-1];
    }
    unsigned int size () {
        return cursor;
    }
    void clear () {
        cursor = 0;
    }
};
int main () {
    stack s;
    string str;
    int n;
    while (cin >> str) {
        if (str == "push") {
            cin >> n;
            s.push(n);
            cout << "ok" << endl;
        }
        else if (str == "pop") cout << s.pop() << endl;
        else if (str == "back") cout << s.back() << endl;
        else if (str == "size") cout << s.size() << endl;
        else if (str == "clear") {
            s.clear();
            cout << "ok" << endl;
        }
        else if (str == "exit") {
            cout << "bye" << endl;
            break;
        }
    }
    return 0;
}

#include <iostream>

#include <string>

using namespace std;

#define SIZE 100

struct stack {

int storage[SIZE];

int cursor = 0; // указатель на верхнюю незаполненную ячейку

void push (int n) {

storage[cursor] = n;

cursor++;

}

int pop () {

return storage[--cursor];

}

int back () {

return storage[cursor-1];

}

unsigned int size () {

return cursor;

}

void clear () {

cursor = 0;

}

};

int main () {

stack s;

string str;

int n;

while (cin >> str) {

if (str == "push") {

cin >> n;

s.push(n);

cout << "ok" << endl;

}

else if (str == "pop") cout << s.pop() << endl;

else if (str == "back") cout << s.back() << endl;

else if (str == "size") cout << s.size() << endl;

else if (str == "clear") {

s.clear();

cout << "ok" << endl;

}

else if (str == "exit") {

cout << "bye" << endl;

break;

}

return 0;

}

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

Решение

Реализуем стек с помощью массива, указателя на на верхнюю незаполненную ячейку массива ([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], который заканчивает выполнение цикла, в котором запрашиваются команды.

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

Related Images:

e-olymp 1776. Рельсы

29/06/2015 by Куленюк Денис Віталійович

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

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

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

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

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

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

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

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

Решение

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

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

#include <stdio.h>           // по какой-то причине e-olimp, не хотел видеть getchar
#include <iostream>
#include <vector>
#include <cstring>
#include <sstream>

using namespace std;

int main(){
    int n;                      // Количество вагонов в поезде
    int number;                 // отвечает за нумерацию вагонов
    stringstream stream_my;     // принимает поезд из потока ввода, и выдает под одному вагону
    while( (cin >> n, getchar(), n != 0) ){       // Считываем количество вагонов
        string s;                       // Перед тем как кинуть в поток, мы сохраняем вагон в строке
        getline(cin, s, '\n');
        while(s != "0"){
            vector<int> stalemate;
            stream_my.str("");
            stream_my.clear();                      // очищаем поток и збрасываем флаги
            stream_my << s;
            stream_my >> number;                  // мы должны считывать number, а закидывать -- i
            for( int i=1 ; i<=n ; i++ ){         //
                stalemate.push_back(i);                 // кидаем в тупик вагоны по порядку, пока не будет найден number
                while(!stalemate.empty() && number == stalemate.back()){        // пока в тупике вагоны идут по порядку вывозим их от туда
                    stalemate.pop_back();
                    stream_my >> number;
                }
            }
            cout << (stalemate.empty()? "Yes" : "No") << endl;      // Если нам что-то помешало вывезти все вагоны из тупика, то ответ No
            getline(cin, s, '\n');
        }
        cout << endl;
    }

}

#include <stdio.h> // по какой-то причине e-olimp, не хотел видеть getchar

#include <iostream>

#include <vector>

#include <cstring>

#include <sstream>

using namespace std;

int main(){

int n; // Количество вагонов в поезде

int number; // отвечает за нумерацию вагонов

stringstream stream_my; // принимает поезд из потока ввода, и выдает под одному вагону

while( (cin >> n, getchar(), n != 0) ){ // Считываем количество вагонов

string s; // Перед тем как кинуть в поток, мы сохраняем вагон в строке

getline(cin, s, '\n');

while(s != "0"){

vector<int> stalemate;

stream_my.str("");

stream_my.clear(); // очищаем поток и збрасываем флаги

stream_my << s;

stream_my >> number; // мы должны считывать number, а закидывать -- i

for( int i=1 ; i<=n ; i++ ){ //

stalemate.push_back(i); // кидаем в тупик вагоны по порядку, пока не будет найден number

while(!stalemate.empty() && number == stalemate.back()){ // пока в тупике вагоны идут по порядку вывозим их от туда

stalemate.pop_back();

stream_my >> number;

}

cout << (stalemate.empty()? "Yes" : "No") << endl; // Если нам что-то помешало вывезти все вагоны из тупика, то ответ No

getline(cin, s, '\n');

}

cout << endl;

}

Related Images:

A1048

11/06/2015 by Кваша Дар`я Михайлівна

Задача. Одним из наиболее часто встречающихся видов списка является стек-список, в котором все включения и исключения элементов делаются только на одном его конце — вершине стека. Механизм функционирования стека хорошо отражен в другом его названии — список типа «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	Пройден

#include <iostream>
using namespace std;
 
struct stack {
   int size=0;//размер
   int storage[1000];//массив
   void push (int n)//добавление эл-та
   {
        storage[size]=n; 
        size++; 
   }
   int pop () //удаление эл-та
   {
        int b=storage[size-1]; 
        size--; 
        return b;
   }
};
 
int main ()
{
   stack st;
   string s;
   while (55) 
   {
       cin >> s;
       if (s=="push") 
       {
           int n;
           cin >> n;
           st.push(n);
           cout << "ok\n";
       }
       if (s=="pop") 
       {
           if (st.size==0) 
           {
               cout << "error\n";
           }
           else cout << st.pop() << endl;
       }   
       if (s=="exit") 
       {
           cout << "bye\n";
           break;
       }
   }
   return 0;
}

#include <iostream>

using namespace std;

struct stack {

int size=0;//размер

int storage[1000];//массив

void push (int n)//добавление эл-та

{

storage[size]=n;

size++;

}

int pop () //удаление эл-та

{

int b=storage[size-1];

size--;

return b;

}

};

int main ()

{

stack st;

string s;

while (55)

{

cin >> s;

if (s=="push")

{

int n;

cin >> n;

st.push(n);

cout << "ok\n";

}

if (s=="pop")

{

if (st.size==0)

{

cout << "error\n";

}

else cout << st.pop() << endl;

}

if (s=="exit")

{

cout << "bye\n";

break;

}

return 0;

}

Решение:

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

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

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

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

Related Images:

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

28/04/2015 by Кібакова Надія Олександрівна

Сортировка вагонов — 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.

Код

#include <iostream>
using namespace std;
 struct stack{                           //стек
 	int truck[100];
 	int length = 0;
 	int pop (){return truck[--length];}
 	void push (int x){truck[length++] = x;}
 	int front () {return truck[length-1];}
 	int size () {return length;}
 	}car; 
int main() {
	int amount_n;
	cin >> amount_n;                 //Ввод (количество вагонов)
	int n;
	int count = 1;
	while (cin >> n){                //Цикл (для ввода нового вагона)
		car.push(n);             //заводим в стек новый вагон 
		if (n == count){count++; car.pop();} //проверяем, если вагон подходит, то выводим его на путь 2
		while (car.size() > 0){  //т.к. перед подходящим вагоном может стоять следующий подходящий вагон или несколько вагонов ,то пока стек не пуст будем проверять последние вагоны в стеке
		if (car.front() == count){count++; car.pop();}	//если вагон подходит выводим на путь 2
		else break;
		}
	}
	
	if (car.size() == 0) {cout << "YES" << endl;}	//если стек пуст, то все вагоны были выведены на путь 2
	else cout << "NO" << endl;
	
	return 0;
}

#include <iostream>

using namespace std;

struct stack{ //стек

int truck[100];

int length = 0;

int pop (){return truck[--length];}

void push (int x){truck[length++] = x;}

int front () {return truck[length-1];}

int size () {return length;}

}car;

int main() {

int amount_n;

cin >> amount_n; //Ввод (количество вагонов)

int n;

int count = 1;

while (cin >> n){ //Цикл (для ввода нового вагона)

car.push(n); //заводим в стек новый вагон

if (n == count){count++; car.pop();} //проверяем, если вагон подходит, то выводим его на путь 2

while (car.size() > 0){ //т.к. перед подходящим вагоном может стоять следующий подходящий вагон или несколько вагонов ,то пока стек не пуст будем проверять последние вагоны в стеке

if (car.front() == count){count++; car.pop();} //если вагон подходит выводим на путь 2

else break;

}

if (car.size() == 0) {cout << "YES" << endl;} //если стек пуст, то все вагоны были выведены на путь 2

else cout << "NO" << endl;

return 0;

}

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

Related Images:

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

19/03/2015 by Бронфен-Бова Роман

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

Решение:

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

#include <iostream>
#include <string>
using namespace std;

struct Node{
	Node * prev;
	int x;
	Node(){prev = nullptr; x = 0;}
	Node(Node * a, int b){prev = a; x = b;}
};

struct stack{
	private:
		Node * Head = nullptr;
		int Size = 0;
	
	public: 
	int size(){
		return Size;
	}
	void push(int p){
		Node * NewHead = new Node(Head,p);
		Head = NewHead;
		Size++;
	}
	int back(){
		if(Size){return Head->x;}
		else{return 0;}
	}
	int pop(){
		if(Size){
			int x = Head->x;
			Node * NewHead = Head->prev;
			delete Head;
			Head = NewHead;
			Size--;
			return x;
		}else{
			return 0;
		}
	}
	void clear(){
		while(Size > 0){
			Node * NewHead = Head->prev;
			delete Head;
			Head = NewHead;
			Size--;
		}
	}
};

int main() {
	stack myStack;
	while(true){
		string s; cin >> s;
		if(s == "exit"){cout << "bye\n"; break;}
		else if(s == "push"){
			int inp; cin >> inp;
			myStack.push(inp);
			cout << "ok\n";
		}else if(s == "back"){
			if(myStack.size()){
				cout << myStack.back() << endl;
			}else{
				cout << "error\n";
			}
		}else if(s == "size"){
			cout << myStack.size() << endl;
		}else if(s == "pop"){
			if(myStack.size()){
				cout << myStack.pop() << endl;
			}else{
				cout << "error\n";
			}
		}else if(s == "clear"){
			cout << "ok\n";
			myStack.clear();
		}
	}
	return 0;
}

#include <iostream>

#include <string>

using namespace std;

struct Node{

Node * prev;

int x;

Node(){prev = nullptr; x = 0;}

Node(Node * a, int b){prev = a; x = b;}

};

struct stack{

private:

Node * Head = nullptr;

int Size = 0;

public:

int size(){

return Size;

}

void push(int p){

Node * NewHead = new Node(Head,p);

Head = NewHead;

Size++;

}

int back(){

if(Size){return Head->x;}

else{return 0;}

}

int pop(){

if(Size){

int x = Head->x;

Node * NewHead = Head->prev;

delete Head;

Head = NewHead;

Size--;

return x;

}else{

return 0;

}

void clear(){

while(Size > 0){

Node * NewHead = Head->prev;

delete Head;

Head = NewHead;

Size--;

}

};

int main() {

stack myStack;

while(true){

string s; cin >> s;

if(s == "exit"){cout << "bye\n"; break;}

else if(s == "push"){

int inp; cin >> inp;

myStack.push(inp);

cout << "ok\n";

}else if(s == "back"){

if(myStack.size()){

cout << myStack.back() << endl;

}else{

cout << "error\n";

}

}else if(s == "size"){

cout << myStack.size() << endl;

}else if(s == "pop"){

if(myStack.size()){

cout << myStack.pop() << endl;

}else{

cout << "error\n";

}

}else if(s == "clear"){

cout << "ok\n";

myStack.clear();

}

return 0;

}

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

#include <iostream>
#include <string>
using namespace std;

struct Node{
	Node * prev;
	int x;
	Node(){prev = nullptr; x = 0;}
	Node(Node * a, int b){prev = a; x = b;}
};

struct queue{
	private:
		Node * Front = nullptr;
		Node * Back = nullptr;
		int Size = 0;
		
	public: 
	
	int size(){
		return Size;
	}
	void push(int p){
		if(Size == 0){
			Node * NewNode = new Node(Back,p);
			Front = NewNode;
			Back = NewNode;
		}else{
			Node * NewNode = new Node(nullptr, p);
			Back->prev = NewNode;
			Back = NewNode;
		}
		Size++;
	}
	int front(){
		if(Size){return Front->x;}
		else{return 0;}
	}
	int pop(){
		if(Size){
			int x = Front->x;
			Node * NewNode = Front->prev;
			delete Front;
			Front = NewNode;
			Size--;
			return x;
		}else{
			return 0;
		}
	}
	void clear(){
		while(Size > 0){
			Node * NewNode = Front->prev;
			delete Front;
			Front = NewNode;
			Size--;
		}
		Front = nullptr;
		Back = nullptr;
	}
};

int main() {
	queue Q;
	while(true){
		string s; cin >> s;
		if(s == "exit"){cout << "bye\n"; break;}
		else if(s == "push"){
			int inp; cin >> inp;
			Q.push(inp);
			cout << "ok\n";
		}else if(s == "front"){
			if(Q.size()){
				cout << Q.front() << endl;
			}else{
				cout << "error\n";
			}
		}else if(s == "size"){
			cout << Q.size() << endl;
		}else if(s == "pop"){
			if(Q.size()){
				cout << Q.pop() << endl;
			}else{
				cout << "error\n";
			}
		}else if(s == "clear"){
			cout << "ok\n";
			Q.clear();
		}
		
		
	}

	return 0;
}

#include <iostream>

#include <string>

using namespace std;

struct Node{

Node * prev;

int x;

Node(){prev = nullptr; x = 0;}

Node(Node * a, int b){prev = a; x = b;}

};

struct queue{

private:

Node * Front = nullptr;

Node * Back = nullptr;

int Size = 0;

public:

int size(){

return Size;

}

void push(int p){

if(Size == 0){

Node * NewNode = new Node(Back,p);

Front = NewNode;

Back = NewNode;

}else{

Node * NewNode = new Node(nullptr, p);

Back->prev = NewNode;

Back = NewNode;

}

Size++;

}

int front(){

if(Size){return Front->x;}

else{return 0;}

}

int pop(){

if(Size){

int x = Front->x;

Node * NewNode = Front->prev;

delete Front;

Front = NewNode;

Size--;

return x;

}else{

return 0;

}

void clear(){

while(Size > 0){

Node * NewNode = Front->prev;

delete Front;

Front = NewNode;

Size--;

}

Front = nullptr;

Back = nullptr;

}

};

int main() {

queue Q;

while(true){

string s; cin >> s;

if(s == "exit"){cout << "bye\n"; break;}

else if(s == "push"){

int inp; cin >> inp;

Q.push(inp);

cout << "ok\n";

}else if(s == "front"){

if(Q.size()){

cout << Q.front() << endl;

}else{

cout << "error\n";

}

}else if(s == "size"){

cout << Q.size() << endl;

}else if(s == "pop"){

if(Q.size()){

cout << Q.pop() << endl;

}else{

cout << "error\n";

}

}else if(s == "clear"){

cout << "ok\n";

Q.clear();

}

return 0;

}

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

#include <iostream>
#include <string>
using namespace std;

struct Node{
	Node * prev;
	Node * next;
	int x;
	Node(){prev = nullptr; next = nullptr; x = 0;}
	Node(Node * a, Node * b, int c){prev = a; next = b; x = c;}
};

struct deque{
	private:
		Node * Front = nullptr;
		Node * Back = nullptr;
		int Size = 0;
		
	public: 
	
	int size(){
		return Size;
	}
	void push_back(int p){
		if(Size == 0){
			Node * NewNode = new Node(Back,Front,p);
			Front = NewNode;
			Back = NewNode;
		}else{
			Node * NewNode = new Node(nullptr, Back, p);
			Back->prev = NewNode;
			Back = NewNode;
		}
		Size++;
	}
	void push_front(int p){
		if(Size == 0){
			Node * NewNode = new Node(Back,Front,p);
			Front = NewNode;
			Back = NewNode;
		}else{
			Node * NewNode = new Node(Front, nullptr, p);
			Front->next = NewNode;
			Front = NewNode;
		}
		Size++;
	}
	int back(){
		if(Size){return Back->x;}
		else{return 0;}
	}
	int front(){
		if(Size){return Front->x;}
		else{return 0;}
	}
	int pop_front(){
		if(Size){
			int x = Front->x;
			Node * NewNode = Front->prev;
			delete Front;
			Front = NewNode;
			Size--;
			return x;
		}else{
			return 0;
		}
	}
	int pop_back(){
		if(Size){
			int x = Back->x;
			Node * NewNode = Back->next;
			delete Back;
			Back = NewNode;
			Size--;
			return x;
		}else{
			return 0;
		}
	}
	void clear(){
		while(Size > 0){
			Node * NewNode = Front->prev;
			delete Front;
			Front = NewNode;
			Size--;
		}
		Front = nullptr;
		Back = nullptr;
	}
};

int main() {
	deque D;
	while(true){
		string s; cin >> s;
		if(s == "exit"){cout << "bye\n"; break;}
		else if(s == "push_back"){
			int inp; cin >> inp;
			D.push_back(inp);
			cout << "ok\n";
		}else if(s == "push_front"){
			int inp; cin >> inp;
			D.push_front(inp);
			cout << "ok\n";
		}else if(s == "front"){
			if(D.size()){
				cout << D.front() << endl;
			}else{
				cout << "error\n";
			}
		}else if(s == "back"){
			if(D.size()){
				cout << D.back() << endl;
			}else{
				cout << "error\n";
			}
		}else if(s == "size"){
			cout << D.size() << endl;
		}else if(s == "pop_front"){
			if(D.size()){
				cout << D.pop_front() << endl;
			}else{
				cout << "error\n";
			}
		}else if(s == "pop_back"){
			if(D.size()){
				cout << D.pop_back() << endl;
			}else{
				cout << "error\n";
			}
		}else if(s == "clear"){
			cout << "ok\n";
			D.clear();
		}
	}
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

#include <iostream>

#include <string>

using namespace std;

struct Node{

Node * prev;

Node * next;

int x;

Node(){prev = nullptr; next = nullptr; x = 0;}

Node(Node * a, Node * b, int c){prev = a; next = b; x = c;}

};

struct deque{

private:

Node * Front = nullptr;

Node * Back = nullptr;

int Size = 0;

public:

int size(){

return Size;

}

void push_back(int p){

if(Size == 0){

Node * NewNode = new Node(Back,Front,p);

Front = NewNode;

Back = NewNode;

}else{

Node * NewNode = new Node(nullptr, Back, p);

Back->prev = NewNode;

Back = NewNode;

}

Size++;

}

void push_front(int p){

if(Size == 0){

Node * NewNode = new Node(Back,Front,p);

Front = NewNode;

Back = NewNode;

}else{

Node * NewNode = new Node(Front, nullptr, p);

Front->next = NewNode;

Front = NewNode;

}

Size++;

}

int back(){

if(Size){return Back->x;}

else{return 0;}

}

int front(){

if(Size){return Front->x;}

else{return 0;}

}

int pop_front(){

if(Size){

int x = Front->x;

Node * NewNode = Front->prev;

delete Front;

Front = NewNode;

Size--;

return x;

}else{

return 0;

}

int pop_back(){

if(Size){

int x = Back->x;

Node * NewNode = Back->next;

delete Back;

Back = NewNode;

Size--;

return x;

}else{

return 0;

}

void clear(){

while(Size > 0){

Node * NewNode = Front->prev;

delete Front;

Front = NewNode;

Size--;

}

Front = nullptr;

Back = nullptr;

}

};

int main() {

deque D;

while(true){

string s; cin >> s;

if(s == "exit"){cout << "bye\n"; break;}

else if(s == "push_back"){

int inp; cin >> inp;

D.push_back(inp);

cout << "ok\n";

}else if(s == "push_front"){

int inp; cin >> inp;

D.push_front(inp);

cout << "ok\n";

}else if(s == "front"){

if(D.size()){

cout << D.front() << endl;

}else{

cout << "error\n";

}

}else if(s == "back"){

if(D.size()){

cout << D.back() << endl;

}else{

cout << "error\n";

}

}else if(s == "size"){

cout << D.size() << endl;

}else if(s == "pop_front"){

if(D.size()){

cout << D.pop_front() << endl;

}else{

cout << "error\n";

}

}else if(s == "pop_back"){

if(D.size()){

cout << D.pop_back() << endl;

}else{

cout << "error\n";

}

}else if(s == "clear"){

cout << "ok\n";

D.clear();

}

return 0;

}

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

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

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

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

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

Related Images:

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

19/03/2015 by Ілларіонова Марія Валеріївна

Задача 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].

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

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

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

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

#include <iostream>
#include <stack>
#include <utility>
#include <algorithm>
using namespace std;
 
const long long mod=1000000;
stack <pair <long long, long long> > st;
 
int main() {
	long long n, a, b, c, x, ans=0;
	cin >> n >> a >> b >> c >> x;
	while (n--) {
		x=(a*x*x+b*x+c)/100%mod;
		if (x%5<2) {
			if (!st.empty()) st.pop();
		}
		else {
			long long mini= st.empty() ? x : min(x, st.top().second);
			st.push(make_pair(x, mini));
		}
 
		if (!st.empty()) ans+=st.top().second;
	}
	cout << ans << endl;
	return 0;
}

#include <iostream>

#include <stack>

#include <utility>

#include <algorithm>

using namespace std;

const long long mod=1000000;

stack <pair <long long, long long> > st;

int main() {

long long n, a, b, c, x, ans=0;

cin >> n >> a >> b >> c >> x;

while (n--) {

x=(a*x*x+b*x+c)/100%mod;

if (x%5<2) {

if (!st.empty()) st.pop();

}

else {

long long mini= st.empty() ? x : min(x, st.top().second);

st.push(make_pair(x, mini));

}

if (!st.empty()) ans+=st.top().second;

}

cout << ans << endl;

return 0;

}

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

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

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

Related Images:

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

18/03/2015 by Ілларіонова Марія Валеріївна

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

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

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

Решение

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

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

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

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

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

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

#include <iostream>
#include <string>
using namespace std;

struct node {
   int value=0;
   node* prev=NULL;
   node(int val, node* prv): value(val), prev(prv) {} // конструктор нашего верхнего элемента в стеке
};

struct stack {
   int cnt=0;
   node* top=NULL;
   void push (int n) {
       top = new node(n, top); // когда создаём новую вершину, но присваиваем ей цену, а предыдущей записываем прошлую топовую вершину
       cnt++;
   }
   bool empty() {
       return cnt == 0;
   }
   int pop() {
       node* prev = top->prev; // записываем предыдущий узел во временную переменную
       int topVal = top->value;
       delete top; // удаляем последний элемент стека
       top = prev; // говорим, что он теперь равен прдыдущему
       cnt--;
       return topVal;
   }
   int back() {
       return top->value;
   }
   int size() {
       return cnt;
   }
   void clear() {
       while (!empty()) pop();
   }
};

int main() {
   ios::sync_with_stdio(false);
   string t;
   int val;
   stack s;
   while (1) {
       cin >> t;
       if (t=="push") {
           cin >> val;
           s.push(val);
           cout << "ok" << endl;
       }
       else if (t=="pop") {
           if (s.empty())
               cout << "error" << endl;
           else {
               val = s.pop();
               cout << val << endl;
           }
       }
       else if (t=="back") {
           if (s.empty())
               cout << "error" << endl;
           else
               cout << s.back() << endl;
       }
       else if (t=="size") cout << s.size() << endl;
       else if (t=="clear") {
           s.clear();
           cout << "ok" << endl;
       }
       else if (t=="exit") {
           cout << "bye" << endl;
           break;
       }
   }
   return 0;
}

#include <iostream>

#include <string>

using namespace std;

struct node {

int value=0;

node* prev=NULL;

node(int val, node* prv): value(val), prev(prv) {} // конструктор нашего верхнего элемента в стеке

};

struct stack {

int cnt=0;

node* top=NULL;

void push (int n) {

top = new node(n, top); // когда создаём новую вершину, но присваиваем ей цену, а предыдущей записываем прошлую топовую вершину

cnt++;

}

bool empty() {

return cnt == 0;

}

int pop() {

node* prev = top->prev; // записываем предыдущий узел во временную переменную

int topVal = top->value;

delete top; // удаляем последний элемент стека

top = prev; // говорим, что он теперь равен прдыдущему

cnt--;

return topVal;

}

int back() {

return top->value;

}

int size() {

return cnt;

}

void clear() {

while (!empty()) pop();

}

};

int main() {

ios::sync_with_stdio(false);

string t;

int val;

stack s;

while (1) {

cin >> t;

if (t=="push") {

cin >> val;

s.push(val);

cout << "ok" << endl;

}

else if (t=="pop") {

if (s.empty())

cout << "error" << endl;

else {

val = s.pop();

cout << val << endl;

}

else if (t=="back") {

if (s.empty())

cout << "error" << endl;

else

cout << s.back() << endl;

}

else if (t=="size") cout << s.size() << endl;

else if (t=="clear") {

s.clear();

cout << "ok" << endl;

}

else if (t=="exit") {

cout << "bye" << endl;

break;

}

return 0;

}