e-olymp 7241. Transit

06/03/2021 by Дарієнко Дмитро

Задача

Країна Ужляндія має вигідне географічне розташування – її територія знаходиться на перетині важливих торгівельних шляхів. Одним із таких є торгівельний шлях, яким сусідня братська держава доставляє свої унікальні обігрівачі до інших країн.

На кордоні Ужляндії та братської держави, де починається цей шлях, розташований спеціальний пропускний пункт, через який щодня проїжджає потяг із величезною кількістю обігрівачів. Зовсім недавно між урядами двох братських країн було погоджено нові правила транзиту обігрівачів через територію Ужляндії на найближчі $N$ днів. Згідно з новим договором має обратися певне число $m$ – максимальна кількість обігрівачів в одному потязі. Тоді з кожного потяга, що транспортує $A_i$ обігрівачів, буде відвантажено рівно $ A_i -m $ одиниць іноземної продукції (звичайно, якщо $A_i > m$ , інакше ж потяг рухатиметься без зупинок і нічого відвантажено не буде). Власне це й буде плата за проходження потяга територією Ужляндії, вона еквівалентна грошовим витратам на утримання залізничних колій. Сумарна кількість відвантажених в Ужляндії за $N$ днів обігрівачів повинна бути не менша $K$, інакше країна зазнає збитків.

Стала відома кількість обігрівачів у потязі в кожен із $N$ днів (ця інформація надається за умовами контракту). Знайдіть максимальне число $m$, при якому Ужляндія не зазнає економічних збитків.

Формат вхідних даних

В першому рядку записано два числа $N$, $K$ ($1 \leqslant N \leqslant 10^6$, $1 \leqslant K \leqslant 2 \cdot 10^9$). В наступному рядку задано $N$ чисел – кількість обігрівачів у потязі в кожен з $N$ днів, що не перевищує $10^9$.

Формат вихідних даних

В єдиному рядку виведіть одне число – відповідь на задачу, гарантується, що відповідь завжди існує.

Пояснення до прикладу

Всього територією Ужляндії пройде $4$ потяги з $11, 6, 1$ та $8$ обігрівачами відповідно. Щоби країна не знала збитків, потрібно відвантажити не менше $7$ обігрівачів. Очевидно, що максимальне можливе $m$, яке задовольнить цю умову, буде рівне $6$, тоді з потягів буде відвантажено відповідно $5, 0, 0, 2$ обігрівачів, що в сумі дорівнює $7$ і задовольняє умову.

Тести

№	Вхідні дані	Вихідні дані
1	4 7 1 8 6 11	6
2	10 20 1 8 6 11 16 14 21 10 13 4	11
3	5 10 12 4 3 6 9	5
4	6 11 5 8 6 9 4 7	4
5	2 1 2 2	1

Код

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

long N, K;
long* A;

long sum_depending_on_mid(int m) {
    long summ = 0;
    for (int i = 0; i <= N - 1 ; i++) {
        if(A[i] > m) summ += A[i] - m;
    }
    return summ;
}

int main() {
    cin >> N >> K;
    A = new long[N];
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    sort(A, A + N);
    long low = 0;
    long high = A[N - 1];
    long mid = 0;
    while (low != high and sum_depending_on_mid(mid = (low + high) / 2) != K) {
        long past_low = low;
        long past_high = high;
        if (sum_depending_on_mid(mid) < K) {
            high = mid;
        } else low = mid;
        if (past_low == low and past_high == high) {
            cout << mid;
            return 0;
        }
    }
    cout << mid;
    delete[] A;
}

#include <iostream>

#include <algorithm>

using namespace std;

long N, K;

long* A;

long sum_depending_on_mid(int m) {

long summ = 0;

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

if(A[i] > m) summ += A[i] - m;

}

return summ;

}

int main() {

cin >> N >> K;

A = new long[N];

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

cin >> A[i];

}

sort(A, A + N);

long low = 0;

long high = A[N - 1];

long mid = 0;

while (low != high and sum_depending_on_mid(mid = (low + high) / 2) != K) {

long past_low = low;

long past_high = high;

if (sum_depending_on_mid(mid) < K) {

high = mid;

} else low = mid;

if (past_low == low and past_high == high) {

cout << mid;

return 0;

}

cout << mid;

delete[] A;

}

Рішення

Для знаходження числа $m$ я використовував бінарний пошук, перед цим зробивши сортування по зростанню елементів в масиві. Отже, вся задача зводиться до використання бінарного пошуку, та функції яка рахує $\sum\limits_{i=0}^{n-1} A_i — m$, при $A_i > m$ ($m$ — значення mid; $n$ — кількість елементів в масиві; $A_i$ — значення $i$-го елемента масиву). Далі ця сума порівнюється з $K$ для подальшої роботи пошуку та знаходження числа $m$. Якщо такого числа $m$ не існує ми шукаємо найближче, при якому країна не зазнає збитків.

Посилання

Задача на e-olymp.
Код рішення на ideone.
Зараховане на e-olymp.

Related Images:

e-olymp 9407. Слияние строк

18/12/2019 by Даниил Кулык

Задача

Имеются две строки $A$ и $B$.

Ваша задача — найти такую строку $C$, которая содержит в себе и $A$ и $B$ в качестве подстрок и является кратчайшей среди всех таких возможных строк.

Подстрокой строки называется последовательно идущая подпоследовательность этой строки. Например, строка $kbtu$ является подстрокой строки $kbtu open$, но строка $fall$ подстрокой не является.

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

Первая строка содержит строку $A$ $(1 \leqslant |A| \leqslant 10^5)$.

Вторая строка содержит строку $B$ $(1 \leqslant |B| \leqslant 10^5)$.

Гарантируется, что обе строки содержат только строчные латинские буквы.

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

Выведите одну строку $C$.

Тесты

№	Входные данные	Выходные данные
1.	compressing single	compressingle
2.	can you	canyou
3.	compressiondoneright doner	compressiondoneright
4.	details tail	details
5.	essential code	essentialcode

Код

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

int main() 
{
    int n, m, z;
    string a, b, c, d;
    cin>>a; // Вводим строку A
    cin>>b; // Вводим строку B
    d = b; // Строку B будем хранить в переменной d
    n = b.length(); // В переменной n храним длину строки B
    m = a.length(); // В переменной m храним длину строки A
    c = a.substr(m - n, n); // Создаём подстроку
    if(a.find(b) == EOF) // Ищем в строке A строку B
    {
        for (int i = 1; i<=n && b != c; i++) // Удаляем символы в конце первой строки и начале второй, пока они не будут равны
        {
            b.erase(n - i,1);  
            c.erase(0, 1);
        }
        z = c.length(); // В переменной z храним длину подстроки
        d.erase(0,z); // Удаляем из строки B элементы подстроки
        cout << a + d; // Выводим такую строку, которая содержит в себе и A и B
    }
    else cout << a; // Выводим строку A
    return 0;
}

#include <iostream>

#include <string>

using namespace std;

int main()

{

int n, m, z;

string a, b, c, d;

cin>>a; // Вводим строку A

cin>>b; // Вводим строку B

d = b; // Строку B будем хранить в переменной d

n = b.length(); // В переменной n храним длину строки B

m = a.length(); // В переменной m храним длину строки A

c = a.substr(m - n, n); // Создаём подстроку

if(a.find(b) == EOF) // Ищем в строке A строку B

{

for (int i = 1; i<=n && b != c; i++) // Удаляем символы в конце первой строки и начале второй, пока они не будут равны

{

b.erase(n - i,1);

c.erase(0, 1);

}

z = c.length(); // В переменной z храним длину подстроки

d.erase(0,z); // Удаляем из строки B элементы подстроки

cout << a + d; // Выводим такую строку, которая содержит в себе и A и B

}

else cout << a; // Выводим строку A

return 0;

}

Решение

В данной задаче необходимо создать строку $C$, которая будет содержать в себе строки $A$ и $B$. Рассмотрим два варианта решения задачи. Первый – если строка $B$ полностью содержится в строке $A$, то выводим строку $A$. Второй – если строка $B$ содержится в $A$ частично или не содержится вообще, выводим строку $A$ $+$ элементы строки $B$, которых нет в $A$.

Для проверки, находится ли строка $B$ в $A$, воспользуемся функцией find(). Если попадаем в первый вариант решения задачи, то выводим $A$. Иначе, создаём цикл, который будет удалять символы в конце первой строки и символы в начале второй, пока они не будут равны. Затем из строки $B$ удаляем элементы, которые входят в строку $A$, и на выход подаём строку $C$, которая состоит из строки $A$ и оставшихся элементов строки $B$.

Ссылки

Условие задачи на e-olymp
Код программы на ideone.com
Засчитанное решение на e-olymp

Related Images:

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

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

Search Algorithms

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

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

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

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

#include <iostream>

#include <stack>

using namespace std;

int main() {

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

int n, v;

cin >> n >> v;

int matrix[n][n];

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

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

cin >> matrix[i][j];

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

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

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

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

while (!plan.empty()) {

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

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

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

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

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

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

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

}

cout << counter << endl;

}

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

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

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

#include <iostream>

#include <queue>

using namespace std;

int main() {

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

int n, v;

cin >> n >> v;

int matrix[n][n];

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

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

cin >> matrix[i][j];

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

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

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

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

while (!plan.empty()) {

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

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

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

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

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

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

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

}

cout << counter << endl;

}

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

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

Related Images:

e-olymp 12. Поврежденная картина

13/01/2018 by Андрей Святозар Чернецкий

Задача

Римская цифра [latex]I[/latex], стоявшая на полу комнаты в точке с координатами [latex]X_0[/latex], [latex]Y_0[/latex], [latex]0[/latex] не выдержала отношения к решению задачи «Римские цифры» и упала на пол. Поскольку нижний конец был прикреплен шарнирно, то он остался на месте, а верхний оказался в точке с координатами [latex]X_1[/latex], [latex]Y_1[/latex], [latex]0[/latex]. В комнате стояла строго вертикально бумажная картина. Зная координаты концов нижнего основания [latex]X_2[/latex], [latex]Y_2[/latex], [latex]0[/latex] и [latex]X_3[/latex], [latex]Y_3[/latex], [latex]0[/latex] и высоту картины [latex]H[/latex] найти длину «разрыва бумаги» на картине.

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

Во входной строке записано 9 чисел [latex]X_0, Y_0, X_1, Y_1, X_2, Y_2, X_3, Y_3, H[/latex]. Все входные данные — целые числа, модуль которых не превышает [latex]10^9[/latex].

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

Программа выводит единственное число – искомую величину с точностью до [latex]0.001[/latex].

Тесты

Входные данные	Выходные данные
1 1 6 1 4 0 4 5 6	4.000
0 0 6 0 2 0 5 0 5	2.397
2 0 5 0 0 0 6 0 5	4.172
0 0 5 0 2 0 6 0 1	2.058
0 0 10 0 2 0 6 0 1	0.000

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

struct t {
    double x, y;
    t() {
        x = 0;
        y = 0;
    }
    t(double x, double y) {
        this->x = x;
        this->y = y;
    }
    t operator+(t &tt) { return t(this->x + tt.x, this->y + tt.y); }
        
    t operator-(t &tt) { return t(this->x - tt.x, this->y - tt.y); }

    bool operator==(t &p) { return ((x == p.x) && (y == p.y)); }

    bool operator!=(t &p) { return !(*this == p); }

    bool t_is_line_segment(t &t1, t &t2) {
        t t3 = *this;
        t a = t2 - t1;
        t b = t3 - t1;
        double sa = a.x * b.y - b.x * a.y;
        if (sa > 0.0) return false;
        if (sa < 0.0) return false;
        if ((a.x * b.x < 0.0) || (a.y * b.y < 0.0)) return false;
        if (a.length() < b.length()) return false;
        if (t1 == t3) return false;
        if (t2 == t3) return false;
        return true;
    }
    double distance(const t &p) {
        double a = this->x - p.x;
        double b = this->y - p.y;
        return sqrt(a * a + b * b);
    }

    double length(void) { return sqrt(x * x + y * y); }
};

struct line {
    double a, b, c;
    line(const t &t1, const t &t2) {
    a = t1.y - t2.y;
    b = t2.x - t1.x;
    c = t1.x * t2.y - t2.x * t1.y;
    }
};

bool intersect(const line &l1, const line &l2, t &res) {
    if (l1.a * l2.b == l2.a * l1.b)
    return false;
    double g = l1.a * l2.b - l2.a * l1.b;
    res.x = -(l1.c * l2.b - l2.c * l1.b) / g;
    res.y = -(l1.a * l2.c - l2.a * l1.c) / g;
    return true;
}

int main() {

    t x0, x1, x2, x3, m; // m точка пересечения

    double h = 6, answer = 0;

    cin >> x0.x >> x0.y >> x1.x >> x1.y >> x2.x >> x2.y >> x3.x >> x3.y >> h;
    double x0x1_d = x0.distance(x1);
    if (((x3.y - x2.y) * (x0.x - x1.x) - (x3.x - x2.x) * (x0.y - x1.y)) == 0) {
        if (x0.t_is_line_segment(x2, x3)) {
            if (x1.t_is_line_segment(x2, x3)) {
                if (x0x1_d <= h) {
                    answer = M_PI * x0x1_d/2;
                } else {
                    answer = x0x1_d * asin(h / x0x1_d);
                }
            } else {
                if (x2.t_is_line_segment(x1, x3)) { 
                                            if (x0x1_d <= h) answer = x0x1_d * asin(x0.distance(x2) / x0x1_d);
                                            else if (x0x1_d * x0x1_d <= h * h + x0.distance(x2) * x0.distance(x2)){
                                                        answer = x0x1_d * (asin (h / x0x1_d) - acos(x0.distance(x2) / x0x1_d));
                                            }
                                } else {
                                            if (x0x1_d <= h) answer = x0x1_d * asin(x0.distance(x3) / x0x1_d);
                                            else if (x0x1_d * x0x1_d <= h * h + x0.distance(x3) * x0.distance(x3)){
                                                        answer = x0x1_d * (asin (h / x0x1_d) - acos(x0.distance(x3) / x0x1_d));
                                            }
                }
            }
        } else {
            double a;
            if (x1.t_is_line_segment(x2, x3)) {
                a = min(x0.distance(x2), x0.distance(x3));
                if (x0x1_d < sqrt(a * a + h * h)) {
                    answer = x0x1_d * acos(a / x0x1_d);
                } else {
                    answer = x0x1_d * asin(a / x0x1_d);
                }
            } else {
                a = max(x0.distance(x2), x0.distance(x3));
                if (x0x1_d < sqrt(a * a + h * h)) {
                    answer = x0x1_d * (asin(h / x0x1_d) - acos(a / x0x1_d));
                }
            }
        }
    } else {
        line l10(x0, x1), l23(x2, x3);
        if (intersect(l10, l23, m)) {
            if (m.t_is_line_segment(x2, x3)) {
                double x0m_d = m.distance(x0);
                answer = sqrt(x0x1_d * x0x1_d - x0m_d * x0m_d);
                if (answer > h) answer = h;
            }
        }
    }
    cout << fixed << setprecision(3) << answer << endl;
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

#include <cmath>

#include <iomanip>

#include <iostream>

using namespace std;

struct t {

double x, y;

t() {

x = 0;

y = 0;

}

t(double x, double y) {

this->x = x;

this->y = y;

}

t operator+(t &tt) { return t(this->x + tt.x, this->y + tt.y); }

t operator-(t &tt) { return t(this->x - tt.x, this->y - tt.y); }

bool operator==(t &p) { return ((x == p.x) && (y == p.y)); }

bool operator!=(t &p) { return !(*this == p); }

bool t_is_line_segment(t &t1, t &t2) {

t t3 = *this;

t a = t2 - t1;

t b = t3 - t1;

double sa = a.x * b.y - b.x * a.y;

if (sa > 0.0) return false;

if (sa < 0.0) return false;

if ((a.x * b.x < 0.0) || (a.y * b.y < 0.0)) return false;

if (a.length() < b.length()) return false;

if (t1 == t3) return false;

if (t2 == t3) return false;

return true;

}

double distance(const t &p) {

double a = this->x - p.x;

double b = this->y - p.y;

return sqrt(a * a + b * b);

}

double length(void) { return sqrt(x * x + y * y); }

};

struct line {

double a, b, c;

line(const t &t1, const t &t2) {

a = t1.y - t2.y;

b = t2.x - t1.x;

c = t1.x * t2.y - t2.x * t1.y;

}

};

bool intersect(const line &l1, const line &l2, t &res) {

if (l1.a * l2.b == l2.a * l1.b)

return false;

double g = l1.a * l2.b - l2.a * l1.b;

res.x = -(l1.c * l2.b - l2.c * l1.b) / g;

res.y = -(l1.a * l2.c - l2.a * l1.c) / g;

return true;

}

int main() {

t x0, x1, x2, x3, m; // m точка пересечения

double h = 6, answer = 0;

cin >> x0.x >> x0.y >> x1.x >> x1.y >> x2.x >> x2.y >> x3.x >> x3.y >> h;

double x0x1_d = x0.distance(x1);

if (((x3.y - x2.y) * (x0.x - x1.x) - (x3.x - x2.x) * (x0.y - x1.y)) == 0) {

if (x0.t_is_line_segment(x2, x3)) {

if (x1.t_is_line_segment(x2, x3)) {

if (x0x1_d <= h) {

answer = M_PI * x0x1_d/2;

} else {

answer = x0x1_d * asin(h / x0x1_d);

}

} else {

if (x2.t_is_line_segment(x1, x3)) {

if (x0x1_d <= h) answer = x0x1_d * asin(x0.distance(x2) / x0x1_d);

else if (x0x1_d * x0x1_d <= h * h + x0.distance(x2) * x0.distance(x2)){

answer = x0x1_d * (asin (h / x0x1_d) - acos(x0.distance(x2) / x0x1_d));

}

} else {

if (x0x1_d <= h) answer = x0x1_d * asin(x0.distance(x3) / x0x1_d);

else if (x0x1_d * x0x1_d <= h * h + x0.distance(x3) * x0.distance(x3)){

answer = x0x1_d * (asin (h / x0x1_d) - acos(x0.distance(x3) / x0x1_d));

}

} else {

double a;

if (x1.t_is_line_segment(x2, x3)) {

a = min(x0.distance(x2), x0.distance(x3));

if (x0x1_d < sqrt(a * a + h * h)) {

answer = x0x1_d * acos(a / x0x1_d);

} else {

answer = x0x1_d * asin(a / x0x1_d);

}

} else {

a = max(x0.distance(x2), x0.distance(x3));

if (x0x1_d < sqrt(a * a + h * h)) {

answer = x0x1_d * (asin(h / x0x1_d) - acos(a / x0x1_d));

}

} else {

line l10(x0, x1), l23(x2, x3);

if (intersect(l10, l23, m)) {

if (m.t_is_line_segment(x2, x3)) {

double x0m_d = m.distance(x0);

answer = sqrt(x0x1_d * x0x1_d - x0m_d * x0m_d);

if (answer > h) answer = h;

}

cout << fixed << setprecision(3) << answer << endl;

return 0;

}

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

Эта задача интересна тем, что для ее решения необходимо смоделировать большое количество разнообразных взаиморасположений картины и буквы. Далее будут использоваться следующие обозначения: [latex]X_0[/latex]- основание буквы, [latex]X_1[/latex] — ее вершины, [latex]X_2[/latex] и [latex]X_3[/latex] — координаты основания картины, [latex]H[/latex] — высота картины.

1. [latex]X_0 X_1[/latex] и [latex]X_2 X_3[/latex] лежат на одной прямой

1.1. [latex]X_0[/latex] принадлежит [latex]X_2[/latex][latex]X_3[/latex]

1.1.1. [latex]X_1[/latex]принадлежит [latex]X_2[/latex][latex]X_3[/latex]

1.1.1.1 [latex]X_0[/latex][latex]X_1[/latex] не превышает [latex]H[/latex]

В таком случае искомая величина — дуга [latex]O X1[/latex], равная [latex]\frac{1}{4} [/latex] длины окружности с радиусом, равным высоте буквы: [latex]O[/latex][latex]X_1[/latex] = [latex]\frac{П\times X_0 X_1}{2} [/latex]

1.1.1.2 [latex]X_0[/latex][latex]X_1[/latex] больше, чем [latex]H[/latex]

в таком случае нам необходимо найти дугу [latex]NX_1[/latex],для этого умножив радиус на величину центрального угла: [latex]NX_1[/latex] =[latex]X_0 X_1 \times \arcsin \frac {H}{X_0 X_1}[/latex]

1.1.2 [latex]X_1[/latex] не принадлежит [latex]X_2 X_3[/latex]

1.1.2.1.[latex]X_2[/latex] принадлежит [latex]X_0 X_1[/latex]

1.1.2.1.1. [latex]X_0 X_1[/latex] не превышает [latex]H[/latex]

В таком случае нам нужно найти дугу [latex]OM[/latex] по схожему с случаем 1.1.1.2 алгоритму: [latex]OM[/latex] = [latex]X_0 X_1 \times \arcsin \frac{X_0 X_3} {X_0 X_1} [/latex]

1.1.2.1.2. [latex]X_0[/latex][latex]X_1[/latex] больше [latex]H[/latex]

1.1.2.1.2.1. [latex]X_0 X_1 < \sqrt{X_0 X_2^2 + H^2} [/latex]

В таком случае искомая величина равна дуге [latex]MN[/latex]= [latex]X_0 X_1 \times (\arcsin \frac{H}{X_0 X_1} — \arccos \frac{X_0 X_3} {X_0 X_1}))

1.1.2.2. данный случай аналогичен предыдущему.Единственное различие заключается в том,что точки [latex]X_2[/latex] и [latex]X_3[/latex] меняются местами в формулах.

1.2 [latex]Х_0[/latex] не принадлежит [latex]X_2[/latex][latex]X_3[/latex]

1.2.1 [latex]X_1[/latex]принадлежит [latex]X_2[/latex][latex]X_3[/latex]

введем новую переменную [latex]A[/latex], равную расстоянию от [latex]X_0[/latex] до картины.

1.2.1.1 [latex]X_0 X_1[/latex] меньше, чем [latex]\sqrt{A^2 + H^2}[/latex]

В данном случае нам нужно найти дугу [latex]M X_1[/latex] = [latex]X_0 X_1 \times \arccos \frac{A}{X_0 X_1}[/latex]

1.2.1.2 [latex]X_0[/latex][latex]X_1[/latex] не меньше, чем [latex]\sqrt{A^2 + H^2}[/latex]

в этом случае нам нужно найти дугу [latex]МХ_1[/latex]= [latex]X_0 X_1 \times \arcsin \frac{A}{X_0 X_1}[/latex]

1.2.2. обе вершины цифры не принадлежат картине

Обозначим через [latex]A[/latex] расстояние от [latex]X_0[/latex] до дальней вершины картины.

1.2.2.1. [latex]X_0 X_1 < \sqrt{A^2 + H^2} [/latex]

Искомая величина — дуга [latex]MN[/latex] = [latex]X_0 X_1\times (\arcsin \frac{H}{X_0 X_1} — \arccos \frac{A}{X_0 X_1})[/latex]

2. [latex]X_0 X_1[/latex] и [latex]X_2 X_3[/latex] не лежат на одной прямой

2.1. [latex]X_0 X_1[/latex] пересекает [latex]X_2 X_3[/latex]

В этом случае длина разрыва будет равна длине отрезка [latex]MN[/latex] либо высоте картины, если она окажется меньше вышеупомянутого отрезка.

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

Ссылки

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

Related Images:

Черная пятница

06/04/2017 by Курьянов Павел

Разбор задачи с 1/8 ACM ICPC по украинскому региону 25 марта 2017.

Задача. Завтра черная пятница — самая большая новогодняя распродажа. Степан, как владелец магазина, принял решение, что цены всех товаров будет снижено на 25%. Он выяснил, что начальные цены на все товары делились на 4, поэтому после снижения цен все цены тоже выражаются целым числом. Степан вечером перед распродажей снял ценники с всех товаров и напечатал для каждого товара еще один ценник со скидкой. Он оставил их на столе, рассчитывая утром их развесить. Но, когда он пришел утром в магазин, то выяснилось, что уборщица смешала все ценники вместе, и теперь Степану нужно отделить старые ценники от новых.
Помогите ему.
Входные данные:
Первый ряд входного файла содержит одно число N (2 ≤ N ≤ 105), N — четное. Следующие N рядов содержат положительные числа не больше чем 109, которые идут в порядке возрастания по одному в ряду — числа со всех ценников (как старых так и новых). Гарантируется, что входные данные корректны, то есть решение существует.
Выходные данные:
Вывести N/2 целых числе в порядке возрастания — стоимость товаров после снижения цен.

Тесты

входные данные	результат работы
6	30
30	40
40	45
42
45
56
60

Код задачи

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

int main() {
    long long n;
    cin>>n;
    long long x[n];
    for(int i=0;i<n;i++)
    {
        cin>>x[i];
    }
    int ind=0;
    for(int i=0;i<n-1;i++)
    {
        if(x[i]!=0)
        {
            ind=find(x+ind,x+n,x[i]*4/3)-x;
                cout<<x[i]<<'\n';
                x[ind]=0;
        }
    }
    return 0;
}

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

long long n;

cin>>n;

long long x[n];

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

{

cin>>x[i];

}

int ind=0;

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

{

if(x[i]!=0)

{

ind=find(x+ind,x+n,x[i]*4/3)-x;

cout<<x[i]<<'\n';

x[ind]=0;

}

return 0;

}

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

Related Images:

e-olymp 1060. Линии

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

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

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

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

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

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

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

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

Тесты

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

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

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

....X

.OOOO

.....

OOOO.

@....

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

+++++

+OOOO

+++++

OOOO+

@++++

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

..X..

.....

OOOOO

.....

..@..

N

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

...X.

.....

O.OOO

.....

....@

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

..++.

.++..

O+OOO

.++++

....@

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

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

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

100

101

102

103

104

105

106

107

#include <iostream>

#include <queue>

using namespace std;

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

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

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

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

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

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

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

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

plan.push(row+1);

plan.push(col);

}

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

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

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

plan.push(row-1);

plan.push(col);

}

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

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

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

plan.push(row);

plan.push(col+1);

}

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

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

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

plan.push(row);

plan.push(col-1);

}

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

}

int main() {

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

queue <int> plan;

cin >> n;

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

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

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

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

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

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

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

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

visited[i][j] = 0;

path[i][j] = -1;

cin >> lab[i][j];

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

x_start = i;

y_start = j;

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

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

path[i][j] = 1;

}

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

x_end = i;

y_end = j;

}

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

x=plan.front();

plan.pop();

y=plan.front();

plan.pop();

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

}

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

cout << "N" << endl;

}

else {

cout << "Y" << endl;

x = x_end;

y = y_end;

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

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

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

x = x-1;

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

}

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

x = x+1;

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

}

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

y = y-1;

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

}

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

y = y+1;

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

}

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

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

cout << lab[i][j];

}

cout << endl;

}

return 0;

}

ideone.com

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

Решение

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

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

Related Images:

e-olimp 2907. Можете ли Вы ответить на эти вопросы — 3

24/06/2016 by Таня Корнилова

Условие

Задана последовательность целых чисел [latex]a_1, a_2, \ldots, a_n[/latex] ([latex]| a_i | \le 10000[/latex], [latex]1 \le n \le 50000[/latex]). Над ней Вам следует выполнить [latex]m[/latex] ([latex]m \le 50000[/latex]) операций:

модифицировать [latex]i[/latex]-ый элемент последовательности
для заданных [latex]x[/latex] и [latex]y[/latex] вывести [latex]MAX[/latex] [latex]\{ a_i + a_{i+1} + \ldots + a_j[/latex], [latex]x \le i \le j \le y \}[/latex]

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

Первая строка содержит значение n. Следующая строка содержит n целых чисел, задающих последовательность [latex]a_1, a_2, \ldots, a_n[/latex]. Третья строка содержит число [latex]m[/latex]. Следующие [latex]m[/latex] строк содержат запросы вида:

[latex]0[/latex] [latex]x[/latex] [latex]y[/latex]: изменить [latex]a_x[/latex] на [latex]y[/latex] ([latex]| y | \le 10000[/latex]).
[latex]1[/latex] [latex]x[/latex] [latex]y[/latex]: вывести [latex]MAX[/latex] [latex]\{ a_i + a_{i+1} + \ldots + a_j, x \le i \le j \le y \}[/latex]

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

    #include <iostream>
    #include <cmath>
    using namespace std;
    struct data {
        int sum, pref, suff, ans;
    };
    data combine (data l, data r) {
        data res;
        res.sum = l.sum + r.sum;
        res.pref = max (l.pref, l.sum + r.pref);
        res.suff = max (r.suff, r.sum + l.suff);
        res.ans = max (max (l.ans, r.ans), l.suff + r.pref);
        return res;
    }
    data make_data (int val) {
        data res;
        res.sum = val;
        res.pref = res.suff = res.ans = val;
        return res;
    }
    void build (int a[], int v, int tl, int tr, data t[]) {
        if (tl == tr)
            t[v] = make_data (a[tl]);
        else {
            int tm = (tl + tr) / 2;
            build (a, v*2, tl, tm, t);
            build (a, v*2+1, tm+1, tr, t);
            t[v] = combine (t[v*2], t[v*2+1]);
        }
    }
    void update (int v, int tl, int tr, int pos, int new_val, data t[]) {
        if (tl == tr)
            t[v] = make_data (new_val);
        else {
            int tm = (tl + tr) / 2;
            if (pos <= tm)
                update (v*2, tl, tm, pos, new_val, t);
            else
                update (v*2+1, tm+1, tr, pos, new_val, t);
            t[v] = combine (t[v*2], t[v*2+1]);
        }
    }
    data query (int v, int tl, int tr, int l, int r, data t[]) {
        if (l == tl && tr == r)
            return t[v];
        int tm = (tl + tr) / 2;
        if (r <= tm)
            return query (v*2, tl, tm, l, r, t);
        if (l > tm)
            return query (v*2+1, tm+1, tr, l, r, t);
        return combine (
            query (v*2, tl, tm, l, tm, t),
            query (v*2+1, tm+1, tr, tm+1, r, t)
        );
    }
     
    int main() {
        int n, m, x, y;
        cin >> n;
        int* a = new int[n];
        for(int i = 0; i < n; i++) {
            cin >> a[i];
        }
        data* t = new data[4*n];
        build(a, 1, 0, n-1, t);
        cin >> m ;
        bool oper;
        for(int i = 0; i < m; i++) {
            cin >> oper >> x >> y;
            if(!oper) {
                update (1, 0, n-1, x-1, y, t);
            } else if(oper) {
                cout << query (1, 0, n-1, x-1, y-1, t).ans << endl;
     
            }
        }
        return 0;
    }

#include <iostream>

#include <cmath>

using namespace std;

struct data {

int sum, pref, suff, ans;

};

data combine (data l, data r) {

data res;

res.sum = l.sum + r.sum;

res.pref = max (l.pref, l.sum + r.pref);

res.suff = max (r.suff, r.sum + l.suff);

res.ans = max (max (l.ans, r.ans), l.suff + r.pref);

return res;

}

data make_data (int val) {

data res;

res.sum = val;

res.pref = res.suff = res.ans = val;

return res;

}

void build (int a[], int v, int tl, int tr, data t[]) {

if (tl == tr)

t[v] = make_data (a[tl]);

else {

int tm = (tl + tr) / 2;

build (a, v*2, tl, tm, t);

build (a, v*2+1, tm+1, tr, t);

t[v] = combine (t[v*2], t[v*2+1]);

}

void update (int v, int tl, int tr, int pos, int new_val, data t[]) {

if (tl == tr)

t[v] = make_data (new_val);

else {

int tm = (tl + tr) / 2;

if (pos <= tm)

update (v*2, tl, tm, pos, new_val, t);

else

update (v*2+1, tm+1, tr, pos, new_val, t);

t[v] = combine (t[v*2], t[v*2+1]);

}

data query (int v, int tl, int tr, int l, int r, data t[]) {

if (l == tl && tr == r)

return t[v];

int tm = (tl + tr) / 2;

if (r <= tm)

return query (v*2, tl, tm, l, r, t);

if (l > tm)

return query (v*2+1, tm+1, tr, l, r, t);

return combine (

query (v*2, tl, tm, l, tm, t),

query (v*2+1, tm+1, tr, tm+1, r, t)

);

}

int main() {

int n, m, x, y;

cin >> n;

int* a = new int[n];

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

cin >> a[i];

}

data* t = new data[4*n];

build(a, 1, 0, n-1, t);

cin >> m ;

bool oper;

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

cin >> oper >> x >> y;

if(!oper) {

update (1, 0, n-1, x-1, y, t);

} else if(oper) {

cout << query (1, 0, n-1, x-1, y-1, t).ans << endl;

}

return 0;

}

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

Ссылка на использованный алгоритм.

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

Related Images:

AL15. Лабиринт

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

Условие

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

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

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

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

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

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

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

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

Замечания

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

C++

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

1

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

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

Тесты

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

Алгоритм

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

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

За поиск маршрута отвечают 2 функции. Функция

stack<pair<int,int>> findRoute(int n, int m, int** matrix, int begin)

1	stack<pair<int,int>> findRoute(int n, int m, int** matrix, int begin)

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

bool search(int n, int m, int** matrix, stack<pair<int,int>>& route, int dir)

1	bool search(int n, int m, int** matrix, stack<pair<int,int>>& route, int dir)

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

Находим, в какую клетку мы попали при данном направлении. Определим все направления как подходящие константы и будем получать направление по формуле [latex]dir / 10, dir \mod 10[/latex], первая координата — по вертикали, вторая — по горизонтали. Так, например, для [latex]down = 10[/latex] получим вектор [latex](1, 0)[/latex], соответствующий перемещению на одну ячейку вниз в матрице (для остальных направлений значения подобраны аналогично).
Проверяем, можем ли мы находиться в этой ячейке, если нет (она занята или находится вне матрицы) — не ищем дальше, возвращаем [latex]false[/latex].
Добавляем координаты ячейки в стек route, проверяем, является ли данная точка выходом, если да — завершаем поиск успешно ([latex]true[/latex]).
Составим массив направлений, от наиболее до наименее приоритетных, в зависимости от предыдущего направления. Например, текущее направление было [latex]down[/latex], мы пришли сверху, лучше всего будет попробовать пойти влево, иначе снова вниз, иначе вправо, наверх нельзя (уже были):

C++

priorityDirs = new int[3]{left, down, right};

42

priorityDirs = new int[3]{left, down, right};

Для других направлений — рассуждения аналогичны.
Поочередно вызовем поиск из новой точки в каждом из направлений в порядке приоритета, при нахождении пути оставшиеся направления (с меньшим приоритетом) не рассматриваем, возвращаем [latex]true[/latex].
Если ни в одном из направлений нельзя попасть к выходу (тупик) — удаляем вершину из стека, возвращаем [latex]false[/latex].

Код

#include <iostream>
#include <stack>
#include <utility>
#define down 10
#define left -1
#define right 1
#define up -10
using namespace std;

void print(int n, int m, int** matrix)
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (matrix[i][j] == 0 || matrix[i][j] == 1)
                cout << matrix[i][j] << " ";
            else
                cout << (char)matrix[i][j] << " ";
        }
        cout << endl;
    }
}

bool search(int n, int m, int** matrix, stack<pair<int,int>>& route, int dir)
{
    pair<int, int> npos = make_pair(dir / 10 + route.top().first, dir % 10 + route.top().second);
    if (npos.first < 0 || npos.first >= n || npos.second < 0 || npos.second >= m || matrix[npos.first][npos.second] != 0)
        return false;
    else
    {
        route.push(npos);
        matrix[npos.first][npos.second] = 1; //чтобы при построении маршрута нельзя было вернутся в предыдущие вершины
        if (npos.first == n - 1)
            return true;
        else
        {
            int* priorityDirs;
            switch (dir)
            {
                case down:
                    priorityDirs = new int[3]{left, down, right};
                    break;
                case left:
                    priorityDirs = new int[3]{left, down, up};
                    break;
                case right:
                    priorityDirs = new int[3]{down, right, up};
                    break;
                case up:
                    priorityDirs = new int[3]{left, right, up};
                    break;
            }
            bool found = true;
            for (int i = 0; i < 3; i++)
            {
                found = search(n, m, matrix, route, priorityDirs[i]);
                if (found)
                    return true;
            }
            matrix[npos.first][npos.second] = 0; //если ячейка не подходит, убираем ее из маршрута (освобождаем)
            route.pop();
            return false;
        }
    }
}

stack<pair<int,int>> findRoute(int n, int m, int** matrix, int begin)
{
    stack<pair<int,int>> route;
    route.push(make_pair(0, begin));
    if (n != 1 && !search(n, m, matrix, route, down)) //n != 1 для корректного ответа на тесты вида №10
        throw -1;
    return route;
}

int main() 
{
    ios::sync_with_stdio(false);
    int n, m;
    scanf("%d%d", &n, &m);
    int** matrix = new int*[n];
    for (int i = 0; i < n; i++)
        matrix[i] = new int[m];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            scanf("%d", &matrix[i][j]);
    bool possible = true;
    int symbol = -1; //определяет символ, которым будет отмечен маршрут человека при необходимости вывода лабиринта на экран
    for (int i = 0; i < m; i++)
    {
        if (matrix[0][i] == 0)
        {
            symbol++;
            try
            {
                stack<pair<int,int>> route = findRoute(n, m, matrix, i);
                while (!route.empty()) //вынимаем из стека координаты пройденных ячеек и отмечаем их в матрице
                {
                    pair<int, int> pos = route.top(); 
                    matrix[pos.first][pos.second] = 'a' + symbol; //для удобства при необходимости вывода маршрута
                    route.pop();
                }
            }
            catch (...)
            {
                possible = false;
                break;
            }
        }
    }
    cout << (possible ? "YES" : "NO") << endl;
    /*
    if (possible)
        print(n, m, matrix);
    */
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

#include <iostream>

#include <stack>

#include <utility>

#define down 10

#define left -1

#define right 1

#define up -10

using namespace std;

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

{

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

{

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

{

if (matrix[i][j] == 0 || matrix[i][j] == 1)

cout << matrix[i][j] << " ";

else

cout << (char)matrix[i][j] << " ";

}

cout << endl;

}

bool search(int n, int m, int** matrix, stack<pair<int,int>>& route, int dir)

{

pair<int, int> npos = make_pair(dir / 10 + route.top().first, dir % 10 + route.top().second);

if (npos.first < 0 || npos.first >= n || npos.second < 0 || npos.second >= m || matrix[npos.first][npos.second] != 0)

return false;

else

{

route.push(npos);

matrix[npos.first][npos.second] = 1; //чтобы при построении маршрута нельзя было вернутся в предыдущие вершины

if (npos.first == n - 1)

return true;

else

{

int* priorityDirs;

switch (dir)

{

case down:

priorityDirs = new int[3]{left, down, right};

break;

case left:

priorityDirs = new int[3]{left, down, up};

break;

case right:

priorityDirs = new int[3]{down, right, up};

break;

case up:

priorityDirs = new int[3]{left, right, up};

break;

}

bool found = true;

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

{

found = search(n, m, matrix, route, priorityDirs[i]);

if (found)

return true;

}

matrix[npos.first][npos.second] = 0; //если ячейка не подходит, убираем ее из маршрута (освобождаем)

route.pop();

return false;

}

stack<pair<int,int>> findRoute(int n, int m, int** matrix, int begin)

{

stack<pair<int,int>> route;

route.push(make_pair(0, begin));

if (n != 1 && !search(n, m, matrix, route, down)) //n != 1 для корректного ответа на тесты вида №10

throw -1;

return route;

}

int main()

{

ios::sync_with_stdio(false);

int n, m;

scanf("%d%d", &n, &m);

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

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

matrix[i] = new int[m];

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

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

scanf("%d", &matrix[i][j]);

bool possible = true;

int symbol = -1; //определяет символ, которым будет отмечен маршрут человека при необходимости вывода лабиринта на экран

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

{

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

{

symbol++;

try

{

stack<pair<int,int>> route = findRoute(n, m, matrix, i);

while (!route.empty()) //вынимаем из стека координаты пройденных ячеек и отмечаем их в матрице

{

pair<int, int> pos = route.top();

matrix[pos.first][pos.second] = 'a' + symbol; //для удобства при необходимости вывода маршрута

route.pop();

}

catch (...)

{

possible = false;

break;

}

cout << (possible ? "YES" : "NO") << endl;

if (possible)

print(n, m, matrix);

return 0;

}

Ссылки

Код для тестирования на ideone.

Related Images:

MLoop 2

02/11/2015 by Женя Максимова

Задача. Используйте метод хорд для того, чтобы отыскать с точностью [latex]\varepsilon[/latex] все действительные корни уравнения [latex]\frac{x}{2 \cdot \sin x +1}=\tan(\ln(x^2+1))[/latex]. Для подготовки необходимых графиков воспользуйтесь этим ресурсом.

Тесты(найдено с помощью математической системы WolframAlpha):

[latex]A[/latex]

[latex]B[/latex]

[latex]x\approx[/latex]

-20

-11.6945378230838209122818536587051434153…

-1.25741503276862309237205903178504130394…

0.547316310185252929580383582338832450320…

10.9948442206261587135425985750810372810…

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

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

const int max_iterations=100;
const double interval = 0.001;  // interval length for roots subdivision
bool is_root = false;  // is false if function has a second type break in root candidate point
double delta; //precision of root search
double A, B;

double f(double x)//our function
{
 double r = DBL_MAX;
 try
  {
   r =  x / (2*sin(x)+1) - tan(log(x*x+1));  
  }
 catch(...)
  {
   //nothing to do for arithmetic exception
  }
 return r;
}

bool is_change_sign(double fa, double fb)
{
 return fa*fb<0;
}

double find_root(double a, double b, double delta,  bool *yes)
{
 double fa;
 double fb;
 double fc;
 double c;
 int l=0;
 fa=f(a);
 fb=f(b);
 double dy,dy1; //old and new OY projections of chord
 dy=fabs(fa-fb);
 dy1=DBL_MAX;
 while(true)
   {
    l++;
    if(l > max_iterations)
      {
       *yes=false;
       return (a+b)/2;
      }
    c = a - (b - a) * fa/(fb - fa);
    fc = f(c);
    if(fa*fc>0)
      {
       a=c;
       fa=fc;
      }
    else
      {
       b=c;
       fb=fc;
      }
    if(fabs(fa)<delta)
      {
       *yes=true;
       return a;
      }
    if(fabs(fb)<delta)
      {
       *yes=true;
       return b;
      }
    if(l>10) //there's a magic number, we must check conditions of break or stop after some iterations(some = 10)
      {
       if(dy1>dy) //checking if there's break of second kind(pole)
         {
          *yes=false;
          return (a+b)/2;
         }
       if(fabs(b-a)<delta) //else we are near the root
         {
          *yes=true;
          return (a+b)/2;
         }
      }
    dy=dy1; //change old chord height
    dy1=fabs(fa-fb); //calculate new chord height
   }
 // we can't get here
 *yes=false;
 return c;
}

int main()
{
 scanf("%lf %lf %lf",&A,&B,&delta);
 double a,b;
 double fa, fb;
 /*
 test interval for finding roots
 int k=2;
 A= sqrt(exp(M_PI*(1/2.0+k))-1)-M_PI;//70010637.8772-10;
 B= sqrt(exp(M_PI*(1/2.0+k))-1)+M_PI;//70010637.8772+10;
 delta = 1e-12;
 printf("A=%20.19g A=%20.19g delta=%20.19g \n",A,B,delta);
 */
 fb = f(A);
 for(a = A, b = A + interval; b<=B; a += interval, b += interval)
  {
   fa = fb;
   fb = f(b);
   if(is_change_sign(fa,fb))
     {
      double r=find_root(a,b,delta, &is_root);
      if(is_root)
       {
        printf("%14.15lf \n",r);
       }
     }
  }
 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

#include <stdio.h>

#include <math.h>

#include <iostream>

#include<cfloat>

using namespace std;

const int max_iterations=100;

const double interval = 0.001; // interval length for roots subdivision

bool is_root = false; // is false if function has a second type break in root candidate point

double delta; //precision of root search

double A, B;

double f(double x)//our function

{

double r = DBL_MAX;

try

{

r = x / (2*sin(x)+1) - tan(log(x*x+1));

}

catch(...)

{

//nothing to do for arithmetic exception

}

return r;

}

bool is_change_sign(double fa, double fb)

{

return fa*fb<0;

}

double find_root(double a, double b, double delta, bool *yes)

{

double fa;

double fb;

double fc;

double c;

int l=0;

fa=f(a);

fb=f(b);

double dy,dy1; //old and new OY projections of chord

dy=fabs(fa-fb);

dy1=DBL_MAX;

while(true)

{

l++;

if(l > max_iterations)

{

*yes=false;

return (a+b)/2;

}

c = a - (b - a) * fa/(fb - fa);

fc = f(c);

if(fa*fc>0)

{

a=c;

fa=fc;

}

else

{

b=c;

fb=fc;

}

if(fabs(fa)<delta)

{

*yes=true;

return a;

}

if(fabs(fb)<delta)

{

*yes=true;

return b;

}

if(l>10) //there's a magic number, we must check conditions of break or stop after some iterations(some = 10)

{

if(dy1>dy) //checking if there's break of second kind(pole)

{

*yes=false;

return (a+b)/2;

}

if(fabs(b-a)<delta) //else we are near the root

{

*yes=true;

return (a+b)/2;

}

dy=dy1; //change old chord height

dy1=fabs(fa-fb); //calculate new chord height

}

// we can't get here

*yes=false;

return c;

}

int main()

{

scanf("%lf %lf %lf",&A,&B,&delta);

double a,b;

double fa, fb;

test interval for finding roots

int k=2;

A= sqrt(exp(M_PI*(1/2.0+k))-1)-M_PI;//70010637.8772-10;

B= sqrt(exp(M_PI*(1/2.0+k))-1)+M_PI;//70010637.8772+10;

delta = 1e-12;

printf("A=%20.19g A=%20.19g delta=%20.19g \n",A,B,delta);

fb = f(A);

for(a = A, b = A + interval; b<=B; a += interval, b += interval)

{

fa = fb;

fb = f(b);

if(is_change_sign(fa,fb))

{

double r=find_root(a,b,delta, &is_root);

if(is_root)

{

printf("%14.15lf \n",r);

}

return 0;

}

Алгоритм

Для начала запишем данное нам уравнение в виде функции [latex]y=f(x)[/latex] и построим ее график:

[latex]y=\frac{x}{2 \cdot sin x +1}-tan(ln(x^2+1))[/latex]

Задача о нахождении приближённых значений действительных корней уравнения [latex]f(x)=0[/latex] предусматривает предварительное отделение корня, то есть установление интервала, в котором других корней данного уравнения нет.

Метод хорд предусматривает замену функции на интервале на секущую, и поиск ее пересечения с осью [latex]OX[/latex]. На заданном интервале [latex][a,b][/latex] с точностью [latex]\varepsilon[/latex] корень будет вычисляться согласно итерационному выражению, которое имеет вид:

[latex]x_{i+1}=x_{i-1}-\frac{f(x_{i-1}) \cdot (x_{i}-x_{i-1})}{f(x_{i})-f(x_{i-1}) ) }[/latex]

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

В точке, где находится предполагаемый корень, имеется разрыв второго рода. Здесь метод хорд обнаруживает перемену знака и начинает сужать отрезок. Однако расстояние между крайними точками отрезка не уменьшается, а увеличивается. А именно увеличивается проекция отрезка на ось [latex]OY[/latex]. И чем ближе мы находимся к точке разрыва, тем она больше, а в самой точке стремится к бесконечности. В качестве примера приведем функцию [latex]\frac{(x-5)^2}{x-4}[/latex], имеющую разрыв второго рода в точке [latex]x=4[/latex].
Аналогичный случай — точка разрыва первого рода, где наша хорда стремится к некоторой константе — величине разрыва. Пример — функция [latex]\frac{\sin x\cdot(x-2.5)}{\left | x-2,5 \right |}[/latex], имеющая разрыв первого рода в точке [latex]x=2,5[/latex].
Функция не является разрывной и даже имеет корень, однако в точке корня производная стремится к бесконечности. Например, функция [latex]\sqrt[3]{x-1,2}[/latex], имеющая корень в точке [latex]x=1,2[/latex]. Для функций подобного рода длина проекции отрезка на ось [latex]OY[/latex] будет очень медленно меняться, вследствие чего для разумного числа итераций она будет превосходить заранее выбранную точность [latex]\varepsilon[/latex].

Функция равна нулю или очень близка к нулю на некотором интервале(например, функция [latex]y=rect(x-1,5)\cdot(x-1)\cdot(x-2)^2[/latex]). Здесь метод хорд найдет пересечение с осью [latex]OX[/latex] в интервале, где находятся корни(одна из сторон отрезка будет корнем), но все последующие итерации будут выдавать эту же точку. Поэтому хорда не будет уменьшаться, и даже этот один корень не будет найден(если будет использоваться стандартная [latex]\delta[/latex]-оценка точности по оси [latex]OX[/latex]).

Функция вида [latex]y=x^{2k}[/latex] или ей подобная, например, [latex]y=1+\sin x[/latex], к которой метод хорд вообще не применим, так как нарушается начальное условие применимости этого метода. Здесь нужно ввести дополнительную проверку. Изменим значение функции на небольшую константу — нашу точность [latex]\varepsilon[/latex] и повторим процедуру поиска корней. В результате мы получим [latex]2k[/latex] корней, каждую пару из которых мы можем считать краями интервала, в котором лежит настоящий корень.

К счастью, в данной нам функции присутствует только один из этих случаев, а именно разрыв второго рода. Аналитически рассмотрев нашу функцию, мы обнаружили, что корни следует искать в окрестности точек[latex]\sqrt{e^{\frac{\pi}{2}+\pi \cdot k}-1}[/latex] с отклонением [latex]\pm\pi[/latex]. В корнях функции ее производная быстро растет с ростом [latex]k[/latex].

Критерием отбрасывания кандидата на корень будет рост длины хорды при сужении интервала. Критерием останова будет сужение интервала до заданной точности [latex]\delta[/latex].
Код программы

Related Images:

e-olymp 4850. Шайтан-машинка

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

Условие

У Ибрагима есть магическая чёрная шайтан-машинка. На ней есть три кнопки и табло. Табло может показывать не более чем четырёхзначные числа. Каждая из кнопок меняет число некоторым образом: первая домножает его на [latex]3[/latex], вторая прибавляет к нему сумму его цифр, а третья вычитает из него [latex]2[/latex]. В случае, если число становится отрицательным или превосходит [latex]9999[/latex], шайтан-машинка ломается.

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

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

В одной строке находится два натуральных числа [latex]a[/latex] и [latex]b[/latex] latex[/latex].

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

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

Задача
Зачтённое решение

Код

Ideone

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <iostream>

using namespace std;

int sum_n (int n){ //подсчёт суммы цифер в числе
    int res = n/1000 + (n%1000-n%100)/100 + (n%100-n%10)/10 + n%10;
    return res;
}

bool was [10000]; //массив использованных вершин.
int vertex[10000]; //подсчёт кол-ва пройденных рёбер..
queue<int> q; //очередь для BFS

//BFS
void bfs (int start, int finish){
    if (start==finish){  //если мы сразу попали в нужную вершину - выходим из программы.
        cout << 0 << endl;
        return;
    }
    else {
        for (int i=0; i<10000; i++){ //предположим, что расстояние до любой вершины = 1
            vertex[i]=1;
        }
        q.push (start); //будем рассматривать каждую вершину
        was[start] = true;
        while (!q.empty()){
            int tmp = q.front(); //рассматриваемая вершина
            q.pop();
            int tmp1 = tmp;
            tmp1 *= 3; //"ребёнок" рассматриваемой вершины, со значением родителбской вершины *3.
            if (!was[tmp1]){
                if (tmp1 == finish){//если финиш, то выводим длину пути до вершины.
                    cout << vertex[tmp] << endl;
                    return;
                }
                else if (tmp1 < 10000 && tmp1>=0){
                    was[tmp1] = true;//иначе помечаем вершину, как пройденную и засовываем её в очередь на рассмотрение
                    q.push(tmp1);
                    vertex[tmp1]=vertex[tmp]+1;//и прибавляем 1 к длине пути.
                }
            }
            //действия повторяются для других операций.
            tmp1=tmp;
            tmp1 += sum_n(tmp1);
            if (!was[tmp1]){
                if (tmp1 == finish){
                    cout << vertex[tmp] << endl;
                    return;
                }
                else if (tmp1 < 10000 && tmp1>=0){
                    was[tmp1] = true;
                    vertex[tmp1]=vertex[tmp]+1;
                    q.push(tmp1);
                }
            }
            tmp1=tmp;
            tmp1 -= 2;
            if (!was[tmp1]){
                if (tmp1 == finish){
                    cout << vertex[tmp] << endl;
                    return;
                }
                else if (tmp1 < 10000 && tmp1>=0){
                    was[tmp1] = true;
                    vertex[tmp1]=vertex[tmp]+1;
                    q.push(tmp1);
                }
            }
        }
    }
}

int main() {
    int a, b;
    cin >> a >> b; //ввод начала и конца
    bfs (a, b);//процедура выполнения
    return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <iostream>

using namespace std;

int sum_n (int n){ //подсчёт суммы цифер в числе

int res = n/1000 + (n%1000-n%100)/100 + (n%100-n%10)/10 + n%10;

return res;

}

bool was [10000]; //массив использованных вершин.

int vertex[10000]; //подсчёт кол-ва пройденных рёбер..

queue<int> q; //очередь для BFS

//BFS

void bfs (int start, int finish){

if (start==finish){ //если мы сразу попали в нужную вершину - выходим из программы.

cout << 0 << endl;

return;

}

else {

for (int i=0; i<10000; i++){ //предположим, что расстояние до любой вершины = 1

vertex[i]=1;

}

q.push (start); //будем рассматривать каждую вершину

was[start] = true;

while (!q.empty()){

int tmp = q.front(); //рассматриваемая вершина

q.pop();

int tmp1 = tmp;

tmp1 *= 3; //"ребёнок" рассматриваемой вершины, со значением родителбской вершины *3.

if (!was[tmp1]){

if (tmp1 == finish){//если финиш, то выводим длину пути до вершины.

cout << vertex[tmp] << endl;

return;

}

else if (tmp1 < 10000 && tmp1>=0){

was[tmp1] = true;//иначе помечаем вершину, как пройденную и засовываем её в очередь на рассмотрение

q.push(tmp1);

vertex[tmp1]=vertex[tmp]+1;//и прибавляем 1 к длине пути.

}

//действия повторяются для других операций.

tmp1=tmp;

tmp1 += sum_n(tmp1);

if (!was[tmp1]){

if (tmp1 == finish){

cout << vertex[tmp] << endl;

return;

}

else if (tmp1 < 10000 && tmp1>=0){

was[tmp1] = true;

vertex[tmp1]=vertex[tmp]+1;

q.push(tmp1);

}

tmp1=tmp;

tmp1 -= 2;

if (!was[tmp1]){

if (tmp1 == finish){

cout << vertex[tmp] << endl;

return;

}

else if (tmp1 < 10000 && tmp1>=0){

was[tmp1] = true;

vertex[tmp1]=vertex[tmp]+1;

q.push(tmp1);

}

int main() {

int a, b;

cin >> a >> b; //ввод начала и конца

bfs (a, b);//процедура выполнения

return 0;

}

Код на Java:

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

class ShaitanEngines {
    private static int N = 10001;
    private static boolean [] was = new boolean [N];
    private static int [] vertice = new int [N];
    private static Queue <Integer> q = new LinkedList();
    public static int sum (int n) {
        return (n/1000 + (n%1000-n%100)/100 + (n%100-n%10)/10 + n%10);  
    }
    public static void bfs (int start, int finish) {
        if (start == finish) {
            System.out.println(1);
            return;
        }
        else {
            for (int i=0; i<N; i++){ //предположим, что расстояние до любой вершины = 1
                vertice[i]=1;
            }
            q.add (start); //будем рассматривать каждую вершину
            was[start] = true;
            while (!q.isEmpty()){
                int tmp = q.element(); //рассматриваемая вершина
                q.remove();
                int tmp1 = tmp;
                tmp1 *= 3; //"ребёнок" рассматриваемой вершины, со значением родителбской вершины *3.
                if (!was[tmp1]){
                    if (tmp1 == finish){//если финиш, то выводим длину пути до вершины.
                        System.out.println(vertice[tmp]);
                        return;
                    }
                    else if (tmp1 < 10000 && tmp1>=0){
                        was[tmp1] = true;//иначе помечаем вершину, как пройденную и засовываем её в очередь на рассмотрение
                        q.add(tmp1);
                        vertice[tmp1]=vertice[tmp]+1;//и прибавляем 1 к длине пути.
                    }
                }
                //действия повторяются для других операций.
                tmp1=tmp;
                tmp1 += sum(tmp1);
                if (!was[tmp1]){
                    if (tmp1 == finish){
                        System.out.println(vertice[tmp]);
                        return;
                    }
                    else if (tmp1 < 10000 && tmp1>=0){
                        was[tmp1] = true;
                        vertice[tmp1]=vertice[tmp]+1;
                        q.add(tmp1);
                    }
                }
                tmp1=tmp;
                tmp1 -= 2;
                if (!was[tmp1]){
                    if (tmp1 == finish){
                        System.out.println(vertice[tmp]);
                        return;
                    }
                    else if (tmp1 < 10000 && tmp1>=0){
                        was[tmp1] = true;
                        vertice[tmp1]=vertice[tmp]+1;
                        q.add(tmp1);
                    }
                }
            }
        }
    }
    public static void main (String[] args) {
        Scanner sc = new Scanner (System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        bfs(a, b);
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class ShaitanEngines {

private static int N = 10001;

private static boolean [] was = new boolean [N];

private static int [] vertice = new int [N];

private static Queue <Integer> q = new LinkedList();

public static int sum (int n) {

return (n/1000 + (n%1000-n%100)/100 + (n%100-n%10)/10 + n%10);

}

public static void bfs (int start, int finish) {

if (start == finish) {

System.out.println(1);

return;

}

else {

for (int i=0; i<N; i++){ //предположим, что расстояние до любой вершины = 1

vertice[i]=1;

}

q.add (start); //будем рассматривать каждую вершину

was[start] = true;

while (!q.isEmpty()){

int tmp = q.element(); //рассматриваемая вершина

q.remove();

int tmp1 = tmp;

tmp1 *= 3; //"ребёнок" рассматриваемой вершины, со значением родителбской вершины *3.

if (!was[tmp1]){

if (tmp1 == finish){//если финиш, то выводим длину пути до вершины.

System.out.println(vertice[tmp]);

return;

}

else if (tmp1 < 10000 && tmp1>=0){

was[tmp1] = true;//иначе помечаем вершину, как пройденную и засовываем её в очередь на рассмотрение

q.add(tmp1);

vertice[tmp1]=vertice[tmp]+1;//и прибавляем 1 к длине пути.

}

//действия повторяются для других операций.

tmp1=tmp;

tmp1 += sum(tmp1);

if (!was[tmp1]){

if (tmp1 == finish){

System.out.println(vertice[tmp]);

return;

}

else if (tmp1 < 10000 && tmp1>=0){

was[tmp1] = true;

vertice[tmp1]=vertice[tmp]+1;

q.add(tmp1);

}

tmp1=tmp;

tmp1 -= 2;

if (!was[tmp1]){

if (tmp1 == finish){

System.out.println(vertice[tmp]);

return;

}

else if (tmp1 < 10000 && tmp1>=0){

was[tmp1] = true;

vertice[tmp1]=vertice[tmp]+1;

q.add(tmp1);

}

public static void main (String[] args) {

Scanner sc = new Scanner (System.in);

int a = sc.nextInt();

int b = sc.nextInt();

bfs(a, b);

}

Решение

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

Всю «карту» расположения операций можно представить в виде графа-дерева, где от каждой вершины отходят максимум 3 ребра (в каждой вершине по операции, проделанной со значением вершины, которая находится на уровень выше). Будем рассматривать каждую вершину. Если исходная вершина и есть конечной, то выходим из программы с вердиктом «0». Иначе будем поочерёдно рассматривать все вершины. Заведём массив расстояний, в котором предположим, что расстояние до нужной нам вершины равно 1. С проходом каждой вершины будем подсчитывать расстояние до нужной нам вершины (прибавляя к расстоянию 1), в которую мы рано или поздно попадём.

Related Images:

А1042

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

Условие:

В данной последовательности действительных чисел [latex]a_{1},…,a_{20}[/latex] выбрать возрастающую подпоследовательность наибольшей длинны.

Тесты:

Число элементов в заданной последовательности	Заданная последовательность	Найденная подпоследовательность
20	1 44 3 66 2 6 55 2 4 9 50 3 4 12 45 8 15 5 18 48	3 6 9 12 15 18
20	1 9 17 25 90 91 92 13 18 23 28 100 75 50 45 44 43 42 41 40	1 9 17 25
20	155 100 80 83 86 89 -60 -40 -20 0 20 40 60 33 33 33 0 0 0 0	-60 -40 -20 0 20 40 60

Код:

#include <stdio.h>
#include <iostream>
#include <map>
#include <string>
#include <vector>
#include <deque>

using namespace std;

// вспомогательные типы
typedef vector< double > tValues;
typedef map< double, bool > tSortedValues;
typedef vector< tValues > tSequences;

// возвращает true, если первый вектор (wheer) содержит второй (what)
bool containValues( tValues& where, tValues& what )
{
   if ( what.size() > 0 )
   {
      for( int i = 0; i < where.size(); i++ )
      {
         if ( where[ i ] == what[ 0 ] )
         {
            int k = i + 1;
            int j = 1;
            for(; j < what.size() && k < where.size() && where[ k ] == what[ j ]; j++, k++ );
            return ( j == what.size() );
         }
      }
   }
   
   return false;
}

// вспомогательная функция печати последовательности
void printSequence( tValues& seq )
{
   if ( seq.size() > 1 )
   {
      double diff = seq[ 1 ] - seq[ 0 ];
      cout << "sequence: size=" << seq.size() << ", diff=" << diff << ", values = { ";
      for( int i = 0; i < seq.size(); i++ )
      {
        cout << seq[ i ] << " ";
      }
      cout << "}\n";
   }
   else
   {
      cout << "NOT a sequence" << endl;
   }
}

int main(void)
{

   int n;
   cin >> n;
   if ( n <= 0 )
   {
      cout << "Input error: wrong length of the sequence" << endl;
      return 0;
   }   

   tValues sourceValues; // вектор для входных значений, в которых мы будем искать последовательность
   for( int i = 0; i < n; i++ ) // ввод входных значений
   {
      double val;
      cin >> val;
      sourceValues.push_back( val );
   }

   // нахождение всех возможные разностей между входными значениями
   tValues diffValues;// вектор для хранения всех возможные разностей между входными значениями
   for( int i = 0; i < sourceValues.size(); i++ )
   {
      tSortedValues sortedValues;
      for( int j = 0; j < sourceValues.size(); j++ )
      {
         if ( j != i )
         {
            double diff =
               ( i < j ) ?
                  sourceValues[ j ] - sourceValues[ i ] :
                  sourceValues[ i ] - sourceValues[ j ] ;
            if ( diff > 0 )
            {
               sortedValues[ diff ] = true;
            }
        }
      }
      for( tSortedValues::iterator it = sortedValues.begin(); it != sortedValues.end(); ++it )
      {
        diffValues.push_back( it->first );
      }
   }

   // главный цикл по входным значениям
   tSequences foundSequences;// вектор векторов, в котором будем помещать все найденные последовательности
   for( int srcValIdx = 0; srcValIdx < sourceValues.size(); srcValIdx++ )
   {
      double seedVal = sourceValues[ srcValIdx ]; // начальное значение для старта поиска последовательности
      // цикл по вектору разности
      for( int diffValIdx = 0; diffValIdx < diffValues.size(); diffValIdx++ )
      {
         double diffVal = diffValues[ diffValIdx ];
         double lastVal;
         tValues candidateSeq;
         candidateSeq.push_back( seedVal );

         // поиск последовательности влево от исходного значения
         lastVal = seedVal;
         for( int j = srcValIdx - 1; j >= 0; j-- )
         {
            double prevVal = sourceValues[ j ];
            if ( prevVal == lastVal - diffVal )
            {
               candidateSeq.insert( candidateSeq.begin(), prevVal );
               lastVal = prevVal;
            }
         }

         // поиск последовательности вправо от исходного значения
         lastVal = seedVal;
         for( int j = srcValIdx + 1; j < sourceValues.size(); j++ )
         {
            double nextVal = sourceValues[ j ];
            if ( nextVal == lastVal + diffVal )
            {
               candidateSeq.push_back( nextVal );
               lastVal = nextVal;
            }
         }
         
         if ( candidateSeq.size() > 2 ) // нейденную последовательность-кандидат помещаем в вектор найденных, если длинна больше двух
         {
            foundSequences.push_back( candidateSeq );
         }
      }
   }

   // удаляем последовательности, которые включают в себя другие
   //  Удалённые последовательности заменяются на пустышки
   for( int i = 0; i < foundSequences.size(); i++ )
   {
      if ( ! foundSequences[ i ].empty() )
      {
         for( int j = 0; j < foundSequences.size(); j++ )
         {
            if ( i != j
               && foundSequences[ i ].size() >= foundSequences[ j ].size() 
               && containValues( foundSequences[ i ], foundSequences[ j ] ) )
            {
               foundSequences[ j ].clear();
            }
         }
      }
   }

    // удаляем из вектора пустышки из прошлого шага
   {
      tSequences tmp;
      for( int i = 0; i < foundSequences.size(); i++ )
      {
         if ( ! foundSequences[ i ].empty() )
         {
            tmp.push_back( foundSequences[ i ] );
         }
      }
      foundSequences = tmp;
   }
   // ищем максимальную последовательность среди найденных
   int maxSize = -1;
   int maxIndex = -1;
   for( int i = 0; i < foundSequences.size(); i++ )
   {
      int size = foundSequences[ i ].size();
      if ( size > maxSize )
      {
         maxSize  = size;
         maxIndex = i;
      }
     // printSequence( foundSequences[ i ] ); // debug 
   }

   if ( maxIndex >= 0 )
   {
      cout << "max size sequence:\n";
      printSequence( foundSequences[ maxIndex ] ); 
   }

   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

#include <stdio.h>

#include <iostream>

#include <map>

#include <string>

#include <vector>

#include <deque>

using namespace std;

// вспомогательные типы

typedef vector< double > tValues;

typedef map< double, bool > tSortedValues;

typedef vector< tValues > tSequences;

// возвращает true, если первый вектор (wheer) содержит второй (what)

bool containValues( tValues& where, tValues& what )

{

if ( what.size() > 0 )

{

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

{

if ( where[ i ] == what[ 0 ] )

{

int k = i + 1;

int j = 1;

for(; j < what.size() && k < where.size() && where[ k ] == what[ j ]; j++, k++ );

return ( j == what.size() );

}

return false;

}

// вспомогательная функция печати последовательности

void printSequence( tValues& seq )

{

if ( seq.size() > 1 )

{

double diff = seq[ 1 ] - seq[ 0 ];

cout << "sequence: size=" << seq.size() << ", diff=" << diff << ", values = { ";

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

{

cout << seq[ i ] << " ";

}

cout << "}\n";

}

else

{

cout << "NOT a sequence" << endl;

}

int main(void)

{

int n;

cin >> n;

if ( n <= 0 )

{

cout << "Input error: wrong length of the sequence" << endl;

return 0;

}

tValues sourceValues; // вектор для входных значений, в которых мы будем искать последовательность

for( int i = 0; i < n; i++ ) // ввод входных значений

{

double val;

cin >> val;

sourceValues.push_back( val );

}

// нахождение всех возможные разностей между входными значениями

tValues diffValues;// вектор для хранения всех возможные разностей между входными значениями

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

{

tSortedValues sortedValues;

for( int j = 0; j < sourceValues.size(); j++ )

{

if ( j != i )

{

double diff =

( i < j ) ?

sourceValues[ j ] - sourceValues[ i ] :

sourceValues[ i ] - sourceValues[ j ] ;

if ( diff > 0 )

{

sortedValues[ diff ] = true;

}

for( tSortedValues::iterator it = sortedValues.begin(); it != sortedValues.end(); ++it )

{

diffValues.push_back( it->first );

}

// главный цикл по входным значениям

tSequences foundSequences;// вектор векторов, в котором будем помещать все найденные последовательности

for( int srcValIdx = 0; srcValIdx < sourceValues.size(); srcValIdx++ )

{

double seedVal = sourceValues[ srcValIdx ]; // начальное значение для старта поиска последовательности

// цикл по вектору разности

for( int diffValIdx = 0; diffValIdx < diffValues.size(); diffValIdx++ )

{

double diffVal = diffValues[ diffValIdx ];

double lastVal;

tValues candidateSeq;

candidateSeq.push_back( seedVal );

// поиск последовательности влево от исходного значения

lastVal = seedVal;

for( int j = srcValIdx - 1; j >= 0; j-- )

{

double prevVal = sourceValues[ j ];

if ( prevVal == lastVal - diffVal )

{

candidateSeq.insert( candidateSeq.begin(), prevVal );

lastVal = prevVal;

}

// поиск последовательности вправо от исходного значения

lastVal = seedVal;

for( int j = srcValIdx + 1; j < sourceValues.size(); j++ )

{

double nextVal = sourceValues[ j ];

if ( nextVal == lastVal + diffVal )

{

candidateSeq.push_back( nextVal );

lastVal = nextVal;

}

if ( candidateSeq.size() > 2 ) // нейденную последовательность-кандидат помещаем в вектор найденных, если длинна больше двух

{

foundSequences.push_back( candidateSeq );

}

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

// Удалённые последовательности заменяются на пустышки

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

{

if ( ! foundSequences[ i ].empty() )

{

for( int j = 0; j < foundSequences.size(); j++ )

{

if ( i != j

&& foundSequences[ i ].size() >= foundSequences[ j ].size()

&& containValues( foundSequences[ i ], foundSequences[ j ] ) )

{

foundSequences[ j ].clear();

}

// удаляем из вектора пустышки из прошлого шага

{

tSequences tmp;

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

{

if ( ! foundSequences[ i ].empty() )

{

tmp.push_back( foundSequences[ i ] );

}

foundSequences = tmp;

}

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

int maxSize = -1;

int maxIndex = -1;

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

{

int size = foundSequences[ i ].size();

if ( size > maxSize )

{

maxSize = size;

maxIndex = i;

}

// printSequence( foundSequences[ i ] ); // debug

}

if ( maxIndex >= 0 )

{

cout << "max size sequence:\n";

printSequence( foundSequences[ maxIndex ] );

}

return 0;

}

План

План программы:

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

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

Программа реализована с использованием шаблонных классов стандартной библиотеки vector и map. Vector используется для хранения всех используемых последовательностей, включая разности. Map используется, как временный объект для сортировки и слияния приращений, которые в ходе поиска встречаются с часто повторяющимися значениями.

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

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

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

Ссылка на ideone.com : http://ideone.com/kf13Zv

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]