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

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

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

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

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

Задача

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

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

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

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

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

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

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

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

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

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

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

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

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

Тесты

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

Код

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

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

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

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

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

    int size(){
        return finish - start;
    }

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

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

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

#include <iostream>

#include <string>

using namespace std;

struct queue{

int storage[100000];

int start;

int finish;

queue(){

start = 0;

finish = 0;

}

void push(int n){

storage[finish] = n;

finish++;

}

int pop(){

int a = storage[start];

start++;

return a;

}

int front(){

return storage[start];

}

int size(){

return finish - start;

}

string clear(){

finish = 0;

start = 0;

return "ok";

}

string exit(){

return "bye";

}

};

int main() {

string a;

queue x;

while(cin >> a){

if(a == "push"){

int n;

cin >> n;

x.push(n);

cout << "ok" << endl;

}

if(a == "pop"){

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

}

if(a == "front"){

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

}

if(a == "size"){

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

}

if(a == "clear"){

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

}

if(a == "exit"){

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

return 0;

}

return 0;

}

Ход решения

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

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

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

Related Images:

AL13

31/03/2016 by Молоканов Юрий

Условие

Имеется [latex]n[/latex] черных и белых карточек, сложенных в стопку. Карточки раскладываются на стол в одну линию следующим образом: первая кладется на стол, вторая — под низ стопки, третья — на стол, четвертая — под низ стопки и т.д., пока все карточки не будут выложены на стол. Каким должно быть исходное расположение карточек в стопке, чтобы разложенные на столе карточки чередовались по цвету: белая, черная, белая, черная и т.д.?

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

№	Входные данные	Выходные данные
1	1	1
2	2	01
3	5	10011
4	12	101100010011
5	20	00111001101100010011

Здесь нули — черные карточки, единицы — белые, а первый символ строки обозначает карточку, лежащую внизу стопки.

Код

#include <iostream>
using namespace std;

// Узел. Используется в очереди
struct node {
    bool val;   // Значение узла
    node *next; // Указатель на следующий узел
    node(int v, node *n = NULL) {
        val = v;
        next = n;
    }
};

// Очередь. Используется как представление стопки
struct Queue {
    node *head;
    Queue(node *h = NULL) {
        head = h;
    }
    void push(bool v) { // Добавить элемент в очередь
        head = new node(v, head);
    }
    bool pop() {    // Изъять элемент из очереди
        if(head != NULL && (head -> next) != NULL) {
            node *i = head;
            node *p = i;
            while(i -> next != NULL) {
                p = i;
                i = i -> next;
            }
            bool v = i -> val;
            p -> next = NULL;
            delete i;
            return v;
        } else {
            node *n = head;
            bool v = head -> val;
            head = head -> next;
            delete n;
            return v;
        }
    }
};

int main() {
    int n;  // Количество карточек в стопке
    cin >> n;
    Queue cards;
    bool t = n % 2; // Цвет текущей карточки. Инициализируется цветом последней выкладываемой карточки
    for(int i = 0; i < n - 1; i++) { // Собираем стопку, не добавляя верхнюю карточку
        cards.push(t);  // Добавляем текущую карточку
        cards.push(cards.pop());    // Перекладываем карточку из-под стопки наверх
        t = !t; // Меняем цвет текущей карточки
    }
    cards.push(1);  // Добавляем белую карточку наверх
    for(int i = 0; i < n; i++)   // Выводим полученную стопку
        cout << cards.pop();
    return 0;
}

#include <iostream>

using namespace std;

// Узел. Используется в очереди

struct node {

bool val; // Значение узла

node *next; // Указатель на следующий узел

node(int v, node *n = NULL) {

val = v;

next = n;

}

};

// Очередь. Используется как представление стопки

struct Queue {

node *head;

Queue(node *h = NULL) {

head = h;

}

void push(bool v) { // Добавить элемент в очередь

head = new node(v, head);

}

bool pop() { // Изъять элемент из очереди

if(head != NULL && (head -> next) != NULL) {

node *i = head;

node *p = i;

while(i -> next != NULL) {

p = i;

i = i -> next;

}

bool v = i -> val;

p -> next = NULL;

delete i;

return v;

} else {

node *n = head;

bool v = head -> val;

head = head -> next;

delete n;

return v;

}

};

int main() {

int n; // Количество карточек в стопке

cin >> n;

Queue cards;

bool t = n % 2; // Цвет текущей карточки. Инициализируется цветом последней выкладываемой карточки

for(int i = 0; i < n - 1; i++) { // Собираем стопку, не добавляя верхнюю карточку

cards.push(t); // Добавляем текущую карточку

cards.push(cards.pop()); // Перекладываем карточку из-под стопки наверх

t = !t; // Меняем цвет текущей карточки

}

cards.push(1); // Добавляем белую карточку наверх

for(int i = 0; i < n; i++) // Выводим полученную стопку

cout << cards.pop();

return 0;

}

Решение

Алгоритм разбора стопки можно описать следующим образом:

Выкладываем на стол верхнюю карточку.
Пока в стопке есть карты, выполняем действия:
1. перекладываем под низ стопки верхнюю карточку;
2. выкладываем на стол верхнюю карточку.

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

Пока на столе не останется одна карточка, выполняем действия:
1. добавляем карточку, выложенную на стол последней из имеющихся, на верх стопки;
2. перекладываем карточку из-под стопки наверх.
Добавляем карточку наверх.

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

Для решения задачи удобнее всего будет воспользоваться очередью, поскольку при построении стопки мы добавляем карточки только в один ее конец, а изымаем при перекладывании всегда из противоположного. Более того, в данном случае структуру можно значительно облегчить, оставив из методов только push() и pop(), причем из последнего можно за ненадобностью удалить проверку исключительной ситуации при попытке изъять карточку из пустой стопки, так как по алгоритму прямо перед изъятием всегда выполняется добавление карточки. Карточки могут быть только двух цветов, поэтому узлы очереди будут хранить значения типа bool.

Перейдем к практическому решению. Прежде всего получим количество карточек в требуемой стопке и объявим очередь:

int n;
cin >> n;
Queue cards;

int n;

cin >> n;

Queue cards;

Затем объявим переменную для цвета текущей карточки и инициализируем ее таким образом, чтобы последняя добавляемая карточка была белой. Так как при четном числе карточек в стопке последняя выкладываемая (она же — первая добавляемая) будет черной, а при нечетном — белой, то при кодировании черных и белых цветов как [latex]0[/latex] и [latex]1[/latex] соответственно инициализируется она следующим значением:

bool t = n % 2;

1	bool t = n % 2;

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

for(int i = 0; i < n - 1; i++) {
    cards.push(t);
    cards.push(cards.pop());
    t = !t;
}
cards.push(1);

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

cards.push(t);

cards.push(cards.pop());

t = !t;

}

cards.push(1);

Наконец, разбираем стопку, начиная с условного низа, и выводим ее как ответ на поставленную задачу:

for(int i = 0; i < n; i++)
    cout << cards.pop();

1 2	for(int i = 0; i < n; i++) cout << cards.pop();

Ссылки

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

Список задач по структурам данных на Algolist.manual.ru.

Related Images:

e-olymp 2820. Перемещение коня

31/03/2016 by Молоканов Юрий

Условие

Ваш друг проводит научные исследования по проблеме Конского Минимального Путешествия (КМП), которая состоит в том, чтобы найти кратчайший замкнутый тур ходов конём, который посещает каждую клетку заданного набора из [latex]n[/latex] клеток на шахматной доске ровно один раз. Он считает, что самая трудная часть задачи состоит в определении наименьшего числа ходов для перемещения коня между двумя заданными клетками и что, как только вы поможете ему решить эту подзадачу, то ему решить всю задачу будет намного легче. Вы, конечно, знаете, что дело обстоит как раз наоборот. Таким образом, вы в свою очередь решили предложить ему самому написать программу, которая решает «трудную» часть.

Ваша задача состоит в том, чтобы написать программу, которая принимает координаты двух клеток [latex]a[/latex] и [latex]b[/latex] в качестве входных данных, а затем определяет количество ходов конем кратчайшим путём из [latex]a[/latex] в [latex]b[/latex].

Входные данные будут содержать один или более тестов. Каждый тест состоит из одной строки, содержащей координаты двух клеток, разделенные одним пробелом. Координаты клетки являются двумя символами, первый из которых буква ([latex]\text{a}[/latex]–[latex]\text{h}[/latex]), задающая столбец и второй – цифра ([latex]1[/latex]–[latex]8[/latex]), задающая строку на шахматной доске.

Для каждого теста вывести одну строку следующего содержания: «To get from [latex]\text{xx}[/latex] to [latex]\text{yy}[/latex] takes [latex]n[/latex] knight moves.»

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

№	Входные данные	Выходные данные
1	1	-1
2	0.25	-0.75
3	0.1	-0.861111
4	0.01	-0.827962
5	0.0000001	-0.822467

Код

#include <iostream>
#include <string>
#include <cmath>
using namespace std;
 
// Клетка шахматной доски
struct cell {
    int a;  // Вертикальная координата (числа)
    int b;  // Горизонтальная координата (буквы)
    int d;  // Расстояние до этой клетки из начальной
}; 
 
// Узел. Используется в очереди
struct node {
    cell val;
    node *next;
    node(cell v, node *n = NULL) {
        val = v;
        next = n;
    }
};
 
// Очередь. Используется для поиска в ширину
struct Queue {
    node *head;
    Queue(node *h = NULL) {
        head = h;
    }
    void push(cell v) { // Добавить элемент в очередь
        head = new node(v, head);
    }
    cell pop() {    // Изъять элемент из очереди
        if((head -> next) != NULL) {
            node *i = head;
            node *p = i;
            while(i -> next != NULL) {
                p = i;
                i = i -> next;
            }
            cell v = i -> val;
            p -> next = NULL;
            delete i;
            return v;
        } else {
            node *n = head;
            cell v = head -> val;
            head = head -> next;
            delete n;
            return v;
        }
    }
    void clear() {  // Очистить очередь
        head = NULL;
    }
};
 
int main() {
    string r;   // Строка для запроса
    Queue q;    // Очередь
    cell current, goal, next;   // Текущая, конечная и следующая клетки
    bool visited[8][8]; // Посещенные клетки
    while(getline(cin, r)) {
        
        // Готовим текущую и конечную клетки
        current.a = (int)(r[1] - '1');
        current.b = (int)(r[0] - 'a');
        goal.a = (int)(r[4] - '1');
        goal.b = (int)(r[3] - 'a');
        current.d = 0;
        
        // Готовим массив посещенных клеток
        for(int i = 0; i < 8; i++)
            for(int j = 0; j < 8; j++)
                visited[i][j] = false;
        visited[current.a][current.b] = true;
        
        // Готовим очередь
        q.push(current);
        
        // Выполняем поиск в ширину
        while( !(current.a == goal.a && current.b == goal.b) ) {    // Пока координаты очередной клетки из очереди не совпадут с координатами конечной
            current = q.pop();  // Достаем новую клетку из очереди
            next.d = current.d + 1; // Расстояние до клеток нового слоя поиска будет на 1 больше, чем до клеток предыдущего
            // Перебираем 8 потенцальных ходов из текущей клетки комбинациями сдвигов по координатам
            for(int i = -2; i <= 2; i++) 
                if(i != 0)
                    for(int j = -(3 - abs(i)); j <= 3 - abs(i); j += 2 * (3 - abs(i))) {
                        // Присваиваем следующей клетке новые координаты
                        next.a = current.a + i;
                        next.b = current.b + j;
                        if(0 <= next.a && next.a <= 7 && 0 <= next.b && next.b <= 7 && !visited[next.a][next.b]) {  // Если следующая клетка находится в пределах доски и не была посещена
                            q.push(next);   // Добавляем ее в очередь
                            visited[next.a][next.b] = true; // Отмечаем ее посещенной
                        }
                    }
        }
        
        // Выводим ответ
        cout << "To get from " << r[0] << r[1] << " to " << r[3] << r[4] << " takes " << current.d << " knight moves." << endl;
        
        // Очищаем очередь для следующего теста
        q.clear();
    }
    return 0;
}

100

101

102

103

104

105

#include <iostream>

#include <string>

#include <cmath>

using namespace std;

// Клетка шахматной доски

struct cell {

int a; // Вертикальная координата (числа)

int b; // Горизонтальная координата (буквы)

int d; // Расстояние до этой клетки из начальной

};

// Узел. Используется в очереди

struct node {

cell val;

node *next;

node(cell v, node *n = NULL) {

val = v;

next = n;

}

};

// Очередь. Используется для поиска в ширину

struct Queue {

node *head;

Queue(node *h = NULL) {

head = h;

}

void push(cell v) { // Добавить элемент в очередь

head = new node(v, head);

}

cell pop() { // Изъять элемент из очереди

if((head -> next) != NULL) {

node *i = head;

node *p = i;

while(i -> next != NULL) {

p = i;

i = i -> next;

}

cell v = i -> val;

p -> next = NULL;

delete i;

return v;

} else {

node *n = head;

cell v = head -> val;

head = head -> next;

delete n;

return v;

}

void clear() { // Очистить очередь

head = NULL;

}

};

int main() {

string r; // Строка для запроса

Queue q; // Очередь

cell current, goal, next; // Текущая, конечная и следующая клетки

bool visited[8][8]; // Посещенные клетки

while(getline(cin, r)) {

// Готовим текущую и конечную клетки

current.a = (int)(r[1] - '1');

current.b = (int)(r[0] - 'a');

goal.a = (int)(r[4] - '1');

goal.b = (int)(r[3] - 'a');

current.d = 0;

// Готовим массив посещенных клеток

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

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

visited[i][j] = false;

visited[current.a][current.b] = true;

// Готовим очередь

q.push(current);

// Выполняем поиск в ширину

while( !(current.a == goal.a && current.b == goal.b) ) { // Пока координаты очередной клетки из очереди не совпадут с координатами конечной

current = q.pop(); // Достаем новую клетку из очереди

next.d = current.d + 1; // Расстояние до клеток нового слоя поиска будет на 1 больше, чем до клеток предыдущего

// Перебираем 8 потенцальных ходов из текущей клетки комбинациями сдвигов по координатам

for(int i = -2; i <= 2; i++)

if(i != 0)

for(int j = -(3 - abs(i)); j <= 3 - abs(i); j += 2 * (3 - abs(i))) {

// Присваиваем следующей клетке новые координаты

next.a = current.a + i;

next.b = current.b + j;

if(0 <= next.a && next.a <= 7 && 0 <= next.b && next.b <= 7 && !visited[next.a][next.b]) { // Если следующая клетка находится в пределах доски и не была посещена

q.push(next); // Добавляем ее в очередь

visited[next.a][next.b] = true; // Отмечаем ее посещенной

}

// Выводим ответ

cout << "To get from " << r[0] << r[1] << " to " << r[3] << r[4] << " takes " << current.d << " knight moves." << endl;

// Очищаем очередь для следующего теста

q.clear();

}

return 0;

}

Решение

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

Прежде всего найдем зависимость [latex]a_{n+1}[/latex] от [latex]a_n[/latex] и выведем рекуррентную формулу для очередного члена:

[latex]a_{n+1} = a_n \cdot \frac {a_{n+1}}{a_n} = a_n \cdot \frac {\frac {(-1)^{i+1}}{(i+1)^2}}{\frac {(-1)^i}{i^2}} = a_n \cdot -(\frac {i}{i+1})^2[/latex]

Для вычислений мы используем рекуррентное соотношение, поэтому до выполнения цикла, накапливающего сумму, переменным члена ряда a и суммы sum потребуется присвоить значение [latex]a_1 = \frac {(-1)^1}{1^2} = -1[/latex]:

double a = -1, sum = -1, E;

1	double a = -1, sum = -1, E;

Теперь опишем, каким образом будет работать цикл:

Цикл будет начинаться со счетчиком [latex]i = 1[/latex], который будет инкрементироваться в конце каждой итерации.
Цикл будет выполняться до тех пор, пока абсолютное значение очередного члена ряда [latex]a_i[/latex] будет не меньше, чем заданная точность [latex]\varepsilon[/latex].
В каждой итерации цикла значение суммы будет увеличиваться на [latex]a_i[/latex].

Реализуем описанный алгоритм с помощью цикла for. Чтобы сократить количество операций в теле цикла до одной, вычислять очередной член ряда будем при проверке выполнения условия продолжения. При присвоении переменной a нового значения воспользуемся кастингом (double) ; в противном случае уже второй член ряда будет обнуляться из-за умножения на дробь с целой частью [latex]0[/latex]:

for(int i = 1; abs(a *= (double)(-i*i)/(i+1)/(i+1)) >= E; i++)
    sum += a;

1 2	for(int i = 1; abs(a = (double)(-ii)/(i+1)/(i+1)) >= E; i++) sum += a;

Наконец, выведем требуемое значение — сумму ряда:

cout << sum;

1	cout << sum;

Ссылки

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

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

Подтверждение решения на E-Olymp.

Related Images:

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

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

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

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

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

Тесты

№	Входные данные	Выходные данные
1	push 2 push 3 push 5 back size pop size push 7 pop clear size exit	ok ok ok 5 3 5 2 ok 7 ok 0 bye
2	push 7 size push 1 pop back exit push 4 pop	ok 1 ok 1 7 bye

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

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

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

#include <iostream>

#include <string>

using namespace std;

#define SIZE 100

struct stack {

int storage[SIZE];

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

void push (int n) {

storage[cursor] = n;

cursor++;

}

int pop () {

return storage[--cursor];

}

int back () {

return storage[cursor-1];

}

unsigned int size () {

return cursor;

}

void clear () {

cursor = 0;

}

};

int main () {

stack s;

string str;

int n;

while (cin >> str) {

if (str == "push") {

cin >> n;

s.push(n);

cout << "ok" << endl;

}

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

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

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

else if (str == "clear") {

s.clear();

cout << "ok" << endl;

}

else if (str == "exit") {

cout << "bye" << endl;

break;

}

return 0;

}

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

Решение

Реализуем стек с помощью массива, указателя на на верхнюю незаполненную ячейку массива ([latex]cursor[/latex]) и функций, с помощью которых выполняются команды push, pop, back, size, clear:

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

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

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

Related Images:

e-olymp 2820. Перемещение коня

30/06/2015 by Янішевська Альона Русланівна

Задача с сайта e-olimp №2820. Перемещение коня

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

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

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

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

Входные данные будут содержать один или более тестов. Каждый тест состоит из одной строки, содержащей координаты двух клеток, разделенные одним пробелом. Координаты клетки являются двумя символами, первый из которых буква (a—h), задающая столбец и второй – цифра (1—8), задающая строку на шахматной доске.

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

Для каждого теста вывести одну строку следующего содержания: «To get from xx to yy takes n knight moves.» (см. пример выходных данных).

Тесты:

Пример входных данных	Пример выходных данных
e2 e4	To get from e2 to e4 takes knight 2 moves.
a1 b2	To get from a1 to b2 takes knight 4 moves.
b2 c3	To get from b2 to c3 takes knight 2 moves.
a1 h8	To get from a1 to h8 takes knight 6 moves.
a1 h7	To get from a1 to h7 takes knight 5 moves.
h8 a1	To get from h8 to a1 takes knight 6 moves.
b1 c3	To get from b1 to c3 takes knight 1 moves.
f6 f6	To get from f6 to f6 takes knight 0 moves.

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

#include<cstdio>
#include<queue>
using namespace std;
 
char a, b;
int nx, ny, tx, ty;
int mx[] = { -1, -1, 1, 1, -2, -2, 2, 2 };
int my[] = { 2, -2, 2, -2, 1, -1, 1, -1 };
int A[8][8];
 
int main() {
    while(scanf("%c%d %c%d\n", &a, &ny, &b, &ty) == 4) {
        nx = a - 'a';
        ny--;
        tx = b - 'a';
        ty--;
        A[nx][ny] = 0;
        queue< pair<int, int> > q;
        q.push(make_pair(nx, ny));
        while(!q.empty()) {
            pair<int, int> c = q.front();
            int x = c.first, y = c.second;
            if(x == tx && y == ty) break;
            q.pop();
            for(int i = 0; i < 8; i++) {
                if(x + mx[i] >= 0 && x + mx[i] < 8 && y + my[i] >= 0 && y + my[i] < 8) {
                    q.push(make_pair(x + mx[i], y + my[i]));
                    A[x + mx[i]][y + my[i]] =  A[x][y] + 1;
                }
            }
        }
        printf("To get from %c%d to %c%d takes %d knight moves.\n", a, ny + 1, b, ty + 1, A[tx][ty]);
    }
}

#include<cstdio>

#include<queue>

using namespace std;

char a, b;

int nx, ny, tx, ty;

int mx[] = { -1, -1, 1, 1, -2, -2, 2, 2 };

int my[] = { 2, -2, 2, -2, 1, -1, 1, -1 };

int A[8][8];

int main() {

while(scanf("%c%d %c%d\n", &a, &ny, &b, &ty) == 4) {

nx = a - 'a';

ny--;

tx = b - 'a';

ty--;

A[nx][ny] = 0;

queue< pair<int, int> > q;

q.push(make_pair(nx, ny));

while(!q.empty()) {

pair<int, int> c = q.front();

int x = c.first, y = c.second;

if(x == tx && y == ty) break;

q.pop();

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

if(x + mx[i] >= 0 && x + mx[i] < 8 && y + my[i] >= 0 && y + my[i] < 8) {

q.push(make_pair(x + mx[i], y + my[i]));

A[x + mx[i]][y + my[i]] = A[x][y] + 1;

}

printf("To get from %c%d to %c%d takes %d knight moves.\n", a, ny + 1, b, ty + 1, A[tx][ty]);

}

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

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

Related Images:

e-olymp 4050. Забавная игра

29/06/2015 by Зелінський Вячеслав Олександрович

Ссылка на задачу.

Засчитанное решение.

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

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

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

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

Первая строка содержит два целых числа: n и k, разделённые пробелом. Здесь n — количество аэропортов (n ≤1000), а k — номер аэропорта, являющегося начальной точкой игры (1 ≤ k ≤ n). Следующая n−1 строка содержит пары целых чисел, разделённых пробелами. Это номера аэропортов, соединённых рейсом. Все рейсы двусторонние и упомянуты только один раз. Каждый аэропорт соединён рейсами не более, чем с 20 другими.

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

Если игрок, начинающий игру, выигрывает, программа должна написать «First player wins flying to airport L«, где L— номер аэропорта, в который игрок должен вылететь из текущего. Если таких аэропортов несколько, программа должна выбрать вариант с меньшим номером аэропорта. Если начинающий игрок проигрывает, программа должна написать «First player loses«.

#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
bool is_use[1001];
vector<int> airports[1001];
int level = 0;					// уровень вложенности dfs
/*int isFindAnsver = false;		// переменная выхода из цикла*/
int second_ver = 0;					// переменная запоминает вторую вершину, для ответа
bool is_second_ver_find = false;
bool is_sort[1001];
bool FIRST_WIN = true, SECOND_WIN = false;
 
bool dfs(int now_ver){			// Возвращает true если выигрывает первы, и false, если второй
	is_use[now_ver] = true;
	bool child;
	level++;
	if(level == 2){
		second_ver = now_ver;
	}
	if(!is_sort[now_ver]){
		sort(airports[now_ver].begin(), airports[now_ver].end());
		is_sort[now_ver] = true;
	}
 
	int count_ver=0;				// переменная считает вершины в которые можно пойти из данной
	for(int i=0 ; i<airports[now_ver].size() ; i++ ){			// 
		if( !is_use[ airports[now_ver][i] ] ){
			// В зависимости от четноси мы должны искать тот ли иной овет
			// от четности зависит то каккой игрок ходит на данный момент
			child = dfs(airports[now_ver][i]);
			// Если нечетное, то мы ищем правильных ход первого, иначе правильный ход второго
			if(level%2 == 1? child == FIRST_WIN : child == SECOND_WIN){		
				if(level == 1){
					if(child == FIRST_WIN){
						cout << "First player wins flying to airport " << second_ver << endl;
					}else{		// SECOND_WIn
						cout << "First player loses" << endl;
					}
					return true;
				}else{
					level--;
					return child;
				}
			}	// если найден нужный нам ответ на этом уровне
 
			count_ver++;
		}
	}
 
	is_use[now_ver] = false;
	
 
	if(level != 1)return ((level--)%2 == 1? SECOND_WIN : FIRST_WIN);			
	else{
		if(child == FIRST_WIN){
			cout << "First player wins flying to airport " << second_ver << endl;
		}else{		
			cout << "First player loses" << endl;
		}
	}
}
 
 
 
int main(){
	int n, k;
	cin >> n >> k;
	int u, v;
	for( int i=0 ; i<n-1 ; i++ ){			
		cin >> u >> v;
		airports[u].push_back(v);
		airports[v].push_back(u);
	}
 
	second_ver = k;
 
	dfs(k);
}

#include <cstdlib>

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

bool is_use[1001];

vector<int> airports[1001];

int level = 0; // уровень вложенности dfs

/*int isFindAnsver = false; // переменная выхода из цикла*/

int second_ver = 0; // переменная запоминает вторую вершину, для ответа

bool is_second_ver_find = false;

bool is_sort[1001];

bool FIRST_WIN = true, SECOND_WIN = false;

bool dfs(int now_ver){ // Возвращает true если выигрывает первы, и false, если второй

is_use[now_ver] = true;

bool child;

level++;

if(level == 2){

second_ver = now_ver;

}

if(!is_sort[now_ver]){

sort(airports[now_ver].begin(), airports[now_ver].end());

is_sort[now_ver] = true;

}

int count_ver=0; // переменная считает вершины в которые можно пойти из данной

for(int i=0 ; i<airports[now_ver].size() ; i++ ){ //

if( !is_use[ airports[now_ver][i] ] ){

// В зависимости от четноси мы должны искать тот ли иной овет

// от четности зависит то каккой игрок ходит на данный момент

child = dfs(airports[now_ver][i]);

// Если нечетное, то мы ищем правильных ход первого, иначе правильный ход второго

if(level%2 == 1? child == FIRST_WIN : child == SECOND_WIN){

if(level == 1){

if(child == FIRST_WIN){

cout << "First player wins flying to airport " << second_ver << endl;

}else{ // SECOND_WIn

cout << "First player loses" << endl;

}

return true;

}else{

level--;

return child;

}

} // если найден нужный нам ответ на этом уровне

count_ver++;

}

is_use[now_ver] = false;

if(level != 1)return ((level--)%2 == 1? SECOND_WIN : FIRST_WIN);

else{

if(child == FIRST_WIN){

cout << "First player wins flying to airport " << second_ver << endl;

}else{

cout << "First player loses" << endl;

}

int main(){

int n, k;

cin >> n >> k;

int u, v;

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

cin >> u >> v;

airports[u].push_back(v);

airports[v].push_back(u);

}

second_ver = k;

dfs(k);

}

Определяем массив аэропортов, булев массив пройденных аэропортов уровень вложенности функции dfs(), переменную запоминающую вторую вершину, булевы переменные для определения победителя, отсортированных вершин. В функции мы отмечаем первую вершину как пройденную переходим на следующий уровень. Сортируем все возможные варианты перехода, выбираем наименьший подходящий нам. Далее определяем переменную, которая считает вершины, в которые можно пойти из данной. В цикле проходим все вершины, пока проходим считаем количество детей.
Если оно равно нулю то это тупик.
И мы посмотрим кто бы выиграл если бы бандиты дошли до этого аэропорта.Если level нечетный, то мы ищем правильный ход первого, иначе второго террориста. Если уровень равен 1, то мы уже выходим. Выводим ответ. Иначе, если level не равен 1, то мы еще не дошли до конца и возвращаем выше, кто выигрывает в данном узле.
При этом каждый бандит ищет ветку где бы он победил.
Определяем количество детей. Если мы не в тупике, то но увеличивается на 1. Далее, если ходит второй террорист, то он выбирает ветку, в котором выиграет он. Если мы попали в тупик, выводим кто выиграл в зависимости от четности пройденного пути.
В main() считываем количество аэропортов и номер первого , записываем в вектора смежные аэропорты для каждого и запоминаем первую вершину. Запускаем dfs().

Related Images:

e-olymp 1776. Рельсы

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

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

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

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

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

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

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

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

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

Решение

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

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

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

using namespace std;

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

}

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

#include <iostream>

#include <vector>

#include <cstring>

#include <sstream>

using namespace std;

int main(){

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

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

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

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

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

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

while(s != "0"){

vector<int> stalemate;

stream_my.str("");

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

stream_my << s;

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

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

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

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

stalemate.pop_back();

stream_my >> number;

}

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

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

}

cout << endl;

}

Related Images:

e-olymp 4514. Сортировка вагонов — А

26/06/2015 by Сіренко Валерія Сергіївна

Задача

К тупику со стороны пути 1 (см. рисунок) подъехал поезд. Разрешается отцепить от поезда один или сразу несколько первых вагонов и завезти их в тупик (при желании, можно даже завезти в тупик сразу весь поезд). После этого часть из этих вагонов вывезти в сторону пути 2. После этого можно завезти в тупик еще несколько вагонов и снова часть оказавшихся вагонов вывезти в сторону пути 2. И так далее (так, что каждый вагон может лишь один раз заехать с пути 1 в тупик, а затем один раз выехать из тупика на путь 2). Заезжать вагонам в тупик с пути 2 или выезжать из тупика на путь 1 запрещается. Нельзя с пути 1 попасть на путь 2, не заезжая в тупик.

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

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

Вводится число N — количество вагонов в поезде (1 ≤ N ≤ 2000). Дальше идут номера вагонов в порядке от головы поезда, едущего по пути 1 в сторону тупика. Вагоны пронумерованы натуральными числами от 1 до N, каждое из которых встречается ровно один раз.

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

Если сделать так, чтобы вагоны шли в порядке от 1 до N, считая от головы поезда, когда поезд поедет по пути 2 из тупика, можно, выведите действия, которые нужно проделать с поездом. Каждое действие описывается двумя числами: типом и количеством вагонов:

если нужно завезти с пути 1 в тупик K вагонов, должно быть выведено сначала число 1, а затем — число K (K ≥ 1),
если нужно вывезти из тупика на путь 2 K вагонов, должно быть выведено сначала число 2, а затем — число K (K ≥ 1).

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

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

Задача на e-olimp

#include <cstdlib>
#include <iostream>
#include <sstream>
#include <vector>
 using namespace std;
 
int main(){
	int n;
	cin >> n;
 
	int a[n];
	vector<int> stalemate;
 
	int last_num = 1;									
	int len;											
	int last_n = 0;					
 
	stringstream stre;							
	for( int i=0 ; i<n ; i++ ){
		cin >> a[i];
		stalemate.push_back(a[i]);						
		if(a[i] == last_num){
			stre << 1 << ' ' << (i-last_n)+1 << endl;
 
			len = 0;
			while(stalemate.back() == last_num && last_num != n+1)
			{					
				stalemate.pop_back();								
				last_num++;											
				len++;												
			}
			last_n = i+1;						
			stre << 2 << ' ' << len << endl;			
		}
	}
	if(last_num != n+1)
	{							
		cout << 0 << endl;
	}
	else
	{
		cout << stre.str() << endl;
	}
}

#include <cstdlib>

#include <iostream>

#include <sstream>

#include <vector>

using namespace std;

int main(){

int n;

cin >> n;

int a[n];

vector<int> stalemate;

int last_num = 1;

int len;

int last_n = 0;

stringstream stre;

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

cin >> a[i];

stalemate.push_back(a[i]);

if(a[i] == last_num){

stre << 1 << ' ' << (i-last_n)+1 << endl;

len = 0;

while(stalemate.back() == last_num && last_num != n+1)

{

stalemate.pop_back();

last_num++;

len++;

}

last_n = i+1;

stre << 2 << ' ' << len << endl;

}

if(last_num != n+1)

{

cout << 0 << endl;

}

else

{

cout << stre.str() << endl;

}

Тесты

input	output
33 2 1	1 32 3
44 1 3 2	1 22 11 22 3
32 3 1	0

Решение

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

int last_num = 1;

15	int last_num = 1;

затем вводим переменную, которая запоминает какой вагон заехал в тупик последним

int last_n = 0;

16	int last_n = 0;

Мы это делаем, для вычисления количества вагонов которое заехало в тупик и которое выехало из тупика. Потом мы поочередно считываем в цикле [latex]for[/latex] все номера вагонов и кидаем их всех в тупик. Но если во время этой операции мы нашли вагон с номером [latex]last\_num[/latex], то сразу пишем (в строковой поток, так как есть вероятность того, что так завести вагоны нельзя) сколько вагонов мы завели в тупик. Далее мы видим, что в тупике есть вагоны идущие по порядку, мы выводим вагоны из тупика и считаем их количество. После мы выводим это количество в строковой поток( с цифрой 2 вначале) и запоминаем сколько вагонов было завезено в тупик. Далее если мы вывели из тупика все вагоны, то выводим строковой поток, иначе выводим 0.

Related Images:

e-olymp 1266. CD

18/06/2015 by Байков Дмитро

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

Предположения:

количество треков на CD не превышает [latex]100[/latex]
ни один трек не длится более [latex]N[/latex] минут
длина каждого трека выражена целым числом
[latex]N[/latex] также целое [latex](0\leq[/latex][latex]N\leq[/latex][latex]200)[/latex]

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

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

Входные данные содержат несколько строк. В каждой строке сначала задано число [latex]N[/latex], далее количество треков и длительность звучания каждого трека. Все числа разделены пробелами. Например, в первой строке входных данных первым задано [latex]N=5[/latex], далее количество треков [latex]s=3[/latex], первый трек имеет длительность [latex]1[/latex] минуту, второй — [latex]3[/latex] минуты, и последний — [latex]4[/latex] минуты.

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

Выведите строку «sum:» и далее продолжительность записи.

Входные данные	Выходные данные
5 3 1 3 4 10 4 9 8 4 2 20 4 10 5 7 4 90 8 10 23 1 2 3 4 5 7 45 8 4 10 44 43 12 9 8 2	sum:5 sum:10 sum:19 sum:55 sum:45

Код:

#include <cstdio>
using namespace std;
 
short d[210][110];
short arr[110];
 
short max (short a, short b) {
	return a<b ? b : a;	
}
int main() {
	int n;
	while (scanf("%d", &n)>0){
		int k;
		scanf("%d", &k);
		for (int i=1; i<=k; i++) scanf("%d", &arr[i]);
		for (int i=1; i<=k; i++)
			for (int j=0; j<=n; j++)
				if (arr[i]<=j) d[j][i]=max(d[j][i-1], arr[i]+d[j-arr[i]][i-1]);
				else d[j][i]=d[j][i-1];
		printf("sum:%d\n", d[n][k]);
	}
	return 0;
}

#include <cstdio>

using namespace std;

short d[210][110];

short arr[110];

short max (short a, short b) {

return a<b ? b : a;

}

int main() {

int n;

while (scanf("%d", &n)>0){

int k;

scanf("%d", &k);

for (int i=1; i<=k; i++) scanf("%d", &arr[i]);

for (int i=1; i<=k; i++)

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

if (arr[i]<=j) d[j][i]=max(d[j][i-1], arr[i]+d[j-arr[i]][i-1]);

else d[j][i]=d[j][i-1];

printf("sum:%d\n", d[n][k]);

}

return 0;

}

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

Ссылка на ideone

import java.util.*;
import java.lang.*;
import java.io.*;
class CD
{
	public static void main (String[] args) throws java.lang.Exception
	{
		int[][] d = new int[210][110];
		short[] arr = new short[110];
		Scanner in = new Scanner(System.in); 
		while (in.hasNext()){
			short n = in.nextShort();	
			short k = in.nextShort();
			for (int i=1; i<=k; i++) arr[i] = in.nextShort();
			for (int i=1; i<=k; i++)
				for (int j=0; j<=n; j++)
					if (arr[i]<=j){
						if (d[j][i-1]< arr[i]+d[j-arr[i]][i-1]) d[j][i]=arr[i]+d[j-arr[i]][i-1];
						else d[j][i]=d[j][i-1];
					}
					else d[j][i]=d[j][i-1];
					System.out.printf("sum: " + d[n][k]);
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class CD

{

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

{

int[][] d = new int[210][110];

short[] arr = new short[110];

Scanner in = new Scanner(System.in);

while (in.hasNext()){

short n = in.nextShort();

short k = in.nextShort();

for (int i=1; i<=k; i++) arr[i] = in.nextShort();

for (int i=1; i<=k; i++)

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

if (arr[i]<=j){

if (d[j][i-1]< arr[i]+d[j-arr[i]][i-1]) d[j][i]=arr[i]+d[j-arr[i]][i-1];

else d[j][i]=d[j][i-1];

}

else d[j][i]=d[j][i-1];

System.out.printf("sum: " + d[n][k]);

}

Ссылка на ideone

Алгоритм решения построен на методе динамического программирования.

Возможны два варианта:

Либо трек не попал на диск, следовательно длинна уже записанных треков на диск [latex](d[j][i])[/latex] равна предыдущему числу ранее записанных треков [latex](d[j][i-1])[/latex].
Либо трек попал на диск, а значит [latex]d[j][i][/latex] равно максимуму из суммы ранее записанных треков [latex](d[j][i-1])[/latex] и суммы заданной длинны [latex]arr[i][/latex] c [latex]d[j-arr[i]][i-1]][/latex], где [latex]d[j-arr[i]][i-1]][/latex] равен сумме уже записанных треков при предыдущем элементе массива [latex]arr[i-1][/latex]

Related Images:

e-olymp 1872. Снеговики

18/06/2015 by Карагяур Мілан Сергійович

Задача:

Зима. 2012 год. На фоне грядущего Апокалипсиса и конца света незамеченной прошла новость об очередном прорыве в областях клонирования и снеговиков: клонирования снеговиков. Вы конечно знаете, но мы вам напомним, что снеговик состоит из нуля или более вертикально поставленных друг на друга шаров, а клонирование — это процесс создания идентичной копии (клона).

В местечке Местячково учитель Андрей Сергеевич Учитель купил через интернет-магазин «Интернет-магазин аппаратов клонирования» аппарат для клонирования снеговиков. Теперь дети могут играть и даже играют во дворе в следующую игру. Время от времени один из них выбирает понравившегося снеговика, клонирует его и:

либо добавляет ему сверху один шар;
либо удаляет из него верхний шар (если снеговик не пустой).

Учитель Андрей Сергеевич Учитель записал последовательность действий и теперь хочет узнать суммарную массу всех построенных снеговиков.

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

Первая строка содержит количество действий n (1 ≤ n ≤ 200000). В строке номер i+1 содержится описание действия:

t m — клонировать снеговика номер t (0 ≤ t < i) и добавить сверху шар массой m (0 < m ≤ 1000);
t 0 — клонировать снеговика номер t (0 ≤ t < i) и удалить верхний шар. Гарантируется, что снеговик не пустой.

В результате действия i, описанного в строке i+1 создается снеговик номер i. Изначально имеется пустой снеговик с номером ноль.

Все числа во входном файле целые.

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

Выведите суммарную массу построенных снеговиков.

Решение: Считываем n — количество действий. Задаем двухмерный массив размером [n+1][2]. Указываем значение первого элемента равное 0 и нулевого элемента равного -1, чтобы он ни на что не ссылался в начале. В цикле считываем номер снеговика, которого нужно клонировать и массу шара, которую нужно добавить. Если масса шара равна 0, то мы клонируем снеговика и убираем последний его шар, ссылаясь на снеговика в котором этого шара еще не было. Если же масса шара не равно 0, то мы клонируем снеговика и добавляем ему шар массой m. Во второй ячейке указываем предка с которого строится новый снеговик. Выводим общую массу снеговиков.

Задача на e-olymp.

Код:

#include <cstdlib>
#include <iostream>

using namespace std;
int main()
{
	
	int n;
	cin >> n;
	int a[n+1][2];
	
	int  count=0;
	a[count][1] = 0;
	a[count][0] = -1;
	count++;
	
	int t, m;
	long long sumr=0;
	
	for( int i=0 ; i<n ; i++ ){
		cin >> t >> m;
		if(m==0){
			a[count][1] = a[ a[t][0] ][1];
			a[count][0] = a[ a[t][0] ][0];
		}else{
			a[count][1] = a[t][1]+m;
			a[count][0] = t;
		}
		sumr+=a[count][1];
		count++;
	}
	cout << sumr << endl;
}

#include <cstdlib>

#include <iostream>

using namespace std;

int main()

{

int n;

cin >> n;

int a[n+1][2];

int count=0;

a[count][1] = 0;

a[count][0] = -1;

count++;

int t, m;

long long sumr=0;

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

cin >> t >> m;

if(m==0){

a[count][1] = a[ a[t][0] ][1];

a[count][0] = a[ a[t][0] ][0];

}else{

a[count][1] = a[t][1]+m;

a[count][0] = t;

}

sumr+=a[count][1];

count++;

}

cout << sumr << endl;

}

Тесты:

Input	Output
8 0 1 1 5 2 4 3 2 4 3 5 0 6 6 1 0	74
4 0 3 1 2 2 1 1 1	18

Related Images:

e-olymp 2479. Баланс скобок

13/06/2015 by Царев Николай Александрович

Условие

(Ссылка на задачу в e-olymp)

Имеется строка, содержащая скобки () и []. Скобочное выражение считается правильным, если:

оно является пустым
если A и B правильны, то AB правильно
если A правильно, то (A) и [A] правильны

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

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

Первая строка содержит количество тестов n. Каждая из следующих n строк содержит выражение, состоящее из скобок () и [].

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

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

Тесты

3
([])
(([()])))
([()[]()])()

Yes
No
Yes

(тесты взяты с e-olymp.com)

Результаты задачи № 2479

#include <iostream>
#include <stack>
#include <string>

using namespace std;

int main()
{
    int n;
    cin >> n;
    char l;
    cin.get(l); //считывание конца строки после числа
    for(int z=0;z<n;z++){
        bool q=1; //переменная "фиксирующая" ошибку
        char hab;
        string str;
        getline(cin,str); //используем, чтобы читать до конца строки
        int j=str.size(); //размер строки ( кол-во обрабатываемых символов)
        stack<char> res; //стэк скобок
        for(int i=0;i<j;i++){
            if((str[i]=='(')||(str[i]=='[')) //если открывающая скобка - то кладем в стэк
                res.push(str[i]);
            else{ //если закрывающая скобка
                    if(!res.empty()){ //если стэк не пуст
                        hab=res.top(); //вытаскиваем последний элемент
                        if(str[i]==')'){ //сверяем на типы скобок
                            if(hab=='('){
                                res.pop(); //удаляем пару
                               }
                            else{
                                q=0;
                                cout << "No" << endl;
                                break;

                            }
                        }
                        else{
                            if(hab=='['){ //второй тип скобок (те же действия)
                                res.pop();
                               }
                            else{
                                q=0;
                                cout << "No" << endl;
                                break;
                            }
                        }
                    }
                    else{ //если стэк пуст  - то ошибочка вышла!
                        cout << "No" << endl;
                        q=0;
                        break;
                    }
            }
        }
        if(q){
        if(res.empty()) //собственно ответ
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
        }

    }
    return 0;
}

#include <iostream>

#include <stack>

#include <string>

using namespace std;

int main()

{

int n;

cin >> n;

char l;

cin.get(l); //считывание конца строки после числа

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

bool q=1; //переменная "фиксирующая" ошибку

char hab;

string str;

getline(cin,str); //используем, чтобы читать до конца строки

int j=str.size(); //размер строки ( кол-во обрабатываемых символов)

stack<char> res; //стэк скобок

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

if((str[i]=='(')||(str[i]=='[')) //если открывающая скобка - то кладем в стэк

res.push(str[i]);

else{ //если закрывающая скобка

if(!res.empty()){ //если стэк не пуст

hab=res.top(); //вытаскиваем последний элемент

if(str[i]==')'){ //сверяем на типы скобок

if(hab=='('){

res.pop(); //удаляем пару

}

else{

q=0;

cout << "No" << endl;

break;

}

else{

if(hab=='['){ //второй тип скобок (те же действия)

res.pop();

}

else{

q=0;

cout << "No" << endl;

break;

}

else{ //если стэк пуст - то ошибочка вышла!

cout << "No" << endl;

q=0;

break;

}

if(q){

if(res.empty()) //собственно ответ

cout << "Yes" << endl;

else

cout << "No" << endl;

}

return 0;

}

Алгоритм

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

Маленький костыль для этой задачи — это лишнее считывание символа в самом начале. Делается это для того, чтобы дальше, мы спокойно могли использовать функцию getline, которая читает строку до символа конца строки. Эти дополнительным вводом, мы как бы забираем на себя символ конца строки стоящий после числа, определяющее кол-во строк.

Ссылка на ideone.com

Related Images:

A1048

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

Задача. Одним из наиболее часто встречающихся видов списка является стек-список, в котором все включения и исключения элементов делаются только на одном его конце — вершине стека. Механизм функционирования стека хорошо отражен в другом его названии — список типа «LIFO» (last in first out) -«последним вошел — первым вышел»).

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

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

Тесты:

Ввод	Вывод	Комментарий
push 5push 7 pop push 11 pop exit	okok 7 ok 11 bye	Пройден
push 1pop pop push 15 pop exit	ok1 error ok 15 bye	Пройден
poppush 7 push 9 push 9 push 1 pop pop pop pop exit	errorok ok ok ok 1 9 9 7 bye	Пройден

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

#include <iostream>

using namespace std;

struct stack {

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

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

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

{

storage[size]=n;

size++;

}

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

{

int b=storage[size-1];

size--;

return b;

}

};

int main ()

{

stack st;

string s;

while (55)

{

cin >> s;

if (s=="push")

{

int n;

cin >> n;

st.push(n);

cout << "ok\n";

}

if (s=="pop")

{

if (st.size==0)

{

cout << "error\n";

}

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

}

if (s=="exit")

{

cout << "bye\n";

break;

}

return 0;

}

Решение:

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

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

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

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

Related Images:

e-olymp 432. Подземелье

20/05/2015 by Царев Николай Александрович

Подземелье

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

Можно ли выбраться из лабиринта? Если да, то какое времени это займет?

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

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

Состоит из ряда подземелий. Каждое описание подземелья начинается со строки, содержащей три целых числа: количество уровней в подземелье l, а также r и c — количество строк и столбцов, описывающих план каждого уровня (все числа не больше 30).

Далее следует l блоков по r строк, каждая по c символов. Каждое число описывает одну ячейку подземелья. Запрещенные для перемещения кубы подземелья обозначены символом ‘#‘, а пустые клетки обозначены ‘.‘. Ваша стартовая позиция обозначается буквой ‘S‘, а выход буквой ‘Е‘. Все описания подземелий отделены пустой строкой. Описание входных данных заканчивается тремя нулями.

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

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

Escaped in X minute(s).

где X — наименьшее время, необходимое для достижения выхода.

Если достичь выход невозможно, вывести строку

Trapped!

ТЕСТЫ:

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

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

3 4 5
S....
.###.
.##..
###.#

#####
#####
##.##
##...

#####
#####
#.###
####E

1 3 3
S##
#E#
###

0 0 0

3 4 5

S....

.###.

.##..

###.#

#####

##.##

##...

#####

#.###

####E

1 3 3

S##

#E#

###

0 0 0

Escaped in 11 minute(s).
Trapped!

1 2	Escaped in 11 minute(s). Trapped!

Тесты взяты с сайта e-olimp. Подтверждение прохождения задачи на e-olimp.

Задача на E-Olimp!

#include <iostream>

using namespace std;

struct node{
   int x,y,z;
   node *prev;
   node (int x0, int y0, int z0,  node* las) { x = x0; y=y0; z=z0;  prev = las;}
   node();
};  //Структура "Узел" используемая в структуре "Очередь"

struct quene{ //Структура "Очередь"
   int k=0;
   node *last=NULL;
   node *first=NULL;
   node *tmp=NULL;

   void push( int n, int m, int g){
       node* x = new node(n,m,g, NULL);
       k++;
       if(k!=1)
           last->prev = x;
       last = x;
       if(k==1)
           first=x;
   }
   
   void pop(){
       tmp=first;
       first=first->prev;
       delete tmp;
       k--;
       }

};



int main()
{
   int l,r,c;
   cin >> l >> r >> c;
   while((l!=0)&&(r!=0)&&(c!=0)){ //Внешний цикл
   int mas[l+2][r+2][c+2];
   bool masb[l+2][r+2][c+2];
   char u;
   int st1,st2,st3;
   int fs1,fs2,fs3;
   for(int i1=0; i1<l+2; i1++){ //Начало считывания и обработки данных
       for(int i2=0; i2<r+2; i2++){
           for(int i3=0; i3<c+2; i3++){
               masb[i1][i2][i3]=0;
               if((i1==0)||(i2==0)||(i3==0)||(i1==l+1)||(i2==r+1)||(i3==c+1))
                   mas[i1][i2][i3]=-1;
               else{
               cin>>u;
               if(u=='#'){
               mas[i1][i2][i3]=-1;}
               if(u=='.'){
                   mas[i1][i2][i3]=0;
               }
               if(u=='S'){
                   mas[i1][i2][i3]=0;
                   st1=i1;st2=i2;st3=i3;
               }
               if(u=='E'){
                   mas[i1][i2][i3]=0;
                   fs1=i1;fs2=i2;fs3=i3;
               }
               }
           }
           }
       } // Конец обработки

   quene ts; //Создание очереди
   ts.push(st1,st2,st3);// Кладем в нее "стартовую" вершину
   while(ts.k!=0){  //Запускаем поиск
       int x1=ts.first->x;
       int y1=ts.first->y;
       int z1=ts.first->z;  //Для удобства сохраняем координаты 
       //обрабатываемой вершины в специальных переменных

       if(mas[x1+1][y1][z1]>=0){ // Вершина справа
           if(mas[x1+1][y1][z1]!=0)
               mas[x1+1][y1][z1]=min(mas[x1+1][y1][z1],mas[x1][y1][z1]+1);
           else
               mas[x1+1][y1][z1]=mas[x1][y1][z1]+1;
           if(masb[x1+1][y1][z1]==0){
               masb[x1+1][y1][z1]=1;
               ts.push(x1+1,y1,z1);
           }
       }

       if(mas[x1-1][y1][z1]>=0){ //Вершина слева
           if(mas[x1-1][y1][z1]!=0)
               mas[x1-1][y1][z1]=min(mas[x1-1][y1][z1],mas[x1][y1][z1]+1);
           else
               mas[x1-1][y1][z1]=mas[x1][y1][z1]+1;
           if(masb[x1-1][y1][z1]==0){
               masb[x1-1][y1][z1]=1;
               ts.push(x1-1,y1,z1);
           }
       }

       if(mas[x1][y1+1][z1]>=0){ //Вершина вверху
           if(mas[x1][y1+1][z1]!=0)
               mas[x1][y1+1][z1]=min(mas[x1][y1+1][z1],mas[x1][y1][z1]+1);
           else
               mas[x1][y1+1][z1]=mas[x1][y1][z1]+1;
           if(masb[x1][y1+1][z1]==0){
               masb[x1][y1+1][z1]=1;
               ts.push(x1,y1+1,z1);
           }
       }

       if(mas[x1][y1-1][z1]>=0){ //Вершина внизу
           if(mas[x1][y1-1][z1]!=0)
               mas[x1][y1-1][z1]=min(mas[x1][y1-1][z1],mas[x1][y1][z1]+1);
           else
               mas[x1][y1-1][z1]=mas[x1][y1][z1]+1;
           if(masb[x1][y1-1][z1]==0){
               masb[x1][y1-1][z1]=1;
               ts.push(x1,y1-1,z1);
           }
       }

       if(mas[x1][y1][z1+1]>=0){ //Вершина на уровень выше
           if(mas[x1][y1][z1+1]!=0)
               mas[x1][y1][z1+1]=min(mas[x1][y1][z1+1],mas[x1][y1][z1]+1);
           else
               mas[x1][y1][z1+1]=mas[x1][y1][z1]+1;
           if(masb[x1][y1][z1+1]==0){
               masb[x1][y1][z1+1]=1;
               ts.push(x1,y1,z1+1);
           }
       }

       if(mas[x1][y1][z1-1]>=0){ //Вершина на уровень ниже
           if(mas[x1][y1][z1-1]!=0)
               mas[x1][y1][z1-1]=min(mas[x1][y1][z1-1],mas[x1][y1][z1]+1);
           else
               mas[x1][y1][z1-1]=mas[x1][y1][z1]+1;
           if(masb[x1][y1][z1-1]==0){
               masb[x1][y1][z1-1]=1;
               ts.push(x1,y1,z1-1);
           }
       }
       ts.pop(); //Удаление обработанной вершины из очереди

       }
       if(mas[fs1][fs2][fs3]!=0) // Последняя проверка результата
       cout <<"Escaped in " << mas[fs1][fs2][fs3] << " minute(s)."<< endl;
       else
       cout << "Trapped!" << endl;
       cin >> l >> r >> c; // Считывание чисел для внешнего цикла
       }
   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

#include <iostream>

using namespace std;

struct node{

int x,y,z;

node *prev;

node (int x0, int y0, int z0, node* las) { x = x0; y=y0; z=z0; prev = las;}

node();

}; //Структура "Узел" используемая в структуре "Очередь"

struct quene{ //Структура "Очередь"

int k=0;

node *last=NULL;

node *first=NULL;

node *tmp=NULL;

void push( int n, int m, int g){

node* x = new node(n,m,g, NULL);

k++;

if(k!=1)

last->prev = x;

last = x;

if(k==1)

first=x;

}

void pop(){

tmp=first;

first=first->prev;

delete tmp;

k--;

}

};

int main()

{

int l,r,c;

cin >> l >> r >> c;

while((l!=0)&&(r!=0)&&(c!=0)){ //Внешний цикл

int mas[l+2][r+2][c+2];

bool masb[l+2][r+2][c+2];

char u;

int st1,st2,st3;

int fs1,fs2,fs3;

for(int i1=0; i1<l+2; i1++){ //Начало считывания и обработки данных

for(int i2=0; i2<r+2; i2++){

for(int i3=0; i3<c+2; i3++){

masb[i1][i2][i3]=0;

if((i1==0)||(i2==0)||(i3==0)||(i1==l+1)||(i2==r+1)||(i3==c+1))

mas[i1][i2][i3]=-1;

else{

cin>>u;

if(u=='#'){

mas[i1][i2][i3]=-1;}

if(u=='.'){

mas[i1][i2][i3]=0;

}

if(u=='S'){

mas[i1][i2][i3]=0;

st1=i1;st2=i2;st3=i3;

}

if(u=='E'){

mas[i1][i2][i3]=0;

fs1=i1;fs2=i2;fs3=i3;

}

} // Конец обработки

quene ts; //Создание очереди

ts.push(st1,st2,st3);// Кладем в нее "стартовую" вершину

while(ts.k!=0){ //Запускаем поиск

int x1=ts.first->x;

int y1=ts.first->y;

int z1=ts.first->z; //Для удобства сохраняем координаты

//обрабатываемой вершины в специальных переменных

if(mas[x1+1][y1][z1]>=0){ // Вершина справа

if(mas[x1+1][y1][z1]!=0)

mas[x1+1][y1][z1]=min(mas[x1+1][y1][z1],mas[x1][y1][z1]+1);

else

mas[x1+1][y1][z1]=mas[x1][y1][z1]+1;

if(masb[x1+1][y1][z1]==0){

masb[x1+1][y1][z1]=1;

ts.push(x1+1,y1,z1);

}

if(mas[x1-1][y1][z1]>=0){ //Вершина слева

if(mas[x1-1][y1][z1]!=0)

mas[x1-1][y1][z1]=min(mas[x1-1][y1][z1],mas[x1][y1][z1]+1);

else

mas[x1-1][y1][z1]=mas[x1][y1][z1]+1;

if(masb[x1-1][y1][z1]==0){

masb[x1-1][y1][z1]=1;

ts.push(x1-1,y1,z1);

}

if(mas[x1][y1+1][z1]>=0){ //Вершина вверху

if(mas[x1][y1+1][z1]!=0)

mas[x1][y1+1][z1]=min(mas[x1][y1+1][z1],mas[x1][y1][z1]+1);

else

mas[x1][y1+1][z1]=mas[x1][y1][z1]+1;

if(masb[x1][y1+1][z1]==0){

masb[x1][y1+1][z1]=1;

ts.push(x1,y1+1,z1);

}

if(mas[x1][y1-1][z1]>=0){ //Вершина внизу

if(mas[x1][y1-1][z1]!=0)

mas[x1][y1-1][z1]=min(mas[x1][y1-1][z1],mas[x1][y1][z1]+1);

else

mas[x1][y1-1][z1]=mas[x1][y1][z1]+1;

if(masb[x1][y1-1][z1]==0){

masb[x1][y1-1][z1]=1;

ts.push(x1,y1-1,z1);

}

if(mas[x1][y1][z1+1]>=0){ //Вершина на уровень выше

if(mas[x1][y1][z1+1]!=0)

mas[x1][y1][z1+1]=min(mas[x1][y1][z1+1],mas[x1][y1][z1]+1);

else

mas[x1][y1][z1+1]=mas[x1][y1][z1]+1;

if(masb[x1][y1][z1+1]==0){

masb[x1][y1][z1+1]=1;

ts.push(x1,y1,z1+1);

}

if(mas[x1][y1][z1-1]>=0){ //Вершина на уровень ниже

if(mas[x1][y1][z1-1]!=0)

mas[x1][y1][z1-1]=min(mas[x1][y1][z1-1],mas[x1][y1][z1]+1);

else

mas[x1][y1][z1-1]=mas[x1][y1][z1]+1;

if(masb[x1][y1][z1-1]==0){

masb[x1][y1][z1-1]=1;

ts.push(x1,y1,z1-1);

}

ts.pop(); //Удаление обработанной вершины из очереди

}

if(mas[fs1][fs2][fs3]!=0) // Последняя проверка результата

cout <<"Escaped in " << mas[fs1][fs2][fs3] << " minute(s)."<< endl;

else

cout << "Trapped!" << endl;

cin >> l >> r >> c; // Считывание чисел для внешнего цикла

}

return 0;

}

ССЫЛКА НА IDEONE.COM

(Программа также проверенна в Code::Blocks)

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

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

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

2) Реализация самого поиска. Создаем очередь и помещаем в нее стартовую вершину. Затем запускаем цикл до тех пор, пока очередь не пуста.

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

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

4) Извлекаем вершину из очереди.

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

Примечание!

1)Для удобной реализации поиска, оба массива создаем на два уровня больше, как бы делая ему рамку ( маску).

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

Related Images:

e-olymp 1061. Покраска лабиринта

19/05/2015 by Сорокина Полина

Задача e-olimp 1061.

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

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

В первой строке находится число N, затем идут N строк по N символов: точка обозначает пустой сегмент, решетка — сегмент со стеной.

3 ≤ N ≤ 33, размер сегмента 3×3, высота стен 3 метра.

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

Вывести одно число — площадь видимой части внутренних стен лабиринта в квадратных метрах.

Пример

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

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

. . . . .

. . . # #

. . # . .

. . # # #

. . . . .

198

C++:

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

int check(int row, int col, char** lab, int** visited, queue<int>& plan){//находим количество стен рядом с каждой клеткой
	int empty = 0;//пустые клетки
	if(!visited[row][col]){
			if(lab[row+1][col]=='.'){//проверяем нижнюю клетку
				empty++;
				if(!visited[row+1][col]){
					plan.push(row+1);
					plan.push(col);
				}
			}
			if(lab[row-1][col]=='.'){//проверяем верхнюю клетку
				empty++;
				if(!visited[row-1][col]){
					plan.push(row-1);
					plan.push(col);
				}
			}
			if(lab[row][col+1]=='.'){//проверяем правую клетку
				empty++;
				if(!visited[row][col+1]){
					plan.push(row);
					plan.push(col+1);
				}
			}
			if(lab[row][col-1]=='.'){//проверяем левую клетку
				empty++;
				if(!visited[row][col-1]){
					plan.push(row);
					plan.push(col-1);
				}
			}
			visited[row][col]=1;//отмечаем, что клетка пройдена
			return 4-empty;//количество стен рядом с клеткой
	}
	return 0;
}

int main() {
	int N;
	cin >> N;
	char** lab = new char* [N+2];
	int** visited = new int * [N+2];
	for(int i=0; i<N+2; i++){
		lab[i] = new char [N+2];
		visited[i] = new int [N+2];
		for(int j=0; j<N+2; j++){
			visited[i][j] = 0;//массив для проверки посещённости клеток
			if(i==0||i==N+1||j==0||j==N+1){
				lab[i][j]='*';//вокруг данного лабиринта делаем стену
			} else {
				cin >> lab[i][j];//данный лабиринт
			}
		}
	}
	queue <int> plan;
	plan.push(1);//начинаем считать с левой верхней клетки
	plan.push(1);
	int walls=0;
	while(!plan.empty()){
		int row=plan.front();
		plan.pop();
		int col=plan.front();
		plan.pop();
		walls+=check(row, col, lab, visited, plan);
	}
	if(!visited[N][N]){//если не попали в правую нижнюю клетку
		plan.push(N);//считаем начиная с неё
		plan.push(N);
		while(!plan.empty()){
			int row=plan.front();
			plan.pop();
			int col=plan.front();
			plan.pop();
			walls+=check(row, col, lab, visited, plan);
		}
	}
	walls-=4;//стены у левого верхнего и правого нижнего угла отсутствуют
	int meters=walls*9;
	cout << meters << endl;
	return 0;
}

#include <iostream>

#include <queue>

using namespace std;

int check(int row, int col, char** lab, int** visited, queue<int>& plan){//находим количество стен рядом с каждой клеткой

int empty = 0;//пустые клетки

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

if(lab[row+1][col]=='.'){//проверяем нижнюю клетку

empty++;

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

plan.push(row+1);

plan.push(col);

}

if(lab[row-1][col]=='.'){//проверяем верхнюю клетку

empty++;

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

plan.push(row-1);

plan.push(col);

}

if(lab[row][col+1]=='.'){//проверяем правую клетку

empty++;

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

plan.push(row);

plan.push(col+1);

}

if(lab[row][col-1]=='.'){//проверяем левую клетку

empty++;

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

plan.push(row);

plan.push(col-1);

}

visited[row][col]=1;//отмечаем, что клетка пройдена

return 4-empty;//количество стен рядом с клеткой

}

return 0;

}

int main() {

int N;

cin >> N;

char** lab = new char* [N+2];

int** visited = new int * [N+2];

for(int i=0; i<N+2; i++){

lab[i] = new char [N+2];

visited[i] = new int [N+2];

for(int j=0; j<N+2; j++){

visited[i][j] = 0;//массив для проверки посещённости клеток

if(i==0||i==N+1||j==0||j==N+1){

lab[i][j]='*';//вокруг данного лабиринта делаем стену

} else {

cin >> lab[i][j];//данный лабиринт

}

queue <int> plan;

plan.push(1);//начинаем считать с левой верхней клетки

plan.push(1);

int walls=0;

while(!plan.empty()){

int row=plan.front();

plan.pop();

int col=plan.front();

plan.pop();

walls+=check(row, col, lab, visited, plan);

}

if(!visited[N][N]){//если не попали в правую нижнюю клетку

plan.push(N);//считаем начиная с неё

plan.push(N);

while(!plan.empty()){

int row=plan.front();

plan.pop();

int col=plan.front();

plan.pop();

walls+=check(row, col, lab, visited, plan);

}

walls-=4;//стены у левого верхнего и правого нижнего угла отсутствуют

int meters=walls*9;

cout << meters << endl;

return 0;

}

Java:

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

class Ideone
{
	public static int check(int row, int col, char [][] lab, int [][] visited, ArrayDeque <Integer> plan){//находим количество стен рядом с каждой клеткой
		int empty = 0;//пустые клетки
		if(visited[row][col]!=1){
				if(lab[row+1][col]=='.'){//проверяем нижнюю клетку
					empty++;
					if(visited[row+1][col]!=1){
						plan.offer(row+1);
						plan.offer(col);
					}
				}
				if(lab[row-1][col]=='.'){//проверяем верхнюю клетку
					empty++;
					if(visited[row-1][col]!=1){
						plan.offer(row-1);
						plan.offer(col);
					}
				}
				if(lab[row][col+1]=='.'){//проверяем правую клетку
					empty++;
					if(visited[row][col+1]!=1){
						plan.offer(row);
						plan.offer(col+1);
					}
				}
				if(lab[row][col-1]=='.'){//проверяем левую клетку
					empty++;
					if(visited[row][col-1]!=1){
						plan.offer(row);
						plan.offer(col-1);
					}
				}
				visited[row][col]=1;//отмечаем, что клетка пройдена
				return 4-empty;//количество стен рядом с клеткой
		}
		return 0;
	}
	
	
	public static void main (String[] args)
	{
		Scanner in = new Scanner(System.in);
		
		int N = in.nextInt();
		char [][] lab = new char [N+2][];
		int [][] visited = new int [N+2][];
		for(int i=0; i<N+2; i++){
			lab[i] = new char [N+2];
			visited[i] = new int [N+2];
			for(int j=0; j<N+2; j++){
				visited[i][j] = 0;//массив для проверки посещённости клеток
				if(i==0||i==N+1||j==0||j==N+1){
					lab[i][j]='*';//вокруг данного лабиринта делаем стену
				}
			}
		}
		String line;
		for(int i=1; i<N+1; i++){
			line = in.next();
			for(int j=1; j<N+1; j++){
				lab[i][j]=line.charAt(j-1);//заполняем лабиринт
			}
		}
		
		ArrayDeque <Integer> plan = new ArrayDeque<Integer>();
		plan.offer(1);//начинаем считать с левой верхней клетки
		plan.offer(1);
		int walls=0;
		while(!plan.isEmpty()){
			int row=plan.poll();
			int col=plan.poll();
			walls+=check(row, col, lab, visited, plan);
		}
		if(visited[N][N]!=1){//если не попали в правую нижнюю клетку
			plan.offer(N);//считаем начиная с неё
			plan.offer(N);
			while(!plan.isEmpty()){
				int row=plan.poll();
				int col=plan.poll();
				walls+=check(row, col, lab, visited, plan);
			}
		}
		walls-=4;//стены у левого верхнего и правого нижнего угла отсутствуют
		int meters = walls * 9;
		System.out.println(meters);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

public static int check(int row, int col, char [][] lab, int [][] visited, ArrayDeque <Integer> plan){//находим количество стен рядом с каждой клеткой

int empty = 0;//пустые клетки

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

if(lab[row+1][col]=='.'){//проверяем нижнюю клетку

empty++;

if(visited[row+1][col]!=1){

plan.offer(row+1);

plan.offer(col);

}

if(lab[row-1][col]=='.'){//проверяем верхнюю клетку

empty++;

if(visited[row-1][col]!=1){

plan.offer(row-1);

plan.offer(col);

}

if(lab[row][col+1]=='.'){//проверяем правую клетку

empty++;

if(visited[row][col+1]!=1){

plan.offer(row);

plan.offer(col+1);

}

if(lab[row][col-1]=='.'){//проверяем левую клетку

empty++;

if(visited[row][col-1]!=1){

plan.offer(row);

plan.offer(col-1);

}

visited[row][col]=1;//отмечаем, что клетка пройдена

return 4-empty;//количество стен рядом с клеткой

}

return 0;

}

public static void main (String[] args)

{

Scanner in = new Scanner(System.in);

int N = in.nextInt();

char [][] lab = new char [N+2][];

int [][] visited = new int [N+2][];

for(int i=0; i<N+2; i++){

lab[i] = new char [N+2];

visited[i] = new int [N+2];

for(int j=0; j<N+2; j++){

visited[i][j] = 0;//массив для проверки посещённости клеток

if(i==0||i==N+1||j==0||j==N+1){

lab[i][j]='*';//вокруг данного лабиринта делаем стену

}

String line;

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

line = in.next();

for(int j=1; j<N+1; j++){

lab[i][j]=line.charAt(j-1);//заполняем лабиринт

}

ArrayDeque <Integer> plan = new ArrayDeque<Integer>();

plan.offer(1);//начинаем считать с левой верхней клетки

plan.offer(1);

int walls=0;

while(!plan.isEmpty()){

int row=plan.poll();

int col=plan.poll();

walls+=check(row, col, lab, visited, plan);

}

if(visited[N][N]!=1){//если не попали в правую нижнюю клетку

plan.offer(N);//считаем начиная с неё

plan.offer(N);

while(!plan.isEmpty()){

int row=plan.poll();

int col=plan.poll();

walls+=check(row, col, lab, visited, plan);

}

walls-=4;//стены у левого верхнего и правого нижнего угла отсутствуют

int meters = walls * 9;

System.out.println(meters);

}

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

Так как в условии не гарантируется, что есть проход от левой верхней до правой нижней клетки, проверяю, посещена ли последняя. Если нет, снова запускаю поиск, начиная с неё.

Засчитанное решение.

Задача на Ideone:
C++
Java

Related Images:

e-olimp 1098. Ходи ферзем!

01/05/2015 by Денисова Ольга

Задача о восьми ферзях

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

Входные данные. В одной строке задано сначала натуральное число T (T < 6) — количество тестов. Далее через пробел задано T блоков по 8 целых чисел от 1 до 8 – номера горизонталей, на которых находится ферзь с i-той вертикали. Вертикали пронумерованы подряд.

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

Тесты

Входные данные	Выходные данные	Комментарий
2 1 1 1 1 1 1 1 1 2 4 6 8 3 2 7 5	71	пройден

Решение

«Поиск с возвратом» в задаче о восьми ферзях.
Алгоритм.
При решении задачи используется два массива : массив расстановок из теста и массив правильной расстановки. Первоначально массив правильных расстановок — пустой (все значения элементов массива = -1).

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

Как только достигается одна из возможных правильных расстановок вызывается функция calc_min_strok(). Если элемент одного массива не равен элементу другого — это ход. Функция calc_min_strok() вычисляет количество ходов для данной расстановки и решает минимальное оно или нет для данного теста.

#include <iostream>
#include <stdio.h>
#include<fstream>
using namespace std;

const int n = 8;// Размер поля
int count_test = 0;// Количество тестов
int mincountstep = n + 1; //Количество ходов
int frtest[n]; //расстановка теста
int fr[n]; //правильная расстановка

bool check(int nf) 
// проверка битых полей
{ 
	if ( fr[nf] < 0 )  return false; //На всякий случай, чтобы не проверять поля где нет ферзей
    for (int i = 0; i < n && fr[i] >= 0; i++) {           
        if ( i == nf ) continue;
        if (fr[nf] == fr[i]  ) return false;  // (Горизонталь) 
        if ( (nf + fr[nf]) ==  (i + fr[i]) ) return false; // Нисходящая диагональ
        if ( (nf - fr[nf]) ==  (i - fr[i]) ) return false; // Восходящая диагональ
    }  
    return true; //если поле свободно
}

void calc_min_strok()
// Вычисление количества ходов и нахождение минимального
{
   int countstep = 0; // количество ходов
   for (int i = 0; i < n; i++){ 
      if ( frtest[i] != fr[i] ) countstep++;
   }
   if ( mincountstep > countstep ) mincountstep = countstep;

}

bool line_up(int i)
//рекурсивня функция установки ферзей (стек расстановок)
 {
    if ( i > n-1) return false ;
    for (int j = 0; j < n; j++) { 
        fr[i] = j;
        if ( check(i) == true ) {              
            if ( i == n-1) { //Если дошли до последней колонки и всё хорошо
            calc_min_strok();
            } else { 
                line_up(i+1);
            } 
        }
        fr[i] = -1 ;  
    } 
  return false ;
}

int main()
{
	cin >> count_test;
	//Обнуление начального массива
	for (int test = 0; test < count_test; test++ ){
	   mincountstep = n + 1;
       for (int i = 0; i < n; i++) fr[i] = -1; 
       //ввод данных теста
	   for (int i = 0; i < n; i++) {     
        	cin >> frtest[i];  
		    frtest[i]--;    
	   }
       line_up(0);    
       cout << mincountstep;
	}   
    
    return 0;
}

#include <iostream>

#include <stdio.h>

#include<fstream>

using namespace std;

const int n = 8;// Размер поля

int count_test = 0;// Количество тестов

int mincountstep = n + 1; //Количество ходов

int frtest[n]; //расстановка теста

int fr[n]; //правильная расстановка

bool check(int nf)

// проверка битых полей

{

if ( fr[nf] < 0 ) return false; //На всякий случай, чтобы не проверять поля где нет ферзей

for (int i = 0; i < n && fr[i] >= 0; i++) {

if ( i == nf ) continue;

if (fr[nf] == fr[i] ) return false; // (Горизонталь)

if ( (nf + fr[nf]) == (i + fr[i]) ) return false; // Нисходящая диагональ

if ( (nf - fr[nf]) == (i - fr[i]) ) return false; // Восходящая диагональ

}

return true; //если поле свободно

}

void calc_min_strok()

// Вычисление количества ходов и нахождение минимального

{

int countstep = 0; // количество ходов

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

if ( frtest[i] != fr[i] ) countstep++;

}

if ( mincountstep > countstep ) mincountstep = countstep;

}

bool line_up(int i)

//рекурсивня функция установки ферзей (стек расстановок)

{

if ( i > n-1) return false ;

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

fr[i] = j;

if ( check(i) == true ) {

if ( i == n-1) { //Если дошли до последней колонки и всё хорошо

calc_min_strok();

} else {

line_up(i+1);

}

fr[i] = -1 ;

}

return false ;

}

int main()

{

cin >> count_test;

//Обнуление начального массива

for (int test = 0; test < count_test; test++ ){

mincountstep = n + 1;

for (int i = 0; i < n; i++) fr[i] = -1;

//ввод данных теста

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

cin >> frtest[i];

frtest[i]--;

}

line_up(0);

cout << mincountstep;

}

return 0;

}

Решение на Java:

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

public class Main {
	static int n ;// Размер поля
	static int count_test ;// Количество тестов
	static int mincountstep ; //Количество ходов
	static int frtest[]; //расстановка теста
	static int fr[]; //правильная расстановка
	
	static boolean check(int nf) 
	// проверка битых полей
	{ 
		if ( fr[nf] < 0 ) return false; //На всякий случай, чтобы не проверять поля где нет ферзей
		for (int i = 0; i < n && fr[i] >= 0; i++) { 
			if ( i == nf ) continue;
			if (fr[nf] == fr[i] ) return false; // (Горизонталь) 
			if ( (nf + fr[nf]) == (i + fr[i]) ) return false; // Нисходящая диагональ
			if ( (nf - fr[nf]) == (i - fr[i]) ) return false; // Восходящая диагональ
		} 
		return true; //если поле свободно
	}
	
	static void calc_min_strok()
	// Вычисление количества ходов и нахождение минимального
	{
		int countstep = 0; // количество ходов
		for (int i = 0; i < n; i++){ 
			if ( frtest[i] != fr[i] ) countstep++;
		}
		if ( mincountstep > countstep ) mincountstep = countstep;
	}
	
	static boolean line_up(int i)
	//рекурсивная функция установки ферзей (стек расстановок)
	{
		if ( i > n-1) return false ;
		for (int j = 0; j < n; j++) { 
			fr[i] = j;
			if ( check(i) == true ) { 
			if ( i == n-1) { //Если дошли до последней колонки и всё хорошо
				calc_min_strok();
			} else { 
				line_up(i+1);
			} 
			}
			fr[i] = -1 ; 
		} 
		return false ;
	}
	
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		count_test = in.nextInt();
		n = 8;// Размер поля
		mincountstep = n + 1; //Количество ходов
		frtest = new int [n]; //расстановка теста
		fr = new int [n]; //правильная расстановка
		
		//Обнуление начального массива
		for (int test = 0; test < count_test; test++ ){
			mincountstep = n + 1;
			for (int i = 0; i < n; i++) fr[i] = -1; 
			//ввод данных теста
			for (int i = 0; i < n; i++) { 
				frtest[i] = in.nextInt();
				frtest[i]--; 
			}
			line_up(0); 
			System.out.print(mincountstep);
		} 
		System.out.println();
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

public class Main {

static int n ;// Размер поля

static int count_test ;// Количество тестов

static int mincountstep ; //Количество ходов

static int frtest[]; //расстановка теста

static int fr[]; //правильная расстановка

static boolean check(int nf)

// проверка битых полей

{

if ( fr[nf] < 0 ) return false; //На всякий случай, чтобы не проверять поля где нет ферзей

for (int i = 0; i < n && fr[i] >= 0; i++) {

if ( i == nf ) continue;

if (fr[nf] == fr[i] ) return false; // (Горизонталь)

if ( (nf + fr[nf]) == (i + fr[i]) ) return false; // Нисходящая диагональ

if ( (nf - fr[nf]) == (i - fr[i]) ) return false; // Восходящая диагональ

}

return true; //если поле свободно

}

static void calc_min_strok()

// Вычисление количества ходов и нахождение минимального

{

int countstep = 0; // количество ходов

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

if ( frtest[i] != fr[i] ) countstep++;

}

if ( mincountstep > countstep ) mincountstep = countstep;

}

static boolean line_up(int i)

//рекурсивная функция установки ферзей (стек расстановок)

{

if ( i > n-1) return false ;

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

fr[i] = j;

if ( check(i) == true ) {

if ( i == n-1) { //Если дошли до последней колонки и всё хорошо

calc_min_strok();

} else {

line_up(i+1);

}

fr[i] = -1 ;

}

return false ;

}

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

count_test = in.nextInt();

n = 8;// Размер поля

mincountstep = n + 1; //Количество ходов

frtest = new int [n]; //расстановка теста

fr = new int [n]; //правильная расстановка

//Обнуление начального массива

for (int test = 0; test < count_test; test++ ){

mincountstep = n + 1;

for (int i = 0; i < n; i++) fr[i] = -1;

//ввод данных теста

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

frtest[i] = in.nextInt();

frtest[i]--;

}

line_up(0);

System.out.print(mincountstep);

}

System.out.println();

}

(Что бы прошло на e-olimp нужно удалить все комментарии)

Related Images:

e-olimp 4000. Обход в глубину

30/04/2015 by Ковальський Олександр Дмитрович

Задача e-olimp 4000

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

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

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

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

Выведите одно число — искомое количество вершин.

Пример:

Входные данные	Выходные данные
5 1	3
0 1 1 0 0
1 0 1 0 0
1 1 0 0 0
0 0 0 0 1
0 0 0 1 0

Решение

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

int main()
	{
		int n;
		int s;
		cin>>n>>s;
		s--;
		int matrix[n][n];
		stack<int> st;
		int counter=1;
		for(int i=0;i<n;i++)
			{
				for(int j=0;j<n;j++)
					{
						cin>>matrix[i][j];
					}
			}
		for(int j=0;j<n;j++)
			{
				if(matrix[s][j] == 1) st.push(j);
			}
		matrix[s][s]=1;
		while(!st.empty())
			{
				int a=st.top();
				st.pop();
				if(matrix[a][a]!=1)
					{
						for(int j=0;j<n;j++)
							{
								if(matrix[a][j] == 1) st.push(j);
							}
						counter++;
						matrix[a][a]=1;
					}
				
			}
		cout<<counter<<endl;
	}

#include <iostream>

#include <stack>

using namespace std;

int main()

{

int n;

int s;

cin>>n>>s;

s--;

int matrix[n][n];

stack<int> st;

int counter=1;

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

{

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

{

cin>>matrix[i][j];

}

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

{

if(matrix[s][j] == 1) st.push(j);

}

matrix[s][s]=1;

while(!st.empty())

{

int a=st.top();

st.pop();

if(matrix[a][a]!=1)

{

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

{

if(matrix[a][j] == 1) st.push(j);

}

counter++;

matrix[a][a]=1;

}

cout<<counter<<endl;

}

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

class Ideone
{
	public static void main (String[] args)
	{
		Scanner in = new Scanner(System.in);
        int n = in.nextInt(), s = in.nextInt()-1, counter = 1;
		int[][] matrix = new int[n][n];
		Stack st = new Stack();
		for(int i = 0;i < n; i++)
			{
				for(int j = 0;j < n; j++)
					{
						matrix[i][j] = in.nextInt();
					}
			}
		for(int j = 0; j < n; j++)
			{
				if(matrix[s][j] == 1) st.push(j);
			}
		matrix[s][s] = 1;
		while(!st.empty())
			{
				int a = (int) st.peek();
				st.pop();
				if(matrix[a][a] != 1)
					{
						for(int j = 0; j < n; j++)
							{
								if(matrix[a][j] == 1) st.push(j);
							}
						counter++;
						matrix[a][a] = 1;
					}
				
			}
		System.out.println(counter);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

public static void main (String[] args)

{

Scanner in = new Scanner(System.in);

int n = in.nextInt(), s = in.nextInt()-1, counter = 1;

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

Stack st = new Stack();

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

{

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

{

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

}

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

{

if(matrix[s][j] == 1) st.push(j);

}

matrix[s][s] = 1;

while(!st.empty())

{

int a = (int) st.peek();

st.pop();

if(matrix[a][a] != 1)

{

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

{

if(matrix[a][j] == 1) st.push(j);

}

counter++;

matrix[a][a] = 1;

}

System.out.println(counter);

}

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

Код на ideone.

Засчитанное решение.

Related Images:

e-olimp 695. Range Variation Query

30/04/2015 by Недомовний Владислав

Задача e-olimp 695.

Последовательность [latex]a_{n}[/latex] задается следующей формулой: [latex]a_{n}=n^{2} mod 12345+n^{3} mod 23456[/latex].

Требуется много раз отвечать на запросы следующего вида:

найти разность между максимальным и минимальным значением среди элементов [latex]a_{i},a_{i+1}, …,a_{j}[/latex];
присвоить элементу [latex]a_{i}[/latex] значение [latex]j[/latex].

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

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

Первая строка содержит натуральное число [latex]k (k\leq 100000)[/latex] — количество запросов. Следующие [latex]k[/latex] строк содержат запросы, по одному в строке. Запрос номер [latex]i[/latex] описывается двумя целыми числами [latex]x_{i},y_{i}[/latex].

Если [latex]x_{i}>0[/latex], то требуется найти разность между максимальным и минимальным значением среди элементов [latex]a_{x_{i}}…a_{y_{i}}[/latex]. При этом [latex]1\leq x_{i}\leq y_{i}\leq 100000[/latex].

Если [latex]x_{i}<0[/latex], то требуется присвоить элементу [latex]a_{-x_{i}}[/latex] значение[latex]y_{i}[/latex]. При этом[latex]-100000\leq x_{i}\leq 1[/latex] и [latex]\left | y_{i} \right |\leq 100000[/latex].

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

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

Пример.

Пример входных данных

Пример выходных данных

1 3

2 4

-2 -100

8 9

-3 -101

2 3

250

234

Решение.

#include <iostream>
#include <math.h>
#include <algorithm>
#include <climits>
using namespace std;
#define length    100000



int main() {
   int a[length];
   for(long long i=1;i<=length;i++)
   {
       a[i-1]=((i%12345)*(i%12345))%12345+((i%23456)*(i%23456)%23456*i%23456)%23456; //заполнение массива
   }
   int k,x,y,result;
   cin>>k; 
   int mmax,mmin; //переменные для хранения максимума и минимума на отрезке
   for(int i=0;i<k;i++)
   {
       cin >> x >> y;
       mmax=INT_MIN;
       mmin=INT_MAX;
       if(x>0)
       {
           for(int i=x-1;i<y;i++) //поиск максимума и минимума на отрезке [x,y]
           {
               if(mmax<a[i]) mmax=a[i];
               if(mmin>a[i]) mmin=a[i];
           }
           cout << mmax-mmin << endl;
       }
       else
       {
           x*=-1;
           a[x-1]=y; //замена x-го элемента на y
       }
   }
}

#include <iostream>

#include <math.h>

#include <algorithm>

#include <climits>

using namespace std;

#define length 100000

int main() {

int a[length];

for(long long i=1;i<=length;i++)

{

a[i-1]=((i%12345)*(i%12345))%12345+((i%23456)*(i%23456)%23456*i%23456)%23456; //заполнение массива

}

int k,x,y,result;

cin>>k;

int mmax,mmin; //переменные для хранения максимума и минимума на отрезке

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

{

cin >> x >> y;

mmax=INT_MIN;

mmin=INT_MAX;

if(x>0)

{

for(int i=x-1;i<y;i++) //поиск максимума и минимума на отрезке [x,y]

{

if(mmax<a[i]) mmax=a[i];

if(mmin>a[i]) mmin=a[i];

}

cout << mmax-mmin << endl;

}

else

{

x*=-1;

a[x-1]=y; //замена x-го элемента на y

}

Так как количество запросов [latex]k\leq 100000[/latex] сначала считаем значение всех элементов последовательности и сохраняем их в массив. Если требуется найти разность между максимумом и минимумом,то находим их проверяя все элементы отрезка и выводим разность. Если требуется заменить элемент, то заменяем соответствующий элемент последовательности на новый.

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

Данный код на ideone.

В скором времени будет добавлено более эффективное решение с помощью дерева отрезков.

Related Images:

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

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

Сортировка вагонов — B

prb4513 К тупику со стороны пути 1 (см. рисунок) подъехал поезд. Разрешается отцепить от поезда один или сразу несколько первых вагонов и завезти их в тупик (при желании, можно даже завезти в тупик сразу весь поезд). После этого часть из этих вагонов вывезти в сторону пути 2. После этого можно завезти в тупик еще несколько вагонов и снова часть оказавшихся вагонов вывезти в сторону пути 2. И так далее (так, что каждый вагон может лишь один раз заехать с пути 1 в тупик, а затем один раз выехать из тупика на путь 2). Заезжать в тупик с пути 2 или выезжать из тупика на путь 1 запрещается. Нельзя с пути 1 попасть на путь 2, не заезжая в тупик.

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

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

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

Вводится число [latex]N[/latex] — количество вагонов в поезде [latex]\left(1\leq N\leq100\right)[/latex]. Дальше идут номера вагонов в порядке от головы поезда, едущего по пути 1 в сторону тупика. Вагоны пронумерованы натуральными числами от [latex]1[/latex] до [latex]N[/latex], каждое из которых встречается ровно один раз.

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

Если сделать так, чтобы вагоны шли в порядке от [latex]1[/latex] до [latex]N[/latex], считая от головы поезда, когда поезд поедет по пути 2 из тупика, можно, выведите сообщение YES, если это сделать нельзя, выведите NO.

Код

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

#include <iostream>

using namespace std;

struct stack{ //стек

int truck[100];

int length = 0;

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

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

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

int size () {return length;}

}car;

int main() {

int amount_n;

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

int n;

int count = 1;

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

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

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

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

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

else break;

}

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

else cout << "NO" << endl;

return 0;

}

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

Related Images:

e-olimp 4847. Очередь с приоритетами

07/04/2015 by Швандт Максим Альбертович

Условие: Реализуйте структуру «очередь с приоритетами», поддерживающую следующие операции:

Добавление элемента в очередь.
Удаление из очереди элемента с наибольшим приоритетом.
Изменение приоритета для произвольного элемента, находящегося в очереди.

Тесты:

input data	output data
add eight 8	<вывод не предусмотрен>
add three 3	<вывод не предусмотрен>
add eleven 11	<вывод не предусмотрен>
add one 1	<вывод не предусмотрен>
add five 5	<вывод не предусмотрен>
add neun 9	<вывод не предусмотрен>
add forteen 14	<вывод не предусмотрен>
add six 6	<вывод не предусмотрен>
add ten 10	<вывод не предусмотрен>
add twelve 12	<вывод не предусмотрен>
add fifteen 15	<вывод не предусмотрен>
add seven 7	<вывод не предусмотрен>
add thirteen 13	<вывод не предусмотрен>
change eleven 1100	<вывод не предусмотрен>
change eleven 1101	<вывод не предусмотрен>
change one 111	<вывод не предусмотрен>
pop	eleven 1101
pop	one 111
pop	fifteen 15
pop	forteen 14
pop	thirteen 13
pop	twelve 12
pop	ten 10
pop	neun 9
pop	eight 8
pop	seven 7
pop	six 6
pop	five 5
pop	three 3
pop	error

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

#include <iostream>

using namespace std;

// шаблонный класс, описывающий узел списка

template <typename KeyType>
class ListNode
{
public:
	ListNode( KeyType& key, ListNode* next ) { mKey = key; mNext = next; };
	KeyType& getKey() { return mKey; };
	ListNode* getNext() { return mNext; };
	void setNext( ListNode* node ) { mNext = node; };
protected:
	KeyType mKey;
	ListNode *mNext;
};

// шаблонный класс, описывающий список
template <typename KeyType, typename ListNodeType>
class List
{
public:
	List() { mHead = NULL; };
	virtual ~List() { clear(); };
	void clear();
	bool find( KeyType& key, ListNodeType*& foundNode, ListNodeType*& foundPrevNode );
	bool remove( KeyType& key );
	void push( KeyType& key ) { mHead = new ListNodeType( key, mHead ); };
	bool pop( KeyType& key );
	ListNodeType* getHead() { return mHead; };
	bool isEmpty() { return mHead == NULL; };
protected:
	ListNodeType* mHead;
};

// очищает все элементы списка и высвобождает память
template <typename KeyType, typename ListNodeType>
void List<KeyType,ListNodeType>::clear()
{
	ListNodeType *n =  mHead;
	while( NULL != n )
	{
	   ListNodeType *prev = n;
	   n = n->getNext();
	   delete prev;
	}
	mHead = NULL;
};

// находит узел списка по ключу
template <typename KeyType, typename ListNodeType>
bool List<KeyType,ListNodeType>::find( KeyType& key, ListNodeType*& foundNode, ListNodeType*& foundPrevNode )
{
	ListNodeType *n =  mHead;
	ListNodeType *prev = NULL;
	while( NULL != n )
	{
	   if ( n->getKey() == key )
	   {
	      foundNode = n;
	      foundPrevNode = prev;
	      return true;
	   }
	   prev = n;
	   n = n->getNext();
	}
	return false;
}

// удаляет узел списка по ключу
template <typename KeyType, typename ListNodeType>
bool List<KeyType,ListNodeType>::remove( KeyType& key )
{
	ListNodeType *n = NULL;
	ListNodeType *prev = NULL;

	if ( find( key, n, prev ) )
	{
	   if ( NULL != prev )
	   {
	      prev->setNext( n->getNext() );
	   }
	   else
	   {
	      mHead = n->getNext();
	   }
	   delete n;
	   return true;
	}
	return false;
};

// удаляет первый элемент
template <typename KeyType, typename ListNodeType>
bool List<KeyType,ListNodeType>::pop( KeyType& key )
{
	if ( mHead != NULL )
	{
	   key = mHead->getKey();
	   ListNodeType* n = mHead;
	   mHead = n->getNext();
	   delete n;
	   return true;
	}
	return false;
};

// Шаблонный класс, описывающий узел дерева двоичного поиска

template <typename KeyType, typename ValueType>
class TreeNode {
public:
	TreeNode( KeyType& key ) : mKey(key), mValue(NULL), mParent(NULL), mLeft(NULL), mRight(NULL) {};
	TreeNode( KeyType& key, ValueType& value ) : mKey(key), mValue(value), mParent(NULL), mLeft(NULL), mRight(NULL) {};
	~TreeNode() { };
	void setLeft( TreeNode* left ) { mLeft = left; };
	void setRight( TreeNode* right ) { mRight = right; };
	void setParent( TreeNode* parent ) { mParent = parent; };
	KeyType getKey() { return mKey; };
	ValueType& getValue() { return mValue; };
	void setValue( ValueType& value ) { mValue = value; };
	TreeNode* getLeft() { return mLeft; };
	TreeNode* getRight() { return mRight; };
	TreeNode* getParent() { return mParent; };
	virtual string getValueAsText() { return ""; };
protected:
	KeyType mKey;
	ValueType mValue;
	TreeNode* mParent;
	TreeNode* mLeft;
	TreeNode* mRight;
};

// шаблонный класс, описывающий дерево
template <typename KeyType, typename NodeType>
class Tree {
	NodeType* mRoot;
public:
	Tree() { mRoot = NULL; };
	~Tree() { clear(); };
	void clear() { dispose( mRoot ); mRoot = NULL; };
	bool isEmpty() { return mRoot == NULL; };
	NodeType* getRoot() { return mRoot; };
	NodeType* findOrInsert( KeyType& key, bool insertIfAbsent );
	void exclude( NodeType* node );
	void remove( NodeType* node ) { exclude( node ); dispose( node ); };
	bool remove( KeyType& key, NodeType* removedNodeCopy );
	bool remove( KeyType& key ) { return( key, NULL ); };
	NodeType* findMax( NodeType* node );
	NodeType* findMax() { return findMax( mRoot ); };
protected:
	void dispose( NodeType* node );
};

// находит узел двоичного дерева по ключу или всталяет, если не найдено
template <typename KeyType, typename NodeType>
NodeType* Tree<KeyType,NodeType>::findOrInsert( KeyType& key, bool insertIfAbsent )
{
	enum EInsertAction
	{
	   eNONE,
	   eROOT,
	   eLEFT,
	   eRIGHT
	};

	EInsertAction doInsert = eNONE;
	NodeType *p = mRoot;

	if ( p != NULL )
	{
	   for(;;)
	   {
	      if ( key < p->getKey() )
	      {
	         if ( p->getLeft() != NULL )
	         {
	            p = p->getLeft();
	         }
	         else
	         {
	            doInsert = eLEFT;
	            break;
	         }
	      }
	      else
	      if ( key > p->getKey() )
	      {
	         if ( p->getRight() != NULL )
	         {
	            p = p->getRight();
	         }
	         else
	         {
	            doInsert = eRIGHT;
	            break;
	         }
	      }
	      else
	      {
	         return p;
	      }
	   }
	}
	else
	{
	   doInsert = eROOT;
	}

	if ( doInsert != eNONE && insertIfAbsent )
	{
	   NodeType* q = new NodeType( key );
	   switch( doInsert )
	   {
	      case eLEFT : p->setLeft( q ); break;
	      case eRIGHT: p->setRight( q ); break;
	      case eROOT : mRoot = q; break;
	      default: break;
	   }
	   q->setParent( p );
	   return q;
	}

	return NULL;
}

// находит узел двоичного дерева с максимальным значением ключа
template <typename KeyType, typename NodeType>
NodeType* Tree<KeyType,NodeType>::findMax( NodeType* node )
{
	if ( node != NULL )
	{
	   NodeType* n = node;
	   while( NULL != n->getRight() )
	   {
	      n = n->getRight();
	   }
	   return n;
	}
	return NULL;
}

// исключает узел двоичного дерева из дерева, не удаляя
template <typename KeyType, typename NodeType>
void Tree<KeyType,NodeType>::exclude( NodeType* node )
{
	if ( NULL != node )
	{
	   NodeType* successor = NULL;

	   if ( node->getLeft() == NULL )
	   {
	      successor = node->getRight();
	   }
	   else
	   if ( node->getRight() == NULL )
	   {
	      successor = node->getLeft();
	   }
	   else
	   {
	      successor = node->getRight();
	      NodeType* left = successor->getLeft();

	      while( left != NULL )
	      {
	         successor = left;
	         left = successor->getLeft();
	      }

	      if ( successor->getParent() != node )
	      {
	     	NodeType* right = successor->getRight();
	         successor->getParent()->setLeft( right );
	         if ( NULL != right)
	         {
	         	successor->getRight()->setParent( successor->getParent() );
	         }
	         successor->setRight( node->getRight() );
	         node->getRight()->setParent( successor );
	      }

	      successor->setLeft( node->getLeft() );
	      node->getLeft()->setParent( successor );
	   }
	   
	   if ( node->getParent() == NULL )
	   {
	      mRoot = successor;
	   }
	   else
	   if ( node->getParent()->getLeft() == node )
	   {
	      node->getParent()->setLeft( successor );
	   }
	   else
	   if ( node->getParent()->getRight() == node )
	   {
	      node->getParent()->setRight( successor );
	   }
	   else
	   {
	      cout << "fatal error: orphaned# " 
	         << "N:" << node << ",P:" << node->getParent() << ",L:" << node->getLeft() << ",R:"<<node->getRight()
	         << endl;
	      return;
	   }
	   
	   if ( NULL != successor )
	   {
	      successor->setParent( node->getParent() );
	   }
	   
	   node->setParent( NULL );
	   node->setLeft( NULL );
	   node->setRight( NULL );
	}
}

// находит и удаляет узел дерева по ключу
template <typename KeyType, typename NodeType>
bool Tree<KeyType,NodeType>::remove( KeyType& key, NodeType* removedNodeCopy )
{
	NodeType* node = findOrInsert( key, false );
	if ( node != NULL )
	{
	   exclude( node );
	   if ( removedNodeCopy != NULL )
	   {
	      *removedNodeCopy = node;
	   }
	   dispose( node );
	   return true;
	}
	return false;
}

// удаляет узел из памяти
template <typename KeyType, typename NodeType>
void Tree<KeyType,NodeType>::dispose( NodeType* node )
{
	if ( node != NULL ) 
	{
	    dispose( node->getLeft() );
	    dispose( node->getRight() );
	    delete node;
	}
}

// класы-контейнеры на основе высше описанных шаблонных классов

class PrioTreeNode;
typedef TreeNode<string,PrioTreeNode*> IdTreeNodeBase;
class IdTreeNode : public IdTreeNodeBase
{
public:
	IdTreeNode( string& id ) : IdTreeNodeBase( id ) {};
	virtual ~IdTreeNode() { mValue = NULL; };
	IdTreeNode* getLeft() { return (IdTreeNode*)mLeft; };
	IdTreeNode* getRight() { return (IdTreeNode*)mRight; };
	IdTreeNode* getParent() { return (IdTreeNode*)mParent; };
};
typedef Tree<string,IdTreeNode> IdTree;

typedef ListNode<IdTreeNode*> IdListNode;
typedef List<IdTreeNode*,IdListNode> IdList;

typedef TreeNode<int,IdList*> PrioTreeNodeBase;
class PrioTreeNode : public PrioTreeNodeBase
{
public:
	PrioTreeNode( int& prio ) : PrioTreeNodeBase( prio ) { mValue = new IdList(); };
	virtual ~PrioTreeNode() { delete mValue; };
	PrioTreeNode* getLeft() { return (PrioTreeNode*)mLeft; };
	PrioTreeNode* getRight() { return (PrioTreeNode*)mRight; };
	PrioTreeNode* getParent() { return (PrioTreeNode*)mParent; };
};
typedef Tree<int,PrioTreeNode> PrioTree;

// класс, реализующий очередь с приоритетами

class PrioQueue
{

public:

	PrioQueue() { }
	~PrioQueue() { }

	bool add( string& id, int prio  );
	bool pop( string& id, int& prio );
	bool change( string& id, int prio );
	void clear();

private:

	IdTree mIdTree;
	PrioTree mPrioTree;

};

bool PrioQueue::add( string& id, int prio  )
{
	IdTreeNode *idNode = mIdTree.findOrInsert( id, true );
	if ( NULL != idNode )
	{
	   PrioTreeNode* prioNode = mPrioTree.findOrInsert( prio, true );
	   if ( NULL != prioNode )
	   {
	      prioNode->getValue()->push( idNode );
	      idNode->setValue( prioNode );
	      return true;
	   }
	}
	return false;
}

bool PrioQueue::pop( string& id, int& prio )
{
	bool result = false;
	PrioTreeNode* prioNode = mPrioTree.findMax();
	if ( NULL != prioNode )
	{
	   prio = prioNode->getKey();
	   if ( ! prioNode->getValue()->isEmpty() )
	   {
	      IdTreeNode* idNode;
	      if ( prioNode->getValue()->pop( idNode ) )
	      {
	         id = idNode->getKey();
	         mIdTree.remove( idNode );
	         if ( prioNode->getValue()->isEmpty() )
	         {
	            mPrioTree.remove( prioNode );
	         }
	         result = true;
	      }
	   }
	}
	return result;
}

bool PrioQueue::change( string& id, int prio )
{
	bool result = false;
	IdTreeNode* idNode = mIdTree.findOrInsert( id, false );
	if ( NULL != idNode )
	{
	   PrioTreeNode* oldPrioNode = idNode->getValue();
	   (void)oldPrioNode->getValue()->remove( idNode );
	   if ( oldPrioNode->getValue()->isEmpty() )
	   {
	      mPrioTree.remove( oldPrioNode );
	   }
	   PrioTreeNode* newPrioNode = mPrioTree.findOrInsert( prio, true );
	   idNode->setValue( newPrioNode );
	   newPrioNode->getValue()->push( idNode );
	   result = true;
	}
	return result;
}

void PrioQueue::clear()
{
	mIdTree.clear();
	mPrioTree.clear();
}

int main( int argc, char** argv )
{
	PrioQueue q;

	string command;
	string id;
	int prio;

	while ( cin >> command )
	{
	   if ( command.compare( 0, 1, "#" ) == 0 ) continue;
	   else
	   if ( command == "add" || command == "ADD" )
	   {
	      cin >> id;
	      cin >> prio;

	      q.add( id, prio );
	   }
	   else
	   if ( command == "change" || command == "CHANGE" )
	   {
	      cin >> id;
	      cin >> prio;

	      q.change( id, prio );
	   }
	   else
	   if ( command == "pop" || command == "POP" )
	   {
	      if ( q.pop( id, prio ) )
	      {
	         cout << id << " " << prio << endl;
	      }
	      else
	      {
	         cout << "error" << endl;
	      }
	   }
	   else
	   if ( command == "clear" || command == "CLEAR" )
	   {
	      q.clear();
	   }
	   else
	   if ( command == "exit" || command == "EXIT" )
	   {
	      cout << "bye" << endl;
	      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

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

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

302

303

304

305

306

307

308

309

310

311

312

313

314

315

316

317

318

319

320

321

322

323

324

325

326

327

328

329

330

331

332

333

334

335

336

337

338

339

340

341

342

343

344

345

346

347

348

349

350

351

352

353

354

355

356

357

358

359

360

361

362

363

364

365

366

367

368

369

370

371

372

373

374

375

376

377

378

379

380

381

382

383

384

385

386

387

388

389

390

391

392

393

394

395

396

397

398

399

400

401

402

403

404

405

406

407

408

409

410

411

412

413

414

415

416

417

418

419

420

421

422

423

424

425

426

427

428

429

430

431

432

433

434

435

436

437

438

439

440

441

442

443

444

445

446

447

448

449

450

451

452

453

454

455

456

457

458

459

460

461

462

463

464

465

466

467

468

469

470

471

472

473

474

475

476

477

478

479

480

481

482

483

484

485

486

487

488

489

490

491

492

493

494

495

496

497

498

499

500

501

502

503

504

505

506

507

508

509

510

511

512

513

514

515

516

517

518

519

520

521

522

523

524

#include <iostream>

using namespace std;

// шаблонный класс, описывающий узел списка

template <typename KeyType>

class ListNode

{

public:

ListNode( KeyType& key, ListNode* next ) { mKey = key; mNext = next; };

KeyType& getKey() { return mKey; };

ListNode* getNext() { return mNext; };

void setNext( ListNode* node ) { mNext = node; };

protected:

KeyType mKey;

ListNode *mNext;

};

// шаблонный класс, описывающий список

template <typename KeyType, typename ListNodeType>

class List

{

public:

List() { mHead = NULL; };

virtual ~List() { clear(); };

void clear();

bool find( KeyType& key, ListNodeType*& foundNode, ListNodeType*& foundPrevNode );

bool remove( KeyType& key );

void push( KeyType& key ) { mHead = new ListNodeType( key, mHead ); };

bool pop( KeyType& key );

ListNodeType* getHead() { return mHead; };

bool isEmpty() { return mHead == NULL; };

protected:

ListNodeType* mHead;

};

// очищает все элементы списка и высвобождает память

template <typename KeyType, typename ListNodeType>

void List<KeyType,ListNodeType>::clear()

{

ListNodeType *n = mHead;

while( NULL != n )

{

ListNodeType *prev = n;

n = n->getNext();

delete prev;

}

mHead = NULL;

};

// находит узел списка по ключу

template <typename KeyType, typename ListNodeType>

bool List<KeyType,ListNodeType>::find( KeyType& key, ListNodeType*& foundNode, ListNodeType*& foundPrevNode )

{

ListNodeType *n = mHead;

ListNodeType *prev = NULL;

while( NULL != n )

{

if ( n->getKey() == key )

{

foundNode = n;

foundPrevNode = prev;

return true;

}

prev = n;

n = n->getNext();

}

return false;

}

// удаляет узел списка по ключу

template <typename KeyType, typename ListNodeType>

bool List<KeyType,ListNodeType>::remove( KeyType& key )

{

ListNodeType *n = NULL;

ListNodeType *prev = NULL;

if ( find( key, n, prev ) )

{

if ( NULL != prev )

{

prev->setNext( n->getNext() );

}

else

{

mHead = n->getNext();

}

delete n;

return true;

}

return false;

};

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

template <typename KeyType, typename ListNodeType>

bool List<KeyType,ListNodeType>::pop( KeyType& key )

{

if ( mHead != NULL )

{

key = mHead->getKey();

ListNodeType* n = mHead;

mHead = n->getNext();

delete n;

return true;

}

return false;

};

// Шаблонный класс, описывающий узел дерева двоичного поиска

template <typename KeyType, typename ValueType>

class TreeNode {

public:

TreeNode( KeyType& key ) : mKey(key), mValue(NULL), mParent(NULL), mLeft(NULL), mRight(NULL) {};

TreeNode( KeyType& key, ValueType& value ) : mKey(key), mValue(value), mParent(NULL), mLeft(NULL), mRight(NULL) {};

~TreeNode() { };

void setLeft( TreeNode* left ) { mLeft = left; };

void setRight( TreeNode* right ) { mRight = right; };

void setParent( TreeNode* parent ) { mParent = parent; };

KeyType getKey() { return mKey; };

ValueType& getValue() { return mValue; };

void setValue( ValueType& value ) { mValue = value; };

TreeNode* getLeft() { return mLeft; };

TreeNode* getRight() { return mRight; };

TreeNode* getParent() { return mParent; };

virtual string getValueAsText() { return ""; };

protected:

KeyType mKey;

ValueType mValue;

TreeNode* mParent;

TreeNode* mLeft;

TreeNode* mRight;

};

// шаблонный класс, описывающий дерево

template <typename KeyType, typename NodeType>

class Tree {

NodeType* mRoot;

public:

Tree() { mRoot = NULL; };

~Tree() { clear(); };

void clear() { dispose( mRoot ); mRoot = NULL; };

bool isEmpty() { return mRoot == NULL; };

NodeType* getRoot() { return mRoot; };

NodeType* findOrInsert( KeyType& key, bool insertIfAbsent );

void exclude( NodeType* node );

void remove( NodeType* node ) { exclude( node ); dispose( node ); };

bool remove( KeyType& key, NodeType* removedNodeCopy );

bool remove( KeyType& key ) { return( key, NULL ); };

NodeType* findMax( NodeType* node );

NodeType* findMax() { return findMax( mRoot ); };

protected:

void dispose( NodeType* node );

};

// находит узел двоичного дерева по ключу или всталяет, если не найдено

template <typename KeyType, typename NodeType>

NodeType* Tree<KeyType,NodeType>::findOrInsert( KeyType& key, bool insertIfAbsent )

{

enum EInsertAction

{

eNONE,

eROOT,

eLEFT,

eRIGHT

};

EInsertAction doInsert = eNONE;

NodeType *p = mRoot;

if ( p != NULL )

{

for(;;)

{

if ( key < p->getKey() )

{

if ( p->getLeft() != NULL )

{

p = p->getLeft();

}

else

{

doInsert = eLEFT;

break;

}

else

if ( key > p->getKey() )

{

if ( p->getRight() != NULL )

{

p = p->getRight();

}

else

{

doInsert = eRIGHT;

break;

}

else

{

return p;

}

else

{

doInsert = eROOT;

}

if ( doInsert != eNONE && insertIfAbsent )

{

NodeType* q = new NodeType( key );

switch( doInsert )

{

case eLEFT : p->setLeft( q ); break;

case eRIGHT: p->setRight( q ); break;

case eROOT : mRoot = q; break;

default: break;

}

q->setParent( p );

return q;

}

return NULL;

}

// находит узел двоичного дерева с максимальным значением ключа

template <typename KeyType, typename NodeType>

NodeType* Tree<KeyType,NodeType>::findMax( NodeType* node )

{

if ( node != NULL )

{

NodeType* n = node;

while( NULL != n->getRight() )

{

n = n->getRight();

}

return n;

}

return NULL;

}

// исключает узел двоичного дерева из дерева, не удаляя

template <typename KeyType, typename NodeType>

void Tree<KeyType,NodeType>::exclude( NodeType* node )

{

if ( NULL != node )

{

NodeType* successor = NULL;

if ( node->getLeft() == NULL )

{

successor = node->getRight();

}

else

if ( node->getRight() == NULL )

{

successor = node->getLeft();

}

else

{

successor = node->getRight();

NodeType* left = successor->getLeft();

while( left != NULL )

{

successor = left;

left = successor->getLeft();

}

if ( successor->getParent() != node )

{

NodeType* right = successor->getRight();

successor->getParent()->setLeft( right );

if ( NULL != right)

{

successor->getRight()->setParent( successor->getParent() );

}

successor->setRight( node->getRight() );

node->getRight()->setParent( successor );

}

successor->setLeft( node->getLeft() );

node->getLeft()->setParent( successor );

}

if ( node->getParent() == NULL )

{

mRoot = successor;

}

else

if ( node->getParent()->getLeft() == node )

{

node->getParent()->setLeft( successor );

}

else

if ( node->getParent()->getRight() == node )

{

node->getParent()->setRight( successor );

}

else

{

cout << "fatal error: orphaned# "

<< "N:" << node << ",P:" << node->getParent() << ",L:" << node->getLeft() << ",R:"<<node->getRight()

<< endl;

return;

}

if ( NULL != successor )

{

successor->setParent( node->getParent() );

}

node->setParent( NULL );

node->setLeft( NULL );

node->setRight( NULL );

}

// находит и удаляет узел дерева по ключу

template <typename KeyType, typename NodeType>

bool Tree<KeyType,NodeType>::remove( KeyType& key, NodeType* removedNodeCopy )

{

NodeType* node = findOrInsert( key, false );

if ( node != NULL )

{

exclude( node );

if ( removedNodeCopy != NULL )

{

*removedNodeCopy = node;

}

dispose( node );

return true;

}

return false;

}

// удаляет узел из памяти

template <typename KeyType, typename NodeType>

void Tree<KeyType,NodeType>::dispose( NodeType* node )

{

if ( node != NULL )

{

dispose( node->getLeft() );

dispose( node->getRight() );

delete node;

}

// класы-контейнеры на основе высше описанных шаблонных классов

class PrioTreeNode;

typedef TreeNode<string,PrioTreeNode*> IdTreeNodeBase;

class IdTreeNode : public IdTreeNodeBase

{

public:

IdTreeNode( string& id ) : IdTreeNodeBase( id ) {};

virtual ~IdTreeNode() { mValue = NULL; };

IdTreeNode* getLeft() { return (IdTreeNode*)mLeft; };

IdTreeNode* getRight() { return (IdTreeNode*)mRight; };

IdTreeNode* getParent() { return (IdTreeNode*)mParent; };

};

typedef Tree<string,IdTreeNode> IdTree;

typedef ListNode<IdTreeNode*> IdListNode;

typedef List<IdTreeNode*,IdListNode> IdList;

typedef TreeNode<int,IdList*> PrioTreeNodeBase;

class PrioTreeNode : public PrioTreeNodeBase

{

public:

PrioTreeNode( int& prio ) : PrioTreeNodeBase( prio ) { mValue = new IdList(); };

virtual ~PrioTreeNode() { delete mValue; };

PrioTreeNode* getLeft() { return (PrioTreeNode*)mLeft; };

PrioTreeNode* getRight() { return (PrioTreeNode*)mRight; };

PrioTreeNode* getParent() { return (PrioTreeNode*)mParent; };

};

typedef Tree<int,PrioTreeNode> PrioTree;

// класс, реализующий очередь с приоритетами

class PrioQueue

{

public:

PrioQueue() { }

~PrioQueue() { }

bool add( string& id, int prio );

bool pop( string& id, int& prio );

bool change( string& id, int prio );

void clear();

private:

IdTree mIdTree;

PrioTree mPrioTree;

};

bool PrioQueue::add( string& id, int prio )

{

IdTreeNode *idNode = mIdTree.findOrInsert( id, true );

if ( NULL != idNode )

{

PrioTreeNode* prioNode = mPrioTree.findOrInsert( prio, true );

if ( NULL != prioNode )

{

prioNode->getValue()->push( idNode );

idNode->setValue( prioNode );

return true;

}

return false;

}

bool PrioQueue::pop( string& id, int& prio )

{

bool result = false;

PrioTreeNode* prioNode = mPrioTree.findMax();

if ( NULL != prioNode )

{

prio = prioNode->getKey();

if ( ! prioNode->getValue()->isEmpty() )

{

IdTreeNode* idNode;

if ( prioNode->getValue()->pop( idNode ) )

{

id = idNode->getKey();

mIdTree.remove( idNode );

if ( prioNode->getValue()->isEmpty() )

{

mPrioTree.remove( prioNode );

}

result = true;

}

return result;

}

bool PrioQueue::change( string& id, int prio )

{

bool result = false;

IdTreeNode* idNode = mIdTree.findOrInsert( id, false );

if ( NULL != idNode )

{

PrioTreeNode* oldPrioNode = idNode->getValue();

(void)oldPrioNode->getValue()->remove( idNode );

if ( oldPrioNode->getValue()->isEmpty() )

{

mPrioTree.remove( oldPrioNode );

}

PrioTreeNode* newPrioNode = mPrioTree.findOrInsert( prio, true );

idNode->setValue( newPrioNode );

newPrioNode->getValue()->push( idNode );

result = true;

}

return result;

}

void PrioQueue::clear()

{

mIdTree.clear();

mPrioTree.clear();

}

int main( int argc, char** argv )

{

PrioQueue q;

string command;

string id;

int prio;

while ( cin >> command )

{

if ( command.compare( 0, 1, "#" ) == 0 ) continue;

else

if ( command == "add" || command == "ADD" )

{

cin >> id;

cin >> prio;

q.add( id, prio );

}

else

if ( command == "change" || command == "CHANGE" )

{

cin >> id;

cin >> prio;

q.change( id, prio );

}

else

if ( command == "pop" || command == "POP" )

{

if ( q.pop( id, prio ) )

{

cout << id << " " << prio << endl;

}

else

{

cout << "error" << endl;

}

else

if ( command == "clear" || command == "CLEAR" )

{

q.clear();

}

else

if ( command == "exit" || command == "EXIT" )

{

cout << "bye" << endl;

return 0;

}

return 0;

}

Компилировать под Gnu C++ 4.7.1

План программы:

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

Задача решалась в два этапа, сначала был написан вариант с упорядоченным списком, который позволял мгновенный pop, но add и change не удовлетворили тестам на скорость т.к. основывались на поиску путем перебора. Было приято решение использовать алгоритм поиска в двоичном дереве, учитывая, что условия задачи позволяли большой объем памяти.

Текущий вариант основывается шаблонном классе, реализующем двоичное дерево. Очередь содержит два объекта – дерево со строковыми ключами для хранения Id и дерево с числовыми ключами для хранения приоритетов. Каждый узел дерева Id указывает на узел дерева приоритетов. Это позволяет немедленно получить приоритет данного Id без поиска, что необходимо для операции change. В свою очередь, каждый узел дерева приоритетов указывает на узлы дерева Id с данным приоритетом. Это позволяет немедленно определить какой Id надо удалять при выполнении pop. Для обслуживания нескольких Id с равным приоритетом пришлось ввести еще один шаблонный класс – список.

Краткое описание операций

Add
1. Находим или добавляем узел дерева Id (ситуацию если он есть игнорируем по условию задачи)
2. Находим или добавляем узел дерева приоритетов
3. Для узла дерева Id устанавливаем указатель на узел дерева приоритетов
4. Для узла дерева приоритетов добавляем в его список узел дерева Id

Pop
1. Находим узел дерева приоритетов с максимальным ключом
2. Удаляем из списка найденного узла первый попавшийся указатель на узел дерева Id, если список
3. Если список уже пуст, удаляем узел дерева приоритетов

Change
1. Находим узел дерева Id (ситуацию если его нет игнорируем по условию задачи)
2. Берем узел дерева приоритетов, на который указывает узел Id и удаляем из его списка этот узел Id (т.к. приоритет уже будет новый), если список оказался пуст, удаляем также узел приоритета
3. Находим или добавляем узел дерева приоритетов с новым приоритетом и устанавливаем связь с узлом Id как в случае добавления.

Ссылка: http://ideone.com/FROADt

Related Images:

e-olimp 3837. Выражения

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

Задача

Арифметические выражения, как правило, записываются с операторами между двумя операндами (такая запись называется инфиксной нотацией). Например, (x + y) * (z — w) — арифметическое выражение в инфиксной нотации. Однако легче написать программу, вычисляющую значение выражения, когда оно находится в постфиксной нотации (известная как обратная польская нотация). В постфиксной нотации оператор записывается за своими двумя операндами, которые и сами в могут быть выражениями. Например, x y + z w — * является постфиксной нотацией приведенного выше выражения. Заметим, что для такой записи скобки не нужны.

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

push: число кладется на верх стека.
pop: число снимается с вершины стека.

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

a := pop();

b := pop();

push(b O a);

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

Предположим, что мы используем вместо стека очередь. Очередь также имеет операции push иpop, но их смысл немного другой:

push: число вставляется в конец очереди.
pop: из начала очереди извлекается число.

Можете ли Вы переписать заданное выражение так, чтобы алгоритм, использующий очередь при его вычислении, давал тот же результат, что и алгоритм вычисления со стеком?

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

Если задана правильная строка в постфиксной нотации, то алгоритм её вычисления на основе стека выглядит следующим образом:

Просматриваем строку слева направо
Если встречаем переменную, помещаем её в конец стека/очереди
Если встречаем символ оператора * , то выполняем следующие действия: снимаем со стека a, снимаем со стека b и кладём на стек b * a.

По условию задачи, мы должны обрабатывать строки, используя вместо стека очередь, поэтому описанные выше действия примут следующий вид: снимаем с очереди a, снимаем с очереди b и кладём в конец очереди b * a.

Постфиксную запись, рассчитанную на обработку посредством стека, будем называть s-постфиксной, а рассчитанную на обработку очередью — q-постфиксной.

Две записи «вычислятся одинаково» в том и только в том случае, когда соответствующие им деревья синтаксического разбора (англ.: parse tree, далее — ДСР) одинаковы. Идея приведённого ниже алгоритма состоит примерно в следующем: на основе s-постфиксной записи строим ДСР, обходя которое специальным образом, получаем q-постфиксную запись. Нужно обходить дерево по уровням справа налево (под уровнем дерева подразумевается множество всех вершин дерева, равноудалённых от корня; уровни дерева естественным образом нумеруются: корень расположен на уровне 0 и так далее). В приведённом ниже коде функция get_levels генерирует уровни ДСР на основе s-постфиксной нотации в виде вектора строк, k-ая компонента которого соответствует k-му уровню ДСР заданной строки, вершины которого (если таковые имеются) перечислены справа налево. Поскольку у ДСР может быть не больше уровней, чем символов в строке, то создаём вектор как раз с таким числом компонент и инициализируем его компоненты пустыми строками.

Корректность функции get_levels можно доказать индукцией по длине строки, отметим, что если строка содержит более одного элемента, то она имеет вид ФGО, где Ф и G — правильные строки, О — символ оператора. Запустить рекурсивно функцию с предпоследней позиции — всё равно, что применить её к строке G. ДСР этой строки является левым поддеревом для ДСР исходной строки и k-ый уровень этого дерева является (k+1)-ым уровнем ДСР исходной строки (именно поэтому вызываем функцию с параметром depth на 1 больше). По индукционному предположению, дойдя до начала строки G, функция корректно «расставит» уровни ДСР этой строки (с учётом + 1) и завершит свою работу. Аналогично будут правильно расставлены уровни ДСР строки Ф, которое является правым поддеревом исходной строки. Таким образом, все вершины ДСР исходной строки будут правильно расставлены, а поскольку рекурсия вызывается сначала для левого, а потом для правого её поддерева, то и перечислены вершины на каждом уровне будут справа налево.

Код на С++

Ссылка на программу в ideone.

#include <iostream>
#include <string>
#include <vector>

using namespace std;

/* Expr - строка-формула, которую мы обрабатываем
 index - текущий символ в строке Expr
 depth - текущий уровень дерева разбора
 Answer - вектор уровней */

void get_levels(string& Expr, int& index, int depth, vector<string>& Answer) {
	Answer[depth] += Expr[index];
	index--;
	if (isupper(Expr[index+1])) {
		get_levels(Expr, index, depth + 1, Answer);
		get_levels(Expr, index, depth + 1, Answer);
	}
}


int main() {
	int n, index;
	cin >> n;
	string Expr;
	for (int k = 0; k < n; k++) {
		cin >> Expr;						
		vector<string> Answer(Expr.size(), "");
		index = Expr.size() - 1;
		get_levels(Expr, index, 0, Answer);
		for (int k = Expr.size() - 1; k >= 0; k--)
			cout << Answer[k];
		cout << endl;
	}
	return 0;
}

#include <iostream>

#include <string>

#include <vector>

using namespace std;

/* Expr - строка-формула, которую мы обрабатываем

index - текущий символ в строке Expr

depth - текущий уровень дерева разбора

Answer - вектор уровней */

void get_levels(string& Expr, int& index, int depth, vector<string>& Answer) {

Answer[depth] += Expr[index];

index--;

if (isupper(Expr[index+1])) {

get_levels(Expr, index, depth + 1, Answer);

}

int main() {

int n, index;

cin >> n;

string Expr;

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

cin >> Expr;

vector<string> Answer(Expr.size(), "");

index = Expr.size() - 1;

get_levels(Expr, index, 0, Answer);

for (int k = Expr.size() - 1; k >= 0; k--)

cout << Answer[k];

cout << endl;

}

return 0;

}

Код на Java

Ссылка на программу в ideone.

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

class Index {
	int in;
	public Index(int a) {
		in = a;
	}
}

class Main
{
	public static void get_levels(char[] Expr, Index index, int depth, String[] Answer) {
		Answer[depth] += Expr[index.in];
		index.in--;
		if (Character.isUpperCase(Expr[index.in + 1])) {
			get_levels(Expr, index, depth + 1, Answer);
			get_levels(Expr, index, depth + 1, Answer);
		}
	}
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		String str = in.nextLine();

		for (int k = 0; k < n; k++) {
			str = in.nextLine();
			char[] Expr = str.toCharArray();
			String[] Answer = new String[Expr.length];
			Arrays.fill(Answer, "");
			Index index = new Index(Expr.length - 1);
			get_levels(Expr, index, 0, Answer);
			for (int j = Expr.length - 1; j >= 0; j--)
				System.out.print(Answer[j]);
			System.out.println();
		}
	}
}