e-olymp 4496. Приключение Незнайки и его друзей

26/06/2019 by Анна Неделева

Задача

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

В этой задаче Вам необходимо узнать, сколько же человечков улетело путешествовать. Известно, что посадка в шар не является оптимальной, а именно: человечки садятся в шар в той очереди, в которой они стоят, как только кому-то из них не хватает места, он и все оставшиеся в очереди разворачиваются и уходят домой.

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

В первой строке содержится количество человечков $n$ $(1 \leqslant n \leqslant 10^{6})$ в цветочном городе. Во второй строке заданы веса каждого из человечков в том порядке, в котором они будут садиться в шар. Все веса натуральные числа и не превышают $10^{9}.$ Далее следует количество запросов $m$ $(1 \leqslant m \leqslant 10^{5})$. Каждый запрос представляет собой одну строку. Если первое число в строке равно единице, то далее следует еще одно число $v$ $(1 \leqslant v \leqslant 10^{9})$ – грузоподъемность воздушного шара. Если же оно равно двум, то далее следует два числа $x$ $(1 \leqslant x \leqslant n)$ и $y$ $(1 \leqslant y \leqslant 10^{9})$ — это значит, что вес человечка, стоящего на позиции $x$, теперь равен $y$.

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

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

Тесты

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

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

#include <iostream>
using namespace std;

struct tree {
    long * tr;
    tree(int n) {
        tr = new long[4 * n + 1];
    }
    void build(int * arr, int v, int l, int r) {
        if (l == r) tr[v] = arr[l];
        else {
            int mid = (l + r) / 2;
            build(arr, v * 2, l, mid);
            build(arr, v * 2 + 1, mid + 1, r);
            tr[v] = tr[v * 2] + tr[v * 2 + 1];
        }
    }
    void update(int v, int l, int r, int pos, int val) {
        if (l == r) tr[v] = val;
        else {
            int mid = (l + r) / 2;
            if (pos <= mid) update(v * 2, l, mid, pos, val);
            else update(v * 2 + 1, mid + 1, r, pos, val);
            tr[v] = tr[v * 2] + tr[v * 2 + 1];
        }
    }
    int find(int v, int l, int r, int max) {
        if (l == r)
            return (tr[v] <= max);
        int mid = (l + r) / 2;
        if (tr[v * 2] > max)
            return find(v * 2, l, mid, max);
        else
            return mid - l + 1 + find(v * 2 + 1, mid + 1, r, max - tr[v * 2]);
    }
};

int main() {
    int n, m, * arr;
    cin >> n;
    arr = new int[n + 1];
    for (int i = 1; i <= n; ++i) cin >> arr[i];
    tree tr(n);
    tr.build(arr, 1, 1, n);
    cin >> m;
    int com, x, y, v;
    for (int i = 0; i < m; ++i) {
        cin >> com;
        switch (com) {
        case 1:
            {
                cin >> v;
                cout << tr.find(1, 1, n, v) << '\n';
                break;
            }
        case 2:
            {
                cin >> x >> y;
                tr.update(1, 1, n, x, y);
                break;
            }
        }
    }
    return 0;
}

#include <iostream>

using namespace std;

struct tree {

long * tr;

tree(int n) {

tr = new long[4 * n + 1];

}

void build(int * arr, int v, int l, int r) {

if (l == r) tr[v] = arr[l];

else {

int mid = (l + r) / 2;

build(arr, v * 2, l, mid);

build(arr, v * 2 + 1, mid + 1, r);

tr[v] = tr[v * 2] + tr[v * 2 + 1];

}

void update(int v, int l, int r, int pos, int val) {

if (l == r) tr[v] = val;

else {

int mid = (l + r) / 2;

if (pos <= mid) update(v * 2, l, mid, pos, val);

else update(v * 2 + 1, mid + 1, r, pos, val);

tr[v] = tr[v * 2] + tr[v * 2 + 1];

}

int find(int v, int l, int r, int max) {

if (l == r)

return (tr[v] <= max);

int mid = (l + r) / 2;

if (tr[v * 2] > max)

return find(v * 2, l, mid, max);

else

return mid - l + 1 + find(v * 2 + 1, mid + 1, r, max - tr[v * 2]);

}

};

int main() {

int n, m, * arr;

cin >> n;

arr = new int[n + 1];

for (int i = 1; i <= n; ++i) cin >> arr[i];

tree tr(n);

tr.build(arr, 1, 1, n);

cin >> m;

int com, x, y, v;

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

cin >> com;

switch (com) {

case 1:

{

cin >> v;

cout << tr.find(1, 1, n, v) << '\n';

break;

}

case 2:

{

cin >> x >> y;

tr.update(1, 1, n, x, y);

break;

}

return 0;

}

Решение задачи

Для решения данной задачи я воспользовалась структурой данных — дерево отрезков.
Её особенность заключается в том, что она предварительно производит некоторые вычисления, благодаря чему при частых однотипных вопросах можно быстрее давать ответ.
Функции построения и модификации элемента стандартные, а запрос на получение количества человечков, от грузоподъёмности воздушного шара — специфический. Рассмотрим принцип его работы:
Проверяем поместятся ли все человечки на воздушный шар, если нет, то делим их (условно на левых и правых) и проверяем для левой части данное условие, если помещаются все, то ответ находится в правой части, если нет, то в левой. Углубляемся по дереву до базового случая, когда нужно уточнить помещается ли последний человечек или нет. При спуске, отнимаем от заданной грузоподъемности шара вес человечков, которых мы уже посадили на шар.
В ответ выдаём номер последнего человечка поместившегося на шар, это и будет их количество, так как отсчёт мы вели с единицы.

Ссылки

Related Images:

А290

08/11/2016 by Сабиров Ильдар

Задача. Даны действительные числа [latex]x_{1},\ldots,x_{n}[/latex], [latex]y_{1},\ldots,y_{n}[/latex]. Получить [latex]x’_{1},\ldots,x’_{n}[/latex],[latex]y’_{1},\ldots,y’_{n}[/latex], преобразовав для получения [latex]x’_{i},y’_{i}[/latex] члены [latex]x_{i},y_{i}[/latex] по правилу: если они оба отрицательны, то каждый из них увеличить на 0.5; если отрицательно только одно число, то отрицательное число заменить его квадратом; если оба числа неотрицательны, то каждое из них заменить на среднее арифметическое исходных значений.

Тесты

n	[latex]x_{1},\ldots,x_{n}[/latex] [latex]y_{1},\ldots,y_{n}[/latex]	[latex]x’_{1},\ldots,x’_{n}[/latex][latex]y’_{1},\ldots,y’_{n}[/latex]	Комментарий
4	1 4 -3 8 3 -2 -4 2	2 4 -2.5 5 2 4 -3.5 5	Пройдено
5	0 -0.5 4 -9 0.35 0 -0.5 11 0.247 1.650	0 0 7.5 81 1 0 0 7.5 0.247 1	Пройдено
3	0 3 -0.14942 -3 0 793	0 1.5 0.0223263 9 1.5 793	Пройдено

Реализация (массив структур)

#include <iostream>
using namespace std;
struct okay {
    double a,b;
};
int main() {
    int numb;
    cin>>numb;
    okay x[numb];
    for(int i=0;i<numb;i++){
        cin>>x[i].a;
    }
    for(int i=0;i<numb;i++){
        cin>>x[i].b;
    }
    for(int i=0;i<numb;i++){
        if(x[i].a<0 && x[i].b<0){
            x[i].a=x[i].a+0.5;
            x[i].b=x[i].b+0.5;
        }
        else if(x[i].a<0 && x[i].b>=0){
            x[i].a=x[i].a*x[i].a;
        }
        else if(x[i].a>=0 && x[i].b<0){
            x[i].b=x[i].b*x[i].b;
        }
        else {
            x[i].a=(x[i].a+x[i].b)/2;
            x[i].b=x[i].a;
        }
    }
    for(int i=0;i<numb;i++){
        cout<<x[i].a<<" ";
    }
    cout<<endl;
    for(int i=0;i<numb;i++){
        cout<<x[i].b<<" ";
    }
    return 0;
}

#include <iostream>

using namespace std;

struct okay {

double a,b;

};

int main() {

int numb;

cin>>numb;

okay x[numb];

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

cin>>x[i].a;

}

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

cin>>x[i].b;

}

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

if(x[i].a<0 && x[i].b<0){

x[i].a=x[i].a+0.5;

x[i].b=x[i].b+0.5;

}

else if(x[i].a<0 && x[i].b>=0){

x[i].a=x[i].a*x[i].a;

}

else if(x[i].a>=0 && x[i].b<0){

x[i].b=x[i].b*x[i].b;

}

else {

x[i].a=(x[i].a+x[i].b)/2;

x[i].b=x[i].a;

}

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

cout<<x[i].a<<" ";

}

cout<<endl;

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

cout<<x[i].b<<" ";

}

return 0;

}

Алгоритм решения (массив структур)
Для выполнения данной задачи, воспользуемся массивом структур. Каждый [latex]i[/latex]-ый элемент такого массива заполняем двумя действительными числами [latex]x_{i}[/latex] и [latex]y_{i}[/latex]. После этого мы выполняем проверку и преобразование этих чисел по заданным в условии правилам. Затем их выводим.

Реализация (класс vector)

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

int main() {
    double a,b;
    vector<double> c;
    vector<double> d;
    while(cin>>a && cin>>b){
        c.push_back(a);
        d.push_back(b);
    }
    for(int i=0;i<c.size();i++){
        if(c[i]<0 && d[i]<0){
            c[i]=c[i]+0.5;
            d[i]=d[i]+0.5;
        }
        else if(c[i]<0 && d[i]>=0){
            c[i]=c[i]*c[i];
        }
        else if(c[i]>=0 && d[i]<0){
            d[i]=d[i]*d[i];
        }
        else {
            c[i]=(c[i]+d[i])/2;
            d[i]=c[i];
        }
    }
    for(int i=0;i<c.size();i++){
        cout<<c[i]<<" ";    
    }
    cout<<endl;
    for(int i=0;i<d.size();i++){
        cout<<d[i]<<" ";
    }
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main() {

double a,b;

vector<double> c;

vector<double> d;

while(cin>>a && cin>>b){

c.push_back(a);

d.push_back(b);

}

for(int i=0;i<c.size();i++){

if(c[i]<0 && d[i]<0){

c[i]=c[i]+0.5;

d[i]=d[i]+0.5;

}

else if(c[i]<0 && d[i]>=0){

c[i]=c[i]*c[i];

}

else if(c[i]>=0 && d[i]<0){

d[i]=d[i]*d[i];

}

else {

c[i]=(c[i]+d[i])/2;

d[i]=c[i];

}

for(int i=0;i<c.size();i++){

cout<<c[i]<<" ";

}

cout<<endl;

for(int i=0;i<d.size();i++){

cout<<d[i]<<" ";

}

return 0;

}

Алгоритм решения (класс vector)
Данный способ реализации помогает решить задачу преобразования чисел [latex]x_{1},\ldots,x_{n}[/latex], [latex]y_{1},\ldots, y_{n}[/latex] для неизвестного значения [latex]n[/latex] — количества элементов [latex]x_{i}[/latex] и [latex]y_{i}[/latex]. Их количество будет зависить от количества введенных элементов. Программа считывает элементы [latex]x_{i}[/latex] и [latex]y_{i}[/latex] поочередно, т.е. [latex]x_{1}\rightarrow y_{1}\rightarrow x_{2} \rightarrow y_{2} \rightarrow\ldots\rightarrow x_{n}\rightarrow y_{n}[/latex]. В остальном алгоритм такой же как с массивом структур.

Ссылка на код (массив структур)
Ссылка на код (класс vector)

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:

acm.timus.ru №2002. Тестовое задание

04/12/2015 by Марченко Філіп Олександрович

Автор задачи: Кирилл Бороздин
Источник задачи: Уральская региональная командная олимпиада по программированию 2013

Ограничения:

Время:	0.5 секунды
Память	64 Мб

Условие

Это было обычное хмурое октябрьское утро. Небо было затянуто тяжёлыми серыми тучами, накрапывал дождь. Капли падали на стёкла автомобилей, били в окна домов. Илья сидел за компьютером и угрюмо взирал на унылый пейзаж за окном. Внезапно его взгляд привлекла надпись, появившаяся в правом нижнем углу экрана: «You have 1 unread email message(s)». Заранее приготовившись удалить бесполезный спам, Илья открыл письмо. Однако оно оказалось куда интереснее…

Вас приветствует отдел по работе с персоналом компании «Рутнок БКС»!

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

«register username password» — зарегистрировать нового пользователя с именем «username» и установить для него пароль «password». Если такой пользователь уже есть в базе данных, необходимо выдать ошибку «fail: user already exists». Иначе нужно вывести сообщение «success: new user added».
«login username password» — войти в систему от имени пользователя «username» с паролем «password». Если такого пользователя не существует в базе данных, необходимо выдать «fail: no such user». Иначе, если был введен неправильный пароль, нужно выдать «fail: incorrect password». Иначе, если пользователь уже находится в системе в данный момент, необходимо вывести «fail: already logged in». Иначе нужно вывести сообщение «success: user logged in».
«logout username» — выйти из системы пользователем «username». Если такого пользователя не существует, необходимо вывести «fail: no such user». Иначе, если пользователь не находится в системе в данный момент, следует выдать «fail: already logged out». Иначе необходимо выдать сообщение «success: user logged out».

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

И вот Илья, откинув все дела, уже решает тестовое задание. Попробуйте и вы выполнить его!

Исходные данные

В первой строке дано целое число [latex]n[/latex] — количество операций [latex]1\leq{n}\leq100[/latex]. В каждой из следующих [latex]n[/latex] строк содержится один запрос в соответствии с форматом, описанным выше. В качестве «username» и «password» могут выступать любые непустые строки длиной до 30 символов включительно. Строки могут состоять только из символов с кодами от 33 до 126.

Результат

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

Пример

Исходные данные

Результат

logout vasya

success: new user added

fail: incorrect password

success: user logged in

fail: no such user

success: user logged out

fail: already logged out

Решение

Для решения данной задачи нам необходимо воспользоваться структурой данных, которая хранит в себе пары вида «ключ — значение», а также структурой, которая будет хранить в себе некоторое множество. Воспользуемся структурами HashMap (Java) / map (C++) (key -> value) и HashSet (множество).

Рассмотрим операции, которые должна уметь обрабатывать наша система:

«register username password». При регистрации нового пользователя будем помещать его в нашу «базу» зарегистрированных пользователей при условии, что он не зарегистрирован. Поиском по ключу в HashMap / map проверим существование уже зарегистрированного никнейма. Если найдётся такой пользователь, то система выдаст сообщение об ошибке.
«login user password». Если база пользователей содержит в себе логин пользователя, пароли совпадают и пользователь не в он-лайне, то система разрешит user’у вход на форум. В противном случае, с соответствующими сообщениями об ошибках, не разрешит вход. Отслеживать пользователей, которые уже online, будем с помощью HashSet. Если пользователя нет в базе пользователей, которые сейчас на сайте, то открывая доступ, система поместит его в базу-online. Тогда новый запрос login с этого ника будет отклонён.
«logout name». Если пользователя нет в базе пользователей, то его logout невозможен. Иначе, если его нет в базе-online, то тоже система выдаст сообщение об ошибке. Если user есть в базе пользователей и находится в онлайне, то выход возможен. Во время logouta удаляем пользователя из базы-online.

Реализация

В данном отчёте задачи будут представлены на языках Java и C++. Опишем, для начала, какие классы и методы необходимо использовать для решения этой задачи на языке Java:

HashMap:

Будем использовать интерфейс Map, имплементация (реализация) — HashMap. Из интерфейса Map воспользуемся следующими методами:

containsKey(Key K) — возвращает true, если ключ найден. В противном случае — false;
put(Key K, Value V) — записывает пару ключ-значение в структуру;
get(Key K) — по ключу возвращает значение.

HashSet:

Используем интерфейс Set, реализация — HashSet. Будем использовать следующие методы:

contains(Object o) — возвращает true, если элемент принадлежит множеству. Иначе — false;
add(Object o) — добавляет элемент во множество;
remove(Object o) — удаляет элемент из множества.

Теперь для С++:

В С++ воспользуемся немного другим подходом. Воспользуемся только map. Создадим структуру, которая будет содержать 2 поля: пароль и статус. Воспользуемся следующими методами:

find (K key) — возвращает итератор элемента.
end() — возвращает итератор за последним элементом.

set или без него?

Для данной задачи использование set’a не принципиально. Но если предположить, что, помимо запросов регистрации, входа и выхода, был бы ещё и запрос вывести пользователей, которые онлайн, преимущество использования set’a очевидно.

Код на Java:

import java.util.*;
import java.lang.*;
import java.io.*;

 class Ideone {
    public static void main (String[] args) {
        
        //create an DB for online and reged users
        Map DB = new HashMap<String, String> (); 
        HashSet <String> DBin = new HashSet <String> ();
        
        Scanner in = new Scanner (System.in);
        PrintWriter out = new PrintWriter(System.out);
        
        //a number of queries
        int n = in.nextInt();
        
        
        for (int i = 0; i < n; i++){
            String s, log, pass;
            
            //command
            s = in.next();
            
            if (s.equals("register")){
                log = in.next();    //login
                pass = in.next();   //password
                if (DB.containsKey(log)){   //login in DB?
                    out.println("fail: user already exists");
                    out.flush();
                }
                else {
                    DB.put(log, pass);
                    out.println("success: new user added");
                    out.flush();
                }
            }
            
            if (s.equals("login")){
                log = in.next();
                pass = in.next();
                if (DB.containsKey(log)){ //if user is reg
                    if (pass.equals(DB.get(log))) { //if the password is well
                        if (!DBin.contains(log)) {  //online?
                            DBin.add(log);
                            out.println("success: user logged in");
                            out.flush();
                        }
                        //Errors
                        else {
                            out.println("fail: already logged in");
                            out.flush();
                        }
                    }
                    else {
                        out.println("fail: incorrect password");
                        out.flush();
                    }
                }
                else {
                    out.println("fail: no such user");
                    out.flush();
                }
            }
            if (s.equals("logout")){
                log = in.next();
                if (!DB.containsKey(log)) { //unreg user can't logout... unfortunately.
                    out.println("fail: no such user");
                    out.flush();
                }
                else {
                    if (!DBin.contains(log)){   //so offline user does
                        out.println("fail: already logged out");
                        out.flush();
                    }
                    else {
                        DBin.remove(log);
                        out.println("success: user logged out");
                        out.flush();
                    }
                }
            }
        }
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone {

public static void main (String[] args) {

//create an DB for online and reged users

Map DB = new HashMap<String, String> ();

HashSet <String> DBin = new HashSet <String> ();

Scanner in = new Scanner (System.in);

PrintWriter out = new PrintWriter(System.out);

//a number of queries

int n = in.nextInt();

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

String s, log, pass;

//command

s = in.next();

if (s.equals("register")){

log = in.next(); //login

pass = in.next(); //password

if (DB.containsKey(log)){ //login in DB?

out.println("fail: user already exists");

out.flush();

}

else {

DB.put(log, pass);

out.println("success: new user added");

out.flush();

}

if (s.equals("login")){

log = in.next();

pass = in.next();

if (DB.containsKey(log)){ //if user is reg

if (pass.equals(DB.get(log))) { //if the password is well

if (!DBin.contains(log)) { //online?

DBin.add(log);

out.println("success: user logged in");

out.flush();

}

//Errors

else {

out.println("fail: already logged in");

out.flush();

}

else {

out.println("fail: incorrect password");

out.flush();

}

else {

out.println("fail: no such user");

out.flush();

}

if (s.equals("logout")){

log = in.next();

if (!DB.containsKey(log)) { //unreg user can't logout... unfortunately.

out.println("fail: no such user");

out.flush();

}

else {

if (!DBin.contains(log)){ //so offline user does

out.println("fail: already logged out");

out.flush();

}

else {

DBin.remove(log);

out.println("success: user logged out");

out.flush();

}

Код на С++:

#include <iostream>
#include <stdio.h>
#include <string>
#include <iomanip>
#include <stack>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <map>

using namespace std;

struct status { //status - password and online
    string password;
    bool online = false;
};

map <string, status> database; //user database


int main () {
    int n; cin >> n; //number of queries
    typedef std::map<std::string, status> db; // use this typedef for an iterator
    while (n--){
        string com, login; //command and login
        status query; //for status input
        cin >> com;
        if (com == "register"){
            cin >> login >> query.password;
            db::iterator it = database.find(login); //returning an iterator
            if (it != database.end()) { //each el from database is in [begin, end). it = database.end() means that there is no such element in db
                cout << "fail: user already exists\n";
            }
            else {
                database[login].password = query.password; // register
                cout << "success: new user added\n";
            }
        }
        //user can log in if he isn't online but he is registered
        if (com == "login") {
            cin >> login >> query.password;
            db::iterator it = database.find(login);
            if (it != database.end()){
                if (query.password == database[login].password){
                    if(!database[login].online){
                        database[login].online = true;
                        cout << "success: user logged in\n";
                    }
                    else cout << "fail: already logged in\n";
                }
                else cout << "fail: incorrect password\n";
            }
            else cout << "fail: no such user\n";
        }
        //logout
        if (com == "logout") {
            cin >> login;
            if (database.find(login) == database.end()) cout << "fail: no such user\n";
            else {
                if (!database[login].online) cout << "fail: already logged out\n";
                else {

                    database[login].online = false;
                    cout << "success: user logged out\n";
                }
            }
        }
    }
    return 0;
}

#include <iostream>

#include <stdio.h>

#include <string>

#include <iomanip>

#include <stack>

#include <vector>

#include <algorithm>

#include <cmath>

#include <queue>

#include <map>

using namespace std;

struct status { //status - password and online

string password;

bool online = false;

};

map <string, status> database; //user database

int main () {

int n; cin >> n; //number of queries

typedef std::map<std::string, status> db; // use this typedef for an iterator

while (n--){

string com, login; //command and login

status query; //for status input

cin >> com;

if (com == "register"){

cin >> login >> query.password;

db::iterator it = database.find(login); //returning an iterator

if (it != database.end()) { //each el from database is in [begin, end). it = database.end() means that there is no such element in db

cout << "fail: user already exists\n";

}

else {

database[login].password = query.password; // register

cout << "success: new user added\n";

}

//user can log in if he isn't online but he is registered

if (com == "login") {

cin >> login >> query.password;

db::iterator it = database.find(login);

if (it != database.end()){

if (query.password == database[login].password){

if(!database[login].online){

database[login].online = true;

cout << "success: user logged in\n";

}

else cout << "fail: already logged in\n";

}

else cout << "fail: incorrect password\n";

}

else cout << "fail: no such user\n";

}

//logout

if (com == "logout") {

cin >> login;

if (database.find(login) == database.end()) cout << "fail: no such user\n";

else {

if (!database[login].online) cout << "fail: already logged out\n";

else {

database[login].online = false;

cout << "success: user logged out\n";

}

return 0;

}

Результаты

Обе реализации прошли все тесты на Тимусе с такими результатами:

Язык	Время работы	Память
С++	0.015	412 КБ
Java	0.124	1 804 КБ

Ссылки

Related Images:

e-olimp: 694. Минимум в очереди

27/03/2015 by Іванов Вячеслав Володимирович

e-olimp: 694 — Минимум в очереди

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

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

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

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

Реализации:

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

Спортивный подход

ideone: http://ideone.com/pvVixS
засчитанное решение: http://www.e-olimp.com/solutions/1926658

#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;

typedef long long ll;

int main(){
  unsigned n; scanf("%u", &n);
  ll a, b, c, x, sum = 0;
  scanf("%lld %lld %lld %lld", &a, &b, &c, &x);

  unsigned capacity = unsigned(1e6);
  ll *head = (ll*)calloc(capacity + 1, sizeof(ll));  //стек, из которого удаляют элементы
  ll *hmin = (ll*)calloc(capacity + 1, sizeof(ll));  //его локальные минимумы
  ll *tail = (ll*)calloc(capacity + 1, sizeof(ll));  //стек, в который добавляют элементы
  ll *tmin = (ll*)calloc(capacity + 1, sizeof(ll));  //его локальные минимумы
  ll r = 0, l = 0;           //позиции в первом и втором стеках

  while(n--){
    x = (a*x*x + b*x + c)/100 % 1000000;    //подсчет нового значения Х
    if(x % 5 < 2){
      if(l == 0){  //если голова пуста
        hmin[1] = head[1] = tail[r]; //инициализация головы очереди
        for(l = 2; l <= r; l++){    //переносим элементы из первого стека во второй, из хвоста в очередь (в обратном порядке)
          head[l] = tail[r - l + 1];     //реализация обратного порядка обхода
          hmin[l] = min(hmin[l-1], head[l]); //минимум на данном шаге равен минимуму из предыдущего и текущего
        }
        r = 0;   //хвост очереди очищен
        l--;     //голова перезаписана
      }
      l--; //сдвиг влево на текущую позицию
    }
    else{
      tail[++r] = x; //записать x в хвост
      if(r == 1)     //если очередь состоит из одного элемента
        tmin[r] = x; //то он же и является минимальным
      else
        tmin[r] = min(tmin[r-1], x);  //иначе оптимальный элемент равен минимуму из того, что было, и нового элемента
    }
    if(r > 0 && l > 0)                //если и голова, и хвост непусты
        sum += min(tmin[r], hmin[l]);  //то добавить к сумме минимум из значений в голове и хвосте
      else
        if(r > 0 && l == 0)
            sum += tmin[r];
        else
          if(r == 0 && l>0)
            sum += hmin[l];
  }
  printf("%lld\n", sum);
  return 0;
}

#include <cstdio>

#include <cstdlib>

#include <algorithm>

using namespace std;

typedef long long ll;

int main(){

unsigned n; scanf("%u", &n);

ll a, b, c, x, sum = 0;

scanf("%lld %lld %lld %lld", &a, &b, &c, &x);

unsigned capacity = unsigned(1e6);

ll *head = (ll*)calloc(capacity + 1, sizeof(ll)); //стек, из которого удаляют элементы

ll *hmin = (ll*)calloc(capacity + 1, sizeof(ll)); //его локальные минимумы

ll *tail = (ll*)calloc(capacity + 1, sizeof(ll)); //стек, в который добавляют элементы

ll *tmin = (ll*)calloc(capacity + 1, sizeof(ll)); //его локальные минимумы

ll r = 0, l = 0; //позиции в первом и втором стеках

while(n--){

x = (a*x*x + b*x + c)/100 % 1000000; //подсчет нового значения Х

if(x % 5 < 2){

if(l == 0){ //если голова пуста

hmin[1] = head[1] = tail[r]; //инициализация головы очереди

for(l = 2; l <= r; l++){ //переносим элементы из первого стека во второй, из хвоста в очередь (в обратном порядке)

head[l] = tail[r - l + 1]; //реализация обратного порядка обхода

hmin[l] = min(hmin[l-1], head[l]); //минимум на данном шаге равен минимуму из предыдущего и текущего

}

r = 0; //хвост очереди очищен

l--; //голова перезаписана

}

l--; //сдвиг влево на текущую позицию

}

else{

tail[++r] = x; //записать x в хвост

if(r == 1) //если очередь состоит из одного элемента

tmin[r] = x; //то он же и является минимальным

else

tmin[r] = min(tmin[r-1], x); //иначе оптимальный элемент равен минимуму из того, что было, и нового элемента

}

if(r > 0 && l > 0) //если и голова, и хвост непусты

sum += min(tmin[r], hmin[l]); //то добавить к сумме минимум из значений в голове и хвосте

else

if(r > 0 && l == 0)

sum += tmin[r];

else

if(r == 0 && l>0)

sum += hmin[l];

}

printf("%lld\n", sum);

return 0;

}

Преимущества

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

Недостатки

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

Объектно-ориентированный подход

ideone: http://ideone.com/A6BpwN
засчитанное решение: http://www.e-olimp.com/solutions/1924823

#include <iostream>
#include <cstdlib>  //calloc()
#include <utility>  //pair
#include <algorithm>  //min(), max()
using namespace std;

const int capacity = 100; //ёмкость каждого узла списка

template <class T>  //T - тип данных, хранящихся в стеке
    class stack{
        private:
            struct node{      //основа стека неограниченной вместительности - односвязный список массивов
                node* prev;   //указатель на предыдущий узел
                T* storage;   //массив данных, хранящихся в текущем узле

                node(){ //конструктор по умолчанию
                    prev = nullptr; //список содержит всего один узел
                    storage = (T*)calloc(capacity+1, sizeof(T));  //выделить память под capacity элементов заданного типа
                }
                node(node* predecessor){  //параметрический конструктор: добавление нового узла в список
                    prev = predecessor;   //последний узел старого списка будет предшественником нового узла
                    storage = (T*)calloc(capacity+1, sizeof(T));  //в отличие от malloc, calloc заполняет выделенный участок памяти нулями
                }
                ~node(){  //деструктор
                    free(storage);  //очистить участок памяти, в котором хранится текущий узел
                }
            };
            node* container;  //односвязный список
            int pos;          //текущая позиция указателя. Используется 1-индексация массивов.
            int stored;       //количество хранимых в данный момент элементов

        public:
            stack(){  //конструктор по умолчанию
                container = new node(); //создать список из одного узла
                pos = stored = 0; //0 - служебная позиция, сигнализирующая о том, что стек пуст
            }
            //(в решении задачи не используется, но объявлять конструктор без деструктора - дурной тон - прим.)
            ~stack(){ //деструктор
                while(container != nullptr){  //пока список не пуст
                    node* predecessor = container->prev;  //сохранить указатель на предшествующий узел
                    delete container; //очистить текущий узел
                    container = predecessor;  //перейти к предшествующему узлу
                }
                pos = stored = 0; //сбросить счетчик и указатель на позицию в стеке
            }

            bool empty(){ //проверка на пустоту
                return stored == 0;
            }

            int size(){ //количество элементов в стеке
                return stored;
            }

            T top(){  //крайний элемент стека
                return container->storage[pos];
            }

            void push(T x){ //добавление элемента
                if(pos == capacity){  //если текущий узел заполнен
                    container = new node(container);  //создать новый узел
                    pos = 0;  //и явно указать, что он пуст
                }
                container->storage[++pos] = x;  //добавить элемент в стек
                ++stored; //количество хранимых элементов увеличилось на 1
            }

            void pop(){ //удаление элемента
                if(pos == 1 && stored >= capacity){ //извлекается последний элемент крайнего узла списка
                    node* predecessor = container->prev;  //сохранить указатель на предыдущий узел
                    delete container; //очистить память, занимаемую пустым узлом
                    container = predecessor;  //обновить указатель на текущий узел
                    pos = capacity + 1; //удаление элемента эквивалентно сдвигу указателя влево
                    //во избежание дублирования участка кода, указателю было присвоено значение
                    //сдвигом влево которого будет получен указатель на крайний элемент узла
                }
                --stored; //число хранимых элементов уменьшается на единицу
                --pos;    //указатель на текущую позицию сдвигается на единицу влево
            }

            void clear(){ //очистка содержимого стека
                while(container != nullptr){  //если список не пуст
                    node* predecessor = container->prev;  //сохранить указатель на предшествующий узел
                    delete container; //очистить текущий узел
                    container = predecessor;  //перейти к предшествующему узлу
                }
                container = new node(); //в отличие от деструктора, в списке оставляется один узел
                pos = stored = 0; //сброс значений счетчика и указателя на текущую позицию
            }

    };

//модифицированные стеки: первый элемент пары - хранимое значение, второй - минимум в данной позиции
stack<pair<long long, long long>> head, tail; //голова и хвост очереди
//head - стек, из которого только удаляют элементы
//tail - стек, в который только добавляют элементы

int main(){
  int n; cin >> n;  //количество операций с очередью
  long long a, b, c, x, min_sum = 0;
  cin >> a >> b >> c >> x;
  while(n--){
      x = (a*x*x + b*x + c)/100 % 1000000;
      if(x % 5 < 2){  //удалить элемент из очереди
          if(head.empty()){ //если соответствующий стек пуст
            while(!tail.empty()){ //то перебросить в него содержимое другого стека
              long long value = tail.top().first;
              tail.pop();
              long long minimum = head.empty() ? value : min(head.top().second, value);
              head.push({value, minimum});
            }
            //по окончании обмена принцип FIFO не нарушен, так как элементы
            //хвоста очереди расположены в голове в порядке, обратном исходному
          }
          if(!head.empty()) //если очередь непуста
            head.pop(); //удалить первый элемент очереди
      }
      else{ //добавить элемент в очередь
          if(tail.empty())  //если соответствующий стек пуст
            tail.push({x, x});  //то добавленный элемент также является текущим минимумом
          else  //в противном случае
            tail.push({x, min(x, tail.top().second)});  //если добавленный элемент меньше всех, содержащихся в стеке
            //то обновить текущий минимум
      }
      if(tail.empty() ^ head.empty()) //если не пуст или первый, или второй стек (но не оба одновременно)
        min_sum += tail.empty() ? head.top().second : tail.top().second;  //прибавить к сумме доступный минимум
      else  //если оба стека одновременно либо пусты, либо нет
        min_sum += tail.empty() ? 0 : min(tail.top().second, head.top().second);  //либо не изменить сумму, либо добавить к ней минимум
        //из значений, хранящихся в обоих стеках
   }
   cout << min_sum << endl; //минимально возможная после всех манипуляций сумма
}

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

#include <iostream>

#include <cstdlib> //calloc()

#include <utility> //pair

#include <algorithm> //min(), max()

using namespace std;

const int capacity = 100; //ёмкость каждого узла списка

template <class T> //T - тип данных, хранящихся в стеке

class stack{

private:

struct node{ //основа стека неограниченной вместительности - односвязный список массивов

node* prev; //указатель на предыдущий узел

T* storage; //массив данных, хранящихся в текущем узле

node(){ //конструктор по умолчанию

prev = nullptr; //список содержит всего один узел

storage = (T*)calloc(capacity+1, sizeof(T)); //выделить память под capacity элементов заданного типа

}

node(node* predecessor){ //параметрический конструктор: добавление нового узла в список

prev = predecessor; //последний узел старого списка будет предшественником нового узла

storage = (T*)calloc(capacity+1, sizeof(T)); //в отличие от malloc, calloc заполняет выделенный участок памяти нулями

}

~node(){ //деструктор

free(storage); //очистить участок памяти, в котором хранится текущий узел

}

};

node* container; //односвязный список

int pos; //текущая позиция указателя. Используется 1-индексация массивов.

int stored; //количество хранимых в данный момент элементов

public:

stack(){ //конструктор по умолчанию

container = new node(); //создать список из одного узла

pos = stored = 0; //0 - служебная позиция, сигнализирующая о том, что стек пуст

}

//(в решении задачи не используется, но объявлять конструктор без деструктора - дурной тон - прим.)

~stack(){ //деструктор

while(container != nullptr){ //пока список не пуст

node* predecessor = container->prev; //сохранить указатель на предшествующий узел

delete container; //очистить текущий узел

container = predecessor; //перейти к предшествующему узлу

}

pos = stored = 0; //сбросить счетчик и указатель на позицию в стеке

}

bool empty(){ //проверка на пустоту

return stored == 0;

}

int size(){ //количество элементов в стеке

return stored;

}

T top(){ //крайний элемент стека

return container->storage[pos];

}

void push(T x){ //добавление элемента

if(pos == capacity){ //если текущий узел заполнен

container = new node(container); //создать новый узел

pos = 0; //и явно указать, что он пуст

}

container->storage[++pos] = x; //добавить элемент в стек

++stored; //количество хранимых элементов увеличилось на 1

}

void pop(){ //удаление элемента

if(pos == 1 && stored >= capacity){ //извлекается последний элемент крайнего узла списка

node* predecessor = container->prev; //сохранить указатель на предыдущий узел

delete container; //очистить память, занимаемую пустым узлом

container = predecessor; //обновить указатель на текущий узел

pos = capacity + 1; //удаление элемента эквивалентно сдвигу указателя влево

//во избежание дублирования участка кода, указателю было присвоено значение

//сдвигом влево которого будет получен указатель на крайний элемент узла

}

--stored; //число хранимых элементов уменьшается на единицу

--pos; //указатель на текущую позицию сдвигается на единицу влево

}

void clear(){ //очистка содержимого стека

while(container != nullptr){ //если список не пуст

node* predecessor = container->prev; //сохранить указатель на предшествующий узел

delete container; //очистить текущий узел

container = predecessor; //перейти к предшествующему узлу

}

container = new node(); //в отличие от деструктора, в списке оставляется один узел

pos = stored = 0; //сброс значений счетчика и указателя на текущую позицию

}

};

//модифицированные стеки: первый элемент пары - хранимое значение, второй - минимум в данной позиции

stack<pair<long long, long long>> head, tail; //голова и хвост очереди

//head - стек, из которого только удаляют элементы

//tail - стек, в который только добавляют элементы

int main(){

int n; cin >> n; //количество операций с очередью

long long a, b, c, x, min_sum = 0;

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

while(n--){

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

if(x % 5 < 2){ //удалить элемент из очереди

if(head.empty()){ //если соответствующий стек пуст

while(!tail.empty()){ //то перебросить в него содержимое другого стека

long long value = tail.top().first;

tail.pop();

long long minimum = head.empty() ? value : min(head.top().second, value);

head.push({value, minimum});

}

//по окончании обмена принцип FIFO не нарушен, так как элементы

//хвоста очереди расположены в голове в порядке, обратном исходному

}

if(!head.empty()) //если очередь непуста

head.pop(); //удалить первый элемент очереди

}

else{ //добавить элемент в очередь

if(tail.empty()) //если соответствующий стек пуст

tail.push({x, x}); //то добавленный элемент также является текущим минимумом

else //в противном случае

tail.push({x, min(x, tail.top().second)}); //если добавленный элемент меньше всех, содержащихся в стеке

//то обновить текущий минимум

}

if(tail.empty() ^ head.empty()) //если не пуст или первый, или второй стек (но не оба одновременно)

min_sum += tail.empty() ? head.top().second : tail.top().second; //прибавить к сумме доступный минимум

else //если оба стека одновременно либо пусты, либо нет

min_sum += tail.empty() ? 0 : min(tail.top().second, head.top().second); //либо не изменить сумму, либо добавить к ней минимум

//из значений, хранящихся в обоих стеках

}

cout << min_sum << endl; //минимально возможная после всех манипуляций сумма

}

Преимущества

Масштабируемость. Добавление функционала сводится к написанию новых методов класса.
Универсальность. Основа стека — односвязный список. Следовательно, его размер ограничен только объёмом доступной оперативной памяти.
Инкапсуляция. Реализация методов класса отделена от контекста выполняемых им функций в теле программы.
Польза процесса. Быстро написать более простое решение, не разобравшись в тонкостях классической реализации, почти наверняка не удастся.

Недостатки

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

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;

}