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]=='.'){//проверяем нижнюю клетку

empty++;

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

plan.push(row+1);

plan.push(col);

}

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

empty++;

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

plan.push(row-1);

plan.push(col);

}

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

empty++;

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

plan.push(row);

plan.push(col+1);

}

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

empty++;

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

plan.push(row);

plan.push(col-1);

}

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

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

}

return 0;

}

int main() {

int N;

cin >> N;

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

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

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

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

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

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

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

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

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

} else {

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

}

queue <int> plan;

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

plan.push(1);

int walls=0;

while(!plan.empty()){

int row=plan.front();

plan.pop();

int col=plan.front();

plan.pop();

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

}

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

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

plan.push(N);

while(!plan.empty()){

int row=plan.front();

plan.pop();

int col=plan.front();

plan.pop();

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

}

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

int meters=walls*9;

cout << meters << endl;

return 0;

}

Java:

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

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

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

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

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

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

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

empty++;

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

plan.offer(row+1);

plan.offer(col);

}

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

empty++;

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

plan.offer(row-1);

plan.offer(col);

}

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

empty++;

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

plan.offer(row);

plan.offer(col+1);

}

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

empty++;

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

plan.offer(row);

plan.offer(col-1);

}

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

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

}

return 0;

}

public static void main (String[] args)

{

Scanner in = new Scanner(System.in);

int N = in.nextInt();

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

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

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

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

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

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

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

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

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

}

String line;

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

line = in.next();

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

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

}

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

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

plan.offer(1);

int walls=0;

while(!plan.isEmpty()){

int row=plan.poll();

int col=plan.poll();

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

}

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

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

plan.offer(N);

while(!plan.isEmpty()){

int row=plan.poll();

int col=plan.poll();

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

}

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

int meters = walls * 9;

System.out.println(meters);

}

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

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

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

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

Related Images:

e-olimp 695. Range Variation Query

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

Задача e-olimp 695.

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

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

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

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

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

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

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

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

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

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

Пример.

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

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

1 3

2 4

-2 -100

8 9

-3 -101

2 3

250

234

Решение.

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



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

#include <iostream>

#include <math.h>

#include <algorithm>

#include <climits>

using namespace std;

#define length 100000

int main() {

int a[length];

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

{

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

}

int k,x,y,result;

cin>>k;

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

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

{

cin >> x >> y;

mmax=INT_MIN;

mmin=INT_MAX;

if(x>0)

{

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

{

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

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

}

cout << mmax-mmin << endl;

}

else

{

x*=-1;

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

}

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

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

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

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

Related Images:

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

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

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

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

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

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

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

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

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

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

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

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

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


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

#include <stdio.h>

#include <vector>

#include <stdlib.h>

using namespace std;

struct Graph {

vector< vector<int> > AdjList;

int Size;

Graph(int n) {

vector<int> List;

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

AdjList.push_back(List);

Size = n;

}

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

Size++;

vector<int> List;

AdjList.push_back(List);

}

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

AdjList[u].push_back(v);

}

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

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

int cur_depth = 0;

int count = 0;

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

return count;

}

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

if (cur_depth <= max_depth) {

on_path[start] = true;

if (start == end)

count++;

else

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

int v = AdjList[start][k];

if (!on_path[v]) {

cur_depth++;

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

on_path[v] = false;

cur_depth--;

}

};

int main() {

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

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

Graph G(n);

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

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

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

}

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

return 0;

}

Решение на Java

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

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

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

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

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

import java.util.*;

import java.lang.*;

import java.io.*;

class myInt {

int v;

public myInt(int a) {

this.v = a;

}

class Graph {

Vector<Vector<Integer>> AdjList;

public Graph(int n) {

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

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

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

}

public void add_vertex() {

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

}

public void add_edge(int u, int v) {

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

}

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

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

myInt cur_depth = new myInt(0);

myInt count = new myInt(0);

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

return count.v;

}

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

if (cur_depth.v <= max_depth) {

on_path[start] = true;

if (start == end)

count.v++;

else

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

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

if (!on_path[v]) {

cur_depth.v++;

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

on_path[v] = false;

cur_depth.v--;

}

class Main

{

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

{

Scanner in = new Scanner(System.in);

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

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

int tmp1, tmp2;

Graph G = new Graph(n);

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

tmp1 = in.nextInt();

tmp2 = in.nextInt();

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

}

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

}

Related Images:

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

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

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

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

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

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

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

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

Тесты:

6 7

1 2

2 3

3 1

4 5

5 6

6 4

2 4

1 1 1 2 2 2

10 19

1 4

7 8

5 10

8 9

9 6

2 6

6 2

3 8

9 2

7 2

9 7

4 5

3 6

7 3

6 7

10 8

10 1

2 9

2 7

1 2 2 1 1 2 2 2 2 1

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

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

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

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

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

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

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

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

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

#include <iostream>

#include <vector>

using namespace std;

vector <int> G[100010];

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

vector<bool> used;

vector<int> order, component;

int res[100010];

int n, m, num=1;

void dfs_1 (int u) {

used[u]=1;

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

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

dfs_1(G[u][i]);

}

order.push_back(u);

}

void dfs_2 (int u) {

used[u]=1;

component.push_back(u);

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

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

dfs_2 (Gt[u][i]);

}

int main() {

ios::sync_with_stdio(false);

cin >> n >> m;

while (m--) {

int a, b;

cin >> a >> b;

a--;

b--;

G[a].push_back(b);

Gt[b].push_back(a);

}

used.assign (n, false);

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

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

}

used.assign (n, false);

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

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

if (used[v]==0) {

dfs_2 (v);

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

res[*I]=num;

num++;

component.clear();

}

cout << num-1 << endl;

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

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

return 0;

}

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

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

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

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

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

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

Related Images:

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

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

Задача:

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

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

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

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

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

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

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

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

Код на С++:

#include <iostream>
using namespace std;

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

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

#include <iostream>

using namespace std;

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

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

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

bool dfs(int key){

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

was[key] = 1;

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

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

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

if(a[key][i]){

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

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

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

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

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

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

}

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

was[key] = 2;

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

return false;

}

int main() {

cin >> n;

a = new int *[n];

was = new int [n];

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

a[i] = new int [n];

was[i] = 0;

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

cin >> a[i][j];

}

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

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

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

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

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

}

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

cout << "0\n";

return 0;

}

Код на Java:

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

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

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

import java.util.*;

import java.lang.*;

import java.io.*;

class Graphdfs

{

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

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

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

public Graphdfs(){}

public Graphdfs(int n)

{

this.n = n;

matrix = new int [n][n];

was = new int [n];

}

public void setMatrix(Scanner in)

{

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

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

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

}

public void showMatrix()

{

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

{

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

{

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

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

else System.out.println();

}

public boolean dfs(int key)

{

was[key] = 1;

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

{

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

{

if(was[i] == 0){

if(dfs(i)) return true;

}

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

return true;

}

was[key] = 2;

return false;

}

public int[] getWas(){

return was;

}

public class Main

{

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

{

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

Scanner in = new Scanner(System.in);

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

int n = in.nextInt();

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

Graphdfs Graph = new Graphdfs(n);

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

Graph.setMatrix(in);

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

//Graph.showMatrix();

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

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

}

System.out.println(0);

}

Пояснение:

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

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

Related Images:

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

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

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

Решение

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

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

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

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

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

#include<iostream>

#include<vector>

#include<set>

#include<map>

#include<string>

using namespace std;

map<string,set<string>> G;

map<string,bool> used;

map<string,bool> rec;

vector<string> V;

void dfs(string cur, string aim){

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

used[cur] = 1;

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

if(*i != aim){

dfs(*i,aim);

}else{

rec[aim] = 1;

return;

}

int main(){

//input

int n; cin >> n;

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

string curVert; cin >> curVert;

V.push_back(curVert);

int m; cin >> m;

while(m--){

string inp; cin >> inp;

G[curVert].insert(inp);

}

if(i != n-1){

string stars;

cin >> stars;

}

//work

for(auto i : V){

dfs(i, i);

used.clear();

}

for(auto i : V){

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

}

return 0;

}

Идея решения

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

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

Related Images:

А397б

16/11/2014 by Швандт Максим Альбертович

Задача: Дана действительная квадратная матрица порядка [latex]n[/latex]. В строках с отрицательным элементом на главной диагонали найти наибольший из всех элементов.

Тесты:

matrix

results the biggest element in line

-1	3	4	5
2	3	6	7
1	4	-2	7
2	3	4	2

—

-1	2	3	4	5
6	7	8	9	10
2	4	-5	7	8
11	-1	0	5	9
1	8	-33	2	-1

—

error: wrong value of n

0	1	3
-2	-5	-1
-4	-9	-4

—

-1

-4

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

#include <stdio.h>
#include <float.h>
  
   // назначение макросов
#define MAX 10
#define X_INIT (-DBL_MAX)

int main(void)
{
   // рабочие переменные
   int n;
   int i;
   int j;
   double x;
   double arr[MAX][MAX];
   
   // проверка ввода порядка n
	if( scanf("%d", &n ) <= 0 )
   {
      printf("error: incomplete input of n\n");
      return 0;
   }
   if( n <= 1 || n > MAX )
   {
      printf("error: wrong value of n\n");
      return 0;
   }
   
   // ввод матрицы с проверкой
	for( i = 0; i < n; i++)
	{
		for( j = 0; j < n; j++)
	   {
         if( scanf("%lf", &arr[i][j] ) < 1 )
         {
            printf("error: incomplete input of array\n");
            return 0;
         }

      }      
	}
   // печать введённой матрицы для отладки
   printf("input array:\n");
   for( i = 0; i < n; i++)
	{
 		for( j = 0; j < n; j++)
	   {
         printf("\t%2.2lf", arr[i][j]);        
         
      } 
      printf("\n");   
	}
   // вывод результата, содержит номер строки, где необходимо было искать наибольший элемент
   printf("result:\n");
   for( i = 0; i < n; i++)
	{
      x = X_INIT;   
      if( arr[i][i] < 0 )
      {
	      for( j = 0; j < n; j++)
	      {   
		      if( arr[i][j] > x ) x = arr[i][j];             
         }
         printf("line = %d, max = %2.2lf\n", i, x); 
	   }  
	}
   
   return 0;
}

#include <stdio.h>

#include <float.h>

// назначение макросов

#define MAX 10

#define X_INIT (-DBL_MAX)

int main(void)

{

// рабочие переменные

int n;

int i;

int j;

double x;

double arr[MAX][MAX];

// проверка ввода порядка n

if( scanf("%d", &n ) <= 0 )

{

printf("error: incomplete input of n\n");

return 0;

}

if( n <= 1 || n > MAX )

{

printf("error: wrong value of n\n");

return 0;

}

// ввод матрицы с проверкой

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

{

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

{

if( scanf("%lf", &arr[i][j] ) < 1 )

{

printf("error: incomplete input of array\n");

return 0;

}

// печать введённой матрицы для отладки

printf("input array:\n");

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

{

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

{

printf("\t%2.2lf", arr[i][j]);

}

printf("\n");

}

// вывод результата, содержит номер строки, где необходимо было искать наибольший элемент

printf("result:\n");

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

{

x = X_INIT;

if( arr[i][i] < 0 )

{

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

{

if( arr[i][j] > x ) x = arr[i][j];

}

printf("line = %d, max = %2.2lf\n", i, x);

}

return 0;

}

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

import java.util.*;
import java.lang.*;
import java.io.*;
 
class MatrixApp
{
   private static final int  X_INIT = -Integer.MAX_VALUE;
   
   public static Integer scanInteger( Scanner in )
   {
       return ( ( in.hasNextInt() ) ? in.nextInt() : null );
   }
 
   public static Double scanDouble( Scanner in )
   {
       return ( ( in.hasNextDouble() ) ? in.nextDouble() : null );
   }
   
   public static void main( String[] args )
   {       
      // проверка ввода порядка n
      Scanner in = new Scanner(System.in); 
      
      int n = scanInteger( in );
      
      if( n <= 0 )
      {
         System.out.printf("error: incomplete input of n\n");
         return;
      }
      
      if( n <= 1 )
      {
         System.out.printf("error: wrong value of n\n");
         return;
      }
      
      // создаем массив нужной размерности
      double arr[][] = new double[n][n];

      // ввод матрицы с проверкой
      for( int i = 0; i < n; i++ )
      {
          for( int j = 0; j < n; j++ )
         {
           arr[i][j] = scanDouble( in );
        }      
      }
      
      in.close();
      
      // печать введённой матрицы для отладки
      System.out.printf("input array:\n");
      for( int i = 0; i < n; i++ )
      {
         for( int j = 0; j < n; j++ )
         {
            System.out.printf("\t%2.2f", arr[i][j]);        
         } 
         System.out.printf("\n");   
      }

      // вывод результата, содержит номер строки, где необходимо было искать наибольший элемент
      System.out.printf("result:\n");
      for( int i = 0; i < n; i++ )
       {
         if( arr[i][i] < 0 )
         {
            double x = arr[i][0]; 
            for( int j = 1; j < n; j++ )
            {   
               if( arr[i][j] > x ) x = arr[i][j];             
            }
            System.out.printf("line = %d, max = %2.2f\n", i, x); 
          }  
       }
 
   
   }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class MatrixApp

{

private static final int X_INIT = -Integer.MAX_VALUE;

public static Integer scanInteger( Scanner in )

{

return ( ( in.hasNextInt() ) ? in.nextInt() : null );

}

public static Double scanDouble( Scanner in )

{

return ( ( in.hasNextDouble() ) ? in.nextDouble() : null );

}

public static void main( String[] args )

{

// проверка ввода порядка n

Scanner in = new Scanner(System.in);

int n = scanInteger( in );

if( n <= 0 )

{

System.out.printf("error: incomplete input of n\n");

return;

}

if( n <= 1 )

{

System.out.printf("error: wrong value of n\n");

return;

}

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

double arr[][] = new double[n][n];

// ввод матрицы с проверкой

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

{

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

{

arr[i][j] = scanDouble( in );

}

in.close();

// печать введённой матрицы для отладки

System.out.printf("input array:\n");

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

{

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

{

System.out.printf("\t%2.2f", arr[i][j]);

}

System.out.printf("\n");

}

// вывод результата, содержит номер строки, где необходимо было искать наибольший элемент

System.out.printf("result:\n");

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

{

if( arr[i][i] < 0 )

{

double x = arr[i][0];

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

{

if( arr[i][j] > x ) x = arr[i][j];

}

System.out.printf("line = %d, max = %2.2f\n", i, x);

}

Ссылка:https://ideone.com/kCDer9

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

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

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

Для поиска наибольшего значения в строке используется макрос X_INIT. Он используется в качестве начального значения максимума. Этим наименьшим значением является взятый с отрицательным знаком макрос DBL_MAX из библиотеки float.h , обозначающий наибольшее значение.

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

Related Images:

Heat Detector

16/10/2014 by Вустянюк Ігор Дмитрович

Задача

Речь пойдёт о первой задаче уровня Medium на сайте codingame.com. По сюжету Бэтмен должен отыскать бомбу в многоэтажном доме. Ему известно количество этажей и количество окон на каждом этаже. Ему также известно направление, в котором находится бомба. Бэтмену нужно как можно быстрее её найти. Процесс поиска выглядит следующим образом: Бэтмен заглядывает в какое-то окно и затем на каждом игровом шаге он перепрыгивает в какое-то другое окно — так до тех пор, пока не отыщет бомбу.

Инциализация

В первой строке заданы числа W и H — соответственно количество окон на каждом этаже (оно для всех этажей одно и то же) и количество этажей в здании.

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

В третьей строке заданы два целых числа — x и y — координаты окна, с которого Бэтмен начинает свой поиск. Первая координата задаёт номер окна на этаже (начиная с нуля), вторая — номер этажа (также начиная с нуля). Нулевой этаж — верхний, нулевое окно на каждом этаже — левое.

Входные данные для одного игрового хода

Одна строка DIR, задающая направление, в котором следует искать бобму:

Выходные данные для одного игрового хода

Одна строка, в которой заданы два целых числа, разделённых одним пробелом, — координаты окна, которое должен проверить Бэтмен.

Решение

Игровой цикл продолжается до тех пор, пока либо бобма взорвётся, либо Бэтмен её обезвредит. Т.е. либо нам не хватит шагов, либо мы угадаем обе координаты. На каждом шаге игрового цикла будем перемещать Бэтмена с учётом направления, в котором находится бомба, и при этом «сжимать» область игрового поля, в которой он может прыгать. Однажды этот промежуток ужмётся в ондну точку — ту самую, абсцисса которой соответствует координате бомбы.

Обозначим координаты бобмы через BX и BY и введём четыре вспомогательных параметра: l, r, u, b — «динамические границы», левая, правая, верхняя и нижняя соответственно. Идея состоит в том, чтобы на каждом шаге выполнялись неравенства [latex] l \leq BX \leq r [/latex] и [latex] d \leq By \leq u [/latex].

Зададим начальные значения [latex] l = 0 [/latex], [latex] r = W — 1 [/latex], [latex] u = 0 [/latex] и [latex] d = H — 1 [/latex]. Тогда после инициализации игры указанные выше неравенства справедливы тривиальным образом (это просто заданные по условию ограничения на возможные значения Bx и By). Переходим к первому ходу, он же первый шаг игрового цикла. Мы считали строку DIR, указавшую нам направление, в котором следует искать бомбу.

Для оси абсцисс имеет место один из трёх случаев:

[latex] BX < x [/latex] (если DIR — одна из строк «L», «DL», «UL»). В этом случае справедливо неравенство [latex] l \leq BX \leq x — 1 [/latex]. Положим [latex] r = x — 1 [/latex]. Тогда будет справедливо неравенство [latex] l \leq BX \leq r [/latex]. Отметим, что новый промежуток [latex] l \ldots r [/latex] в этом случае будет на единицу короче предыдущего.
[latex] BX = x [/latex] (если DIR — одна из строк «U» и «B»). В этом случае всё хорошо.
[latex] BX > x [/latex] (если DIR — одна из строк «R», «DR», «UR»). В этом случае справедливо неравенство [latex] x + 1 \leq BX \leq r [/latex]. Положим [latex] l = x + 1 [/latex]. Тогда будет справедливо неравенство [latex] l \leq BX \leq r [/latex]. Отметим, что новый промежуток [latex] l \ldots r [/latex] в этом случае будет на единицу короче предыдущего.

Если [latex] BX = x [/latex], то всё хорошо — мы уже знаем абсциссу бомбы. А что делать в остальных двух случаях? Как эффективнее искать бомбу? Можно просматривать все значения из промежутка [latex] l \ldots r [/latex] поочерёдно слева направо, но что если бомба расположена у правого края? Можно просматривать все значения поочерёдно справа налево, но что если координата бомбы равна l, а промежуток большой? Остаётся один естественный вариант — «прыгнуть» в середину промежутка, т.е. в точку с абсциссой [latex] \left \lfloor \frac{l + r}{2} \right \rfloor[/latex]. На следующем шаге цикла надо повторить приведённые выше рассуждения, изменения границ и «прыжок». Таким образом, либо мы случайно наткнётся на абсциссу бомбы, либо промежуток [latex] l .. r [/latex], уменьшаясь каждый раз на одно число, ужмётся в точку, т.е. мы тоже найдём абсциссу бомбы! Осталось применить те же рассуждения к ординате бомбы. Надеюсь, код ответит на оставшиеся вопросы.

Код

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    int W, H;   // Количество окон по горизонтали и вертикали соответственно
    cin >> W >> H; cin.ignore();
    int l = 0, r = W - 1, u = 0, d = H - 1; // Начальные значения границ
    int N;
    cin >> N; cin.ignore();
    int x, y;
    cin >> x >> y; cin.ignore();

    // Игровой цикл
    while (1) {
        string DIR; // Направление, в котором находится бомба
        cin >> DIR;
        if ((DIR[0] == 'L')  ||  (DIR[1] == 'L'))
            r = x - 1;
        if ((DIR[0] == 'R')  ||  (DIR[1] == 'R'))
            l = x + 1;
        if (DIR[0] == 'U')
            d = y - 1;
        if (DIR[0] == 'D')
            u = y + 1;
        
        x = (l + r)/2;  // Абсцисса нового окна
        y = (u + d)/2;  // Ордината нового окна
        
        cout << x << " " << y << endl;
    }
}

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

using namespace std;

int main()

{

int W, H; // Количество окон по горизонтали и вертикали соответственно

cin >> W >> H; cin.ignore();

int l = 0, r = W - 1, u = 0, d = H - 1; // Начальные значения границ

int N;

cin >> N; cin.ignore();

int x, y;

cin >> x >> y; cin.ignore();

// Игровой цикл

while (1) {

string DIR; // Направление, в котором находится бомба

cin >> DIR;

if ((DIR[0] == 'L') || (DIR[1] == 'L'))

r = x - 1;

if ((DIR[0] == 'R') || (DIR[1] == 'R'))

l = x + 1;

if (DIR[0] == 'U')

d = y - 1;

if (DIR[0] == 'D')

u = y + 1;

x = (l + r)/2; // Абсцисса нового окна

y = (u + d)/2; // Ордината нового окна

cout << x << " " << y << endl;

}

Код на Java

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

class Main
{
    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner in = new Scanner(System.in);
        int w = in.nextInt(), h = in.nextInt();
        int l = 0, r = w-1, u = 0, d = h-1;
        int n = in.nextInt(), x = in.nextInt(), y = in.nextInt();
        
        while (true) {
            char dir = in.next().charAt(0);
            if ((dir == 'L') || (dir == 'L'))
                r = x-1;
            if ((dir == 'R') || (dir == 'R'))
                l = x+1;
            if (dir == 'U')
                d = y-1;
            if (dir == 'D')
                u = y+1;
            x = (l + r) / 2;
            y = (u + d) / 2;
            System.out.println(x + " " + y);
        }
    }
}