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

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

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

e-olimp 3809. ГАС Очередь

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

Задача e-olimp.com №3809. Ссылка на засчитанное решение.

За последние несколько лет электронные очереди прочно вошли в повседневную жизнь. Во многих государственных учреждениях можно встретить терминал, печатающий бумажку с номером, и, не задавая привычный вопрос «Кто последний?«, посетители с помощью электронного табло узнают, сколько еще им ждать и когда наступит их очередь.

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

Известно, что у каждого человека есть такой критерий, как раздражительность. Если этот параметр равен [latex]w[/latex], то через [latex]t[/latex] часов ожидания в очереди этот человек обрушит на голову чиновника ровно [latex]wt[/latex] единиц злобы и ругани. Так, если посетителя начнут обслуживать сразу же после его прихода, то чиновник не пострадает, а если посетитель пришел в начале третьего часа, а его обслуживание началось только в начале пятого — количество гнева будет равно [latex]2w[/latex].

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

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

В первой строке задано одно целое число [latex]t[/latex] — количество случаев, которые вам предстоит обработать. Далее следуют [latex]t[/latex] описаний самих случаев.

Описание каждого случая состоит из: числа [latex]n[/latex] в первой строке — количества посетителей, и [latex]n[/latex] описаний самих посетителей. Для каждого посетителя в отдельной строке указаны два целых числа [latex]r_{i}[/latex] и [latex]w_{i}[/latex] [latex]\left(1\leq r_{i},w_i\leq {10}^{6} \right)[/latex] — номер часа, в начале которого посетитель пришел, и его коэффициент раздражительности, соответственно.

Суммарное количество посетителей во всех случаях одного теста не превосходит [latex]10^{5}[/latex].

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

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

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

#include <cstdio>
#include <queue>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;

pair <long long, long long> v [100010]; // массив пар (время, ярость) поменяла местами, чтобы не писать перегруженный оператор, так как сравнивается по умолчанию по первому значению
priority_queue <pair <long long, long long> > q; // очередь пар (ярость, время)

int main() {
	long long t;
	scanf("%lld", &t);
	while (t--) {
		long long n;
		scanf("%lld", &n);
		long long ans=0;
		for (int i=0; i<n; i++) {
			long long r, w;
			scanf("%lld%lld", &r, &w);
			v[i]=make_pair(r,w);
		}
		sort (v, v+n); // сортируем по времени прибытия
		long long k=0;
		long long tim=1;
		for (; tim<=1000000; ) { // цикл от 1 до максимального количества пришедших
			while (v[k].first==tim) { // если встретился такой человек, пришедший в нужный момент времени
				q.push(make_pair(v[k].second, v[k].first)); // то закидываем его в очередь по ярости (по невозрастанию)
				k++;
				if (k==n) break; // выходим из циклов, если прошли все возможные люди
			}
			if (k==n) break;
			if (q.empty()) {
				if (k<n) tim=max(tim+1, v[k].first); // если очередь уже пуста, но люди не закончились, то время ставим на максимум, чтобы не получить TLE
				else tim++;
			}
			else {
				ans+=(long long)q.top().first*(tim-q.top().second);
				tim++;
				q.pop();
			}
		}
		while (!q.empty()) {
			ans+=(long long)q.top().first*(tim-q.top().second); // если очередь не пуста, а люди уже прийти не могут, то просто запускаем по одному
			tim++;
			q.pop();
		}
		printf("%lld\n", ans);
	}
	return 0;
}

#include <cstdio>

#include <queue>

#include <vector>

#include <utility>

#include <algorithm>

using namespace std;

pair <long long, long long> v [100010]; // массив пар (время, ярость) поменяла местами, чтобы не писать перегруженный оператор, так как сравнивается по умолчанию по первому значению

priority_queue <pair <long long, long long> > q; // очередь пар (ярость, время)

int main() {

long long t;

scanf("%lld", &t);

while (t--) {

long long n;

scanf("%lld", &n);

long long ans=0;

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

long long r, w;

scanf("%lld%lld", &r, &w);

v[i]=make_pair(r,w);

}

sort (v, v+n); // сортируем по времени прибытия

long long k=0;

long long tim=1;

for (; tim<=1000000; ) { // цикл от 1 до максимального количества пришедших

while (v[k].first==tim) { // если встретился такой человек, пришедший в нужный момент времени

q.push(make_pair(v[k].second, v[k].first)); // то закидываем его в очередь по ярости (по невозрастанию)

k++;

if (k==n) break; // выходим из циклов, если прошли все возможные люди

}

if (k==n) break;

if (q.empty()) {

if (k<n) tim=max(tim+1, v[k].first); // если очередь уже пуста, но люди не закончились, то время ставим на максимум, чтобы не получить TLE

else tim++;

}

else {

ans+=(long long)q.top().first*(tim-q.top().second);

tim++;

q.pop();

}

while (!q.empty()) {

ans+=(long long)q.top().first*(tim-q.top().second); // если очередь не пуста, а люди уже прийти не могут, то просто запускаем по одному

tim++;

q.pop();

}

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

}

return 0;

}

Алгоритм состоит в том, чтобы на каждом моменте времени забирать к себе самого агрессивного из людей в очереди.

Для реализации наиболее подходящей структурой хранения данных является очередь с приоритетом, максимум из которой можно извлечь за [latex]O \left( \log n \right)[/latex], тогда суммарное асимптотическое время решения задачи займёт [latex]O \left( \ n log n \right)[/latex].

Related Images:

e-olimp 2510. Сортировка очередями

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

e-olimp 2510. Сортировка очередями

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

Рассматривается специальное устройство, содержащее входной поток, выходной поток и k очередей, пронумерованных числами от [latex]1[/latex] до [latex]k[/latex].

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

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

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

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

Реализация:

Ideone: http://ideone.com/X37iWg
Засчитанное решение: http://www.e-olimp.com/solutions/1935453

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

int main()
{
    unsigned n; scanf("%u", &n);    //количество команд
    int* to_sort = new int[n];      //исходный массив
    for(int i = 0; i < n; i++)
        scanf("%d", to_sort + i);

    unsigned k; scanf("%u", &k);    //количество очередей
    queue<int>* sorting_machine = new queue<int>[k];    //массив очередей

    int *order = new int[n];    //порядок размещения чисел по очередям
    for(int i = 0; i < n; i++){
        //подходящая очередь либо пуста, либо имеет последний элемент, меньший данного
        //найти её номер в массиве
        int available = find_if(sorting_machine, sorting_machine + k,
            [&](const queue<int> &q){return q.empty() || q.back() <= to_sort[i];}) - sorting_machine;
        //если таких очередей нет, то сортировка невозможна
        if(available >= k){
            puts("NO");
            return 0;
        }
        //добавить элемент массива в одну из очередей
        sorting_machine[available].push(to_sort[i]);
        order[i] = available + 1;
    }

    puts("YES");
    for(int i = 0; i < n; i++){
        //вывод порядка размещения исходного массива чисел по очередям
        printf("I(%d)\n", order[i]);
    }
    for(int i = 0; i < n; i++){
        //так как и очередей, и элементов мало, найти минимальный доступный элемент
        queue<int>* minimum = min_element(sorting_machine, sorting_machine + k,
        [&](const queue<int> x, const queue<int> y){
            return !x.empty() && !y.empty() && x.front() < y.front();
        });
        minimum->pop(); //удалить его
        //и вывести номер соответствующей очереди
        printf("R(%d)\n", minimum-sorting_machine+1);
    }
    return 0;
}

#include <cstdio>

#include <queue>

#include <algorithm>

using namespace std;

int main()

{

unsigned n; scanf("%u", &n); //количество команд

int* to_sort = new int[n]; //исходный массив

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

scanf("%d", to_sort + i);

unsigned k; scanf("%u", &k); //количество очередей

queue<int>* sorting_machine = new queue<int>[k]; //массив очередей

int *order = new int[n]; //порядок размещения чисел по очередям

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

//подходящая очередь либо пуста, либо имеет последний элемент, меньший данного

//найти её номер в массиве

int available = find_if(sorting_machine, sorting_machine + k,

[&](const queue<int> &q){return q.empty() || q.back() <= to_sort[i];}) - sorting_machine;

//если таких очередей нет, то сортировка невозможна

if(available >= k){

puts("NO");

return 0;

}

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

sorting_machine[available].push(to_sort[i]);

order[i] = available + 1;

}

puts("YES");

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

//вывод порядка размещения исходного массива чисел по очередям

printf("I(%d)\n", order[i]);

}

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

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

queue<int>* minimum = min_element(sorting_machine, sorting_machine + k,

[&](const queue<int> x, const queue<int> y){

return !x.empty() && !y.empty() && x.front() < y.front();

});

minimum->pop(); //удалить его

//и вывести номер соответствующей очереди

printf("R(%d)\n", minimum-sorting_machine+1);

}

return 0;

}

Детали реализации:

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

find_if() — найти первый элемент участка контейнера, удовлетворяющий логическому условию. Принимает итераторы
на левую и правую границу интересующего участка, а также унарное логическое условие. Возвращает итератор на интересующий
элемент или итератор на область за пределами участка, если условие не выполнилось ни разу.
min_element() — найти минимальный элемент на заданном участке контейнера. Принимает итераторы на левую и правую
границу интересующего участка и двухместный предикат, задающий отношение порядка. Возвращает итератор на интересующий
элемент или за на область за пределами участка, если условие не выполнилось ни разу (пустой контейнер, некорректный порядок).

Related Images:

e-olimp 122. Горные маршруты

02/04/2015 by Вустянюк Ігор Дмитрович

Задача. Горный туристический комплекс состоит из n турбаз, соединенных между собой k горными переходами (другие маршруты в горах опасны). Любой переход между двумя базами занимает 1 день. Туристическая группа находится на базе a и собирается попасть на базу b не более чем за d дней. Сколько существует разных таких маршрутов (без циклов) между a и b?
Ссылка на задачу

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

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

Кроме того, добавлен параметр depth — длина рассматриваемого в данный момент пути (или глубина текущего рекуррентного вызова, если угодно). Этот параметр изначально имеет значение 0 и при каждом вызове сравнивается с максимально допустимым значением. Перед рекуррентным вызовом мы увеличиваем значение depth, ведь длина нового пути будет на 1 больше. После вызова, т.е. возвращаясь на предыдущий уровень рекурсии, мы уменьшаем длину пути (ведь мы «отбросили» последнюю вершину, т.е. длина пути уменьшилась на 1).

Алгоритм работает примерно так: сначала посещаем начальную вершину и помечаем её как локально посещённую. Если она — искомая, увеличиваем количество найденных путей на 1 и алгоритм завершает свою работу (путей без циклов, содержащих более одной вершины, в этом случае быть не может). Если же начальная вершина не совпадает с целевой, то для всех вершин, в которые можно попасть из неё, применяем рекуррентно тот же алгоритм. Если таких вершин нет, алгоритм завершается, возвращая 0 (нет ни одного пути из начальной вершины в конечную). Если же такие вершины имеются, то увеличиваем параметр «глубина» и вызываем для них рекуррентно наш алгоритм. После выхода из рекурсии, возвращаем параметр «глубина» к последнему его значению (тем, что было перед вызовом) и, чтобы мы могли использовать данную вершину в других путях помечаем её как «локально свободную».

Стоит отметить, что в общем случае задача поиска всех простых путей (пусть даже удовлетворяющих определённым условиям, как в данной задаче) является NP-полной, т.е. решается исключительно переборными алгоритами, работающими за неполиномиальное время (более эффективных алгоритмов для решения таких задач на сегодняшний день неизвестно; кто их найдёт, получит миллион долларов; я не нашёл). Также отметим, что простая модификация приведённого алгоритма позволяет не только вычислять количество простых путей указанной длины, но и перечислять их.

Решение на С++

#include <stdio.h>
#include <vector>
#include <stdlib.h>
using namespace std;

struct Graph {
	vector< vector<int> > AdjList;
	int Size;
	
	Graph(int n) {
		vector<int> List;
		for (int k = 0; k < n; k++)
			AdjList.push_back(List);
		Size = n;
	}

	void add_vertex() {					// вершина == целое число == номер этой вершины в списке вершин
		Size++;
		vector<int> List;
		AdjList.push_back(List);
	}
	
	void add_edge(int u, int v) {		// u и v уже должны быть в списке вершин
		AdjList[u].push_back(v);
	}

	int simple_paths(int start, int end, int max_depth) {
		bool* on_path = (bool*) calloc(Size, sizeof(bool));
		int cur_depth = 0;
		int count = 0;
		simple_paths(start, end, on_path, cur_depth, max_depth, count);
		return count;
	}
	
	void simple_paths(int start, int end, bool* on_path, int& cur_depth, int max_depth, int& count) {
		if (cur_depth <= max_depth) {
			on_path[start] = true;
			if (start == end)
				count++;
			else
				for (int k = 0; k < AdjList[start].size(); k++) {
					int v = AdjList[start][k];
					if (!on_path[v]) {
						cur_depth++;
						simple_paths(v, end, on_path, cur_depth, max_depth, count);
						on_path[v] = false;
						cur_depth--;
					}
				}
		}
	}
	
};


int main() {
	int n, k, a, b, d, tmp1, tmp2;
	scanf("%d %d %d %d %d", &n, &k, &a, &b, &d);
	Graph G(n);
	for (int i = 0; i < k; i++) {
		scanf("%d %d", &tmp1, &tmp2);
		G.add_edge(tmp1 - 1, tmp2 - 1);
	}
	printf("%d\n", G.simple_paths(a-1, b-1, d));
	return 0;
}

#include <stdio.h>

#include <vector>

#include <stdlib.h>

using namespace std;

struct Graph {

vector< vector<int> > AdjList;

int Size;

Graph(int n) {

vector<int> List;

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

AdjList.push_back(List);

Size = n;

}

void add_vertex() { // вершина == целое число == номер этой вершины в списке вершин

Size++;

vector<int> List;

AdjList.push_back(List);

}

void add_edge(int u, int v) { // u и v уже должны быть в списке вершин

AdjList[u].push_back(v);

}

int simple_paths(int start, int end, int max_depth) {

bool* on_path = (bool*) calloc(Size, sizeof(bool));

int cur_depth = 0;

int count = 0;

simple_paths(start, end, on_path, cur_depth, max_depth, count);

return count;

}

void simple_paths(int start, int end, bool* on_path, int& cur_depth, int max_depth, int& count) {

if (cur_depth <= max_depth) {

on_path[start] = true;

if (start == end)

count++;

else

for (int k = 0; k < AdjList[start].size(); k++) {

int v = AdjList[start][k];

if (!on_path[v]) {

cur_depth++;

simple_paths(v, end, on_path, cur_depth, max_depth, count);

on_path[v] = false;

cur_depth--;

}

};

int main() {

int n, k, a, b, d, tmp1, tmp2;

scanf("%d %d %d %d %d", &n, &k, &a, &b, &d);

Graph G(n);

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

scanf("%d %d", &tmp1, &tmp2);

G.add_edge(tmp1 - 1, tmp2 - 1);

}

printf("%d\n", G.simple_paths(a-1, b-1, d));

return 0;

}

Решение на Java

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

class myInt {
	int v;
	public myInt(int a) {
		this.v = a;
	}
}

class Graph {
	Vector<Vector<Integer>> AdjList;

	public Graph(int n) {
		AdjList = new Vector<Vector<Integer>>(n);
		for (int k = 0; k < n; k++)
			AdjList.add(new Vector<Integer>());
	}
	
	public void add_vertex() {
		AdjList.add(new Vector<Integer>());
	}
	
	public void add_edge(int u, int v) {
		AdjList.elementAt(u).add(v);
	}
	
	public int simple_paths(int start, int end, int max_depth) {
		boolean[] on_path = new boolean[AdjList.size()];
		myInt cur_depth = new myInt(0);
		myInt count = new myInt(0);
		simple_paths(start, end, on_path, cur_depth, max_depth, count);
		return count.v;
	}
	
	public void simple_paths(int start, int end, boolean[] on_path, myInt cur_depth, int max_depth, myInt count) {
		if (cur_depth.v <= max_depth) {
			on_path[start] = true;
			if (start == end)
				count.v++;
			else
				for (int k = 0; k < AdjList.elementAt(start).size(); k++) {
					int v = AdjList.elementAt(start).elementAt(k);
					if (!on_path[v]) {
						cur_depth.v++;
						simple_paths(v, end, on_path, cur_depth, max_depth, count);
						on_path[v] = false;
						cur_depth.v--;
					}
				}
		}
	}
}

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		int n = in.nextInt(), k = in.nextInt();
		int a = in.nextInt(), b = in.nextInt(), d = in.nextInt();
		int tmp1, tmp2;
		Graph G = new Graph(n);
		for (int i = 0; i < k; i++) {
			tmp1 = in.nextInt();
			tmp2 = in.nextInt();
			G.add_edge(tmp1 - 1, tmp2 - 1);
		}
		System.out.println(G.simple_paths(a-1, b-1, d));
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class myInt {

int v;

public myInt(int a) {

this.v = a;

}

class Graph {

Vector<Vector<Integer>> AdjList;

public Graph(int n) {

AdjList = new Vector<Vector<Integer>>(n);

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

AdjList.add(new Vector<Integer>());

}

public void add_vertex() {

AdjList.add(new Vector<Integer>());

}

public void add_edge(int u, int v) {

AdjList.elementAt(u).add(v);

}

public int simple_paths(int start, int end, int max_depth) {

boolean[] on_path = new boolean[AdjList.size()];

myInt cur_depth = new myInt(0);

myInt count = new myInt(0);

simple_paths(start, end, on_path, cur_depth, max_depth, count);

return count.v;

}

public void simple_paths(int start, int end, boolean[] on_path, myInt cur_depth, int max_depth, myInt count) {

if (cur_depth.v <= max_depth) {

on_path[start] = true;

if (start == end)

count.v++;

else

for (int k = 0; k < AdjList.elementAt(start).size(); k++) {

int v = AdjList.elementAt(start).elementAt(k);

if (!on_path[v]) {

cur_depth.v++;

simple_paths(v, end, on_path, cur_depth, max_depth, count);

on_path[v] = false;

cur_depth.v--;

}

class Main

{

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

{

Scanner in = new Scanner(System.in);

int n = in.nextInt(), k = in.nextInt();

int a = in.nextInt(), b = in.nextInt(), d = in.nextInt();

int tmp1, tmp2;

Graph G = new Graph(n);

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

tmp1 = in.nextInt();

tmp2 = in.nextInt();

G.add_edge(tmp1 - 1, tmp2 - 1);

}

System.out.println(G.simple_paths(a-1, b-1, d));

}

Related Images:

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

01/04/2015 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.

Результат на C++

Результат на Java

Код на C++:

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

class Deque{
	private:
	int *a = new int [100];
	int size_;
	int front_;
	int back_;
	int capacity;
	void resize(int);
	public:
	Deque(): size_(0), front_(1), back_(0), capacity(100){}
	void push_back(int);
	void push_front(int);
	void pop_back();
	void pop_front();
	int size() const;
	int back() const;
	int front() const;
	void clear();
};

void Deque::resize(int newcapacity){  //Функция изменения размера.
	int* tmp = new int [newcapacity];   //Создаем новый динамический массив с новой размерностью
	int j = front_;                     //Присваиваем начальное значение счетчику.
	for(int i = 0; j!= back_; ++i){     //Продвигаемся по деку, пока счетчик не будет равен позиции последнего элемента.
		tmp[i] = a[j];
		j = (j+1)%capacity;
	}
	tmp[size_ - 1] = a[back_];    //Так как в цикле перенос последнего элемента из старого массива в новый не произошел, вручную переносим последний элемент старого массива.
	delete []a;                   //Удаляем лишнюю память.
	a = tmp;                      //Присваиваем указателю на старый массив указатель на новый массив.
	capacity = newcapacity;       //Меняем значение вместимости.
	front_ = 0;                   //Теперь первый элемент нового массива стоит на нулевой позиции.
	back_ = size_ - 1;            //А последний - на позиции на единицу меньшей чем кол-во элементов.
}

void Deque::push_back(int b){
	if(size_ == capacity){
		this -> resize(2*capacity);
	}
	back_ = (back_ + 1)%capacity;
	a[back_] = b;
	size_++;
}
void Deque::push_front(int b){
	if(size_ == capacity){
		this -> resize(2*capacity);
	}
	front_ = (front_ - 1 + capacity)%capacity;
	a[front_] = b;
	size_++;
}

void Deque::pop_back(){
	back_ = (back_ - 1 + capacity)%capacity;
	size_--;
}
void Deque::pop_front(){
	front_ = (front_ + 1)%capacity;
	size_--;
}
int Deque::size() const{
	return size_;
}

int Deque::front() const{
	return a[front_];
}

int Deque::back() const{
	return a[back_];
}

void Deque::clear(){
	back_ = 0;
	front_ = 1;
	size_ = 0;
}
	
int main() {
	Deque a;
	string s;
	int n;
	while(cin >> s){
		if(s == "push_back"){
			cin >> n;
			a.push_back(n);
			cout << "ok\n";
		}
		else if(s == "push_front"){
			cin >> n;
			a.push_front(n);
			cout << "ok\n";
		}
		else if(s == "pop_back"){
			if(a.size()){
				cout << a.back() << endl;
				a.pop_back();
			}
			else{
				cout << "error\n";
			}
		}
		else if(s == "pop_front"){
			if(a.size()){
				cout << a.front() << endl;
				a.pop_front();
			}
			else{
				cout << "error\n";
			}
		}
		else if(s == "front"){
			if(a.size()){
				cout << a.front() << endl;
			}
			else{
				cout << "error\n";
			}
		}
		else if(s == "back"){
			if(a.size()){
				cout << a.back() << endl;
			}
			else{
				cout << "error\n";
			}
		}
		else if(s == "size"){
			cout << a.size() << endl;
		}
		else if(s == "clear"){
			cout << "ok\n";
			a.clear();
		}
		else if(s == "exit"){
			cout << "bye\n";
			return 0;
		}
	}
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

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

#include <iostream>

#include <string>

using namespace std;

class Deque{

private:

int *a = new int [100];

int size_;

int front_;

int back_;

int capacity;

void resize(int);

public:

Deque(): size_(0), front_(1), back_(0), capacity(100){}

void push_back(int);

void push_front(int);

void pop_back();

void pop_front();

int size() const;

int back() const;

int front() const;

void clear();

};

void Deque::resize(int newcapacity){ //Функция изменения размера.

int* tmp = new int [newcapacity]; //Создаем новый динамический массив с новой размерностью

int j = front_; //Присваиваем начальное значение счетчику.

for(int i = 0; j!= back_; ++i){ //Продвигаемся по деку, пока счетчик не будет равен позиции последнего элемента.

tmp[i] = a[j];

j = (j+1)%capacity;

}

tmp[size_ - 1] = a[back_]; //Так как в цикле перенос последнего элемента из старого массива в новый не произошел, вручную переносим последний элемент старого массива.

delete []a; //Удаляем лишнюю память.

a = tmp; //Присваиваем указателю на старый массив указатель на новый массив.

capacity = newcapacity; //Меняем значение вместимости.

front_ = 0; //Теперь первый элемент нового массива стоит на нулевой позиции.

back_ = size_ - 1; //А последний - на позиции на единицу меньшей чем кол-во элементов.

}

void Deque::push_back(int b){

if(size_ == capacity){

this -> resize(2*capacity);

}

back_ = (back_ + 1)%capacity;

a[back_] = b;

size_++;

}

void Deque::push_front(int b){

if(size_ == capacity){

this -> resize(2*capacity);

}

front_ = (front_ - 1 + capacity)%capacity;

a[front_] = b;

size_++;

}

void Deque::pop_back(){

back_ = (back_ - 1 + capacity)%capacity;

size_--;

}

void Deque::pop_front(){

front_ = (front_ + 1)%capacity;

size_--;

}

int Deque::size() const{

return size_;

}

int Deque::front() const{

return a[front_];

}

int Deque::back() const{

return a[back_];

}

void Deque::clear(){

back_ = 0;

front_ = 1;

size_ = 0;

}

int main() {

Deque a;

string s;

int n;

while(cin >> s){

if(s == "push_back"){

cin >> n;

a.push_back(n);

cout << "ok\n";

}

else if(s == "push_front"){

cin >> n;

a.push_front(n);

cout << "ok\n";

}

else if(s == "pop_back"){

if(a.size()){

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

a.pop_back();

}

else{

cout << "error\n";

}

else if(s == "pop_front"){

if(a.size()){

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

a.pop_front();

}

else{

cout << "error\n";

}

else if(s == "front"){

if(a.size()){

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

}

else{

cout << "error\n";

}

else if(s == "back"){

if(a.size()){

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

}

else{

cout << "error\n";

}

else if(s == "size"){

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

}

else if(s == "clear"){

cout << "ok\n";

a.clear();

}

else if(s == "exit"){

cout << "bye\n";

return 0;

}

return 0;

}

Код на Java:

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

 
class Deque{
	private int[] a = new int [100];
	private int size_;
	private int front_;
	private int back_;
	private int capacity;
	private void resize(int newcapacity){  //Функция изменения размера.
		int[] tmp = new int [newcapacity];   //Создаем новый динамический массив с новой размерностью
		int j = front_;                     //Присваиваем начальное значение счетчику.
		for(int i = 0; j!= back_; ++i){     //Продвигаемся по деку, пока счетчик не будет равен позиции последнего элемента.
			tmp[i] = a[j];
			j = (j+1)%capacity;
		}
		tmp[size_ - 1] = a[back_];    //Так как в цикле перенос последнего элемента из старого массива в новый не произошел, вручную переносим последний элемент старого массива.
		a = tmp;                      //Присваиваем указателю на старый массив указатель на новый массив.
		capacity = newcapacity;       //Меняем значение вместимости.
		front_ = 0;                   //Теперь первый элемент нового массива стоит на нулевой позиции.
		back_ = size_ - 1;            //А последний - на позиции на единицу меньшей чем кол-во элементов.
	}
	public Deque()
	{
		size_ = 0; front_ = 1; back_ = 0; capacity = 100;
	}
	public void push_back(int b){
		if(size_ == capacity){
			this.resize(2*capacity);
		}
		back_ = (back_ + 1)%capacity;
		a[back_] = b;
		size_++;
	}
	public void push_front(int b){
		if(size_ == capacity){
			this.resize(2*capacity);
		}
		front_ = (front_ - 1 + capacity)%capacity;
		a[front_] = b;
		size_++;
	}
	public void pop_back(){
		back_ = (back_ - 1 + capacity)%capacity;
		size_--;
	}
	public void pop_front(){
		front_ = (front_ + 1)%capacity;
		size_--;
	}
	public int size(){
		return size_;
	}
	public int back(){
		return a[back_];
	}
	public int front(){
		return a[front_];	
	}
	public void clear(){
		back_ = 0;
		front_ = 1;
		size_ = 0;
	}
};

public class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		Deque a = new Deque();
		String s;
		String[] oper = {"push_back", "push_front", "pop_back", "pop_front", "front", "back", "size", "clear", "exit"};
		int n;
		am:while(true){
			s = in.next();
			if(s.equals(oper[0])){
				n = in.nextInt();
				a.push_back(n);
				out.println("ok");
			}
			else if(s.equals(oper[1])){
				n = in.nextInt();
				a.push_front(n);
				out.println("ok");
			}
			else if(s.equals(oper[2])){
				if(a.size() != 0){
					out.println(a.back());
					a.pop_back();
				}
				else{
					out.println("error");
				}
			}
			else if(s.equals(oper[3])){
				if(a.size() != 0){
					out.println(a.front());
					a.pop_front();
				}
				else{
					out.println("error");
				}
			}
			else if(s.equals(oper[4])){
				if(a.size() != 0){
					out.println(a.front());
				}
				else{
					out.println("error");
				}
			}
			else if(s.equals(oper[5])){
				if(a.size() != 0){
					out.println(a.back());
				}
				else{
					out.println("error");
				}
			}
			else if(s.equals(oper[6])){
				out.println(a.size());
			}
			else if(s.equals(oper[7])){
				out.println("ok");
				a.clear();
			}
			else if(s.equals(oper[8])){
				out.println("bye");
				//System.exit(0);
				break am;
			}
		}
		out.flush();
	}
}

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

import java.util.*;

import java.lang.*;

import java.io.*;

class Deque{

private int[] a = new int [100];

private int size_;

private int front_;

private int back_;

private int capacity;

private void resize(int newcapacity){ //Функция изменения размера.

int[] tmp = new int [newcapacity]; //Создаем новый динамический массив с новой размерностью

int j = front_; //Присваиваем начальное значение счетчику.

for(int i = 0; j!= back_; ++i){ //Продвигаемся по деку, пока счетчик не будет равен позиции последнего элемента.

tmp[i] = a[j];

j = (j+1)%capacity;

}

a = tmp; //Присваиваем указателю на старый массив указатель на новый массив.

capacity = newcapacity; //Меняем значение вместимости.

front_ = 0; //Теперь первый элемент нового массива стоит на нулевой позиции.

back_ = size_ - 1; //А последний - на позиции на единицу меньшей чем кол-во элементов.

}

public Deque()

{

size_ = 0; front_ = 1; back_ = 0; capacity = 100;

}

public void push_back(int b){

if(size_ == capacity){

this.resize(2*capacity);

}

back_ = (back_ + 1)%capacity;

a[back_] = b;

size_++;

}

public void push_front(int b){

if(size_ == capacity){

this.resize(2*capacity);

}

front_ = (front_ - 1 + capacity)%capacity;

a[front_] = b;

size_++;

}

public void pop_back(){

back_ = (back_ - 1 + capacity)%capacity;

size_--;

}

public void pop_front(){

front_ = (front_ + 1)%capacity;

size_--;

}

public int size(){

return size_;

}

public int back(){

return a[back_];

}

public int front(){

return a[front_];

}

public void clear(){

back_ = 0;

front_ = 1;

size_ = 0;

}

};

public class Main

{

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

{

Scanner in = new Scanner(System.in);

PrintWriter out = new PrintWriter(System.out);

Deque a = new Deque();

String s;

String[] oper = {"push_back", "push_front", "pop_back", "pop_front", "front", "back", "size", "clear", "exit"};

int n;

am:while(true){

s = in.next();

if(s.equals(oper[0])){

n = in.nextInt();

a.push_back(n);

out.println("ok");

}

else if(s.equals(oper[1])){

n = in.nextInt();

a.push_front(n);

out.println("ok");

}

else if(s.equals(oper[2])){

if(a.size() != 0){

out.println(a.back());

a.pop_back();

}

else{

out.println("error");

}

else if(s.equals(oper[3])){

if(a.size() != 0){

out.println(a.front());

a.pop_front();

}

else{

out.println("error");

}

else if(s.equals(oper[4])){

if(a.size() != 0){

out.println(a.front());

}

else{

out.println("error");

}

else if(s.equals(oper[5])){

if(a.size() != 0){

out.println(a.back());

}

else{

out.println("error");

}

else if(s.equals(oper[6])){

out.println(a.size());

}

else if(s.equals(oper[7])){

out.println("ok");

a.clear();

}

else if(s.equals(oper[8])){

out.println("bye");

//System.exit(0);

break am;

}

out.flush();

}

Пояснение:

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

Трудности возникли тогда, когда количество элементов в деке сравнялось с вместимостью базового массива. В таком случае необходимо величить вместимость дека. Сделать это можно следующим образом. Нужно создать новый массив, перенести в него элементы старого массива, а после присвоить указателю на старый массив указатель на новый. После увеличения вместимости дека возник вопрос: Куда указывают указатели? Мы их не меняли, а значит они имеют прежние значения, что уже не актуально. Так как первый элемент в новом массиве находится на нулевой позиции, меняем значение указателя на первый элемент (front_) на нуль. Указатель на последний элемент (back_) теперь должен иметь значение равное, уменьшенному на единицу, количеству элементов. Осталось только изменить значение вместимости (capacity), у меня вместимость увеличивается вдвое.

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

Related Images:

e-olimp 1667. Конденсация графа

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

Задача e-olimp.com №1667. Ссылка на засчитанное решение.

Вам задан связный ориентированный граф с [latex]N[/latex] вершинами и [latex]M[/latex] ребрами [latex]\left(1\leq N\leq 20000, 1\leq M\leq 200000 \right)[/latex]. Найдите компоненты сильной связности заданного графа и топологически отсортируйте его конденсацию.

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

Граф задан во входном файле следующим образом: первая строка содержит числа [latex]N[/latex] и [latex]M[/latex]. Каждая из следующих [latex]M[/latex] строк содержит описание ребра — два целых числа из диапазона от [latex]1[/latex] до [latex]N[/latex] — номера начала и конца ребра.

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

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

Тесты:

6 7

1 2

2 3

3 1

4 5

5 6

6 4

2 4

1 1 1 2 2 2

10 19

1 4

7 8

5 10

8 9

9 6

2 6

6 2

3 8

9 2

7 2

9 7

4 5

3 6

7 3

6 7

10 8

10 1

2 9

2 7

1 2 2 1 1 2 2 2 2 1

Иллюстрация к первому тесту:

Иллюстрация ко второму тесту:

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

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

vector <int> G[100010];
vector <int> Gt[100010]; // транспонированній граф
vector<bool> used;
vector<int> order, component;
int res[100010];
int n, m, num=1;

void dfs_1 (int u) {
 used[u]=1;
 for (int i=0; i<G[u].size(); i++) {
     if (used[G[u][i]]==0) {
         dfs_1(G[u][i]);
     }
 }
 order.push_back(u);
}

void dfs_2 (int u) {
  used[u]=1;
  component.push_back(u);
  for (int i=0; i<Gt[u].size(); i++) {
      if (used[Gt[u][i]]==0) {
          dfs_2 (Gt[u][i]);
      }
  }
}

int main() {
 ios::sync_with_stdio(false);
 cin >> n >> m;
 
 while (m--) {
     int a, b;
     cin >> a >> b;
     a--;
     b--;
     G[a].push_back(b);
     Gt[b].push_back(a);
 }
 
 used.assign (n, false);

 for (int i=0; i<n; i++) {
         if (used[i]==0) dfs_1(i);
 }
 
 used.assign (n, false);
 
 for (int i=0; i<n; i++) {
      int v=order[n-1-i];
      if (used[v]==0) {
          dfs_2 (v);
          for(auto I=component.begin(); I!=component.end(); I++)
              res[*I]=num;
          num++;
          component.clear();
      }
  }
  
  cout << num-1 << endl;
  for (int i=0; i<n-1; i++) cout << res[i] << " ";
  cout << res[n-1] << endl;
  return 0;
}

#include <iostream>

#include <vector>

using namespace std;

vector <int> G[100010];

vector <int> Gt[100010]; // транспонированній граф

vector<bool> used;

vector<int> order, component;

int res[100010];

int n, m, num=1;

void dfs_1 (int u) {

used[u]=1;

for (int i=0; i<G[u].size(); i++) {

if (used[G[u][i]]==0) {

dfs_1(G[u][i]);

}

order.push_back(u);

}

void dfs_2 (int u) {

used[u]=1;

component.push_back(u);

for (int i=0; i<Gt[u].size(); i++) {

if (used[Gt[u][i]]==0) {

dfs_2 (Gt[u][i]);

}

int main() {

ios::sync_with_stdio(false);

cin >> n >> m;

while (m--) {

int a, b;

cin >> a >> b;

a--;

b--;

G[a].push_back(b);

Gt[b].push_back(a);

}

used.assign (n, false);

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

if (used[i]==0) dfs_1(i);

}

used.assign (n, false);

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

int v=order[n-1-i];

if (used[v]==0) {

dfs_2 (v);

for(auto I=component.begin(); I!=component.end(); I++)

res[*I]=num;

num++;

component.clear();

}

cout << num-1 << endl;

for (int i=0; i<n-1; i++) cout << res[i] << " ";

cout << res[n-1] << endl;

return 0;

}

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

Прежде всего топологически сортируем граф [latex]G[/latex] (с помощью функции dfs_1), записывая результат в вектор order. В итоге первой вершиной этого вектора окажется некая вершина [latex]u[/latex], принадлежащая «корневой» компоненте сильной связности, то есть в которую не входит ни одно ребро в графе конденсаций.

Теперь нужно сделать такой обход из этой вершины, который посетил бы только эту компоненту сильной связности и не зашёл бы ни в какую другую. Для этого служит функция dfs_2, которая применяется к траспонированному графу [latex]G^{T}[/latex] (граф, полученный из [latex]G[/latex] изменением направления каждого ребра на противоположное). В этом графе будут те же компоненты сильной связности, что и в исходном графе. Пусть [latex]G^{*}[/latex] — это граф конденсации, получаемый из данного графа сжатием каждой компоненты сильной связности в одну вершину (очевидно, что он ацикличен). Тогда [latex]\left(G^{T} \right)^{*}[/latex] будет равен транспонированному графу конденсации исходного графа [latex]G^{*}[/latex]. Это значит, что теперь из рассматриваемой нами «корневой» компоненты уже не будут выходить рёбра в другие компоненты.

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

Таким образом, чтобы обойти всю «корневую» компоненту сильной связности, содержащую некоторую вершину [latex]u[/latex], достаточно запустить обход из этой вершины в графе[latex]G^{T}[/latex]. Этот обход посетит все вершины этой компоненты сильной связности и только их. Дальше мы можем мысленно удалить эти вершины из графа, находить очередную вершину с максимальным значением времени выхода и запускать обход на транспонированном графе из неё.

Так после каждого запуска dfs_2 в векторе component окажутся все вершины, принадлежащие одной компоненте связности. Поэтому каждой из тих вершин присваиваем номер компоненты, после чего вектор component чистится и идёт новая итерация (номер компоненты при этом увеличивается на 1).

Related Images:

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

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

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

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

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

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

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

Реализации:

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

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

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

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

typedef long long ll;

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

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

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

#include <cstdio>

#include <cstdlib>

#include <algorithm>

using namespace std;

typedef long long ll;

int main(){

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

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

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

unsigned capacity = unsigned(1e6);

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

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

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

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

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

while(n--){

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

if(x % 5 < 2){

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

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

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

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

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

}

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

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

}

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

}

else{

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

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

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

else

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

}

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

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

else

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

sum += tmin[r];

else

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

sum += hmin[l];

}

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

return 0;

}

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

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

Недостатки

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    };

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

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

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

#include <iostream>

#include <cstdlib> //calloc()

#include <utility> //pair

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

using namespace std;

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

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

class stack{

private:

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

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

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

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

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

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

}

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

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

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

}

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

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

}

};

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

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

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

public:

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

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

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

}

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

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

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

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

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

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

}

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

}

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

return stored == 0;

}

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

return stored;

}

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

return container->storage[pos];

}

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

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

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

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

}

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

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

}

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

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

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

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

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

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

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

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

}

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

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

}

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

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

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

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

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

}

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

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

}

};

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

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

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

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

int main(){

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

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

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

while(n--){

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

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

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

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

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

tail.pop();

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

head.push({value, minimum});

}

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

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

}

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

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

}

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

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

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

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

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

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

}

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

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

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

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

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

}

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

}

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

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

Недостатки

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

Related Images:

e-olimp 6130. Дек неограниченного размера (как список деков)

26/03/2015 by Вустянюк Ігор Дмитрович

Как пишет Википедия в статье Double-Ended Queue, есть три основных способа реализации двухсторонней очереди (она же — дек, дека и т.д.):

— хранить дек в циклическом буфере и расширять при переполнении (при таком подходе реже нужны расширения);

— хранить содержимое дека в массиве, начиная от его центра, и при переполнении расширять массив (например, создавать новый массив и копировать туда содержимое старого);

— хранить дек в виде многих малых массивов, добавляя новые массивы с того или другого конца при необходимости.

Здесь приведу свою реализацию третьим способом: малые деки хранятся в виде двусвязного списка и добавляются/удаляются в соответствующих ситуациях.; конструктор основного дека создаёт единственный малый дек, который заполняется от центра к краям.

Соответствующая задача на e-olimp: 6130 и зачтённое решение.

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

О плюсах и минусах

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

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

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

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

const int Max = 1000;		// максимально допустимое число элементов в малом деке

struct node {
	node* prev;
	node* next;
	int* dequeue;
	
	node(node* Pr, node* Ne) {
		prev = Pr;
		next = Ne;
		dequeue = new int[Max]();
	}
	
	void print() {
		for(int k = 0; k < Max; k++)
			cout << dequeue[k] << " ";
		cout << endl;
	}
};

struct Dequeue {
	node* first;
	node* last;
	int f;		// индекс первого свободного элемента в первой деке
	int l;		// индекс последнего свободного элемента в последней деке
	int Size;

	Dequeue() {
		node* N = new node(nullptr, nullptr);
		first = N;
		last = N;
		f = Max/2 - 1;
		l = Max/2;
		Size = 0;
	}

// Управление двусвязным списком
	void add_first () {			// добавляет новый узел в начало списка
		node* N = new node(nullptr, first);
		first -> prev = N;
		first = N;
		f = Max - 1;
	}
	
	void add_last () {		// добавляет новый узел в конец списка
		node* N = new node(last, nullptr);
		last -> next = N;
		last = N;
		l = 0;
	}
	
	void delete_first () {		// удаляет первый узел списка
		node* N = first -> next;
		delete first;
		first = N;
		first -> prev = nullptr;
		f = 0;
	}
	
	void delete_last () {		// удаляет последний узел списка
		node* N = last -> prev;
		delete last;
		last = N;
		last -> next = nullptr;
		l = Max - 1;
	}

// Управление деком
	void push_front (int n) {
		(first -> dequeue)[f] = n;
		f--;
		Size++;
		if (f == -1)		// если первый дек переполнен
			add_first();	// добавляем в начало списка новый дек
	}
	
	void push_back (int n) {
		(last -> dequeue)[l] = n;
		l++;
		Size++;
		if (l == Max)		// если последний дек переполнен
			add_last();		// добавляем в конец списка новый дек
	}
	
	int pop_front () {
		Size--;
		if (f == Max - 1)
			delete_first();
		else
			f++;
		return (first -> dequeue)[f];
	}
	
	int pop_back () {
		Size--;
		if (l == 0)
			delete_last();
		else
			l--;
		return (last -> dequeue)[l];
	}
	
	int front () {
		if (f == Max - 1)
			return ((first -> next) -> dequeue)[0];
		else
			return (first -> dequeue)[f+1];
	}
	
	int back () {
		if (l == 0)
			return ((last -> prev) -> dequeue)[Max - 1];
		else
			return (last -> dequeue)[l-1];
	}
	
	int size() {
		return Size;
	}
	
	bool empty() {return (Size == 0);}
	
	void clear() {
		node* N = first;
		while (N) {
			node* M = N -> next;
			delete N->prev;
			delete N;
			N = M;
		}
		
		N = new node(nullptr, nullptr);
		
		first = N;
		last = N;
		Size = 0;
		f = Max/2 - 1;
		l = Max/2;
	}
	
	void print() {
		node* N = first;
		while (N) {
			N -> print();
			N = N->next;
		}
	}
};


int main() {
	Dequeue D;
	string comand;
	int x;
	while(cin >> comand) {
		if (comand == "push_front") {
			cin >> x;
			D.push_front(x);
			cout << "ok\n";
		}
		if (comand == "push_back") {
			cin >> x;
			D.push_back(x);
			cout << "ok\n";
		}
		
		if (comand == "pop_front") {
			if (D.empty())
				cout << "error\n";
			else
				cout << D.pop_front() << "\n";
		}
		if (comand == "pop_back") {
			if (D.empty())
				cout << "error\n";
			else
				cout << D.pop_back() << "\n";
		}

		if (comand == "front") {
			if (D.empty())
				cout << "error\n";
			else
				cout << D.front() << "\n";
		}
		if (comand == "back") {
			if (D.empty())
				cout << "error\n";
			else
				cout << D.back() << "\n";
		}
		
		if (comand == "size") {
			cout << D.size() << "\n";
		}
		if (comand == "clear") {
			D.clear();
			cout << "ok\n";
		}
		if (comand == "exit") {
			cout << "bye\n";
			return 0;
		}
		if (comand == "print") {
			D.print();
		}
	}
	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

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

#include <iostream>

#include <string>

using namespace std;

const int Max = 1000; // максимально допустимое число элементов в малом деке

struct node {

node* prev;

node* next;

int* dequeue;

node(node* Pr, node* Ne) {

prev = Pr;

next = Ne;

dequeue = new int[Max]();

}

void print() {

for(int k = 0; k < Max; k++)

cout << dequeue[k] << " ";

cout << endl;

}

};

struct Dequeue {

node* first;

node* last;

int f; // индекс первого свободного элемента в первой деке

int l; // индекс последнего свободного элемента в последней деке

int Size;

Dequeue() {

node* N = new node(nullptr, nullptr);

first = N;

last = N;

f = Max/2 - 1;

l = Max/2;

Size = 0;

}

// Управление двусвязным списком

void add_first () { // добавляет новый узел в начало списка

node* N = new node(nullptr, first);

first -> prev = N;

first = N;

f = Max - 1;

}

void add_last () { // добавляет новый узел в конец списка

node* N = new node(last, nullptr);

last -> next = N;

last = N;

l = 0;

}

void delete_first () { // удаляет первый узел списка

node* N = first -> next;

delete first;

first = N;

first -> prev = nullptr;

f = 0;

}

void delete_last () { // удаляет последний узел списка

node* N = last -> prev;

delete last;

last = N;

last -> next = nullptr;

l = Max - 1;

}

// Управление деком

void push_front (int n) {

(first -> dequeue)[f] = n;

f--;

Size++;

if (f == -1) // если первый дек переполнен

add_first(); // добавляем в начало списка новый дек

}

void push_back (int n) {

(last -> dequeue)[l] = n;

l++;

Size++;

if (l == Max) // если последний дек переполнен

add_last(); // добавляем в конец списка новый дек

}

int pop_front () {

Size--;

if (f == Max - 1)

delete_first();

else

f++;

return (first -> dequeue)[f];

}

int pop_back () {

Size--;

if (l == 0)

delete_last();

else

l--;

return (last -> dequeue)[l];

}

int front () {

if (f == Max - 1)

return ((first -> next) -> dequeue)[0];

else

return (first -> dequeue)[f+1];

}

int back () {

if (l == 0)

return ((last -> prev) -> dequeue)[Max - 1];

else

return (last -> dequeue)[l-1];

}

int size() {

return Size;

}

bool empty() {return (Size == 0);}

void clear() {

node* N = first;

while (N) {

node* M = N -> next;

delete N->prev;

delete N;

N = M;

}

N = new node(nullptr, nullptr);

first = N;

last = N;

Size = 0;

f = Max/2 - 1;

l = Max/2;

}

void print() {

node* N = first;

while (N) {

N -> print();

N = N->next;

}

};

int main() {

Dequeue D;

string comand;

int x;

while(cin >> comand) {

if (comand == "push_front") {

cin >> x;

D.push_front(x);

cout << "ok\n";

}

if (comand == "push_back") {

cin >> x;

D.push_back(x);

cout << "ok\n";

}

if (comand == "pop_front") {

if (D.empty())

cout << "error\n";

else

cout << D.pop_front() << "\n";

}

if (comand == "pop_back") {

if (D.empty())

cout << "error\n";

else

cout << D.pop_back() << "\n";

}

if (comand == "front") {

if (D.empty())

cout << "error\n";

else

cout << D.front() << "\n";

}

if (comand == "back") {

if (D.empty())

cout << "error\n";

else

cout << D.back() << "\n";

}

if (comand == "size") {

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

}

if (comand == "clear") {

D.clear();

cout << "ok\n";

}

if (comand == "exit") {

cout << "bye\n";

return 0;

}

if (comand == "print") {

D.print();

}

return 0;

}

Related Images:

e-olimp 4004. Есть ли цикл?

22/03/2015 by Карташов Денис Геннадійович

Задача:

Дан ориентированный граф. Требуется определить, есть ли в нём цикл.

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

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

В первой строке вводится натуральное число [latex]N ( N \leq 50)[/latex] — количество вершин. Далее в [latex]N[/latex] строках следуют по [latex]N[/latex] чисел, каждое из которых — «0» или «1«. [latex]j [/latex] -е число в [latex]i[/latex] -й строке равно «1» тогда и только тогда, когда существует ребро, идущее из [latex]i[/latex] -й вершины в [latex]j[/latex]-ю. Гарантируется, что на диагонали матрицы будут стоять нули.

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

Выведите «0«, если в заданном графе цикла нет, и «1«, если он есть.

Результат на С++

Результат на Java

Код на С++:

#include <iostream>
using namespace std;

int ** a; // Матрица смежности будет записана именно сюда.
int n = 51; // Число вершин. 
int * was;// Массив цвета вершины.

bool dfs(int key){
  //"Красим" вершину в серый цвет (указываем, что мы в нее вошли).
  was[key] = 1;
  //Проходим все связанные с текущей вершиной.
  for(int i = 0; i < n; i++){
  //Если значение элемента строки матрицы (по условию, нам дана матрица смежности) отлично от "0", то:
      if(a[key][i]){
          //если вершина "белая" (т. е. мы в неё еще не заходили)- 
          //запускаем рекурсивный вызов DFS от этой вершины.
          if(was[i] == 0){if(dfs(i)) return true;}
          //если вершина "серая" (мы её уже навещали, но не возвращались из ее потомков)-  
          //мы нашли цикл, следовательно поиск можно завершить.
          else if(was[i] == 1){ return true;}
      }
  }
  //Если ни один из if - ов не сработал, то "красим" вершину в черный цвет (отмечаем, как пройденную)
  was[key] = 2;
 //и возвращаем результат поиска (мы ничего не нашли).
  return false;
}
int main() {
  cin >> n;
  a = new int *[n];
  was = new int [n];
  for(int i = 0; i < n; i++){
      a[i] = new int [n];
      was[i] = 0;
      for(int j = 0; j < n; j++){
          cin >> a[i][j];
      }
  }
  for(int i = 0; i < n; i++){
      //Проверяем поиском каждую вершину. Если поиск оказался успешным - выводим "1". 
      //Проверка цвета сделана ради ускорения процесса, иначе в поиске пришлось бы проходить весь 
      //цикл, даже если вершина покрашена в черный цвет.
      if(!was[i]&&dfs(i)) {cout << "1\n"; return 0;}
  }
  //Если if ни разу не сработал - выводим "0".
  cout << "0\n";
  return 0;
}

#include <iostream>

using namespace std;

int ** a; // Матрица смежности будет записана именно сюда.

int n = 51; // Число вершин.

int * was;// Массив цвета вершины.

bool dfs(int key){

//"Красим" вершину в серый цвет (указываем, что мы в нее вошли).

was[key] = 1;

//Проходим все связанные с текущей вершиной.

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

//Если значение элемента строки матрицы (по условию, нам дана матрица смежности) отлично от "0", то:

if(a[key][i]){

//если вершина "белая" (т. е. мы в неё еще не заходили)-

//запускаем рекурсивный вызов DFS от этой вершины.

if(was[i] == 0){if(dfs(i)) return true;}

//если вершина "серая" (мы её уже навещали, но не возвращались из ее потомков)-

//мы нашли цикл, следовательно поиск можно завершить.

else if(was[i] == 1){ return true;}

}

//Если ни один из if - ов не сработал, то "красим" вершину в черный цвет (отмечаем, как пройденную)

was[key] = 2;

//и возвращаем результат поиска (мы ничего не нашли).

return false;

}

int main() {

cin >> n;

a = new int *[n];

was = new int [n];

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

a[i] = new int [n];

was[i] = 0;

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

cin >> a[i][j];

}

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

//Проверяем поиском каждую вершину. Если поиск оказался успешным - выводим "1".

//Проверка цвета сделана ради ускорения процесса, иначе в поиске пришлось бы проходить весь

//цикл, даже если вершина покрашена в черный цвет.

if(!was[i]&&dfs(i)) {cout << "1\n"; return 0;}

}

//Если if ни разу не сработал - выводим "0".

cout << "0\n";

return 0;

}

Код на Java:

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

class Graphdfs
{
	private int[][] matrix; // Матрица смежности будет записана именно сюда.
	private int n; // Число вершин. 
	private int[] was;// Массив цвета вершины.
	public Graphdfs(){}
	public Graphdfs(int n)
	{
		this.n = n;
		matrix = new int [n][n];
		was = new int [n];
	}
	public void setMatrix(Scanner in)
	{
		for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
			matrix[i][j] = in.nextInt();
	}
	public void showMatrix()
	{
		for(int i = 0; i < n; i++)
		{
			for(int j = 0; j < n; j++)
			{
				System.out.print(matrix[i][j]);
				if(j < n - 1) System.out.print(" ");
				else System.out.println();
			}
		}
	}
 	public boolean dfs(int key)
 	{
		was[key] = 1;
		for(int i = 0; i < n; i++)
		{
			if(matrix[key][i] != 0)
			{
				if(was[i] == 0){
					if(dfs(i)) return true;
				}
				else if(was[i] == 1){
					return true;
				}
			}
		}
		was[key] = 2;
		return false;
	}
	public int[] getWas(){
		return was;
	}
}

public class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		//System.out.println("ok1");
		Scanner in = new Scanner(System.in);
		//System.out.println("ok2");
		int n = in.nextInt();
		//System.out.println("ok3");
		Graphdfs Graph = new Graphdfs(n);
		//System.out.println("ok4");
		Graph.setMatrix(in);
		//System.out.println("ok5");
		//Graph.showMatrix();
		for(int i = 0; i < n; i++){
			if(Graph.getWas()[i] == 0 &&Graph.dfs(i) == true) {System.out.println(1); System.exit(0);}
		}
		System.out.println(0);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Graphdfs

{

private int[][] matrix; // Матрица смежности будет записана именно сюда.

private int n; // Число вершин.

private int[] was;// Массив цвета вершины.

public Graphdfs(){}

public Graphdfs(int n)

{

this.n = n;

matrix = new int [n][n];

was = new int [n];

}

public void setMatrix(Scanner in)

{

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

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

matrix[i][j] = in.nextInt();

}

public void showMatrix()

{

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

{

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

{

System.out.print(matrix[i][j]);

if(j < n - 1) System.out.print(" ");

else System.out.println();

}

public boolean dfs(int key)

{

was[key] = 1;

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

{

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

{

if(was[i] == 0){

if(dfs(i)) return true;

}

else if(was[i] == 1){

return true;

}

was[key] = 2;

return false;

}

public int[] getWas(){

return was;

}

public class Main

{

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

{

//System.out.println("ok1");

Scanner in = new Scanner(System.in);

//System.out.println("ok2");

int n = in.nextInt();

//System.out.println("ok3");

Graphdfs Graph = new Graphdfs(n);

//System.out.println("ok4");

Graph.setMatrix(in);

//System.out.println("ok5");

//Graph.showMatrix();

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

if(Graph.getWas()[i] == 0 &&Graph.dfs(i) == true) {System.out.println(1); System.exit(0);}

}

System.out.println(0);

}

Пояснение:

Циклом в графе называется цепь, в которой первая и последняя вершина совпадает. Значит, если проходя по вершинам графа в лексикографическом порядке, в какой — то момент я попаду в вершину в которую вошел, но еще не вышел, то это будет означать, что я нашёл цикл.

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

Related Images:

e-olimp 553. Рекурсия

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

Задача: Рекурсия

Решение

ссылка на ideone, засчитанное решение на e-olimp

#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<string>
using namespace std;

map<string,set<string>> G;
map<string,bool> used;
map<string,bool> rec;
vector<string> V;

void dfs(string cur, string aim){
   if(used[cur] || rec[aim]) return;
   used[cur] = 1;
   for(auto i = G[cur].begin(); i != G[cur].end(); i++){
      if(*i != aim){
         dfs(*i,aim);
      }else{
         rec[aim] = 1;
         return;
      }
   }
}

int main(){
   //input
   int n; cin >> n;
   for(int i = 0; i < n; i++){
      string curVert; cin >> curVert;
      V.push_back(curVert);
      int m; cin >> m;
      while(m--){
         string inp; cin >> inp;
         G[curVert].insert(inp);
      }
      if(i != n-1){
         string stars;
         cin >> stars;
      }
   }
   //work
   for(auto i : V){
      dfs(i, i);
      used.clear();
   }
   for(auto i : V){
      cout << i << (rec[i] ? ": YES" : ": NO") << endl;
   }
   return 0;
}

#include<iostream>

#include<vector>

#include<set>

#include<map>

#include<string>

using namespace std;

map<string,set<string>> G;

map<string,bool> used;

map<string,bool> rec;

vector<string> V;

void dfs(string cur, string aim){

if(used[cur] || rec[aim]) return;

used[cur] = 1;

for(auto i = G[cur].begin(); i != G[cur].end(); i++){

if(*i != aim){

dfs(*i,aim);

}else{

rec[aim] = 1;

return;

}

int main(){

//input

int n; cin >> n;

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

string curVert; cin >> curVert;

V.push_back(curVert);

int m; cin >> m;

while(m--){

string inp; cin >> inp;

G[curVert].insert(inp);

}

if(i != n-1){

string stars;

cin >> stars;

}

//work

for(auto i : V){

dfs(i, i);

used.clear();

}

for(auto i : V){

cout << i << (rec[i] ? ": YES" : ": NO") << endl;

}

return 0;

}

Идея решения

Можно заметить, что каждая процедура — это вершина ориентированного графа. Чтобы узнать, является ли процедура потенциально рекурсивной, нужно было запустить из неё поиск в глубину и узнать, сможем ли мы прийти к ней вновь.

Было решено использовать map<string,set<string>> как структуру для описания графа: каждая вершина — это строка и у каждой вершины есть множество вершин (строк), смежных с ней.
А еще задача имеет классификацию — поиск в глубину, что как бы намекает.

Related Images:

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

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

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

Решение:

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

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

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

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

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

#include <iostream>

#include <string>

using namespace std;

struct Node{

Node * prev;

int x;

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

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

};

struct stack{

private:

Node * Head = nullptr;

int Size = 0;

public:

int size(){

return Size;

}

void push(int p){

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

Head = NewHead;

Size++;

}

int back(){

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

else{return 0;}

}

int pop(){

if(Size){

int x = Head->x;

Node * NewHead = Head->prev;

delete Head;

Head = NewHead;

Size--;

return x;

}else{

return 0;

}

void clear(){

while(Size > 0){

Node * NewHead = Head->prev;

delete Head;

Head = NewHead;

Size--;

}

};

int main() {

stack myStack;

while(true){

string s; cin >> s;

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

else if(s == "push"){

int inp; cin >> inp;

myStack.push(inp);

cout << "ok\n";

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

if(myStack.size()){

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

}else{

cout << "error\n";

}

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

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

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

if(myStack.size()){

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

}else{

cout << "error\n";

}

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

cout << "ok\n";

myStack.clear();

}

return 0;

}

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

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

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

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

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

	return 0;
}

#include <iostream>

#include <string>

using namespace std;

struct Node{

Node * prev;

int x;

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

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

};

struct queue{

private:

Node * Front = nullptr;

Node * Back = nullptr;

int Size = 0;

public:

int size(){

return Size;

}

void push(int p){

if(Size == 0){

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

Front = NewNode;

Back = NewNode;

}else{

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

Back->prev = NewNode;

Back = NewNode;

}

Size++;

}

int front(){

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

else{return 0;}

}

int pop(){

if(Size){

int x = Front->x;

Node * NewNode = Front->prev;

delete Front;

Front = NewNode;

Size--;

return x;

}else{

return 0;

}

void clear(){

while(Size > 0){

Node * NewNode = Front->prev;

delete Front;

Front = NewNode;

Size--;

}

Front = nullptr;

Back = nullptr;

}

};

int main() {

queue Q;

while(true){

string s; cin >> s;

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

else if(s == "push"){

int inp; cin >> inp;

Q.push(inp);

cout << "ok\n";

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

if(Q.size()){

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

}else{

cout << "error\n";

}

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

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

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

if(Q.size()){

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

}else{

cout << "error\n";

}

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

cout << "ok\n";

Q.clear();

}

return 0;

}

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

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

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

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

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

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

#include <iostream>

#include <string>

using namespace std;

struct Node{

Node * prev;

Node * next;

int x;

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

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

};

struct deque{

private:

Node * Front = nullptr;

Node * Back = nullptr;

int Size = 0;

public:

int size(){

return Size;

}

void push_back(int p){

if(Size == 0){

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

Front = NewNode;

Back = NewNode;

}else{

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

Back->prev = NewNode;

Back = NewNode;

}

Size++;

}

void push_front(int p){

if(Size == 0){

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

Front = NewNode;

Back = NewNode;

}else{

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

Front->next = NewNode;

Front = NewNode;

}

Size++;

}

int back(){

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

else{return 0;}

}

int front(){

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

else{return 0;}

}

int pop_front(){

if(Size){

int x = Front->x;

Node * NewNode = Front->prev;

delete Front;

Front = NewNode;

Size--;

return x;

}else{

return 0;

}

int pop_back(){

if(Size){

int x = Back->x;

Node * NewNode = Back->next;

delete Back;

Back = NewNode;

Size--;

return x;

}else{

return 0;

}

void clear(){

while(Size > 0){

Node * NewNode = Front->prev;

delete Front;

Front = NewNode;

Size--;

}

Front = nullptr;

Back = nullptr;

}

};

int main() {

deque D;

while(true){

string s; cin >> s;

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

else if(s == "push_back"){

int inp; cin >> inp;

D.push_back(inp);

cout << "ok\n";

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

int inp; cin >> inp;

D.push_front(inp);

cout << "ok\n";

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

if(D.size()){

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

}else{

cout << "error\n";

}

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

if(D.size()){

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

}else{

cout << "error\n";

}

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

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

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

if(D.size()){

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

}else{

cout << "error\n";

}

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

if(D.size()){

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

}else{

cout << "error\n";

}

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

cout << "ok\n";

D.clear();

}

return 0;

}

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

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

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

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

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

Related Images:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

#include <iostream>

#include <stack>

#include <utility>

#include <algorithm>

using namespace std;

const long long mod=1000000;

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

int main() {

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

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

while (n--) {

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

if (x%5<2) {

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

}

else {

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

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

}

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

}

cout << ans << endl;

return 0;

}

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

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

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

Related Images:

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

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

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

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

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

Решение

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

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

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

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

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

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

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

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

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

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