e-olymp 9066. Кружок стрельбы

03/03/2020 by Владислав Гринькив

Задача

После успешного обучения Атрея стрельбе из лука «Когтя» Фэй решила не останавливаться на достигнутом и открыть целый кружок стрельбы из лука.

На занятие кружка пришли $n$ учеников. Фэй пронумеровала их целыми числами от $1$ до $n$. В начале занятия ученики встали вдоль координатной прямой, заблаговременно нарисованной на полу, причем i-й ученик стоял в точке с координатой $x_i$. Получилось так, что координаты учеников строго возрастали, то есть $x_i \lt x_{i+1}$ для всех $i$ от $1$ до $n-1$.

У каждого из учеников есть свой волшебный лук, который характеризуется своей дальностью $r_i$ и силой $c_i$. Оба параметра — целые положительные числа. Когда ученик совершает выстрел из лука, магический снаряд начинает лететь вдоль координатной прямой в сторону увеличения координаты. Снаряд летит до тех пор, пока его сила положительна. В момент выстрела сила заряда равна силе лука, из которого совершается выстрел. Каждый раз, когда снаряд пролетает очередные $r_i$ единиц расстояния вдоль прямой, он теряет одну единицу силы.

Если ученик произвел выстрел, и снаряд, выпущенный им, достиг следующего по порядку вдоль прямой ученика, снаряд прекращает свой полет, а ученик, которого достиг снаряд, внезапно решает, что ему тоже надо произвести выстрел, и совершает его. Ученик совершит выстрел, даже если снаряд достиг его, имея силу $0$.

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

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

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

Первая строка содержит количество учеников $n$ $(1 \leqslant n \leqslant 1000)$ на кружке Фэй.

Каждая из следуюших $n$ строк содержит три целых числа $x_i$, $r_i$ и $c_i$ ($1 \leqslant x_i \leqslant 10^9$, $1 \leqslant r_i$, $c_i \leqslant 100$) — координату очередного ученика, а также дальность и силу его лука соответственно. Гарантируется, что $x_i \lt x_{i+1}$ для всех $i$ от $1$ до $n-1$.

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

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

Тесты

№	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	5 1 3 3 5 1 2 8 2 3 10 1 2 11 3 2	2
2	6 1 3 5 4 2 2 7 4 3 10 1 2 11 3 2 13 4 3	1

Код

#include <iostream>
using namespace std;
struct archerProfile {
  unsigned long x;
  unsigned long r;
  unsigned int c;
}archer[1000];
int main(){ 
  int n;
  int commands = 1;
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> archer[i].x >> archer[i].r >> archer[i].c;
  }
  for (int i = 0; i < n - 1; i++) {
    unsigned long long distanceBetweenArchers = archer[i + 1].x - archer[i].x;
    if (distanceBetweenArchers > archer[i].c * archer[i].r) {
      commands += 1;
    }
  }
  cout << commands;
  return 0;
}

#include <iostream>

using namespace std;

struct archerProfile {

unsigned long x;

unsigned long r;

unsigned int c;

}archer[1000];

int main(){

int n;

int commands = 1;

cin >> n;

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

cin >> archer[i].x >> archer[i].r >> archer[i].c;

}

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

unsigned long long distanceBetweenArchers = archer[i + 1].x - archer[i].x;

if (distanceBetweenArchers > archer[i].c * archer[i].r) {

commands += 1;

}

cout << commands;

return 0;

}

Решение

Для решения задачи, мы должны найти расстояние между лучниками, то есть $x_{i+1}-x_i$, после чего найти максимальное расстояние, которое пролетит стрела у $x_{i}$ лучника умножив силу его лука $c_i$ и расстояние $r_i$, после чего сделать проверку, если расстояние между лучниками больше чем максимальное расстояние которое пролетит стрела, то мы дадим команду совершить ещё один выстрел.

Ссылки

Условие задачи на e-olymp
Код на Ideone
Засчитанное решение на e-olymp

Related Images:

e-olymp 9531. Комплексные числа: сложение и вычитание

20/12/2019 by Никита Гербали

Условие

Даны два комплексных числа. Найдите их сумму или разность.

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

В каждой строке задан пример на сложение или вычитание комплексных чисел. Комплексное число задается в формате $a+bi$ или $a-bi$, где $a$ целое, $b$ целое неотрицательное. Действительная и мнимая часть каждого комплексного числа по модулю не превышает $10^{9}$.

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

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

Тесты

№	Входные данные	Выходные данные
1	2+3i + 7-4i	9-1i
2	-1-1i — -1-1i	0+0i
3	56743+876i — 1234-124i	55509+1000i
4	331+10i — 331+10i	0+0i

Код

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

struct complex_number {  //создадим структуру комплексных чисел
    int real;
    int imagine;
};

complex_number convert(string term) {
    complex_number x;
    x.real = 1;  //чтобы не вводить отдельные переменные для знака присвоим начальное значение не 0, а 1
    x.imagine = 1;
    if (term[0] == '-') {  //если нулевой символ минус, то меняем значение действительной части на -1;
        x.real *= -1;
        term.erase(term.begin(), term.begin() + 1);  //удаляем минус на нулевой позиции, если он есть, чтобы было легче найти второй знак
    }
    int index = term.find('+');  //находим индекс знака, если это плюс
    if (index == -1) {
        index = term.find('-');  //находим индекс знака, если это минус
        x.imagine = -1;  //меняем значение мнимой части на -1, если второй знак минус
    }
    x.real *= atoi(&term.substr(0, index)[0]);  //находим действительную часть
    x.imagine *= atoi(&term.substr(index + 1, term.size() - 2)[0]);  //находим мнимую часть
    return x;  //возвращаем полученное комплексное число
}

int main() {
    string term1, term2;
    char sign;
    complex_number convert_term1, convert_term2;
    while (cin >> term1 >> sign >> term2) {
        convert_term1 = convert(term1);  //переводим первую строку в первое слагаемое
        convert_term2 = convert(term2);  //переводим вторую строку во второе слагаемое
        if (sign == '+') { //выполняем действие соответствующее считанному знаку
            convert_term1.real += convert_term2.real;
            convert_term1.imagine += convert_term2.imagine;
        }
        else {
            convert_term1.real -= convert_term2.real;
            convert_term1.imagine -= convert_term2.imagine;
        }  //если мнимая часть отрицательная, то минус между мнимой и действительной частями выведется сам, а если она положительная, то мы должны вывести плюс вручную
        cout << convert_term1.real << (convert_term1.imagine >= 0 ? "+" : "") << convert_term1.imagine << "i" << endl;
    }
}

#include <iostream>

#include <string>

using namespace std;

struct complex_number { //создадим структуру комплексных чисел

int real;

int imagine;

};

complex_number convert(string term) {

complex_number x;

x.real = 1; //чтобы не вводить отдельные переменные для знака присвоим начальное значение не 0, а 1

x.imagine = 1;

if (term[0] == '-') { //если нулевой символ минус, то меняем значение действительной части на -1;

x.real *= -1;

term.erase(term.begin(), term.begin() + 1); //удаляем минус на нулевой позиции, если он есть, чтобы было легче найти второй знак

}

int index = term.find('+'); //находим индекс знака, если это плюс

if (index == -1) {

index = term.find('-'); //находим индекс знака, если это минус

x.imagine = -1; //меняем значение мнимой части на -1, если второй знак минус

}

x.real *= atoi(&term.substr(0, index)[0]); //находим действительную часть

x.imagine *= atoi(&term.substr(index + 1, term.size() - 2)[0]); //находим мнимую часть

return x; //возвращаем полученное комплексное число

}

int main() {

string term1, term2;

char sign;

complex_number convert_term1, convert_term2;

while (cin >> term1 >> sign >> term2) {

convert_term1 = convert(term1); //переводим первую строку в первое слагаемое

convert_term2 = convert(term2); //переводим вторую строку во второе слагаемое

if (sign == '+') { //выполняем действие соответствующее считанному знаку

convert_term1.real += convert_term2.real;

convert_term1.imagine += convert_term2.imagine;

}

else {

convert_term1.real -= convert_term2.real;

convert_term1.imagine -= convert_term2.imagine;

} //если мнимая часть отрицательная, то минус между мнимой и действительной частями выведется сам, а если она положительная, то мы должны вывести плюс вручную

cout << convert_term1.real << (convert_term1.imagine >= 0 ? "+" : "") << convert_term1.imagine << "i" << endl;

}

Решение

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

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

Ссылки

E-olymp

Ideone

Related Images:

e-olymp 1344. Личные дела

20/06/2019 by Михаил Бутник

Задача

Однажды, неловкая секретарша перепутала личные дела учащихся. Теперь их снова необходимо упорядочить сначала по классам, а внутри класса по фамилиям.

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

В первой строке дано число $N \left(1 \leqslant N \leqslant 1000\right)$ – количество личных дел. Далее для каждого из $N$ учащихся следующие данные (каждое в своей строке): фамилия и имя, класс, дата рождения. Фамилия и имя – строки не более чем из $20$ символов, класс – строка состоящая из числа (от $1$ до $11$) и латинской буквы (от «A» до «Z»), дата рождения – дата в формате «ДД.ММ.ГГ». Гарантируется, что внутри одного класса нет однофамильцев.

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

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

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	3 Sidorov Sidor 9A 20.07.93 Petrov Petr 10B 23.10.92 Ivanov Ivan 9A 10.04.93	9A Ivanov Ivan 10.04.93 9A Sidorov Sidor 20.07.93 10B Petrov Petr 23.10.92
2	4 Petrov Sidor 9A 20.07.02 Sidorov Petr 10B 23.10.01 Ivanov Bogdan 9A 10.04.02 Tereshkova Olga 9B 17.08.02	9A Ivanov Bogdan 10.04.02 9A Petrov Sidor 20.07.02 9B Tereshkova Olga 17.08.02 10B Sidorov Petr 23.10.01
3	2 Borisevich Sidor 9A 20.03.02 Burkalo Petr 9A 23.12.01	9A Borisevich Sidor 20.03.02 9A Burkalo Petr 23.12.01
4	1 Zadorozhniy Pavel 11A 20.03.02	11A Zadorozhniy Pavel 20.03.02

Код 1

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

struct student {
    string name, surname;
    char letter;
    int Class;
    string date;
};

bool operator > (const student &a, const student &b) {
    bool res = false;
    if (a.Class > b.Class) res = true;
    else if (a.Class == b.Class) {
        if (a.letter > b.letter) res = true;
        else if (a.letter == b.letter) {
            if (a.surname > b.surname) res = true;
        }
    }
    return res;
};

int main() {
    int n;
    cin >> n;
    student *a = new student[n];
    for (int i = 0; i < n; i++) {
        cin >> a[i].surname >> a[i].name >> a[i].Class >> a[i].letter >> a[i].date;
    }
    for (int k = 2; k <= n; k++) {
        for (int i = 0; i <= n - k; i++) {
            if (a[i] > a[i + 1]) {
                swap(a[i], a[i + 1]);
            }
        }
    }
    for (int i = 0; i < n; i++) {
        cout << a[i].Class << a[i].letter << " " << a[i].surname << " " << a[i].name << " " << a[i].date << endl;
    }
    return 0;
}

#include <iostream>

#include <string>

using namespace std;

struct student {

string name, surname;

char letter;

int Class;

string date;

};

bool operator > (const student &a, const student &b) {

bool res = false;

if (a.Class > b.Class) res = true;

else if (a.Class == b.Class) {

if (a.letter > b.letter) res = true;

else if (a.letter == b.letter) {

if (a.surname > b.surname) res = true;

}

return res;

};

int main() {

int n;

cin >> n;

student *a = new student[n];

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

cin >> a[i].surname >> a[i].name >> a[i].Class >> a[i].letter >> a[i].date;

}

for (int k = 2; k <= n; k++) {

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

if (a[i] > a[i + 1]) {

swap(a[i], a[i + 1]);

}

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

cout << a[i].Class << a[i].letter << " " << a[i].surname << " " << a[i].name << " " << a[i].date << endl;

}

return 0;

}

Код 2

#include <iostream>
using namespace std;
 
struct student {
  char name[21];
  char surname[21];
  char letter;
  int Class;
  char date[9];
};
 
bool operator > (const student & a,
  const student & b) {
  bool res = false;
  bool tmp = true;
  if (a.Class > b.Class) res = true;
  else if (a.Class == b.Class) {
    if (a.letter > b.letter) res = true;
    else if (a.letter == b.letter) {
      for (int i = 0; i < 21; i++) {
        if (a.surname[i] < b.surname[i]) {
          tmp = false;
          break;
        } else if (a.surname[i] > b.surname[i]) {
          tmp = true;
          break;
        }
      }
      if (tmp) res = true;
    }
  }
  return res;
};
 
int main() {
  int n;
  cin >> n;
  student *a = new student[n];
  for (int i = 0; i < n; i++) {
    cin >> a[i].surname >> a[i].name >> a[i].Class >> a[i].letter >> a[i].date;
  }
  for (int k = 2; k <= n; k++) {
    for (int i = 0; i <= n - k; i++) {
      if (a[i] > a[i + 1]) {
        swap(a[i], a[i + 1]);
      }
    }
  }
  for (int i = 0; i < n; i++) {
    cout << a[i].Class << a[i].letter << " " << a[i].surname << " " << a[i].name << " " << a[i].date << endl;
  }
  return 0;
}

#include <iostream>

using namespace std;

struct student {

char name[21];

char surname[21];

char letter;

int Class;

char date[9];

};

bool operator > (const student & a,

const student & b) {

bool res = false;

bool tmp = true;

if (a.Class > b.Class) res = true;

else if (a.Class == b.Class) {

if (a.letter > b.letter) res = true;

else if (a.letter == b.letter) {

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

if (a.surname[i] < b.surname[i]) {

tmp = false;

break;

} else if (a.surname[i] > b.surname[i]) {

tmp = true;

break;

}

if (tmp) res = true;

}

return res;

};

int main() {

int n;

cin >> n;

student *a = new student[n];

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

cin >> a[i].surname >> a[i].name >> a[i].Class >> a[i].letter >> a[i].date;

}

for (int k = 2; k <= n; k++) {

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

if (a[i] > a[i + 1]) {

swap(a[i], a[i + 1]);

}

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

cout << a[i].Class << a[i].letter << " " << a[i].surname << " " << a[i].name << " " << a[i].date << endl;

}

return 0;

}

Решение

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

Запустить код 1 (ideone) можно здесь
Запустить код 2 (ideone) можно здесь
Задача на E-olymp

Related Images:

e-olymp 4844. Поиск общей подстроки

24/02/2019 by Владимир Дроздин

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

Задача

Дана строка [latex] A = [/latex] [latex] a_1a_2…a_n [/latex] и строка [latex] B = [/latex] [latex] b_1b_2…b_m [/latex]. Также дано число [latex] L [/latex].

Нужно узнать, есть ли у строк [latex] A [/latex] и [latex] B [/latex] общая подстрока длиной [latex] L [/latex].

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

В первых двух строках записаны строки [latex]A[/latex] и [latex]B[/latex], состоящие из строчных латинских букв. Эти строки непустые и имеют длину не более [latex]100000[/latex] символов. В третьей строке записано целое число [latex]L (0 \leq L \leq 100000) [/latex] — длина общей подстроки.

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

В выходной файл выведите [latex]YES[/latex], если существует общая подстрока такой длины. В противном случае выведите [latex]NO[/latex].

Тесты

#	Входные данные	Выходные данные
1	saaa baaa 3	YES
2	raabc taaac 3	NO
3	aaaaaaaka akaa 3	YES
4	abcdfeg qwertycdfeg 10	NO

Код 1

#include <iostream>
#include <map>
using namespace std;
 
struct state {
    int len, link;
    map <char,int> next;
};
 
state st[2*100000]; 
int sz, last;
 
void sa_init() {
    sz = 0;
    last = 0;
    st[0].len = 0;
    st[0].link = -1;
    sz++;
}
 
void sa_extend (char c) {
    int cur = sz++;
    st[cur].len = st[last].len + 1;
    int p;
    for (p = last; p != -1 && !st[p].next.count(c); p = st[p].link) st[p].next[c] = cur;
    if (p == -1) st[cur].link = 0;
    else {
        int q = st[p].next[c];
        if (st[p].len + 1 == st[q].len) st[cur].link = q;
        else {
            int clone = sz++;
            st[clone].len = st[p].len + 1;
            st[clone].next = st[q].next;
            st[clone].link = st[q].link;
            st[q].link = st[cur].link = clone;
        }
    }
    last = cur;
}
 
int longest_common_string (string a, string b) {
    sa_init();
    for (int i = 0; i < a.length(); i++) sa_extend (a[i]);
    int v = 0, l = 0, best = 0, bestpos = 0;
    for (int i = 0; i < b.length(); i++) {
        while (v != 0 && ! st[v].next.count(b[i])) {
            v = st[v].link;
            l = st[v].len;
        }
        if (st[v].next.count(b[i])) {
            v = st[v].next[b[i]];
            l++;
        }
        if (l > best){
            best = l;
            bestpos = i;
        }
    }
    return best;
}
 
int main() {
    string a, b;
    int n;
    cin >> a >> b >> n;
    if (longest_common_string(a, b) >= n) cout << "YES";
    else cout << "NO";
    return 0;
}

#include <iostream>

#include <map>

using namespace std;

struct state {

int len, link;

map <char,int> next;

};

state st[2*100000];

int sz, last;

void sa_init() {

sz = 0;

last = 0;

st[0].len = 0;

st[0].link = -1;

sz++;

}

void sa_extend (char c) {

int cur = sz++;

st[cur].len = st[last].len + 1;

int p;

for (p = last; p != -1 && !st[p].next.count(c); p = st[p].link) st[p].next[c] = cur;

if (p == -1) st[cur].link = 0;

else {

int q = st[p].next[c];

if (st[p].len + 1 == st[q].len) st[cur].link = q;

else {

int clone = sz++;

st[clone].len = st[p].len + 1;

st[clone].next = st[q].next;

st[clone].link = st[q].link;

st[q].link = st[cur].link = clone;

}

last = cur;

}

int longest_common_string (string a, string b) {

sa_init();

for (int i = 0; i < a.length(); i++) sa_extend (a[i]);

int v = 0, l = 0, best = 0, bestpos = 0;

for (int i = 0; i < b.length(); i++) {

while (v != 0 && ! st[v].next.count(b[i])) {

v = st[v].link;

l = st[v].len;

}

if (st[v].next.count(b[i])) {

v = st[v].next[b[i]];

l++;

}

if (l > best){

best = l;

bestpos = i;

}

return best;

}

int main() {

string a, b;

int n;

cin >> a >> b >> n;

if (longest_common_string(a, b) >= n) cout << "YES";

else cout << "NO";

return 0;

}

Решение 1

Суффиксный автомат

Создадим структуру struct state, которая будет хранить информацию о переходах. len — это длина строки (далее будем использовать, как длину строки в каком-то состоянии), link — это суффиксальная ссылка, список переходов будем хранить в контейнере map <char, int> next, где ключом будет выступать символ, а значением — номер состояния.. Сам суффиксный автомат будем хранить в массиве этой структуры. Заведем переменные last и sz, отвечающие за последнее состояние и номер нового состояния соответственно.

Нам потребуется функция инициализирующая суффиксный автомат sa_init(). Так как вначале состояние лишь одно, то его длина равна [latex]0[/latex], а суффиксную ссылку приравняем к [latex]-1[/latex].

В автомат будем добавлять символы поочередно, для чего нам потребуется еще одна функция sa_extend(). В начале которой будем присваивать новому состоянию соответствующий номер. А затем будем просматривать все переходы из последнего состояния по текущему символу. Таким образом переход либо будет, либо нет. Если его нет, то добавим его в текущее состояние cur и продолжим смотреть дальше, если же при этом мы дошли до состояния, на которое указывает суффиксная ссылка изначального состояния (нулевого), то суффиксную ссылку текущего состояния приравняем к нулю. Далее рассматриваем случай, когда из текущего состояния по символу переход существует, обозначим q за состояние, куда ведет переход.

Поиск наибольшей общей подстроки

Сначала для строки a построим суффиксный автомат. Заведем две переменные, благодаря которым найдем совпадающую часть двух строк. Для этого нужна переменная, отвечающая за состояние v и переменная, отвечающая за длину совпадающей части l. Если есть переход, то переходим и увеличиваем длину на 1. Если нету, то уменьшаем длину совпадающей подстроки и переходим в новое состояние, меняя l. Цикл будет работать до тех пор, пока не найдем переход. Однако, если по суффиксным ссылкам мы дошли до состояния, в которое ведет ссылка изначальной вершины, то символ не встретился. Теперь длина наибольшей общей подстроки bestpos — это максимум из всех значений l.

Код 2

#include <iostream>
#include <cstring>
using namespace std;
 
int main() {
    char a[100001], b[100001]; 
    int l1, l2, l, k = 0;
    cin >> a >> b >> l;
    l1 = strlen(a);
    l2 = strlen(b);
    if (l1 < l || l2 < l) cout << "NO";
    else {
        for (int i = 0; i < l1; i ++) {
            for (int j = i; j <= l ; j ++) {
                if (a[j] == b[j]) k ++;
                else i ++;
                if (k == l) {
                    cout << "YES";
                    return 0;
                }
            }
            k = 0;
        }
        cout << "NO";
    }
    return 0;
}

#include <iostream>

#include <cstring>

using namespace std;

int main() {

char a[100001], b[100001];

int l1, l2, l, k = 0;

cin >> a >> b >> l;

l1 = strlen(a);

l2 = strlen(b);

if (l1 < l || l2 < l) cout << "NO";

else {

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

for (int j = i; j <= l ; j ++) {

if (a[j] == b[j]) k ++;

else i ++;

if (k == l) {

cout << "YES";

return 0;

}

k = 0;

}

cout << "NO";

}

return 0;

}

Решение 2

Стоит отметить сразу, что данный код, по сути не работает на некоторых тестах, например когда символы, которые должны входить в искомую наибольшую подстроку, стоят в начале или конце обоих строк или хотя бы одной из них. Однако, как показывает практика, тесты на e-olymp данный способ посимвольного сравнения проходит. В данном варианте решения будем использовать c-string. Сами строки объявлены так: char a[100001], b[100001];, где [latex]100001[/latex] — это максимальная длина строки, которая может быть по условию задачи, и еще [latex]+1[/latex]. Объявить можно было еще и так: char * a = new char [100001];

Ссылки

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:

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

04/04/2016 by Кудымовская Вика

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

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

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

push_front

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

push_back

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

pop_front

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

pop_back

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

front

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

back

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

size

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

clear

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

exit

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

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

pop_front,
pop_back,
front,
back

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

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

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

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

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

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

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

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

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

Реализация

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

#define SIZE 10000
struct deque
{
    int storage[SIZE];
    int _size = 0, start = 0, end = 0;
    void push_front(int n)
    {
        if (_size == SIZE) { cout << "Full\n"; }
        else if (_size == 0) { storage[start] = n; _size++; }
        else { 
            if (start == 0) { start = SIZE - 1; storage[start] = n; _size++; }
            else { start--; storage[start] = n; _size++; }
            }
    }
    void push_back(int n)
    {
        if (_size == SIZE) { cout << "Full\n"; }
        else if (_size == 0) { storage[end] = n; _size++; }
        else {
            if (end == SIZE-1) { end = 0; storage[end] = n; _size++; }
            else { end++; storage[end] = n; _size++; }
        }
    }
    int pop_front()
    {
        int b;
        if (_size != 0 && (start == end)) { b = storage[start]; _size--; return b; }
        else if (_size == 0) { return -1; }
        else
        {
            b = storage[start];
            if (start == SIZE - 1) { start = 0; _size--; }
            else { start++; _size--; }
            return b;
        }
    }
    int pop_back()
    {
        int b;
        if (_size != 0 && (start == end)) { b = storage[end]; _size--; return b; }
        else if (_size == 0) { return -1; }
        else
        {
            b = storage[end];
            if (end == 0) { end = SIZE - 1; _size--; }
            else { end--; _size--; }
            return b;
        }
    }
    int front() { if (_size == 0) return -1; else return storage[start]; }
    int back() { if (_size == 0) return -1; else return storage[end]; }
    int size() { return _size; }
    void clear()
    {
        _size = 0;
        start = end = 0; 
    }
};

int main()
{
    deque d;
    string s;
    int n;
    while (cin >> s)
    {
        if (s == "push_front")
        {
            cin >> n;
            d.push_front(n);
            cout << "ok\n";
        }
        else if (s == "push_back")
        {
            cin >> n;
            d.push_back(n);
            cout << "ok\n";
        }
        else if (s == "pop_front")
        {
            cout << d.pop_front() << endl;
        }
        else if (s == "pop_back")
        {
            cout << d.pop_back() << endl;
        }
        else if (s == "front")
        {
            cout << d.front() << endl;
        }
        else if (s == "back")
        {
            cout << d.back() << endl;
        }
        else if (s == "size")
        {
            cout << d.size() << endl;
        }
        else if (s == "clear")
        {
            d.clear();
            cout << "ok\n";
        }

        else if (s == "exit") {
            cout << "bye\n";
            return 0;
        }
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

#include <iostream>

#include <string>

using namespace std;

#define SIZE 10000

struct deque

{

int storage[SIZE];

int _size = 0, start = 0, end = 0;

void push_front(int n)

{

if (_size == SIZE) { cout << "Full\n"; }

else if (_size == 0) { storage[start] = n; _size++; }

else {

if (start == 0) { start = SIZE - 1; storage[start] = n; _size++; }

else { start--; storage[start] = n; _size++; }

}

void push_back(int n)

{

if (_size == SIZE) { cout << "Full\n"; }

else if (_size == 0) { storage[end] = n; _size++; }

else {

if (end == SIZE-1) { end = 0; storage[end] = n; _size++; }

else { end++; storage[end] = n; _size++; }

}

int pop_front()

{

int b;

if (_size != 0 && (start == end)) { b = storage[start]; _size--; return b; }

else if (_size == 0) { return -1; }

else

{

b = storage[start];

if (start == SIZE - 1) { start = 0; _size--; }

else { start++; _size--; }

return b;

}

int pop_back()

{

int b;

if (_size != 0 && (start == end)) { b = storage[end]; _size--; return b; }

else if (_size == 0) { return -1; }

else

{

b = storage[end];

if (end == 0) { end = SIZE - 1; _size--; }

else { end--; _size--; }

return b;

}

int front() { if (_size == 0) return -1; else return storage[start]; }

int back() { if (_size == 0) return -1; else return storage[end]; }

int size() { return _size; }

void clear()

{

_size = 0;

start = end = 0;

}

};

int main()

{

deque d;

string s;

int n;

while (cin >> s)

{

if (s == "push_front")

{

cin >> n;

d.push_front(n);

cout << "ok\n";

}

else if (s == "push_back")

{

cin >> n;

d.push_back(n);

cout << "ok\n";

}

else if (s == "pop_front")

{

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

}

else if (s == "pop_back")

{

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

}

else if (s == "front")

{

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

}

else if (s == "back")

{

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

}

else if (s == "size")

{

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

}

else if (s == "clear")

{

d.clear();

cout << "ok\n";

}

else if (s == "exit") {

cout << "bye\n";

return 0;

}

return 0;

}

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

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

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

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

Related Images:

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

31/03/2016 by Антон Локтев

Задача

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

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

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

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

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

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

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

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

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

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

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

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

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

Тесты

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

Код

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

struct queue{
    int storage[100000];
    int start;
    int finish;
    queue(){
        start = 0;
        finish = 0;
    }

    void push(int n){
        storage[finish] = n;
        finish++;
    }

    int pop(){
        int a = storage[start];
        start++;
        return a;
    }

    int front(){
        return storage[start];
    }

    int size(){
        return finish - start;
    }

    string clear(){
        finish = 0;
        start = 0;
        return "ok";
    }

    string exit(){
        return "bye";
    }
};

int main() {
    string a;
    queue x;
    while(cin >> a){
        if(a == "push"){
            int n;
            cin >> n;
            x.push(n);
            cout << "ok" << endl;
        }
        if(a == "pop"){
            cout << x.pop() << endl;
        }
        if(a == "front"){
            cout << x.front() << endl;
        }
        if(a == "size"){
            cout << x.size() << endl;
        }
        if(a == "clear"){
            cout << x.clear() << endl;
        }
        if(a == "exit"){
            cout << x.exit() << endl;
            return 0;
        }
    }
    return 0;
}

#include <iostream>

#include <string>

using namespace std;

struct queue{

int storage[100000];

int start;

int finish;

queue(){

start = 0;

finish = 0;

}

void push(int n){

storage[finish] = n;

finish++;

}

int pop(){

int a = storage[start];

start++;

return a;

}

int front(){

return storage[start];

}

int size(){

return finish - start;

}

string clear(){

finish = 0;

start = 0;

return "ok";

}

string exit(){

return "bye";

}

};

int main() {

string a;

queue x;

while(cin >> a){

if(a == "push"){

int n;

cin >> n;

x.push(n);

cout << "ok" << endl;

}

if(a == "pop"){

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

}

if(a == "front"){

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

}

if(a == "size"){

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

}

if(a == "clear"){

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

}

if(a == "exit"){

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

return 0;

}

return 0;

}

Ход решения

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

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

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

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:

Условие

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

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

Тесты

№

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

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

Код

Решение

Ссылки

Related Images:

Задача

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

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

Тесты

Код 1

Код 2

Решение

Related Images:

Задача

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

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

Тесты

Код 1

Решение 1

Суффиксный автомат

Поиск наибольшей общей подстроки

Код 2

Решение 2

Ссылки

Related Images:

Related Images:

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

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

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

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

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

Реализация

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

Related Images:

Related Images:

Related Images: