Category Archives: B. Стеки-деки-очереди

К этой категории относятся задачи двух типов. Задачи первого типа требуют реализации поведения очереди, стека или дека при помощи обычных массивов или списочных структур. В задачах второго типа необходимо использовать соответствующие классы из STL. Обычно тип задачи ясен из условия. Если это не так, то обратитесь за разъяснением к преподавателю.

В этой категории встречаются задачи с префиксом AL. Это задачи, взятые с сайта ALGOLIST. К ним стоит подойти с особым вниманием и разработать хороший набор тестов.

e-olymp 8669. Все делители

14/12/2019 by Катя Романцова

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

Найдите все делители натурального числа $n$.

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

Одно натуральное число $ n ( n \leqslant 10^9 ) $.

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

Выведите в возрастающем порядке все делители числа $n$.

Тесты

№	Входные данные	Выходные данные
1	10	1 2 5 10
2	36	1 2 3 4 6 9 12 18 36
3	455	1 5 7 13 35 65 91 455
4	38965	1 5 7793 38965
5	999999	1 3 7 9 11 13 21 27 33 37 39 63 77 91 99 111 117 143 189 231 259 273 297 333 351 407 429 481 693 777 819 999 1001 1221 1287 1443 2079 2331 2457 2849 3003 3367 3663 3861 4329 5291 6993 8547 9009 10101 10989 12987 15873 25641 27027 30303 37037 47619 76923 90909 111111 142857 333333 999999
6	1000000000	1 2 4 5 8 10 16 20 25 32 40 50 64 80 100 125 128 160 200 250 256 320 400 500 512 625 640 800 1000 1250 1280 1600 2000 2500 2560 3125 3200 4000 5000 6250 6400 8000 10000 12500 12800 15625 16000 20000 25000 31250 32000 40000 50000 62500 64000 78125 80000 100000 125000 156250 160000 200000 250000 312500 320000 390625 400000 500000 625000 781250 800000 1000000 1250000 1562500 1600000 1953125 2000000 2500000 3125000 3906250 4000000 5000000 6250000 7812500 8000000 10000000 12500000 15625000 20000000 25000000 31250000 40000000 50000000 62500000 100000000 125000000 200000000 250000000 500000000 1000000000

Код

Код №1

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

int main() {
    int n;
    cin >> n;
        const double sqrt_n = sqrt ( n );
    for ( int i = 1; i < sqrt_n; i++ ) {
        if ( n % i == 0 ) cout << i << " "; 
    }
    for ( int i = sqrt_n; i >= 1; i-- ) { 
        if ( n % i == 0 ) cout << n / i << " ";
    } 
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

int n;

cin >> n;

const double sqrt_n = sqrt ( n );

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

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

}

for ( int i = sqrt_n; i >= 1; i-- ) {

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

}

return 0;

}

Код №2

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

int main() {
    int n;
    cin >> n;
    int < stack > div;
    const double sqrt_n = sqrt ( n ); 
    for ( int i = 1; i <= sqrt_n; i++ ) {
        if ( n % i == 0 ) {
            div.push ( i );
            cout << i << " ";
        }
    }
    if ( div.top () == sqrt_n ) div.pop(); //удаляем последний элемент, если он является корнем
    while ( !div.empty () ) {
            cout << n / div.top () << " ";
            div.pop (); //выводим и удаляем первый элемент
    }
    return 0;
}

#include <iostream>

#include <cmath>

#include <stack>

using namespace std;

int main() {

int n;

cin >> n;

int < stack > div;

const double sqrt_n = sqrt ( n );

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

if ( n % i == 0 ) {

div.push ( i );

cout << i << " ";

}

if ( div.top () == sqrt_n ) div.pop(); //удаляем последний элемент, если он является корнем

while ( !div.empty () ) {

cout << n / div.top () << " ";

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

}

return 0;

}

Решение

Можно заметить, что делитель и частное взаимодополняют друг друга. Мы найдем делители, потом частные этого выражения. Так как частные также являются делителями. Значит последовательность делителей в порядке возрастания можно разделить на две части. Создадим два цикла для нахождения этих двух частей:

В первом цикле проверяем каждое натуральное число от $1$ до $\sqrt n$. В коде №1 выводим числа, если они являются делителями. В коде №2 помещаем их в стек и выводим;
Во втором цикле в коде №1 делим заданное число $n$ на все делители и выводим. В коде №2 делим заданное число $n$ на все элементы стека и выводим.

Примечание: для избежания повторения в коде №2, удаляем $\sqrt n$ из стека.

Ссылки

Условие задачи на E-olymp

Код №1 на Ideone

Код №2 на Ideone

Засчитанный код №1 на E-olymp

Засчитанный код №2 на E-olymp

Related Images:

e-olymp 2270. Поиск цикла

02/12/2019 by Наташа Писаревская

Задача

Дан ориентированный невзвешенный граф. Необходимо определить есть ли в нём циклы, и если есть, то вывести любой из них.

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

В первой строке находятся два натуральных числа $n$ и $m$ $($$1$ $\leqslant$ $n$ $\leqslant$ $10$^$5$$, $$1$ $\leqslant$ $m$ $\leqslant$ $10$^$5$$)$ — количество вершин и ребер в графе соответственно. Далее в $m$ строках перечислены рёбра графа. Каждое задаётся парой чисел — номерами начальной и конечной вершин соответственно.

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

Если в графе нет цикла, то вывести «NO», иначе вывести «YES» и затем перечислить вершины в порядке обхода цикла.

Тесты

№	Входные данные	Выходные данные
1	2 2 1 2 1 2	NO
2	2 2 1 2 2 1	YES 1 2
3	6 7 1 2 1 5 2 3 2 4 4 6 6 5 5 2	YES 2 4 6 5
4	6 6 1 3 2 4 3 4 1 2 3 5 3 6	NO
5	4 4 1 3 4 2 2 3 3 4	YES 3 4 2

#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> graph; 
vector<int> used, path;
int flag, n, m;
// поиск в глубину для каждой вершины
void dfs (int v) {
    if (flag == 1) return; // если уже нашли цикл, то останавливаемся
    else {
        used[v] = 1; // посещаем вершину 
        path.push_back(v); // добавляем ее в порядок обхода графа
        for (int i = 0; i < graph[v].size(); i++) {
            int to = graph[v][i];// следующая вершина графа
            if (used[to] == 1) { // если мы ее посетили, но не вышли из нее, значит мы нашли цикл
                path.push_back(to); // добавляем следующую вершину в порядок обхода графа
                flag = 1; // ставим индикатор, что мы нашли цикл и останавливаемся
                return;
            } 
            else {
                dfs(to); // если не посетили, то посещаем 
            }
            if (flag == 1) return; // если нашли цикл, то останавливаемся 
        }
        used[v] = 2; // если не нашли цикл, то выходим из вершины 
        path.pop_back();
    }
} 
// проверяем вершины на наличие цикла 
void checkNodes() { 
    for (int i = 1; i <= n; i++) {
        if (used[i] == 0) { // если не посещали вершину, то посещаем ее 
            dfs(i);
            if (flag == 1) return; // если нашли цикл, то останавливаемся
        }   
    }
} 
int main(){
    int v1, v2; 
    cin >> n >> m; // считываем количество вершин и ребер 
    graph.resize(n + 1); 
    used.resize(n + 1, 0);
    for (int i = 0; i < m; i++) {
        cin >> v1 >> v2; // считываем ребра и заполняем граф
        graph[v1].push_back(v2);
    }
    checkNodes();  // проверяем вершины на наличие цикла
    if (flag == 1) { // если цикл найден
        int i = path.size() - 2; // последняя вершина цикла   
        int to = path.back(); // вершина в которой зациклились 
        while (path[i] != to) { // получаем индекс вершины в которой зациклились
            i--;
        }
        cout << "YES" << endl;
        while (i < path.size() - 1) { // выводим сам цикл
            cout << path[i] << " ";
            i++; 
        }
        cout << endl;
    }
    else cout << "NO" << endl;
}

#include <iostream>

#include <vector>

using namespace std;

vector<vector<int>> graph;

vector<int> used, path;

int flag, n, m;

// поиск в глубину для каждой вершины

void dfs (int v) {

if (flag == 1) return; // если уже нашли цикл, то останавливаемся

else {

used[v] = 1; // посещаем вершину

path.push_back(v); // добавляем ее в порядок обхода графа

for (int i = 0; i < graph[v].size(); i++) {

int to = graph[v][i];// следующая вершина графа

if (used[to] == 1) { // если мы ее посетили, но не вышли из нее, значит мы нашли цикл

path.push_back(to); // добавляем следующую вершину в порядок обхода графа

flag = 1; // ставим индикатор, что мы нашли цикл и останавливаемся

return;

}

else {

dfs(to); // если не посетили, то посещаем

}

if (flag == 1) return; // если нашли цикл, то останавливаемся

}

used[v] = 2; // если не нашли цикл, то выходим из вершины

path.pop_back();

}

// проверяем вершины на наличие цикла

void checkNodes() {

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

if (used[i] == 0) { // если не посещали вершину, то посещаем ее

dfs(i);

if (flag == 1) return; // если нашли цикл, то останавливаемся

}

int main(){

int v1, v2;

cin >> n >> m; // считываем количество вершин и ребер

graph.resize(n + 1);

used.resize(n + 1, 0);

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

cin >> v1 >> v2; // считываем ребра и заполняем граф

graph[v1].push_back(v2);

}

checkNodes(); // проверяем вершины на наличие цикла

if (flag == 1) { // если цикл найден

int i = path.size() - 2; // последняя вершина цикла

int to = path.back(); // вершина в которой зациклились

while (path[i] != to) { // получаем индекс вершины в которой зациклились

i--;

}

cout << "YES" << endl;

while (i < path.size() - 1) { // выводим сам цикл

cout << path[i] << " ";

i++;

}

cout << endl;

}

else cout << "NO" << endl;

}

Решение

Для решения данной задачи воспользуемся поиском в глубину. Также будем отмечать вершины в различными цветами ($0$ (белый) — мы еще не посещали вершину, $1$ (серый) — посетили вершину и не вышли из нее (зациклились), $2$ (черный) — посетили вершину и вышли из неё).

В векторе $graph$ будем хранить сам граф, для проверки на цикличность воспользуемся вектором $visited$, так же будем хранить порядок обхода графа в векторе $path$. Так как по условию, в случае нескольких циклов, необходимо вывести любой, то мы будем находить первый и на этом останавливаться, для этого заведем переменную $flag$, которая равна 1, если цикл уже найден, и равна 0, если цикл еще не найден. В векторе $visited$ будем окрашивать вершину в один из цветов. Если мы захотим посетить $1$ (серую) вершину, то это будет означать, что мы отыскали цикл в этой вершине, тогда устанавливаем $flag = 1$.

Осталось лишь вывести его на экран. Для этого воспользуемся вектором $path$, в котором последний элемент — вершина, в которой цикл. Ищем предпоследнее вхождение этой вершины в векторе $path$ и выводим сам цикл.

Ссылки

Условие задачи на e-olymp

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

Related Images:

Алгоритмы поиска

16/11/2019 by Мазурок Игорь Евгеньевич

Search Algorithms

Хочу предложить простой, но достаточно общий взгляд на алгоритмы поиска в ширину BFS (Breadth-first Search), в глубину DFS (Depth-first Search) и бесконечное количество других с общей схемой. Фактически это алгоритмы обхода соседних вершин графа в которых последовательно строятся пути из некоторой исходной вершины ко всем остальным.
Сначала сформулируем общую схему алгоритмов этого типа. И без обычных для учебников избыточных сложностей в виде белых-серых-черных вершин.

Заводим PLAN поиска — контейнер данных, где будем хранить вершины в которых мы планируем побывать. Изначально он пуст.
Добавляем в PLAN поиска исходную вершину с которой нам предписано начать.
Пока PLAN не пуст и цель поиска не достигнута делаем следующее
1. GET: Извлекаем из PLAN какую-нибудь вершину v.
2. Посещаем вершину v. Если мы не просто обходим вершины, а что-то ищем, то здесь самое время обыскать вершину v на предмет достижения цели поиска.
3. Как-то отмечаем, что вершина v уже посещена.
4. PUT: Добавляем в PLAN все соседние с v вершины, которые еще не были посещены.
Выводим результат поиска.

Самым важным для реализации этой схемы является PLAN. Это контейнер данных в котором нам нужны две функции GET — чтобы что-то из контейнера достать и PUT — чтобы в контейнер что-то положить. Конечно лучше использовать уже готовые контейнеры. Выбор контейнера будет определять стратегию поиска.
DFS (Depth-first Search). Например, если в качестве контейнера выбрать СТЕК, то мы реализуем алгоритм поиска в глубину. Ведь организация доступа к элементам стека такова, что мы в первую очередь будем посещать те вершины, которые попали в план последними. Посмотрим на код решения задачи
Обход в глубину:

#include <iostream>
#include <stack>
using namespace std;
int main() {
    // чтение исходных данных
    int n, v;
    cin >> n >> v;
    int matrix[n][n];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> matrix[i][j];
    stack <int> plan; // план посещения в виде стека
    plan.push(--v);   // мы нумеруем с 0, а не с 1
    matrix[v][v] = 1; // отмечаем, что эта вершина уже заносилась в план 
    int counter = 1;  // начальную уже сосчитали
    while (!plan.empty()) {
        v = plan.top(); // посещаем следующую по плану вершину 
        plan.pop();       // удаляем ее из плана посещения
        for (int u = 0; u < n; u++) { // перебираем соседние с ней
            if (matrix[v][u] and !matrix[u][u]) { // если новая, то
                plan.push(u);     // добавляем ее в план
                matrix[u][u] = 1; // отмечаем, что уже не новая
                counter++;        // считаем, сколько было вершин
            }
        }
    }
    cout << counter << endl;
}

#include <iostream>

#include <stack>

using namespace std;

int main() {

// чтение исходных данных

int n, v;

cin >> n >> v;

int matrix[n][n];

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

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

cin >> matrix[i][j];

stack <int> plan; // план посещения в виде стека

plan.push(--v); // мы нумеруем с 0, а не с 1

matrix[v][v] = 1; // отмечаем, что эта вершина уже заносилась в план

int counter = 1; // начальную уже сосчитали

while (!plan.empty()) {

v = plan.top(); // посещаем следующую по плану вершину

plan.pop(); // удаляем ее из плана посещения

for (int u = 0; u < n; u++) { // перебираем соседние с ней

if (matrix[v][u] and !matrix[u][u]) { // если новая, то

plan.push(u); // добавляем ее в план

matrix[u][u] = 1; // отмечаем, что уже не новая

counter++; // считаем, сколько было вершин

}

cout << counter << endl;

}

Единственное важное пояснение. Чтобы отметить, что вершина уже посещалась, я использую диагональ матрицы смежности графа. в условии специально подчеркнули, что там всегда нули, а значит я могу поставить matrix[v][v] = 1, чтобы обозначить вершину v как уже посещенную.

BFS (Breadth-first Search). Стоит нам немного изменить код и использовать для хранения плана ОЧЕРЕДЬ, алгоритм меняет стратегию и осуществляет поиск в ширину. Поскольку вершины будут посещаться в том порядке в котором мы их добавляли, это очень похоже на распространение волны из начальной точки. Отсюда другое название таких алгоритмов — заливки (flood) или волновые алгоритмы.

#include <iostream>
#include <queue>
using namespace std;
int main() {
    // чтение исходных данных
    int n, v;
    cin >> n >> v;
    int matrix[n][n];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> matrix[i][j];
    queue <int> plan; // план посещения в виде очереди
    plan.push(--v);   // мы нумеруем с 0, а не с 1
    matrix[v][v] = 1; // отмечаем, что эта вершина уже заносилась в план 
    int counter = 1;  // начальную уже сосчитали
    while (!plan.empty()) {
        v = plan.front(); // посещаем следующую по плану вершину 
        plan.pop();       // удаляем ее из плана посещения
        for (int u = 0; u < n; u++) { // перебираем соседние с ней
            if (matrix[v][u] and !matrix[u][u]) { // если новая, то
                plan.push(u);     // добавляем ее в план
                matrix[u][u] = 1; // отмечаем, что уже не новая
                counter++;        // считаем, сколько было вершин
            }
        }
    }
    cout << counter << endl;
}

#include <iostream>

#include <queue>

using namespace std;

int main() {

// чтение исходных данных

int n, v;

cin >> n >> v;

int matrix[n][n];

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

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

cin >> matrix[i][j];

queue <int> plan; // план посещения в виде очереди

plan.push(--v); // мы нумеруем с 0, а не с 1

matrix[v][v] = 1; // отмечаем, что эта вершина уже заносилась в план

int counter = 1; // начальную уже сосчитали

while (!plan.empty()) {

v = plan.front(); // посещаем следующую по плану вершину

plan.pop(); // удаляем ее из плана посещения

for (int u = 0; u < n; u++) { // перебираем соседние с ней

if (matrix[v][u] and !matrix[u][u]) { // если новая, то

plan.push(u); // добавляем ее в план

matrix[u][u] = 1; // отмечаем, что уже не новая

counter++; // считаем, сколько было вершин

}

cout << counter << endl;

}

Если для хранения плана написать свой контейнер или хотя бы переопределить методы GET и PUT, то вы получите новый алгоритм поиска. Например, можно извлекать вершину из плана случайным образом. В этом случае мы получим один из рандомизированных алгоритмов семейства Монте-Карло.

Задание: Найдите все четыре места, где код поиска в глубину отличается от кода поиска в ширину.
Подсказка: Если не смогди найти четвертое отличие — оно в комментариях 🙂

Related Images:

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

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

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

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

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

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

Тесты

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

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

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


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

#include <iostream>

#include <cstring>

#include <stack>

using namespace std;

stack<int> s;

char str[100];

int n;

int main(void)

{

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

{

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

{

cin>>n;;

s.push(n);

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

} else

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

{

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

s.pop();

} else

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

{

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

} else

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

{

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

} else

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

{

while(!s.empty())

s.pop();

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

} else

{

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

break;

}

return 0;

}

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

Ссылки

Related Images:

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

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

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

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

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

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

Тесты

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

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

#include <iostream>
using namespace std;

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

#include <iostream>

using namespace std;

int main() {

int k = 0;

double p[101] = {0};

double x[200];

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

cin >> x[i];

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

p[k]+=1;

}

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

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

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

}

return 0;

}

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

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

import java.util.*;

import java.lang.*;

import java.io.*;

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

class Ideone {

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

int k = 0;

Scanner in = new Scanner(System.in);

double[] x = new double[200];

double[] p = new double[101];

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

x[i] = in.nextDouble();

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

p[k] += 1;

}

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

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

}

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

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

Related Images:

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

01/06/2017 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, если это не указано особо.

Тесты

№

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

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

push_back 3

push_back 14

size

clear

push_front 1

back

push_back 2

front

pop_back

size

pop_front

size

exit

bye

size

push_back 8

push_front 4

size

front

back

push_back 3

pop_front

front

pop_back

back

exit

bye

Решение

#include <iostream>
#include <vector>
#include <string>
using namespace std;
struct Deque
{
    vector<int> box1;
    vector<int> box2;
    int n, box_size=0;
    void push_front(int n)
    {
        box1.push_back(n);
        box_size++;
    }
    void push_back(int n)
    {
        box2.push_back(n);
        box_size++;
    }
    int pop_front()
    {
        if(box1.size()>0)
        {
            int a=box1[box1.size()-1];
            box1.erase(box1.end()-1);
            box_size--;
            return a;
        }
        else if(box2.size()>0)
        {
            int a=box2[0];
            box2.erase(box2.begin());
            box_size--;
            return a;
        }
        return 1;
    }
    int pop_back()
    {
        if(box2.size()>0)
        {
            int a=box2[box2.size()-1];
            box2.erase(box2.end()-1);
            box_size--;
            return a;
        }
        else if(box1.size()>0)
        {
            int a=box1[0];
            box1.erase(box1.begin());
            box_size--;
            return a;
        }
        return 1;
    }
    int front()
    {
        if(box1.size()>0)
        {
            int a=box1[box1.size()-1];
            return a;
        }
        else if(box2.size()>0)
        {
            int a=box2[0];
            return a;
        }
        return 1;
    }
    int back()
    {
        if(box2.size()>0)
        {
            int a=box2[box2.size()-1];
            return a;
        }
        else if(box1.size()>0)
        {
            int a=box1[0];
            return a;
        }
        return 1;
    }
    int size()
    {
        return box_size;
    }
    string clear()
    {
        box1.erase(box1.begin(), box1.end());
        box2.erase(box2.begin(), box2.end());
        box_size=0;
        return "ok";
    }
    string exit()
    {
        return "bye";
    }
};
int main() 
{
    Deque a;
    string s;
    while(cin>>s)
    {
        if(s=="push_front")
        {
            int n;
            cin>>n;
            a.push_front(n);
            cout<<"ok"<<endl;
        }
        if(s=="push_back")
        {
            int n;
            cin>>n;
            a.push_back(n);
            cout<<"ok"<<endl;
        }
        if(s=="pop_front")
        {
            cout<<a.pop_front()<<endl;
        }
        if(s=="pop_back")
        {
            cout<<a.pop_back()<<endl;
        }
        if(s=="front")
        {
            cout<<a.front()<<endl;
        }
        if(s=="back")
        {
            cout<<a.back()<<endl;
        }
        if(s=="size")
        {
            cout<<a.size()<<endl;
        }
        if(s=="clear"){
            a.clear();
            cout<<a.clear()<<endl;
        }
        if(s=="exit")
        {
            cout<<a.exit()<<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

151

#include <iostream>

#include <vector>

#include <string>

using namespace std;

struct Deque

{

vector<int> box1;

vector<int> box2;

int n, box_size=0;

void push_front(int n)

{

box1.push_back(n);

box_size++;

}

void push_back(int n)

{

box2.push_back(n);

box_size++;

}

int pop_front()

{

if(box1.size()>0)

{

int a=box1[box1.size()-1];

box1.erase(box1.end()-1);

box_size--;

return a;

}

else if(box2.size()>0)

{

int a=box2[0];

box2.erase(box2.begin());

box_size--;

return a;

}

return 1;

}

int pop_back()

{

if(box2.size()>0)

{

int a=box2[box2.size()-1];

box2.erase(box2.end()-1);

box_size--;

return a;

}

else if(box1.size()>0)

{

int a=box1[0];

box1.erase(box1.begin());

box_size--;

return a;

}

return 1;

}

int front()

{

if(box1.size()>0)

{

int a=box1[box1.size()-1];

return a;

}

else if(box2.size()>0)

{

int a=box2[0];

return a;

}

return 1;

}

int back()

{

if(box2.size()>0)

{

int a=box2[box2.size()-1];

return a;

}

else if(box1.size()>0)

{

int a=box1[0];

return a;

}

return 1;

}

int size()

{

return box_size;

}

string clear()

{

box1.erase(box1.begin(), box1.end());

box2.erase(box2.begin(), box2.end());

box_size=0;

return "ok";

}

string exit()

{

return "bye";

}

};

int main()

{

Deque a;

string s;

while(cin>>s)

{

if(s=="push_front")

{

int n;

cin>>n;

a.push_front(n);

cout<<"ok"<<endl;

}

if(s=="push_back")

{

int n;

cin>>n;

a.push_back(n);

cout<<"ok"<<endl;

}

if(s=="pop_front")

{

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

}

if(s=="pop_back")

{

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

}

if(s=="front")

{

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

}

if(s=="back")

{

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

}

if(s=="size")

{

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

}

if(s=="clear"){

a.clear();

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

}

if(s=="exit")

{

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

break;

}

return 0;

}

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

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

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

e-olymp.

Related Images:

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

21/05/2017 by Валентина Андриеш

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

push_front

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

push_back

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

pop_front

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

pop_back

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

front

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

back

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

size

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

clear

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

exit

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

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

Тесты

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

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

struct Node{                //структура звена списка 
    int value;          //передаваемое значение
    Node *next, *prev;      //указатели на следующий и предыдущий элементы
};

struct deque{
    Node *head=nullptr;     //инициализация начала и конца списка, размера дека 
    Node *tail=nullptr;
    int count=0;
    void push_back(int num){
        Node* element=new Node; //выделение памяти под новый элемент структуры
        element->value=num;  //добавляем значение в структуру
        count++;
        if(!head){          //если список пуск
            head=element;       //т.к элемент единственный, 
            tail=head;      //он является и хвостом и головой
        }
        else{
            element->prev=tail; //предыдущий элемент списка относительно добавленного, будет последним(хвостом)
            tail->next=element; //следующий элемент за хвостом это добавляемый элемент списка
            tail=element;       //присваивание элементу статуса хвоста
        }
        cout<<"ok"<<endl;
    }
    void push_front(int num){
        Node *element=new Node;
        element->value=num;
        count++;
        if(!head){
            head=element;
            tail=head;
        }
        else{
            element->next=head;      //следующий элемент за добавляемым элементом является хвост
            head->prev=element;      //перед головой находится добавляемый элемент
            head=element;           //присваивание элементу статуса головы
        }
        cout<<"ok"<<endl;
    }
    void pop_back(){
        if(count!=0){               //если дек не пустой
            cout<<tail->value<<endl;
            if(count>1){         //если в деке находится больше одного элемента
                Node *element=tail;     //указываем на то, что будет использоваться хвост
                tail=tail->prev; //присваиваем статус хвоста предыдущему элементу
                tail->next=nullptr;     //указываем на то, что за элементом пусто
                delete element;     //удаляем бывший хвост
                count--;        //уменьшаем размер дека
            }
            else{               //если в деке находится всего один элемент
                head=tail=0;        //присваиваем ему значение ноль
                count--;        //уменьшаем размер дека
            }
        }
        else cout<<"error"<<endl;
    }
    void pop_front(){
        if(count!=0){
            cout<<head->value<<endl;
            if(head->next){          //если в деке больше одного элемента 
                Node *element=head; //указываем на то, что будем использовать голову
                head=head->next; //присваиваем статус головы следующему за бывшей головой элементу 
                head->prev=nullptr;  //указываем на то, что перед головой пусто
                delete element;     //удаляем бывшую голову
                count--;        //уменьшаем размер дека
            }
            else if(head==tail){    //если элемент один в деке
                head->next=nullptr;  //указываем, что за головой пусто
                head=nullptr;       //указываем на то, что голова тоже пуста
                delete head;        //удаляем единственный элемент
                count=0;        //присваиваем ноль размеру дека
            }
        }
        else cout<<"error"<<endl;
    }
    void back(){
        if(count!=0)cout<<tail->value<<endl; //выводим значение хвоста
        else cout<<"error"<<endl;
    }
    void front(){
        if(count!=0)cout<<head->value<<endl; //выводим значение головы
        else cout<<"error"<<endl;
    }
    void size(){
        cout<<count<<endl;          //выводим размер дека
    }
    void clear(){
        count=0;               //присваиваем размеру дека ноль
        cout<<"ok"<<endl;
        while(head)             //цикл: пока по адресу головы что-то лежит
     {
         tail=head->next;        //присваиваем статус хвоста следующему элементу, что лежит за головой 
         delete head;           //удаляем первый элемент дека
         head=tail;             //указываем на то, что хвост принимает статус головы
     }
    }
    void exit(){
        cout<<"bye";
    }
};

int main() {
    deque deq;
    string str;
    while(cin>>str){
        if(str=="push_front"){
            int num;
            cin>>num;
            deq.push_front(num);
        }
        if(str=="push_back"){
            int num;
            cin>>num;
            deq.push_back(num);
        }
        if(str=="pop_front")deq.pop_front();
        if(str=="pop_back")deq.pop_back();
        if(str=="clear")deq.clear();
        if(str=="size")deq.size();
        if(str=="front")deq.front();
        if(str=="back")deq.back();
        if(str=="exit"){
            deq.exit();
            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

#include <iostream>

#include <string>

using namespace std;

struct Node{ //структура звена списка

int value; //передаваемое значение

Node *next, *prev; //указатели на следующий и предыдущий элементы

};

struct deque{

Node *head=nullptr; //инициализация начала и конца списка, размера дека

Node *tail=nullptr;

int count=0;

void push_back(int num){

Node* element=new Node; //выделение памяти под новый элемент структуры

element->value=num; //добавляем значение в структуру

count++;

if(!head){ //если список пуск

head=element; //т.к элемент единственный,

tail=head; //он является и хвостом и головой

}

else{

element->prev=tail; //предыдущий элемент списка относительно добавленного, будет последним(хвостом)

tail->next=element; //следующий элемент за хвостом это добавляемый элемент списка

tail=element; //присваивание элементу статуса хвоста

}

cout<<"ok"<<endl;

}

void push_front(int num){

Node *element=new Node;

element->value=num;

count++;

if(!head){

head=element;

tail=head;

}

else{

element->next=head; //следующий элемент за добавляемым элементом является хвост

head->prev=element; //перед головой находится добавляемый элемент

head=element; //присваивание элементу статуса головы

}

cout<<"ok"<<endl;

}

void pop_back(){

if(count!=0){ //если дек не пустой

cout<<tail->value<<endl;

if(count>1){ //если в деке находится больше одного элемента

Node *element=tail; //указываем на то, что будет использоваться хвост

tail=tail->prev; //присваиваем статус хвоста предыдущему элементу

tail->next=nullptr; //указываем на то, что за элементом пусто

delete element; //удаляем бывший хвост

count--; //уменьшаем размер дека

}

else{ //если в деке находится всего один элемент

head=tail=0; //присваиваем ему значение ноль

count--; //уменьшаем размер дека

}

else cout<<"error"<<endl;

}

void pop_front(){

if(count!=0){

cout<<head->value<<endl;

if(head->next){ //если в деке больше одного элемента

Node *element=head; //указываем на то, что будем использовать голову

head=head->next; //присваиваем статус головы следующему за бывшей головой элементу

head->prev=nullptr; //указываем на то, что перед головой пусто

delete element; //удаляем бывшую голову

count--; //уменьшаем размер дека

}

else if(head==tail){ //если элемент один в деке

head->next=nullptr; //указываем, что за головой пусто

head=nullptr; //указываем на то, что голова тоже пуста

delete head; //удаляем единственный элемент

count=0; //присваиваем ноль размеру дека

}

else cout<<"error"<<endl;

}

void back(){

if(count!=0)cout<<tail->value<<endl; //выводим значение хвоста

else cout<<"error"<<endl;

}

void front(){

if(count!=0)cout<<head->value<<endl; //выводим значение головы

else cout<<"error"<<endl;

}

void size(){

cout<<count<<endl; //выводим размер дека

}

void clear(){

count=0; //присваиваем размеру дека ноль

cout<<"ok"<<endl;

while(head) //цикл: пока по адресу головы что-то лежит

{

tail=head->next; //присваиваем статус хвоста следующему элементу, что лежит за головой

delete head; //удаляем первый элемент дека

head=tail; //указываем на то, что хвост принимает статус головы

}

void exit(){

cout<<"bye";

}

};

int main() {

deque deq;

string str;

while(cin>>str){

if(str=="push_front"){

int num;

cin>>num;

deq.push_front(num);

}

if(str=="push_back"){

int num;

cin>>num;

deq.push_back(num);

}

if(str=="pop_front")deq.pop_front();

if(str=="pop_back")deq.pop_back();

if(str=="clear")deq.clear();

if(str=="size")deq.size();

if(str=="front")deq.front();

if(str=="back")deq.back();

if(str=="exit"){

deq.exit();

break;

}

return 0;

}

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

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

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

Related Images:

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

09/05/2017 by Андреев Даниил

Задача

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

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

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

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

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

Тесты

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

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

#include <iostream>
#include <deque>
using namespace std;
 
int main(){
    deque<int> folder;
    unsigned long long N;
    
    cin >> N;
    folder.push_back(N%10);
    N/=10;
    while (N!=0){
        for (int i=0; i<folder.size(); i++){
            if (folder.at(i) == N%10)
                i+=folder.size();   
            if (i == folder.size() -1)
                folder.push_back(N%10);
        }
        N/=10;
    }
    cout << "sum:" << folder.size();
 
    return 0;
}

#include <iostream>

#include <deque>

using namespace std;

int main(){

deque<int> folder;

unsigned long long N;

cin >> N;

folder.push_back(N%10);

N/=10;

while (N!=0){

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

if (folder.at(i) == N%10)

i+=folder.size();

if (i == folder.size() -1)

folder.push_back(N%10);

}

N/=10;

}

cout << "sum:" << folder.size();

return 0;

}

Решение

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

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

#include <iostream>
using namespace std;
 
int main(){
    int folder[10]={0}, sum=0;
    long long N;
 
    cin >> N;
    while (N!=0){
        folder[N%10]++;
        N/=10;
    }
    for (int j=0; j<10; j++)
        if(folder[j]!=0)    sum++;
    cout << "sum:" << sum;
 
    return 0;
}

#include <iostream>

using namespace std;

int main(){

int folder[10]={0}, sum=0;

long long N;

cin >> N;

while (N!=0){

folder[N%10]++;

N/=10;

}

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

if(folder[j]!=0) sum++;

cout << "sum:" << sum;

return 0;

}

Решение

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

Ссылки

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

Related Images:

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

08/05/2017 by Андреев Даниил

Задача

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

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

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

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

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

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

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

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

Тесты

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

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

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

struct deque{
    #define Size 200000
    int start, end;
    int folder[Size];
    
    deque(){
        start = end = Size/2;
    }
    void push_front(int var){
        folder[--start] = var;
        cout << "ok" << endl;
    }
    void push_back(int var){
        folder[end++] = var;
        cout << "ok" << endl;
    }
    void pop_front(){
        cout << folder[start++] << endl;
    }
    void pop_back(){
        cout << folder[--end] << endl;
    }
    void front(){
        cout << folder[start] << endl;
    }
    void back(){
        cout << folder[end-1] << endl;
    }
    void size(){
        cout << end-start << endl;
    }
    void clear(){
        start = end = Size/2;
        cout << "ok" << endl; 
    }
};
        
int main() {
    string s;
    deque deq;
    int n;

    while (cin >> s){
        if (s == "push_front"){
            cin >> n;
            deq.push_front(n);
        }
        else    if (s == "push_back"){
                cin >> n;
                deq.push_back(n);
        }
        else    if (s == "pop_front")   deq.pop_front();
        else    if (s == "pop_back")    deq.pop_back();
        else    if (s == "front")   deq.front();
        else    if (s == "back")    deq.back();
        else    if (s == "size")    deq.size();
        else    if (s == "clear")   deq.clear();
        else    if (s == "exit"){
                cout << "bye";
                return 0;
        }
    }
}

#include <iostream>

#include <string>

using namespace std;

struct deque{

#define Size 200000

int start, end;

int folder[Size];

deque(){

start = end = Size/2;

}

void push_front(int var){

folder[--start] = var;

cout << "ok" << endl;

}

void push_back(int var){

folder[end++] = var;

cout << "ok" << endl;

}

void pop_front(){

cout << folder[start++] << endl;

}

void pop_back(){

cout << folder[--end] << endl;

}

void front(){

cout << folder[start] << endl;

}

void back(){

cout << folder[end-1] << endl;

}

void size(){

cout << end-start << endl;

}

void clear(){

start = end = Size/2;

cout << "ok" << endl;

}

};

int main() {

string s;

deque deq;

int n;

while (cin >> s){

if (s == "push_front"){

cin >> n;

deq.push_front(n);

}

else if (s == "push_back"){

cin >> n;

deq.push_back(n);

}

else if (s == "pop_front") deq.pop_front();

else if (s == "pop_back") deq.pop_back();

else if (s == "front") deq.front();

else if (s == "back") deq.back();

else if (s == "size") deq.size();

else if (s == "clear") deq.clear();

else if (s == "exit"){

cout << "bye";

return 0;

}

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

import java.util.*;

class deque{
    private static final int Size = 200000;
    int start, end;
    int [] folder = new int[Size] ;
    
    deque(){
        start = end = Size/2;
    }
    void push_front(int var){
        folder[--start] = var;
        System.out.println("ok");
    }
    void push_back(int var){
        folder[end++] = var;
        System.out.println("ok");
    }
    void pop_front(){
        System.out.println(folder[start++]);
    }
    void pop_back(){
        System.out.println(folder[--end]);
    }
    void front(){
        System.out.println(folder[start]);
    }
    void back(){
        System.out.println(folder[end-1]);
    }
    void size(){
        System.out.println(end-start);
    }
    void clear(){
        start = end = Size/2;
        System.out.println("ok");
    }
};

class Main
{
    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner scan = new Scanner(System.in);
        deque deq = new deque();
        String S;
        
        while (scan.hasNext()){
            S = scan.next();
            if (S.equals("push_front")) deq.push_front(scan.nextInt());
            else    if (S.equals("push_back"))  deq.push_back(scan.nextInt());
            else    if (S.equals("pop_front"))  deq.pop_front();
            else    if (S.equals("pop_back"))   deq.pop_back();
            else    if (S.equals("front"))  deq.front();
            else    if (S.equals("back"))   deq.back();
            else    if (S.equals("size"))   deq.size();
            else    if (S.equals("clear"))  deq.clear();
            else    if (S.equals("exit")){
                    System.out.println("bye");
                    System.exit(0);
                }
        }
    }
}

import java.util.*;

class deque{

private static final int Size = 200000;

int start, end;

int [] folder = new int[Size] ;

deque(){

start = end = Size/2;

}

void push_front(int var){

folder[--start] = var;

System.out.println("ok");

}

void push_back(int var){

folder[end++] = var;

System.out.println("ok");

}

void pop_front(){

System.out.println(folder[start++]);

}

void pop_back(){

System.out.println(folder[--end]);

}

void front(){

System.out.println(folder[start]);

}

void back(){

System.out.println(folder[end-1]);

}

void size(){

System.out.println(end-start);

}

void clear(){

start = end = Size/2;

System.out.println("ok");

}

};

class Main

{

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

{

Scanner scan = new Scanner(System.in);

deque deq = new deque();

String S;

while (scan.hasNext()){

S = scan.next();

if (S.equals("push_front")) deq.push_front(scan.nextInt());

else if (S.equals("push_back")) deq.push_back(scan.nextInt());

else if (S.equals("pop_front")) deq.pop_front();

else if (S.equals("pop_back")) deq.pop_back();

else if (S.equals("front")) deq.front();

else if (S.equals("back")) deq.back();

else if (S.equals("size")) deq.size();

else if (S.equals("clear")) deq.clear();

else if (S.equals("exit")){

System.out.println("bye");

System.exit(0);

}

Решение

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

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

Ссылки

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

Related Images:

e-olymp 1060. Линии

28/06/2016 by Кондратюк Настя

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

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

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

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

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

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

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

Тесты

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

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

5
....X
.OOOO
.....
OOOO.
@....

....X

.OOOO

.....

OOOO.

@....

Y
+++++
+OOOO
+++++
OOOO+
@++++

+++++

+OOOO

+++++

OOOO+

@++++

5
..X..
.....
OOOOO
.....
..@..

..X..

.....

OOOOO

.....

..@..

N

5
...X.
.....
O.OOO
.....
....@

...X.

.....

O.OOO

.....

....@

Y
..++.
.++..
O+OOO
.++++
....@

..++.

.++..

O+OOO

.++++

....@

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

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

/* нахождение пути*/
void find_path(int n, int row, int col, char** lab, int** visited, int** path, queue<int>& plan){
    if(!visited[row][col]){
        /* проверяем не вышли ли мы за границы лабиринта, есть ли клетка 
        в массиве посещенных и можно ли через нее пройти*/
        if ((row+1) < n && (row+1) >= 0 && !visited[row+1][col] &&
            (lab[row+1][col] == '.' || lab[row+1][col] == 'X')) {
                path[row+1][col] = path[row][col] + 1;
                plan.push(row+1);
                plan.push(col);
        }
        if((row-1) < n && (row-1) >= 0 && !visited[row-1][col] && 
            (lab[row-1][col] == '.' || lab[row-1][col] == 'X')) {
                path[row-1][col] = path[row][col] + 1;
                plan.push(row-1);
                plan.push(col);
        }
        if((col + 1) < n && (col + 1) >= 0 && !visited[row][col+1] && 
            (lab[row][col+1] == '.' || lab[row][col+1] == 'X')) {
                path[row][col+1] = path[row][col] + 1;
                plan.push(row);
                plan.push(col+1);
        }
        if((col - 1) < n && (col - 1) >= 0 && !visited[row][col-1] && 
            (lab[row][col-1] == '.' || lab[row][col-1] == 'X')) {
                path[row][col-1] = path[row][col] + 1;
                plan.push(row);
                plan.push(col-1);
        }
        visited[row][col] = 1; /* отмечаем клетку в которой побывали */
    }
}
 
int main() {
    int n, x_start, y_start, x_end, y_end, x, y;
    queue <int> plan; 
    cin >> n;
    char** lab = new char* [n];
    int** visited = new int * [n];
    int** path = new int * [n];
    for(int i=0; i<n; i++){
        lab[i] = new char [n];   /* массив для хранения лабиринта */
        visited[i] = new int [n]; /* массив для хранения информации о посещении клеток*/
        path[i] = new int [n];  /* массив для хранения найденных путей */
        for(int j=0; j<n; j++){
            visited[i][j] = 0;  
            path[i][j] = -1;   
            cin >> lab[i][j]; 
            if (lab[i][j] == '@') { /* находим начало пути*/
                x_start = i;
                y_start = j;
                plan.push(i);  /* заносим начальную клетку */
                plan.push(j);  /* в план посещения */
                path[i][j] = 1;
            }
            else if (lab[i][j] == 'X') { /* находим конечную точку */
                x_end = i;
                y_end = j;
            }
        }
    }
    while(!plan.empty()){ /* пока очередь посещения клеток непустая*/
        x=plan.front();
        plan.pop();
        y=plan.front();
        plan.pop();
        find_path(n, x, y, lab, visited, path, plan); /* продолжаем поиск пути*/
    }
    if(!visited[x_end][y_end]){
        cout << "N" << endl;
    }
    else {
        cout << "Y" << endl;
            x = x_end;
            y = y_end;
            lab[x][y] = '+';
            while (path[x][y] != 2) { /* восстановление пути*/
                if ((x-1) >= 0 && (x-1) < n && (path[x-1][y] == path[x][y] - 1)) {
                    x = x-1;
                    lab[x][y] = '+';
                }
                else if ((x+1) >= 0 && (x+1) < n && (path[x+1][y] == path[x][y] - 1)) {
                    x = x+1;
                    lab[x][y] = '+';
                }
                else if ((y-1) >= 0 && (y-1) < n && (path[x][y-1] == path[x][y] - 1)) {
                    y = y-1;
                    lab[x][y] = '+';
                }
                else if ((y+1) >= 0 && (y+1) < n && (path[x][y+1] == path[x][y] - 1)) {
                    y = y+1;
                    lab[x][y] = '+';
                }
            }
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    cout << lab[i][j];
                }
                cout << endl;
            }
        }
    return 0;
}

100

101

102

103

104

105

106

107

#include <iostream>

#include <queue>

using namespace std;

/* нахождение пути*/

void find_path(int n, int row, int col, char** lab, int** visited, int** path, queue<int>& plan){

if(!visited[row][col]){

/* проверяем не вышли ли мы за границы лабиринта, есть ли клетка

в массиве посещенных и можно ли через нее пройти*/

if ((row+1) < n && (row+1) >= 0 && !visited[row+1][col] &&

(lab[row+1][col] == '.' || lab[row+1][col] == 'X')) {

path[row+1][col] = path[row][col] + 1;

plan.push(row+1);

plan.push(col);

}

if((row-1) < n && (row-1) >= 0 && !visited[row-1][col] &&

(lab[row-1][col] == '.' || lab[row-1][col] == 'X')) {

path[row-1][col] = path[row][col] + 1;

plan.push(row-1);

plan.push(col);

}

if((col + 1) < n && (col + 1) >= 0 && !visited[row][col+1] &&

(lab[row][col+1] == '.' || lab[row][col+1] == 'X')) {

path[row][col+1] = path[row][col] + 1;

plan.push(row);

plan.push(col+1);

}

if((col - 1) < n && (col - 1) >= 0 && !visited[row][col-1] &&

(lab[row][col-1] == '.' || lab[row][col-1] == 'X')) {

path[row][col-1] = path[row][col] + 1;

plan.push(row);

plan.push(col-1);

}

visited[row][col] = 1; /* отмечаем клетку в которой побывали */

}

int main() {

int n, x_start, y_start, x_end, y_end, x, y;

queue <int> plan;

cin >> n;

char** lab = new char* [n];

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

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

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

lab[i] = new char [n]; /* массив для хранения лабиринта */

visited[i] = new int [n]; /* массив для хранения информации о посещении клеток*/

path[i] = new int [n]; /* массив для хранения найденных путей */

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

visited[i][j] = 0;

path[i][j] = -1;

cin >> lab[i][j];

if (lab[i][j] == '@') { /* находим начало пути*/

x_start = i;

y_start = j;

plan.push(i); /* заносим начальную клетку */

plan.push(j); /* в план посещения */

path[i][j] = 1;

}

else if (lab[i][j] == 'X') { /* находим конечную точку */

x_end = i;

y_end = j;

}

while(!plan.empty()){ /* пока очередь посещения клеток непустая*/

x=plan.front();

plan.pop();

y=plan.front();

plan.pop();

find_path(n, x, y, lab, visited, path, plan); /* продолжаем поиск пути*/

}

if(!visited[x_end][y_end]){

cout << "N" << endl;

}

else {

cout << "Y" << endl;

x = x_end;

y = y_end;

lab[x][y] = '+';

while (path[x][y] != 2) { /* восстановление пути*/

if ((x-1) >= 0 && (x-1) < n && (path[x-1][y] == path[x][y] - 1)) {

x = x-1;

lab[x][y] = '+';

}

else if ((x+1) >= 0 && (x+1) < n && (path[x+1][y] == path[x][y] - 1)) {

x = x+1;

lab[x][y] = '+';

}

else if ((y-1) >= 0 && (y-1) < n && (path[x][y-1] == path[x][y] - 1)) {

y = y-1;

lab[x][y] = '+';

}

else if ((y+1) >= 0 && (y+1) < n && (path[x][y+1] == path[x][y] - 1)) {

y = y+1;

lab[x][y] = '+';

}

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

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

cout << lab[i][j];

}

cout << endl;

}

return 0;

}

ideone.com

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

Решение

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

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

Related Images:

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

06/06/2016 by Грешилов Константин

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

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

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

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

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

Тесты:

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

Решение:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool cyclic (int v, int &cycle_st, vector <int> *graph, vector <int> &color ) { //проверка графа на цикличность
    color[v] = 1;
    for (size_t i = 0; i < graph[v].size(); ++i) {
        int to = graph[v][i];
        if (color[to] == 0) { //если в вершину не входили ни разу
            if (cyclic (to, cycle_st, graph,  color))  return true;
        }
        else if (color[to] == 1) { //если в указанную вершину ранее входили, то значит, что найден цикл
            cycle_st = to; // и меняем значение индикатора 
            return true; 
        }
    }
    color[v] = 2; //указываем, что в вершину больше ни разу входить не будем
    return false;
}
void dfs (int v, vector <int> *graph, vector<bool> &used, vector <int> &answer) {
    used[v] = true; //указываем, что использовали данную вершину
    for (int i=0; i < graph[v].size(); i++) {
        int to = graph[v][i]; //по списку проходим по всем вершинам, к которым можно пройти от вершины v
        if (!used[to])//и если вершину не рассматривали, то применяем алгоритм поиска в глубину для неё
            dfs (to, graph, used, answer);
    }
    answer.push_back (v+1); // заносим вершину в вектор, хранящий результат
}
 
void topological_sort(int n, vector <int> *graph, vector<bool> &used, vector <int> &answer) {
    for (int i = 0; i < n; i++) //указываем, что ни одна вершина не была использована
        used[i] = false;
    for (int i = 0; i < n; i++)
        if (!used[i]) //если в ходе предыдущий операций вершина не использовалась
            dfs (i, graph, used, answer); // то вызываем для неё алгоритм поиска в глубину
    reverse (answer.begin(), answer.end());
}

int main() {
    int n, m; // число вершин и ребер
    cin >> n >> m;
    int a, b;
    vector <int> graph[100001]; // граф
    vector <bool> used (n);
    vector<int> answer;
    vector<int> color (n,0); //массив, хранящий кол-во посещений для данной вершины.
    int cycle_st = -1;
    for (int i = 0; i < m; i++){
            cin >> a >> b;
            graph[a-1].push_back(b-1);
        }
    for (int i = 0; i < n; i++){
        if (cyclic(i, cycle_st, graph, color)) //проверка графа на ацикличность
            break;
    }
    if (cycle_st != -1){ 
        cout << "-1";
    }
    else{
        topological_sort(n, graph, used, answer);
        for (int i = 0; i < answer.size(); i++)
        {
            cout << answer[i] << " "; 
        }
        cout << endl;
    }
    return 0;
}

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

bool cyclic (int v, int &cycle_st, vector <int> *graph, vector <int> &color ) { //проверка графа на цикличность

color[v] = 1;

for (size_t i = 0; i < graph[v].size(); ++i) {

int to = graph[v][i];

if (color[to] == 0) { //если в вершину не входили ни разу

if (cyclic (to, cycle_st, graph, color)) return true;

}

else if (color[to] == 1) { //если в указанную вершину ранее входили, то значит, что найден цикл

cycle_st = to; // и меняем значение индикатора

return true;

}

color[v] = 2; //указываем, что в вершину больше ни разу входить не будем

return false;

}

void dfs (int v, vector <int> *graph, vector<bool> &used, vector <int> &answer) {

used[v] = true; //указываем, что использовали данную вершину

for (int i=0; i < graph[v].size(); i++) {

int to = graph[v][i]; //по списку проходим по всем вершинам, к которым можно пройти от вершины v

if (!used[to])//и если вершину не рассматривали, то применяем алгоритм поиска в глубину для неё

dfs (to, graph, used, answer);

}

answer.push_back (v+1); // заносим вершину в вектор, хранящий результат

}

void topological_sort(int n, vector <int> *graph, vector<bool> &used, vector <int> &answer) {

for (int i = 0; i < n; i++) //указываем, что ни одна вершина не была использована

used[i] = false;

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

if (!used[i]) //если в ходе предыдущий операций вершина не использовалась

dfs (i, graph, used, answer); // то вызываем для неё алгоритм поиска в глубину

reverse (answer.begin(), answer.end());

}

int main() {

int n, m; // число вершин и ребер

cin >> n >> m;

int a, b;

vector <int> graph[100001]; // граф

vector <bool> used (n);

vector<int> answer;

vector<int> color (n,0); //массив, хранящий кол-во посещений для данной вершины.

int cycle_st = -1;

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

cin >> a >> b;

graph[a-1].push_back(b-1);

}

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

if (cyclic(i, cycle_st, graph, color)) //проверка графа на ацикличность

break;

}

if (cycle_st != -1){

cout << "-1";

}

else{

topological_sort(n, graph, used, answer);

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

{

cout << answer[i] << " ";

}

cout << endl;

}

return 0;

}

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

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

void dfs (int v, vector <int> *graph, vector<bool> &used, vector <int> &answer)

20	void dfs (int v, vector <int> *graph, vector<bool> &used, vector <int> &answer)

void topological_sort(int n, vector <int> *graph, vector<bool> &used, vector <int> &answer)

30	void topological_sort(int n, vector <int> *graph, vector<bool> &used, vector <int> &answer)

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

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

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

Related Images:

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

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

Задача

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

push n

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

pop

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

back

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

size

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

clear

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

exit

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

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

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

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

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

Тесты

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

Код

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

#include <iostream>

using namespace std;

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

long long s[100];

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

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

s[cursor++]=n;

}

long long pop(){

return s[--cursor];

}

long long back(){

return s[cursor-1];

}

unsigned size(){

return cursor;

}

void clear(){

cursor=0;

s[cursor]=0;

}

};

int main() {

stack x;

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

long long n;

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

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

cin>>n;

x.push(n);

cout<<"ok"<<endl;

}

else if(b=="pop"){

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

cout<<"error"<<endl;

}

else

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

}

else if(b=="back"){

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

cout<<"error"<<endl;

}

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

}

else if(b=="size"){

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

}

else if(b=="clear"){

x.clear();

cout<<"ok"<<endl;

}

else if(b=="exit"){

cout<<"bye"<<endl;

break;

}

return 0;

}

Решение

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

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

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

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

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

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

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

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

Ссылка на ideone.

Related Images:

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

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

Задача

push n

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

pop

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

back

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

size

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

clear

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

exit

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

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

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

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

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

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

Тесты:

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

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

#include <iostream>
using namespace std;

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

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

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

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

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

#include <iostream>

using namespace std;

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

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

{

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

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

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

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

{

capacity = link_array_size;

}

void link_push (int n)

{

capacity--;

array [capacity] = n;

}

int link_pop ()

{

capacity++;

return array[capacity-1];

}

};

struct stack //сам стек

{

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

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

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

{

head = h;

s = 0;

}

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

{

link* a = new link;

a->next = head;

head = a;

}

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

{

link * a = head;

head = a->next;

delete a;

}

void push (int n)

{

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

{

add_link();

}

head->link_push(n);

s++;

}

int pop ()

{

if (s>0)

{

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

if (head->capacity == link_array_size)

{

destroy_link();

}

s--;

return n;

}

else

{

throw 0;

}

int back()

{

if (s>0)

{

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

}

else

{

throw 0;

}

int size()

{

return s;

}

void clear()

{

while (head!=NULL)

{

destroy_link();

}

s = 0;

}

};

int main()

{

string s;

stack Q;

while (cin>>s)

{

if (s == "push")

{

int n;

cin>>n;

Q.push(n);

cout<<"ok"<<endl;

}

if (s == "pop")

{

try

{

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

}

catch (int e)

{

cout<<"error"<<endl;

}

if (s == "back")

{

try

{

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

}

catch (int e)

{

cout<<"error"<<endl;

}

if (s == "size")

{

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

}

if (s == "clear")

{

Q.clear();

cout<<"ok"<<endl;

}

if (s == "exit")

{

cout<<"bye"<<endl;

break;

}

return 0;

}

Решение

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

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

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

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

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

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

Related Images:

AL6

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

Задача AL6

Условие

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

Тесты

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

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

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

#include <iostream>

#include <string>

#include <cstring>

#include <cmath>

using namespace std;

struct stack{

char *bkt = new char;

int cur;

stack(){cur = 0;}

void push(char x){

bkt[cur++] = x;

}

void pop(){

cur--;

}

char back(){

return bkt[cur-1];

}

int size(){

return cur;

}

};

int main() {

string brace;

cin >> brace;

stack x;

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

else{

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

else cout << "NO";

return 0;

}

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

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

x.push(brace[i]);

}

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

x.pop();

}

else{

cout << "NO";

return 0;

}

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

else cout << "NO";

return 0;

}

Решение

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

Ссылки

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

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

Related Images:

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

26/05/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 программа должна проверять, содержится ли в деке хотя бы один элемент. Если во входных данных встречается операция pop_front, pop_back, front, back, и при этом дек пуст, то программа должна вместо числового значения вывести строку error.

#include <iostream>
#include <string>
using namespace std;
 
struct stack{
    int storage[1000];
    int end=0;
    int sizze=0;
    int start=1;
    int lol=100;
    int push_back(int x){
        end = (end + 1)%lol;
        storage[end] = x;
        sizze++;
    }
    int push_front(int x){start = (start - 1+lol)%lol;
                    storage[start] = x;
                    sizze++;}               
                    
    void pop_back(){end = (end - 1+lol)%lol;
                sizze--;}
    void pop_front(){start = (start + 1)%lol;
                sizze--;}           
                
    int back() const{return storage[end];}
    int size() const{return sizze;}
    void clear(){end = 0;
                sizze = 0;
                start = 1;
                }
                
    int front() const{
        return storage[start];
}
    
};

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

#include <iostream>

#include <string>

using namespace std;

struct stack{

int storage[1000];

int end=0;

int sizze=0;

int start=1;

int lol=100;

int push_back(int x){

end = (end + 1)%lol;

storage[end] = x;

sizze++;

}

int push_front(int x){start = (start - 1+lol)%lol;

storage[start] = x;

sizze++;}

void pop_back(){end = (end - 1+lol)%lol;

sizze--;}

void pop_front(){start = (start + 1)%lol;

sizze--;}

int back() const{return storage[end];}

int size() const{return sizze;}

void clear(){end = 0;

sizze = 0;

start = 1;

}

int front() const{

return storage[start];

}

};

int main() {

stack storage;

string s;

int n;

while(cin >> s){

if(s == "push_back"){

cin >> n;

storage.push_back(n);

cout << "ok\n";

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

cin >> n;

storage.push_front(n);

cout << "ok\n";

}

else if(s == "pop_back"){

if(storage.size()){

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

storage.pop_back();

}else{

cout << "error\n";

}

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

if(storage.size()){

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

storage.pop_front();

}else{

cout << "error\n";

}

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

if(storage.size()){

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

}

else{

cout << "error\n";

}

else if(s == "back"){

if(storage.size()){

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

}else{

cout << "error\n";

}

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

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

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

storage.clear();

cout << "ok\n";

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

cout << "bye\n";

return 0;

}

return 0;

}

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

Код на ideone

Related Images:

e-olymp 982. Связность

15/05/2016 by Женя Максимова

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

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

В первой строке заданы количество вершин [latex]n[/latex] и ребер [latex]m[/latex] в графе соответственно [latex](1 \leq n \leq 100, 1 \leq m \leq 10000)[/latex]. Каждая из следующих m строк содержит по два числа [latex]u_i[/latex] и [latex]v_i[/latex] [latex](1 \leq u_i, v_i \leq n);[/latex] каждая такая строка означает, что в графе существует ребро между вершинами [latex]u_i[/latex] и [latex]v_i[/latex].

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

Выведите «YES», если граф является связным и «NO» в противном случае.

Тесты

Тесты, взятые с e-olymp.com

Test	Input	Output
1	3 2 1 2 3 2	YES
2	3 1 1 3	NO

Мои тесты

Test	Input	Output
1	4 2 1 2 3 4	NO
2	4 5 1 2 2 1 2 4 2 4 4 2	NO
3	5 4 1 2 5 1 3 5 4 3	YES

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

#include <bits/stdc++.h>
using namespace std;

#define in_range(x,y,z) for(int x=y; x<z; x++)

int main()
{
  int m,n;
  cin >> n >> m;
  vector < vector<int> > g(n); // граф
  int s=0; // начальная вершина
  in_range(i,0,m) // считывание графа
    {
      int u,v;
      cin >> u >> v;
      g[u-1].push_back(v-1);
      g[v-1].push_back(u-1);
    }
  queue<int> q; // очередь с вершинами, которые мы рассматриваем на данном этапе
  q.push (s);
  vector<bool> used (n); // логический массив, указывающий, посещена ли вершина
  used[s] = true;
  while (!q.empty()) // пока мы не обойдем все вершины, которые можно достигнуть из данной
    {
      int v = q.front();
      q.pop(); // достаем из головы очереди одну вершину
      for (size_t i=0; i<g[v].size(); ++i) //просмотрим все ребра, исходящие из данной вершины
        {
          int to = g[v][i];
          if (!used[to]) // если текущая вершина еще не была посещена
            {
              used[to] = true; //отмечаем, что мы ее посетили
              q.push (to); // помещаем в очередь
            }
        }
    }
  vector<bool>::iterator it;
  it = find (used.begin(), used.end(), false); // проверяем, остались ли еще непосещенные вершины
  if (it == used.end())
    cout << "YES"; // если все вершины посещены, то граф связный
  else
    cout << "NO";
  return 0;
}

#include <bits/stdc++.h>

using namespace std;

#define in_range(x,y,z) for(int x=y; x<z; x++)

int main()

{

int m,n;

cin >> n >> m;

vector < vector<int> > g(n); // граф

int s=0; // начальная вершина

in_range(i,0,m) // считывание графа

{

int u,v;

cin >> u >> v;

g[u-1].push_back(v-1);

g[v-1].push_back(u-1);

}

queue<int> q; // очередь с вершинами, которые мы рассматриваем на данном этапе

q.push (s);

vector<bool> used (n); // логический массив, указывающий, посещена ли вершина

used[s] = true;

while (!q.empty()) // пока мы не обойдем все вершины, которые можно достигнуть из данной

{

int v = q.front();

q.pop(); // достаем из головы очереди одну вершину

for (size_t i=0; i<g[v].size(); ++i) //просмотрим все ребра, исходящие из данной вершины

{

int to = g[v][i];

if (!used[to]) // если текущая вершина еще не была посещена

{

used[to] = true; //отмечаем, что мы ее посетили

q.push (to); // помещаем в очередь

}

vector<bool>::iterator it;

it = find (used.begin(), used.end(), false); // проверяем, остались ли еще непосещенные вершины

if (it == used.end())

cout << "YES"; // если все вершины посещены, то граф связный

else

cout << "NO";

return 0;

}

Алгоритм

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

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

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

Related Images:

e-olymp 6127. Очередь неограниченного размера

15/04/2016 by Катя Писова

Задача

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

push n

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

pop

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

front

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

size

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

clear

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

exit

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

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

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

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

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

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

Тесты

№	Входные данные	Выходные данные:
1	push 1 front exit	ok 1 bye
2	size push 1 size push 2 size push 3 size exit	0 ok 1 ok 2 ok 3 bye

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

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

struct node{
    int value;
    node *next;
    node():value(0), next(NULL){}
    node(int value, node *next)
    :value(value), next(next){}
};

struct _queue{
    int _size;
    node *first;
    node *last;
    _queue():_size(0), first(NULL), last(NULL){}

    void push (int v){
        node *new_node = new node(v, last);
        if(_size == 0){
            first = last = new_node;
        }
        else{
            last->next = new_node;
            last = new_node;
        }
        _size++;
    }

    void pop(){
        if (_size > 0){
            int val = first->value;
            first = first->next;
            _size--;
            cout << val;
        }
        else throw 0;
    }

    void front(){
        if (_size > 0) cout << first->value;
        else throw 0;
    }
    
    int size(){
        return _size;
    }

    void clear(){
        while (_size > 0){
            node *new_node = first->next;
            delete first;
            first = new_node;
            _size--;
        }
        first = NULL;
        last = NULL;
    }
};


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

100

101

102

#include <iostream>

#include <string>

#include <exception>

using namespace std;

struct node{

int value;

node *next;

node():value(0), next(NULL){}

node(int value, node *next)

:value(value), next(next){}

};

struct _queue{

int _size;

node *first;

node *last;

_queue():_size(0), first(NULL), last(NULL){}

void push (int v){

node *new_node = new node(v, last);

if(_size == 0){

first = last = new_node;

}

else{

last->next = new_node;

last = new_node;

}

_size++;

}

void pop(){

if (_size > 0){

int val = first->value;

first = first->next;

_size--;

cout << val;

}

else throw 0;

}

void front(){

if (_size > 0) cout << first->value;

else throw 0;

}

int size(){

return _size;

}

void clear(){

while (_size > 0){

node *new_node = first->next;

delete first;

first = new_node;

_size--;

}

first = NULL;

last = NULL;

}

};

int main()

{

_queue q;

string s;

int n;

while (cin >> s){

if (s == "size"){

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

}

if (s == "push"){

cin >> n;

q.push(n);

cout << "ok" << endl;

}

if (s == "pop"){

try{

q.pop();

}

catch(int e){cout << "error";}

cout << endl;

}

if (s == "front"){

try {

q.front();

}

catch(int e){cout << "error";}

cout<<endl;

}

if (s == "clear"){

q.clear();

cout << "ok" << endl;

}

if (s == "exit"){

cout << "bye" <<endl;

return 0;

}

return 0;

}

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

Каждый элемент (узел) очереди состоит из информационной части (его значение) и адресной. В адресную часть первого элемента записываем адрес следующего элемента и т.д., тем самым мы создаем порядок следования элементов в очереди, связывая их между собой. При добавлении или удалении элемента мы соответственно изменяем размер очереди, который изначально равен нулю, а также меняем позиции указателей на начало и конец очереди. В условии задачи сказано, что если во входных данных встречается операция front или pop, и при этом очередь пуста, то программа должна вместо числового значения вывести строку error. Поэтому создаем исключительную ситуацию для проверки наличия в очереди хотя бы одного элемента.

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

Related Images:

AL15. Лабиринт

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

Условие

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

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

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

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

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

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

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

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

Замечания

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

C++

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

1

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

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

Тесты

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