e-olymp 2955. Персистентый массив

19/05/2016 by Сплошнов Кирилл

Условие

Задача взята отсюда.

Дан массив (вернее, первая, начальная его версия). Нужно уметь отвечать на два запроса:

[latex]a_i[j] = x[/latex] — создать из [latex]i[/latex]-ой версии новую, в которой [latex]j[/latex]-ый элемент равен [latex]x[/latex], а остальные элементы такие же, как в [latex]i[/latex]-ой версии.
[latex]get[/latex] [latex]a_i[j][/latex] — сказать, чему равен [latex]j[/latex]-ый элемент в [latex]i[/latex]-ой версии.

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

Количество чисел в массиве [latex]n[/latex] [latex](1 \leq n \leq 10^5)[/latex] и [latex]n[/latex] элементов массива. Далее количество запросов [latex]m[/latex] [latex](1 \leq m \leq 10^5)[/latex] и [latex]m[/latex] запросов. Формат описания запросов можно посмотреть в примере. Если уже существует [latex]k[/latex] версий, новая версия получает номер [latex]k + 1[/latex]. И исходные, и новые элементы массива — целые числа от [latex]0[/latex] до [latex]10^9[/latex]. Элементы в массиве нумеруются числами от [latex]1[/latex] до [latex]n[/latex].

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

На каждый запрос типа [latex]get[/latex] вывести соответствующий элемент нужного массива.

Тесты

№	Входные данные	выходные данные
1	6 1 2 3 4 5 6 11 create 1 6 10 create 2 5 8 create 1 5 30 get 1 6 get 1 5 get 2 6 get 2 5 get 3 6 get 3 5 get 4 6 get 4 5	6 5 10 5 10 8 6 30
2	2 42 2048 17 create 1 1 1 create 2 2 1 create 3 2 5 create 3 1 4 create 5 2 6 get 1 1 get 1 2 get 2 1 get 2 2 get 3 1 get 3 2 get 4 1 get 4 2 get 5 1 get 5 2 get 6 1 get 6 2	42 2048 1 2048 1 1 1 5 4 1 4 6

Код

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

struct Node
{
    Node* lchild;
    Node* rchild;
    int val;
};

void build(Node* node, int* base, int l, int r)
{
    if (l == r)
        node->val = base[l-1]; //дерево пронумеровано с единицы
    else
    {
        int m = (l + r) / 2;
        node->lchild = new Node();
        build(node->lchild, base, l, m);
        node->rchild = new  Node();
        build(node->rchild, base, m + 1, r);
    }
}

void add(Node* to, Node* from, int l, int r, int npos, int nv)
{
    if (l == r)
        to->val = nv;
    else
    {
        int m = (l + r) / 2;
        if (npos <= m)
        {
            to->rchild = from->rchild;
            Node* left = new Node();
            add(left, from->lchild, l, m, npos, nv);
            to->lchild = left;
        }
        else
        {
            to->lchild = from->lchild;
            Node* right = new Node();
            add(right, from->rchild, m + 1, r, npos, nv);
            to->rchild = right;
        }
    }
}

int get(Node* node, int l, int r, int pos)
{
    if (l == r)
        return node->val;
    else
    {
        int m = (l + r) / 2;
        if (pos <= m)
            return get(node->lchild, l, m, pos);
        else
            return get(node->rchild, m + 1, r, pos);
    }
}

int main() 
{
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    int base[n];
    for (int i = 0; i < n; i++)
        cin >> base[i];
    vector<Node*> versions;
    versions.push_back(new Node());
    build(versions.at(0), base, 1, n);
    int k;
    cin >> k;
    for (int i = 0; i < k; i++)
    {
        string s;
        cin >> s;
        if (s == "create")
        {
            int rootPos, newPos, newVal;
            cin >> rootPos >> newPos >> newVal;
            versions.push_back(new Node());
            add(versions.back(), versions.at(rootPos-1), 1, n, newPos, newVal);
        }
        else
        {
            int rootPos, valPos;
            cin >> rootPos >> valPos;
            cout << get(versions.at(rootPos-1), 1, n, valPos) << endl;
        }
    }
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

struct Node

{

Node* lchild;

Node* rchild;

int val;

};

void build(Node* node, int* base, int l, int r)

{

if (l == r)

node->val = base[l-1]; //дерево пронумеровано с единицы

else

{

int m = (l + r) / 2;

node->lchild = new Node();

build(node->lchild, base, l, m);

node->rchild = new Node();

build(node->rchild, base, m + 1, r);

}

void add(Node* to, Node* from, int l, int r, int npos, int nv)

{

if (l == r)

to->val = nv;

else

{

int m = (l + r) / 2;

if (npos <= m)

{

to->rchild = from->rchild;

Node* left = new Node();

add(left, from->lchild, l, m, npos, nv);

to->lchild = left;

}

else

{

to->lchild = from->lchild;

Node* right = new Node();

add(right, from->rchild, m + 1, r, npos, nv);

to->rchild = right;

}

int get(Node* node, int l, int r, int pos)

{

if (l == r)

return node->val;

else

{

int m = (l + r) / 2;

if (pos <= m)

return get(node->lchild, l, m, pos);

else

return get(node->rchild, m + 1, r, pos);

}

int main()

{

ios::sync_with_stdio(false);

int n;

cin >> n;

int base[n];

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

cin >> base[i];

vector<Node*> versions;

versions.push_back(new Node());

build(versions.at(0), base, 1, n);

int k;

cin >> k;

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

{

string s;

cin >> s;

if (s == "create")

{

int rootPos, newPos, newVal;

cin >> rootPos >> newPos >> newVal;

versions.push_back(new Node());

add(versions.back(), versions.at(rootPos-1), 1, n, newPos, newVal);

}

else

{

int rootPos, valPos;

cin >> rootPos >> valPos;

cout << get(versions.at(rootPos-1), 1, n, valPos) << endl;

}

return 0;

}

Решение

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

struct Node
{
Node* lchild;
Node* rchild;
int val;
};

struct Node

{

Node* lchild;

Node* rchild;

int val;

};

(Тут [latex]lchild[/latex] и [latex]rchild[/latex] — ссылки на левый и правый поддеревья соответственно, а [latex]val[/latex] — значение, хранящееся в узле.)

Замечание: тут и далее под левым подотрезком отрезка [latex][l, l + 1, \ldots, m, m + 1, \ldots, r — 1, r][/latex], [latex]m = \lfloor\frac{l + r}{2}\rfloor[/latex] подразумевается отрезок [latex][l, \ldots, m][/latex] а под правым — [latex][m + 1, \ldots, r][/latex].

Заведем вектор-хранилище корней дерева [latex]versions[/latex] (об этом позднее). Для начала занесем туда 1 элемент — корень изначального дерева, и построим на нем дерево из элементов массива. Вопрос в том, какую информацию хранить в вершинах дерева? Оказывается, достаточно хранить в листьях элементы массива, а остальные узлы заполнять ни чем не надо — исходя из условия, запросы будут только к конкретным элементам массива. Рекурсивная процедура построения дерева стандартна, отличается только технической реализацией (вместо номеров вершин передаем ссылки на необходимые нам узлы) — рекурсивно создаем у текущего узла [latex]lchild[/latex] и [latex]rchild[/latex] и вызываем функцию построения для них, пока длина отрезка, за который они отвечают, не станет равна единице. Тогда присваиваем полю [latex]val[/latex] этого узла значение соотв. элемента массива.

Например, для массива {[latex]1, 2, 3, 4, 5, 6[/latex]} в результате построения мы получим следующую структуру (где на самом деле значения хранятся только на отрезках длины [latex]1[/latex], для остальных узлов подотрезки массива, отвечающие им, только подразумеваются).

Теперь разберемся, как эффективно создавать новые версии массива. Пусть у нас уже есть [latex]k[/latex] версий массива и мы хотим создать из [latex]i[/latex]-й [latex](k+1)[/latex]-ю. Для начала добавим в хранилище новый узел-корень, отвечающий данной версии.

Теперь рассуждаем так: допустим, элемент, который надо поменять, находиться в правом подотрезке (для левого, рассуждения будут симметричны). Левые подотрезки идентичны, тогда просто присваиваем [latex]lchild[/latex] нового узла ссылку на [latex]lchild[/latex] исходного. Правые будут отличаться. Тогда создаем у нового узла [latex]rchild[/latex], и проводим те же размышления относительного правого подотрезка, [latex]rchild[/latex]-ов исходного и нового узлов, повторяя это до тех пор, пока мы не придем в лист дерева, тогда просто присвоим этому новому узлу требуемое значение. Получаем несложный рекурсивный алгоритм функции void add(Node* to, Node* from, int l, int r, int npos, int nv);

Для наглядности, рассмотрим пример с тем же массивом. Пусть сперва нас просят выполнить create 1 6 42 — создать из первой версии новую, где шестой элемент равен [latex]42[/latex], а затем create 2 4 667 — создать новую уже из второй, где [latex]4[/latex]-й элемент равен [latex]667[/latex]. Вот, что мы получим в результате (черный цвет — первая версия, красный — вторая, синий — третья):

Рассмотрим, как получилась вторая версия. Создаем корень {[latex]1, 2, 3, 4, 5, 42[/latex]}. Необходимый нам элемент в правом подотрезке. Тогда [latex]lchild[/latex] нового корня будет ссылаться на [latex]lchild[/latex] исходного, а [latex]rchild[/latex] {[latex]4, 5, 42[/latex]}. Мы создаем. Аналогично поступаем с {[latex]4, 5, 42[/latex]} относительно {[latex]4, 5, 6[/latex]}. Левое поддерево {[latex]4, 5[/latex]} — общее, создаем правое поддерево {[latex]42[/latex]} и завершаем алгоритм. Для получения третьей версии можно провести аналогичные рассуждения, но уже беря в качестве исходного дерева вторую версию.

Так как на каждом этапе отрезок делится пополам, то очевидно, что как и в стандартной реализации ДО, асимптотика этой функции будет [latex]O(\log{n})[/latex], а при создании новой версии будет создано не более чем [latex]\lceil\log_2{n}\rceil[/latex] вершин, т.е. алгоритм является достаточно эффективным как в плане времени, так и расходуемой памяти.

Осталось реализовать функцию int get(Node* node, int l, int r, int pos); Она реализуется стандартно: спускаемся по необходимой версии дерева (из нужного узла-корня в [latex]storage[/latex]), в левое или правое поддерево, пока не дойдем до необходимой нам вершины (это будет отрезок единичной длины), далее возвращаем содержимое [latex]val[/latex] этого узла. Реализация облегчается еще и тем, что запрашивают элемент — т.е. отрезок единичной длины, и не надо рассматривать случай, когда необходимый отрезок лежит частично в левом, а частично в правом поддереве.

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

Ссылки

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

Рабочий код на Ideone.

Замечание

Легко заметить, что в функции int get(Node* node, int l, int r, int pos); можно очень просто избавиться от рекурсии:

int get(Node* node, int l, int r, int pos)
{
    while (l != r)
    {
        int m = (l + r) / 2;
        if (pos <= m)
        {
            r = m;
            node = node->lchild;
        }
        else
        {
            l = m + 1;
            node = node->rchild;
        }
    }
    return node->val;
}

int get(Node* node, int l, int r, int pos)

{

while (l != r)

{

int m = (l + r) / 2;

if (pos <= m)

{

r = m;

node = node->lchild;

}

else

{

l = m + 1;

node = node->rchild;

}

return node->val;

}

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

Related Images:

e-olymp 695. Range Variation Query

19/05/2016 by Сплошнов Кирилл

Условие

Задача взята отсюда.

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

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

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

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

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

Если [latex]x_i > 0[/latex], то требуется найти разность между максимальным и минимальным значением среди элементов [latex]a_{xi}, a_{xi+1}, \ldots, a_{yi}[/latex]. При этом [latex]1 \leq x_i \leq y_i \leq 10^5[/latex].

Если [latex]x_i < 0[/latex], то требуется присвоить элементу [latex]a_{-xi}[/latex] значение [latex]y_i[/latex]. При этом [latex]-10^5 \leq x_i \leq 1[/latex] и [latex]|y_i| \leq 10^5[/latex].

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

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

Тесты

№	Входные данные	Выходные данные
1	7 1 3 2 4 -2 -100 1 5 8 9 -3 -101 2 3	34 68 250 234 1
2	4 1 100000 100000 100000 -100000 42000 1 100000	35753 0 41998
3	13 1 17 -5 -400 -3 500 3 5 1 17 -2 345 2 345 2 3 2 5 -1 -100000 -2 100000 1 2 1 100000	5200 900 5602 35813 155 900 200000 200000

Код

#include <iostream>
#include <utility>
#include <algorithm>
#define SIZE 100000
using namespace std;

void build(pair<int, int>* tree, int pos, int l, int r)
{
    if (l == r)
    {
        tree[pos].first = (l % 12345) * (l % 12345) % 12345 + ((l % 23456) * (l % 23456) % 23456) * (l % 23456) % 23456;
        tree[pos].second = tree[pos].first;
    }
    else
    {
        int m = (l + r) / 2;
        build(tree, pos * 2, l, m);
        build(tree, pos * 2 + 1, m + 1, r);
        tree[pos] = make_pair(max(tree[pos * 2].first, tree[pos * 2 + 1].first), min(tree[pos * 2].second, tree[pos * 2 + 1].second));
    }
}

pair<int, int> get(pair<int, int>* tree, int pos, int l, int r, int ql, int qr)
{
    if (l == ql && r == qr)
        return tree[pos];
    else
    {
        int m = (l + r) / 2;
        if (qr <= m)
            return get(tree, pos * 2, l, m, ql, qr);
        else if (ql >= m + 1)
            return get(tree, pos * 2 + 1, m + 1, r, ql, qr);
        else
        {
            pair<int, int> a = get(tree, pos * 2, l, m, ql, m);
            pair<int, int> b = get(tree, pos * 2 + 1, m + 1, r, m + 1, qr);
            return make_pair(max(a.first, b.first), min(a.second, b.second));
        }
    }
}

void modify(pair<int, int>* tree, int pos, int l, int r, int npos, int nv)
{
    if (l == r)
    {
        tree[pos].first = nv;
        tree[pos].second = nv;
    }
    else
    {
        int m = (l + r) / 2;
        if (npos <= m)
            modify(tree, pos * 2, l, m, npos, nv);
        else
            modify(tree, pos * 2 + 1, m + 1, r, npos, nv);
        tree[pos] = make_pair(max(tree[pos * 2].first, tree[pos * 2 + 1].first), min(tree[pos * 2].second, tree[pos * 2 + 1].second));
    }
}

int main() 
{
    ios::sync_with_stdio(false);
    pair<int, int> tree[SIZE * 4];
    build(tree, 1, 1, SIZE);
    int n, x, y;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> x >> y;
        if (x > 0)
        {
            pair<int, int> query = get(tree, 1, 1, SIZE, x, y);
            cout << query.first - query.second << endl;
        }
        else
            modify(tree, 1, 1, SIZE, -x, y);
    }
    return 0;
}

#include <iostream>

#include <utility>

#include <algorithm>

#define SIZE 100000

using namespace std;

void build(pair<int, int>* tree, int pos, int l, int r)

{

if (l == r)

{

tree[pos].first = (l % 12345) * (l % 12345) % 12345 + ((l % 23456) * (l % 23456) % 23456) * (l % 23456) % 23456;

tree[pos].second = tree[pos].first;

}

else

{

int m = (l + r) / 2;

build(tree, pos * 2, l, m);

build(tree, pos * 2 + 1, m + 1, r);

tree[pos] = make_pair(max(tree[pos * 2].first, tree[pos * 2 + 1].first), min(tree[pos * 2].second, tree[pos * 2 + 1].second));

}

pair<int, int> get(pair<int, int>* tree, int pos, int l, int r, int ql, int qr)

{

if (l == ql && r == qr)

return tree[pos];

else

{

int m = (l + r) / 2;

if (qr <= m)

return get(tree, pos * 2, l, m, ql, qr);

else if (ql >= m + 1)

return get(tree, pos * 2 + 1, m + 1, r, ql, qr);

else

{

pair<int, int> a = get(tree, pos * 2, l, m, ql, m);

pair<int, int> b = get(tree, pos * 2 + 1, m + 1, r, m + 1, qr);

return make_pair(max(a.first, b.first), min(a.second, b.second));

}

void modify(pair<int, int>* tree, int pos, int l, int r, int npos, int nv)

{

if (l == r)

{

tree[pos].first = nv;

tree[pos].second = nv;

}

else

{

int m = (l + r) / 2;

if (npos <= m)

modify(tree, pos * 2, l, m, npos, nv);

else

modify(tree, pos * 2 + 1, m + 1, r, npos, nv);

tree[pos] = make_pair(max(tree[pos * 2].first, tree[pos * 2 + 1].first), min(tree[pos * 2].second, tree[pos * 2 + 1].second));

}

int main()

{

ios::sync_with_stdio(false);

pair<int, int> tree[SIZE * 4];

build(tree, 1, 1, SIZE);

int n, x, y;

cin >> n;

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

{

cin >> x >> y;

if (x > 0)

{

pair<int, int> query = get(tree, 1, 1, SIZE, x, y);

cout << query.first - query.second << endl;

}

else

modify(tree, 1, 1, SIZE, -x, y);

}

return 0;

}

Решение

Задача решается с помощью стандартного Дерева Отрезков (подробно про ДО прочитать можно, например, на сайте Е-maxx, ссылка ниже). Отметим особенности построения данного дерева. В вершинах дерева хранить будем не по одному, а по два значения — соответственно максимум и минимум на отрезке. Тогда при построении дерева, спускаясь до листа, будем считать элемент последовательности по формуле, данной в условии, и это значение будет как минимумом, так и максимум для отрезка из одного элемента. Для остальных элементов имеем:

tree[pos] = make_pair(max(tree[pos * 2].first, tree[pos * 2 + 1].first), min(tree[pos * 2].second, tree[pos * 2 + 1].second));

1	tree[pos] = make_pair(max(tree[pos * 2].first, tree[pos * 2 + 1].first), min(tree[pos * 2].second, tree[pos * 2 + 1].second));

Где элементы с номерами [latex]pos * 2[/latex] и [latex]pos * 2 + 1[/latex] — левый и правый потомок соответственно. Для удобства, дерево нумеруется с единицы.

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

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

Таким образом, в самой программе мы просто строим дерево, а потом в цикле отвечаем на запросы, выполняя необходимые действия (как описано в условии). При запросе типа [latex]1[/latex] [latex](x_i > 0)[/latex] выводим разницу между полученными максимумом и минимумом.

Ссылки

Засчитанное решение на сайте e-olymp.
Рабочий код на Ideone.
Статья про Дерево Отрезков на e-maxx.

Related Images:

e-olymp 5082. Степени вершин

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

Условие

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

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

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

В первой строчке находится число [latex]1 \leq N \leq 1000[/latex] В следующих [latex]N[/latex] строчках находится матрица смежности.

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

Выведите [latex]N[/latex] чисел – степени всех вершин.

Тесты

Ввод	Вывод
2 0 1 1 0	1 1
3 0 1 0 1 0 1 0 1 0	1 2 1
3 0 1 0 1 0 1 0 1 0	1 4 1
5 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1	6 1 6 1 6
5 0 0 1 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 0 1 0 0 0 1	1 3 4 3 3
5 0 1 1 1 1 1 0 0 0 0 0 1 1 1 0 0 0 0 0 1 1 1 1 1 0	4 1 4 1 4
5 1 0 0 0 1 0 1 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0	3 3 2 1 1

Алгоритм

Для решении задачи даже не нужно запоминать значения элементов матрицы. Выполняем данные действия [latex]N[/latex] раз, для каждой строки матрицы. Храним ответ в переменной counter, изначально [latex]0[/latex]. По очереди считываем все ее элементы и, если текущий элемент равен [latex]1[/latex], то прибавялем степени [latex]2[/latex], если элемент принадлежит главной диагонали (т.к. тогда это петля, а при подсчете степени ребро-петля учитывается дважды), иначе — [latex]1[/latex]. Затем выводим результат через пробел.

Код

#include <iostream>
using namespace std;

int main() 
{
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int counter = 0, x;
		for (int j = 0; j < n; j++)
		{
			cin >> x;
			if (x)
				counter += (i == j ? 2 : 1);
		}
		cout << counter << " ";
	}
	return 0;
}

#include <iostream>

using namespace std;

int main()

{

ios::sync_with_stdio(false);

int n;

cin >> n;

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

{

int counter = 0, x;

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

{

cin >> x;

if (x)

counter += (i == j ? 2 : 1);

}

cout << counter << " ";

}

return 0;

}

Ссылки

Засчитанное решение на e-olymp.
Код для тестирования на Ideone.

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:

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

26/03/2016 by Сплошнов Кирилл

Задача взята отсюда.

Условие

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

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

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

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

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

Решение

Для решения использовался алгоритм топологической сортировки методом поиска в глубину (подробнее в комментариях к коду). Функция bool dfs() (поиск в глубину) также проверяет, цикличен ли граф, т.к. по условию он может как содержать, так и не содержать циклы. Результат сортировки заносим в вектор result, потом выводим его элементы по порядку.

Тесты

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

Код

#include <iostream>
#include <vector>
#include <algorithm>
#define WHITE 0 //вершина не посещена
#define GREY 1 //вершина обрабатывается
#define BLACK 2 //вершина обработана
using namespace std;

bool dfs (int v, vector<int>* vertex, int* state, vector<int> &result, int size) //возвращает true или false в зависимости от того, был ли найден цикл
{
	state[v] = GREY; //отмечаем, что вершина в процессе обработки
	for (int i = 0; i < vertex[v].size(); i++) //для каждой вершины, в которую можно попасть из данной
	{
		int dest = vertex[v].at(i);
		if (state[dest] == WHITE) //если еще не посетили - запускаем поиск в глубину, возвращаем true, если далее был найден цикл
		{
			if (dfs(dest, vertex, state, result, size))
				return true;
		}
		else if (state[dest] == GREY) //если из вершины можно попасть туда, где мы уже были при данном порядке обхода - найден цикл
		{
			return true;
		}
	}
    //если цикл не найден:
	state[v] = BLACK; //помечаем вершину как обработанную
	result.push_back(v+1); //помещаем ее номер (со сдвигом на 1, из-за разницы в нумерациях) в вектор-результат сортировки
	return false;
}

void topologicalSort(vector<int>* vertex, int* state, vector<int> &result, int size)
{
	for (int i = 0; i < size; i++) //для каждой вершины графа
	{
		if (state[i] == WHITE) //если она еще не посещена
		{
			bool cyclic = dfs(i, vertex, state, result, size); //вызываем для нее поиск в глубину
			if (cyclic) //если нашли цикл, возвращаем единственное значение -1 (по условию)
			{
				result.clear();
				result.push_back(-1);
				return;
			}
		}
	}
	reverse(result.begin(), result.end()); //вершины добавляются в вектор в порядке, противоположном топологической сортировке, так что нужно вызвать для вектора reverse()
}

int main() 
{
	ios::sync_with_stdio(false); 
	int n, m;
	cin >> n >> m;
	vector<int> vertex[n]; //сам граф
	int state[n]; //массив состояний вершин
	vector<int> result;
	fill (state, state + n, WHITE); //изначально ни одна вершина не посещена
	for (int i = 0; i < n; i++)
	{
		int begin, end;
		cin >> begin >> end;
		vertex[begin-1].push_back(end-1);
	}
	topologicalSort(vertex, state, result, n); //сортируем граф
	for (int i = 0; i < result.size(); i++)
		cout << result.at(i) << " ";
	return 0;
}

#include <iostream>

#include <vector>

#include <algorithm>

#define WHITE 0 //вершина не посещена

#define GREY 1 //вершина обрабатывается

#define BLACK 2 //вершина обработана

using namespace std;

bool dfs (int v, vector<int>* vertex, int* state, vector<int> &result, int size) //возвращает true или false в зависимости от того, был ли найден цикл

{

state[v] = GREY; //отмечаем, что вершина в процессе обработки

for (int i = 0; i < vertex[v].size(); i++) //для каждой вершины, в которую можно попасть из данной

{

int dest = vertex[v].at(i);

if (state[dest] == WHITE) //если еще не посетили - запускаем поиск в глубину, возвращаем true, если далее был найден цикл

{

if (dfs(dest, vertex, state, result, size))

return true;

}

else if (state[dest] == GREY) //если из вершины можно попасть туда, где мы уже были при данном порядке обхода - найден цикл

{

return true;

}

//если цикл не найден:

state[v] = BLACK; //помечаем вершину как обработанную

result.push_back(v+1); //помещаем ее номер (со сдвигом на 1, из-за разницы в нумерациях) в вектор-результат сортировки

return false;

}

void topologicalSort(vector<int>* vertex, int* state, vector<int> &result, int size)

{

for (int i = 0; i < size; i++) //для каждой вершины графа

{

if (state[i] == WHITE) //если она еще не посещена

{

bool cyclic = dfs(i, vertex, state, result, size); //вызываем для нее поиск в глубину

if (cyclic) //если нашли цикл, возвращаем единственное значение -1 (по условию)

{

result.clear();

result.push_back(-1);

return;

}

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

}

int main()

{

ios::sync_with_stdio(false);

int n, m;

cin >> n >> m;

vector<int> vertex[n]; //сам граф

int state[n]; //массив состояний вершин

vector<int> result;

fill (state, state + n, WHITE); //изначально ни одна вершина не посещена

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

{

int begin, end;

cin >> begin >> end;

vertex[begin-1].push_back(end-1);

}

topologicalSort(vertex, state, result, n); //сортируем граф

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

cout << result.at(i) << " ";

return 0;

}

Ссылки

Код на ideaone.

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

Наглядное объяснение топологической сортировки здесь.

Related Images:

e-olymp 185. Орки будущего

26/03/2016 by Сплошнов Кирилл

Условие

Задача взята с сайта e-olymp. Полное условие можно прочитать здесь.

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

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

Из условия:

«…теперь в их алфавите в качестве гласных использовались только буквы «а», «o», «e», «u».»

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

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

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

Единственное число – номер Орка, признанного Орком Года. В случае, если однозначно определить победителя невозможно, вывести "O-o-o-rks...".

Решение

Напишем 2 функции: int countSyllables(char* speech), которая будет считать гласные (т.к. кол-во слогов всегда равно кол-ву гласных), и int countWords(char* speech), считающую кол-во слов. Для написания первой воспользуемся стандартной функцией strpbrk(), для второй — функцией strtok(). Для каждой считанной строки будем по очереди вызывать эти 2 функции и заносить полученные значения в соответствующие массивы syllables и words (вызывать будем именно в таком порядке, т.к. функция strtok() делает строку непригодной к дальнейшему использованию).

Далее, чтобы избежать работы с вещественными числами (что может привести к потере точности) будем сравнивать полученные результаты согласно требованиям, но вместо деления воспользуемся соотношением пропорции. Заведем переменную-флаг ambiguous, показывающую, однозначен ли победитель. В зависимости от ее значения, выведем номер победителя (переменная winner, по умолчанию победитель — первый орк) или строку "O-o-o-rks..."

Тесты

№	Входные данные	Выходные данные
1	2 Hello, World! Ok.	2
2	3 Ooh, hey there 😀 Hello, World of me! Will be ambiguous???	O-o-o-rks…
3	4 Some people like C! Some say Java is better. Heh, or maybe Python? Who knows for sure?	O-o-o-rks…
4	5 A Lannister always pays his debts. Winter is coming… Hear me roar! King of the North! Sherlock?	1
5	8 O-o-o-rks… Is not the same as… O-o-o-rks! or O-o-orks… …trust me,… …when writing code, one must be extremely careful! …beware!	O-o-o-rks…

Код

#include <iostream>
#include <cstring>
#define SIZE 1001
using namespace std;

int countWords(char* speech)
{
    int wordCount = 0;
    char delim[] = " ,.!?:;-\"\'";
    char* pointer = strtok(speech, delim);
    while (pointer != NULL)
    {
        pointer = strtok(NULL, delim);
        wordCount++;
    }
    return wordCount;   
}

int countSyllables(char* speech)
{
    int syllableCount = 0;
    char vowels[] = "aoeuAOEU";
    char* pointer = strpbrk(speech, vowels);
    while (pointer != NULL)
    {
        pointer = strpbrk(pointer + 1, vowels);
        syllableCount++;
    }
    return syllableCount;
}

int main() 
{
    int n;
    cin >> n;
    char speech[SIZE];
    int words[n];
    int syllables[n];
    cin.ignore(); //пропустить перевод строки между числом и первой речью
    for (int i = 0; i < n; i++)
    {
        cin.getline(speech, SIZE);
        syllables[i] = countSyllables(speech);
        words[i] = countWords(speech);
    }
    bool many = false;
    int winner = 0;
    for (int i = 1; i < n; i++)
    {
        if (syllables[i] * words[winner] < syllables[winner] * words[i])
        {
            winner = i;
            many = false;
        }
        else if (syllables[i] * words[winner] == syllables[winner] * words[i])
        {
            if (words[winner] < words[i])
            {
                winner = i;
                many = false;
            }
            else if (words[winner] == words[i])
                many = true;
        }
    }
    if (many)
        cout << "O-o-o-rks...";
    else
        cout << winner + 1 << endl;
    return 0;
}

#include <iostream>

#include <cstring>

#define SIZE 1001

using namespace std;

int countWords(char* speech)

{

int wordCount = 0;

char delim[] = " ,.!?:;-\"\'";

char* pointer = strtok(speech, delim);

while (pointer != NULL)

{

pointer = strtok(NULL, delim);

wordCount++;

}

return wordCount;

}

int countSyllables(char* speech)

{

int syllableCount = 0;

char vowels[] = "aoeuAOEU";

char* pointer = strpbrk(speech, vowels);

while (pointer != NULL)

{

pointer = strpbrk(pointer + 1, vowels);

syllableCount++;

}

return syllableCount;

}

int main()

{

int n;

cin >> n;

char speech[SIZE];

int words[n];

int syllables[n];

cin.ignore(); //пропустить перевод строки между числом и первой речью

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

{

cin.getline(speech, SIZE);

syllables[i] = countSyllables(speech);

words[i] = countWords(speech);

}

bool many = false;

int winner = 0;

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

{

if (syllables[i] * words[winner] < syllables[winner] * words[i])

{

winner = i;

many = false;

}

else if (syllables[i] * words[winner] == syllables[winner] * words[i])

{

if (words[winner] < words[i])

{

winner = i;

many = false;

}

else if (words[winner] == words[i])

many = true;

}

if (many)

cout << "O-o-o-rks...";

else

cout << winner + 1 << endl;

return 0;

}

Ссылки

Код на ideaone.

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

Related Images:

A299

26/03/2016 by Сплошнов Кирилл

Условие

Дана последовательность действительных чисел [latex]a_1, a_2, \dots, a_n[/latex]. Требуется домножить все члены последовательности на квадрат её наименьшего члена, если [latex]a_1 \geq 0[/latex], в противном случае — на квадрат наибольшего.

Решение

Для решения воспользуемся стандартным классом vector. Для этого заведем переменную данного типа, заполним её числами со входного потока. Далее, в зависимости от первого (нулевого) элемента вектора, воспользуемся стандартной функцией min_element() или max_element() (библиотека algorithm). Далее умножим каждый элемент на (соответственно) минимум/максимум и выведем последовательность.

Тесты

№	Входные данные	Выходные данные
1	-2 2 43 5 -10 12 0 -1	-3698 3698 79507 9245 -18490 22188 0 -1849
2	0 100 99 0 -1 1	0 100 99 0 -1 1
3	42 1 1 1 0 -1 24 -24 -42	74088 1764 1764 1764 0 -1764 42336 -42336 -74088

Код

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

int main() 
{
	vector<int> x;
	int a;
	while (cin >> a)
		x.push_back(a);
	if (x.at(0) >= 0)
	{
		int min = *min_element(x.begin(), x.end());
		for (int &i : x)
			i *= min * min;
	}
	else
	{
		int max = *max_element(x.begin(), x.end());
		for (int &i : x)
			i *= max * max;
	}
	for (int i : x)
		cout << i << " ";
	return 0;
}

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

int main()

{

vector<int> x;

int a;

while (cin >> a)

x.push_back(a);

if (x.at(0) >= 0)

{

int min = *min_element(x.begin(), x.end());

for (int &i : x)

i *= min * min;

}

else

{

int max = *max_element(x.begin(), x.end());

for (int &i : x)

i *= max * max;

}

for (int i : x)

cout << i << " ";

return 0;

}

Замечание

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

Ссылки

Код на ideaone (vector).

Related Images:

e-olymp 1073. Статическая сложность

05/03/2016 by Сплошнов Кирилл

Условие

Задача взята с сайта e-olymp, полное условие можно прочитать здесь.

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

В первой строке находится целое число [latex]k[/latex] — число программ во входном файле. Затем идут [latex]k[/latex] программ, удовлетворяющих приведенной грамматике. Пробелы и переводы строк могут встречаться везде в программе, но не в ключевых словах [latex]BEGIN[/latex], [latex]END[/latex], [latex]LOOP[/latex] и [latex]OP[/latex], нет их и в целых числах.

Вложенность операторов [latex]LOOP[/latex] не превышает [latex]10[/latex], размер входного файла не более [latex]2[/latex] Кбайт, коэффициенты многочлена в ответе не превышают [latex]50000[/latex].

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

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

Для каждой программы сначала идет строка с номером программы. В следующей строке записывается время работы программы в терминах [latex]n[/latex] — многочлен степени не более [latex]10[/latex]. Многочлен должен быть записан обычным способом, то есть подобные слагаемые должны быть приведены, слагаемое большей степени должно предшествовать слагаемому меньшей степени, слагаемые с коэффициентом [latex]0[/latex] не записываются, множители [latex]1[/latex] не записываются. Общий вид второй строки [latex]Runtime = a*n^{10}+b*n^9+\ldots+i*n^2+j*n+k[/latex]. Если время выполнения нулевое, нужно вывести [latex]Runtime = 0[/latex]. За строкой с многочленом должна следовать пустая строка, кроме последнего тестового случая.

Решение

Создадим массив коэффициентов [latex]coefficients[/latex] на 11 элементов (нулевой элемент — свободный член, 10-й — десятая (максимальная) степень). В цикле для каждой программы будем:

Обнулять массив [latex]coefficients[/latex].
Заполнять его новыми данными с помощью функции void getCoefficients(int* coefficients);
Строить на основании полученных коэффициентов требуемую строку-многочлен, за это отвечает функция string toString(int* coefficients);
Выводить требуемую информацию.

Рассмотрим процесс заполнения массива. Создадим вектор для строк [latex]params[/latex], где будем хранить кол-ва повторений для всех открытых циклах, от внешнего к внутреннему, и переменную-счетчик [latex]keywords[/latex]. Функция будет завершать свою работу при значении [latex]keywords[/latex] равном [latex]0[/latex]. Изначально присвоим [latex]keywords = 1[/latex] (оператор [latex]BEGIN[/latex]). Далее, в цикле будем, в зависимости от прочитанного оператора:

[latex]END[/latex]: уменьшаем значение [latex]keywords[/latex] на [latex]1[/latex], удаляем последний элемент из [latex]params[/latex] (чтобы не было проблем с последним оператором [latex]END[/latex] (пустой вектор), положим в него перед циклом строку «[latex]1[/latex]»). Если [latex]keywords[/latex] равно нулю — завершаем работу.
[latex]LOOP[/latex]: увеличиваем значение [latex]keywords[/latex] на [latex]1[/latex], считываем следующую строку и добавляем ее в конец [latex]params[/latex].
[latex]OP[/latex]: Считываем следующую строку, преобразовываем ее к числу (кол-ву операций) стандартной функцией stoi(). Далее, проходя по строкам из [latex]params[/latex], если строка равна [latex]n[/latex], увеличиваем степень (номер ячейки массива, куда прибавим результат) на [latex]1[/latex], иначе — преобразовываем к числу и домножаем на кол-во операций. Прибавляем полученный результат к числу в соответствующей ячейке массива.

Функция toString() реализована достаточно просто (см. код). Пробегаем по элементам массива с конца, и если элемент [latex]n[/latex] не равен нулю, прибавляем к строке-многочлену соответствующий набор символов (отдельно учитывая случаи при [latex]n = 1[/latex], [latex]n=-1[/latex], первой и нулевой степени и т.д.). Если в итоге строка пустая, возвращаем «[latex]0[/latex]».

Тесты

№

Ввод

Вывод

2
BEGIN
LOOP n
OP 4
LOOP 3
LOOP n
OP 1
END
OP 2
END
OP 1
END
OP 17
END

BEGIN
OP 1997 LOOP n LOOP n OP 1 END END
END

Program #1
Runtime = 3*n^2+11*n+17

Program #2
Runtime = n^2+1997

3
BEGIN
END

BEGIN
LOOP n LOOP n LOOP n OP 1
LOOP n LOOP n LOOP n OP 1
LOOP n LOOP n LOOP n OP 1
END END END OP 3
END END END OP 3
END END END OP 3
END

BEGIN OP 42
LOOP n LOOP 5 LOOP n
OP 7 END OP 2 END OP 1 END
OP 1 END

Program #1
Runtime = 0

Program #2
Runtime = n^9+4*n^6+4*n^3+3

Program #3
Runtime = 35*n^2+11*n+43

Код

#include <iostream>
#include <string>
#include <vector>
#define MAX_POWER 10
using namespace std;

void getCoefficients(int* coefficients)
{
	int keywords = 1;
	vector<string> params;
	string begin;
	cin >> begin;
	params.push_back(((string) "1")); //чтобы вектор не был пустой на последнем END (который соответствует BEGIN)
	while (true)
	{
		string keyword;
		cin >> keyword;
		if (keyword == (string)"END")
        {
            keywords--;
            params.pop_back();
            if (keywords == 0) 
            {
            	break;
            }
        }
        else if (keyword == (string)"LOOP")
        {
            keywords++;
            string param;
            cin >> param;
            params.push_back(param);
        }
        else if (keyword == (string)"OP")
        {
        	string num;
        	cin >> num;
            int coefficient = stoi(num);
            int multiplier = 1, pow = 0;
            for (string param : params)
            {
                if (param == (string)"n") 
                {
                	pow++;
                }
                else 
                {
                	multiplier *= stoi(param);
                }
            }
            coefficients[pow] += coefficient * multiplier;
        }
	}
}

string toString(int* coefficients)
{
	string result;
    for (int i = MAX_POWER; i > 0; i--)
    {
        if (coefficients[i] != 0)
            {
                if (coefficients[i] == 1) 
                {
                	result += "n";
                }
                else if (coefficients[i] == -1) 
                {
                	result += "-n";
                }
                else
                {
                	result += to_string(coefficients[i]); //стандартная функция, преобразовывает число в строку
                	result += "*n";
                }
                if (i != 1) //если степень не первая, добавляем "^[степень]"
                {
                	result += "^";
                	result += to_string(i);
                }
            }
            if (coefficients[i-1] > 0 && result.length() != 0) //проверка, чтобы + не стоял в начале строки и между членами не было "+-"
            {
            	result += "+";
            }
        }
        if (result.length() == 0 || coefficients[0] != 0) //прибавляем последний коэффициент, если он не равен нулю или строка пустая
        {
        	result += to_string(coefficients[0]);
        }
        return result;
}

int main() 
{
	int n;
	cin >> n;
	int coefficients[MAX_POWER + 1];
	for (int i = 1; i <= n; i++)
	{
		cout << "Program #" << i << endl;
		fill(coefficients, coefficients + MAX_POWER + 1, 0); //обнуляем массив коэффициентов
		getCoefficients(coefficients);
		cout << "Runtime = " << toString(coefficients) << endl;
		if (i != n)
		{
			cout << endl; 
		}
	}
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

#include <iostream>

#include <string>

#include <vector>

#define MAX_POWER 10

using namespace std;

void getCoefficients(int* coefficients)

{

int keywords = 1;

vector<string> params;

string begin;

cin >> begin;

params.push_back(((string) "1")); //чтобы вектор не был пустой на последнем END (который соответствует BEGIN)

while (true)

{

string keyword;

cin >> keyword;

if (keyword == (string)"END")

{

keywords--;

params.pop_back();

if (keywords == 0)

{

break;

}

else if (keyword == (string)"LOOP")

{

keywords++;

string param;

cin >> param;

params.push_back(param);

}

else if (keyword == (string)"OP")

{

string num;

cin >> num;

int coefficient = stoi(num);

int multiplier = 1, pow = 0;

for (string param : params)

{

if (param == (string)"n")

{

pow++;

}

else

{

multiplier *= stoi(param);

}

coefficients[pow] += coefficient * multiplier;

}

string toString(int* coefficients)

{

string result;

for (int i = MAX_POWER; i > 0; i--)

{

if (coefficients[i] != 0)

{

if (coefficients[i] == 1)

{

result += "n";

}

else if (coefficients[i] == -1)

{

result += "-n";

}

else

{

result += to_string(coefficients[i]); //стандартная функция, преобразовывает число в строку

result += "*n";

}

if (i != 1) //если степень не первая, добавляем "^[степень]"

{

result += "^";

result += to_string(i);

}

if (coefficients[i-1] > 0 && result.length() != 0) //проверка, чтобы + не стоял в начале строки и между членами не было "+-"

{

result += "+";

}

if (result.length() == 0 || coefficients[0] != 0) //прибавляем последний коэффициент, если он не равен нулю или строка пустая

{

result += to_string(coefficients[0]);

}

return result;

}

int main()

{

int n;

cin >> n;

int coefficients[MAX_POWER + 1];

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

{

cout << "Program #" << i << endl;

fill(coefficients, coefficients + MAX_POWER + 1, 0); //обнуляем массив коэффициентов

getCoefficients(coefficients);

cout << "Runtime = " << toString(coefficients) << endl;

if (i != n)

{

cout << endl;

}

return 0;

}

Ссылки

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

Рабочий код на ideaone.

Related Images:

e-olymp 1072. Химические реакции

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

Условие

Задача взята с сайта e-olymp, полное условие можно прочитать здесь.

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

В первой строке находится формула — левая часть уравнения, во второй- одно число [latex]N (1 \leq N \leq 10)[/latex] — количество рассматриваемых правых частей, в каждой из последующих [latex]N[/latex] строк — одна формула — предполагаемая правая часть уравнения.

Длина формулы не превосходит [latex]100[/latex] символов, каждый отдельный химический элемент встречается всего не более [latex]10000[/latex] раз в каждой формуле.

(Примечание: понятие формулы в данном алфавите можно прочитать по ссылке выше.)

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

Для каждой из [latex]N[/latex] заданных строк вывести одну строку вида

формула левой части==формула правой части

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

формула левой части!=формула правой части

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

Решение (вспомогательные функции)

Так как задача достаточно объемная, напишем ряд вспомогательных функций:

Определяет, является ли символ цифрой.

bool isDigit(char c);

1

bool isDigit(char c);
Определяет, является ли символ буквой в верхнем регистре.

bool isUpperCaseLetter(char c);

1

bool isUpperCaseLetter(char c);
Определяет, является ли символ буквой в нижнем регистре.

bool isLowerCaseLetter(char c);

1

bool isLowerCaseLetter(char c);
Будем хранить содержимое формулы используя структуру map (карта), ключами будут выступать названия элементов (строки), значениями — количества их вхождений. Если элемента в карте нет, добавляем пару <элемент, кол-во>, иначе — прибавляем к старом числу вхождений новое. За это отвечает следующая функция.

void update(map<string, int> &map, string key, int value);

1

void update(map<string, int> &map, string key, int value);
Для простоты разобьем формулу на подформулы (по знаку [latex]+[/latex], если он встречается), и будем работать с каждой формулой по отдельности. Функция разбивает строку на подстроки по знаку [latex]+[/latex] и заполняет ими вектор [latex]storage[/latex] (так как мы не знаем кол-во подформул заранее, вектор предпочтительнее массива).

void split(string formula, vector<string> &storage);

1

void split(string formula, vector<string> &storage);
По условию, перед каждой подформулой может идти множитель, относящейся ко всей подформуле. Функция возвращает множитель ( [latex]1[/latex], если множитель не записан явно).

int getMultiplier(string formula);

1

int getMultiplier(string formula);
Основная функция. Добавляет в карту [latex]content[/latex] содержимое подформулы.

void getContent(string formula, int multiplier, map<string, int> &content);

1

void getContent(string formula, int multiplier, map<string, int> &content);
Обрабатывает формулу. Просто вызывает функции №[latex]6[/latex] и №[latex]7[/latex] по очереди для каждой из подформул (элементов из [latex]subformulas[/latex]).

void process(vector<string> subformulas, map<string, int> &content);

1

void process(vector<string> subformulas, map<string, int> &content);

Решение (основной алгоритм)

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

void getContent(string formula, int multiplier, map<string, int> &content);

1	void getContent(string formula, int multiplier, map<string, int> &content);

Тут:

[latex]formula[/latex] — подформула обрабатываемой формулы (без общего множителя);
[latex]multiplier[/latex] — множитель, определяется предыдущей функцией, перед вызовом данной;
[latex]content[/latex] — карта, куда записываются элементы всех подформул текущей формулы (доступ осуществляется по адресу).

Алгоритм разделяется на 2 случая, в зависимости от наличия скобок. Предположим, скобок в подформуле (далее — просто формуле) нет. Заведем переменные [latex]name[/latex] (название элемента. тип string) и [latex]coefficient[/latex] (задний коэффициент, тип string). Тогда, проходя по порядку по символам формулы, будем выполнять следующие действия в зависимости от текущего символа([latex]c[/latex]):

[latex]c[/latex] — цифра: добавляем его в конец строки [latex]coefficient[/latex];
[latex]c[/latex] — буква в нижнем регистре: добавляем его в конец строки [latex]name[/latex];
[latex]c[/latex] — буква в верхнем регистре: если строка [latex]name[/latex] — пустая (первый элемент в формуле), то добавляем его в конец строки [latex]name[/latex]. Иначе, сперва обнуляем [latex]name[/latex], потом добавляем. Тогда, если строка [latex]coefficient[/latex] — пустая, присваиваем [latex]coefficient=[/latex]»[latex]1[/latex]». Получаем количество вхождений элемента как [latex]multiplier*stoi(coefficient)[/latex], где stoi() — стандартная функция, преобразующая число к строке. Затем добавляем в карту элемент и полученное кол-во вхождений.

update(content, name, multiplier * stoi(coefficient));

140

update(content, name, multiplier * stoi(coefficient));

(Примечание: пункт [latex]3[/latex] для последнего элемента (кроме обновления значения [latex]name[/latex]) придется повторить отдельно.)

update(content, name, multiplier * stoi(coefficient));

153	update(content, name, multiplier * stoi(coefficient));

Если же в формуле имеются скобки, то:

Находим первую открывающую скобку.
Находим соответствующую ей закрывающую скобку.
Для выражения в скобках вычисляем задний коэффициент (см. код), заносим в переменную [latex]newMultiplier[/latex] значение множителя для выражения внутри скобок.
Рекурсивно вызываем функцию getContent() для:
1. Выражения перед открывающей скобкой, если формула не начинается с нее.
  
  getContent(formula.substr(0, begin - 1), multiplier, content);
  
  106
  
  getContent(formula.substr(0, begin - 1), multiplier, content);
  
  ([latex]begin[/latex] — номер первого символа внутри скобок.)
2. Выражения внутри скобок.
  
  getContent(formula.substr(begin, end - begin), newMultiplier, content);
  
  108
  
  getContent(formula.substr(begin, end - begin), newMultiplier, content);
  
  ([latex]end[/latex] — номер закрывающей скобки.)
3. Выражения после закрывающей скобки или заднего коэффициента, если присутствует (если только скобка/коэффициент не является концом формулы).
  
  getContent(formula.substr(afterEnd), multiplier, content);
  
  111
  
  getContent(formula.substr(afterEnd), multiplier, content);
  
  ([latex]afterEnd[/latex] — следующий после скобки/коэффициента символ.)

Этот алгоритм фактически является решением задачи. Теперь в методе [latex]main[/latex] надо всего лишь обработать главную формулу, а затем для каждого случая в цикле — сравниваемую с ней формулу, сравнив после содержимое их карт (сравнение осуществляется просто используя оператор сравнения ==). Обработка подразумевает последовательный вызов функций split() и process().

Тесты

№	Ввод	Вывод
1	C2H5OH+3O2+3(SiO2) 6 2CO2+3H2O+3SiO2 2C+6H+13O+3Si 99C2H5OH+3SiO2 3SiO4+C2H5OH C2H5OH+3O2+3(SiO2)+Ge 3(Si(O)2)+2CO+3H2O+O2	C2H5OH+3O2+3(SiO2)==2CO2+3H2O+3SiO2 C2H5OH+3O2+3(SiO2)==2C+6H+13O+3Si C2H5OH+3O2+3(SiO2)!=99C2H5OH+3SiO2 C2H5OH+3O2+3(SiO2)==3SiO4+C2H5OH C2H5OH+3O2+3(SiO2)!=C2H5OH+3O2+3(SiO2)+Ge C2H5OH+3O2+3(SiO2)==3(Si(O)2)+2CO+3H2O+O2
2	2H2O 5 HHOHHO 2H+H2+(O(O)) 2((H2)O) HOHHOHe H4O	2H2O==HHOHHO 2H2O==2H+H2+(O(O)) 2H2O==2((H2)O) 2H2O!=HOHHOHe 2H2O!=H4O
3	8Zn+Ar4+Ne 3 Ne(Ar2(Zn)4)2 2Ne(Ar2(Zn)4) Ne+2Zn2(((((Ar)))))2Zn2	8Zn+Ar4+Ne==Ne(Ar2(Zn)4)2 8Zn+Ar4+Ne!=2Ne(Ar2(Zn)4) 8Zn+Ar4+Ne==Ne+2Zn2(((((Ar)))))2Zn2

Код

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

bool isDigit(char c) { return  c >= '0' && c <= '9'; }

bool isUpperCaseLetter(char c) { return  c >= 'A' && c <= 'Z'; }

bool isLowerCaseLetter(char c) { return  c >= 'a' && c <= 'z'; }

void update(map<string, int> &map, string key, int value)
{
    if (map.count(key)) //вернет 0 (false) если элемент не найден, иначе - 1 (true)
    {
        map.at(key) = map.at(key) + value; //обновляем значение элемента в карте
    }
    else
    {
        map.insert(make_pair(key, value)); //добавляем элемент в карту
    }
}

void split(string formula, vector<string> &storage)
{
    int begin = 0, length = 0;
    for (int i = 0; i < formula.length(); i++)
    {
        if (formula.at(i) == '+')
        {
            storage.push_back(formula.substr(begin, length));
            length = 1;
            begin = ++i;
        }
        else
        {
            length++;
        }
    }
    storage.push_back(formula.substr(begin, length));
}

int getMultiplier(string formula)
{
    int res = 0;
    for (int i = 0; i < formula.length(); i++)
    {
        if (isDigit(formula.at(i))) 
        {
            res *= 10;
            res += (formula.at(i) - '0'); //получаем из символа соответствующую цифру
        }
        else break;
    }
    return res == 0 ? 1 : res; //0 - если перед формулой нет множителя, тогда он должен быть 1
}

void getContent(string formula, int multiplier, map<string, int> &content)
{ 
    if (formula.find('(') != string::npos) //если есть скобки
    {
        int begin = formula.find('(') + 1; //первый символ внутри скобок
        int end;
        int bracketCounter = 1;
        for (int i = begin; true; i++)
        {
            if (formula.at(i) == '(')
            {
                bracketCounter ++;
            }
            else if (formula.at(i) == ')')
            {
                bracketCounter--;
                if (bracketCounter == 0)
                {
                    end = i; //находим соответствующую закрывающую скобку
                    break;
                }
            }
        }
        int newMultiplier = multiplier;
        int afterEnd = end + 1;
        int backCoefficient = 0; //вычисляем коэффициент за скобочным выражением
        for (int i = 1; true; i++)
        {
            if (end + i != formula.length() && isDigit(formula.at(end + i))) //пока есть числа за закрывающей скобкой, обновляем значение заднего коэффициента
            {
                backCoefficient *= 10;
                backCoefficient += (formula.at(end + i) - '0');
                afterEnd++;
            }
            else
            {
                if (backCoefficient == 0) //если чисел после закрывающей скобки нет, коэффициент равен 1
                {
                    backCoefficient++;
                }
                newMultiplier *= backCoefficient; //вычисляем новое значение множителя для выражения внутри скобок
                break;
            }
        }
        if (begin != 1)
        {
            getContent(formula.substr(0, begin - 1), multiplier, content); 
        }
        getContent(formula.substr(begin, end - begin), newMultiplier, content); 
        if (afterEnd < formula.length())
        {
            getContent(formula.substr(afterEnd), multiplier, content);
        }
    }
    else //если скобок нет
    {
        string name = "";
        string coefficient = "";
        for (char c : formula)
        {
            if (isDigit(c)) 
            {
                coefficient += c;
            }
            else if (isLowerCaseLetter(c)) 
            {
                name += c;
            }
            else if (isUpperCaseLetter(c))
            {
                if (name.empty()) 
                {
                    name += c;
                }
                else
                {
                    if (coefficient.empty()) 
                    {
                        coefficient = "1";
                    }
                    update(content, name, multiplier * stoi(coefficient));
                    name.clear();
                    name += c;
                    coefficient = "";
                }
            }
        }
        if (!name.empty())
        {
            if (coefficient.empty()) 
            {
                coefficient = "1";
            }
            update(content, name, multiplier * stoi(coefficient));
        }
    }
}

void process(vector<string> subformulas, map<string, int> &content)
{
    for (string subformula : subformulas) //для каждой подформулы:
    {
        int multiplier = getMultiplier(subformula); //вычисляем множитель перед ней
        if (multiplier != 1) //если множитель записан явно
        {
            getContent(subformula.substr(floor(log10(multiplier)+1)), multiplier, content); //передаем в функцию подформулу, начиная с первого символа, не относящегося к переднему множителю
        }
        else
        {
            getContent(subformula, multiplier, content); //иначе передаем подформулу целиком
        }
    }
}

int main() 
{
    string mainFormula;
    vector<string> mainSubformulas;
    map<string, int> mainContent;
    cin >> mainFormula;
    split(mainFormula, mainSubformulas);
    process(mainSubformulas, mainContent);
    int n;
    cin >> n;
    string formulaToCompare;
    vector<string> subformulasToCompare;
    map<string, int> contentToCompare;
    for (int i = 0; i < n; i++)
    {
        subformulasToCompare.clear(); //
        contentToCompare.clear();
        cin >> formulaToCompare;
        split(formulaToCompare, subformulasToCompare);
        process(subformulasToCompare, contentToCompare);
        cout << mainFormula << (mainContent == contentToCompare ? "==" : "!=") << formulaToCompare << 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

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

#include <iostream>

#include <cmath>

#include <string>

#include <vector>

#include <map>

using namespace std;

bool isDigit(char c) { return c >= '0' && c <= '9'; }

bool isUpperCaseLetter(char c) { return c >= 'A' && c <= 'Z'; }

bool isLowerCaseLetter(char c) { return c >= 'a' && c <= 'z'; }

void update(map<string, int> &map, string key, int value)

{

if (map.count(key)) //вернет 0 (false) если элемент не найден, иначе - 1 (true)

{

map.at(key) = map.at(key) + value; //обновляем значение элемента в карте

}

else

{

map.insert(make_pair(key, value)); //добавляем элемент в карту

}

void split(string formula, vector<string> &storage)

{

int begin = 0, length = 0;

for (int i = 0; i < formula.length(); i++)

{

if (formula.at(i) == '+')

{

storage.push_back(formula.substr(begin, length));

length = 1;

begin = ++i;

}

else

{

length++;

}

storage.push_back(formula.substr(begin, length));

}

int getMultiplier(string formula)

{

int res = 0;

for (int i = 0; i < formula.length(); i++)

{

if (isDigit(formula.at(i)))

{

res *= 10;

res += (formula.at(i) - '0'); //получаем из символа соответствующую цифру

}

else break;

}

return res == 0 ? 1 : res; //0 - если перед формулой нет множителя, тогда он должен быть 1

}

void getContent(string formula, int multiplier, map<string, int> &content)

{

if (formula.find('(') != string::npos) //если есть скобки

{

int begin = formula.find('(') + 1; //первый символ внутри скобок

int end;

int bracketCounter = 1;

for (int i = begin; true; i++)

{

if (formula.at(i) == '(')

{

bracketCounter ++;

}

else if (formula.at(i) == ')')

{

bracketCounter--;

if (bracketCounter == 0)

{

end = i; //находим соответствующую закрывающую скобку

break;

}

int newMultiplier = multiplier;

int afterEnd = end + 1;

int backCoefficient = 0; //вычисляем коэффициент за скобочным выражением

for (int i = 1; true; i++)

{

if (end + i != formula.length() && isDigit(formula.at(end + i))) //пока есть числа за закрывающей скобкой, обновляем значение заднего коэффициента

{

backCoefficient *= 10;

backCoefficient += (formula.at(end + i) - '0');

afterEnd++;

}

else

{

if (backCoefficient == 0) //если чисел после закрывающей скобки нет, коэффициент равен 1

{

backCoefficient++;

}

newMultiplier *= backCoefficient; //вычисляем новое значение множителя для выражения внутри скобок

break;

}

if (begin != 1)

{

getContent(formula.substr(0, begin - 1), multiplier, content);

}

getContent(formula.substr(begin, end - begin), newMultiplier, content);

if (afterEnd < formula.length())

{

getContent(formula.substr(afterEnd), multiplier, content);

}

else //если скобок нет

{

string name = "";

string coefficient = "";

for (char c : formula)

{

if (isDigit(c))

{

coefficient += c;

}

else if (isLowerCaseLetter(c))

{

name += c;

}

else if (isUpperCaseLetter(c))

{

if (name.empty())

{

name += c;

}

else

{

if (coefficient.empty())

{

coefficient = "1";

}

update(content, name, multiplier * stoi(coefficient));

name.clear();

name += c;

coefficient = "";

}

if (!name.empty())

{

if (coefficient.empty())

{

coefficient = "1";

}

update(content, name, multiplier * stoi(coefficient));

}

void process(vector<string> subformulas, map<string, int> &content)

{

for (string subformula : subformulas) //для каждой подформулы:

{

int multiplier = getMultiplier(subformula); //вычисляем множитель перед ней

if (multiplier != 1) //если множитель записан явно

{

getContent(subformula.substr(floor(log10(multiplier)+1)), multiplier, content); //передаем в функцию подформулу, начиная с первого символа, не относящегося к переднему множителю

}

else

{

getContent(subformula, multiplier, content); //иначе передаем подформулу целиком

}

int main()

{

string mainFormula;

vector<string> mainSubformulas;

map<string, int> mainContent;

cin >> mainFormula;

split(mainFormula, mainSubformulas);

process(mainSubformulas, mainContent);

int n;

cin >> n;

string formulaToCompare;

vector<string> subformulasToCompare;

map<string, int> contentToCompare;

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

{

subformulasToCompare.clear(); //

contentToCompare.clear();

cin >> formulaToCompare;

split(formulaToCompare, subformulasToCompare);

process(subformulasToCompare, contentToCompare);

cout << mainFormula << (mainContent == contentToCompare ? "==" : "!=") << formulaToCompare << endl;

}

return 0;

}

Ссылки

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

Код на ideaone.

Related Images:

e-olymp 331. Предложение — чемпион

30/11/2015 by Сплошнов Кирилл

Условие

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

Замечание

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

Тесты

Входные данные	Номер предложения
No palindrom here. Here it is: abcba! Seriously, I just hate orks…	2
Some random text ahead: AaA o-O-o I. 1 22 333. Result will be 1.	1
Some random text ahead: AaA o-O-o I. 1 22 333 4444. Now result will be 2!	2
Some random text ahead: AaA o-O-o I. 1 — 22 — 333. Result will be 1.	1
No. Palindrom. at. ALL?!	0

Решение

Заведем переменную [latex]currentSentence[/latex], хранящую номер текущего предложения, будем считывать по слову и увеличивать ее значение на 1, если текущее слово заканчивается на точку, восклицательный или вопросительный знак. Далее, поочередно удаляем с конца лишние символы, заменяя их терминальным, пока не встретится первая буква. Затем переводим слово в нижний регистр и проверяем его на палиндромность, если да — увеличиваем на 1 переменную-счетчик кол-ва палиндромов в текущем предложении [latex]palCount[/latex]. Если слово было последним в предложении (за это отвечает флаг [latex]endOfSentence[/latex]) — сравниваем предложение с предыдущим чемпионом, после обнуляем значение [latex]palCount[/latex].

Код

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

int main() 
{
	char s[256];
	int maxPalNum = 0;
	int champion = 0;
	int currentSentence = 1; 
	int palCount = 0;
	while (cin >> s)
	{
		if (s[0] == '-' && strlen(s) == 1) 
			continue; //если тире, то просто считываем следующее слово
		bool endOfSentence = false;
		if (s[strlen(s)-1] == '.' || s[strlen(s)-1] == '!' || s[strlen(s)-1] == '?')
			endOfSentence = true; //слово - последнее в предложении
		for (int i = strlen(s) - 1; i >= 0; i--)
		{
			if (!(s[i] >= 'a' && s[i] <= 'z' || s[i] >= 'A' && s[i] <= 'Z' || s[i] >= '1' && s[i] <= '9' || s[i] == '-'))
				s[i] = '\0';
			else
				break;
		}
		for (int i = 0; i < strlen(s); i++)//перевод в нижний регистр
		{
			if (s[i] >= 'A' && s[i] <= 'Z')
				s[i] += 32;
		}
		bool pal = true;
		for (int i = 0; i < strlen(s) / 2; i++)
		{
			if (s[i] != s[strlen(s)-i-1])
			{
				pal = false;
				break;
			}
		}
		if (pal)
			palCount ++;
		if (endOfSentence) //если слово было последним - сравниваем предложения
		{
			if (palCount > maxPalNum)
			{
				maxPalNum = palCount;
				champion = currentSentence;
			}
			currentSentence++;
			palCount = 0;
		}
	}
	cout << champion;
	return 0;
}

#include <iostream>

#include <cstring>

using namespace std;

int main()

{

char s[256];

int maxPalNum = 0;

int champion = 0;

int currentSentence = 1;

int palCount = 0;

while (cin >> s)

{

if (s[0] == '-' && strlen(s) == 1)

continue; //если тире, то просто считываем следующее слово

bool endOfSentence = false;

if (s[strlen(s)-1] == '.' || s[strlen(s)-1] == '!' || s[strlen(s)-1] == '?')

endOfSentence = true; //слово - последнее в предложении

for (int i = strlen(s) - 1; i >= 0; i--)

{

if (!(s[i] >= 'a' && s[i] <= 'z' || s[i] >= 'A' && s[i] <= 'Z' || s[i] >= '1' && s[i] <= '9' || s[i] == '-'))

s[i] = '\0';

else

break;

}

for (int i = 0; i < strlen(s); i++)//перевод в нижний регистр

{

if (s[i] >= 'A' && s[i] <= 'Z')

s[i] += 32;

}

bool pal = true;

for (int i = 0; i < strlen(s) / 2; i++)

{

if (s[i] != s[strlen(s)-i-1])

{

pal = false;

break;

}

if (pal)

palCount ++;

if (endOfSentence) //если слово было последним - сравниваем предложения

{

if (palCount > maxPalNum)

{

maxPalNum = palCount;

champion = currentSentence;

}

currentSentence++;

palCount = 0;

}

cout << champion;

return 0;

}

Ссылки

Рабочий код на Ideaone.

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

Related Images:

MLoops 23

01/11/2015 by Сплошнов Кирилл

Условие

Найдите закономерность и напишите программу, которая выводит аналогичную таблицу для любых чисел [latex]n > 0[/latex] (количество столбцов) и [latex]m > 0[/latex] (количество строк):

0, 1, 8, 27, 64, 125, 216
, 343, 512, 729, 1000, 13
31, 1728, 2197, 2744, 337
5, 4096, 4913, 5832, 6859
, 8000, 9261, 10648, 1216
7, 13824, 15625, 17576, 1
9683, 21952, 24389, 27000
, 29791, 32768, 35937, 39

0, 1, 8, 27, 64, 125, 216

, 343, 512, 729, 1000, 13

31, 1728, 2197, 2744, 337

5, 4096, 4913, 5832, 6859

, 8000, 9261, 10648, 1216

7, 13824, 15625, 17576, 1

9683, 21952, 24389, 27000

, 29791, 32768, 35937, 39

Тесты

[latex]n \times {m}[/latex]	Выходные данные
[latex]2 \times {2}[/latex]	0, _1
[latex]2 \times {10}[/latex]	0, _1 , 8, _2 7, _6 4, _1 25
[latex]5 \times {5}[/latex]	0, 1, _8, 2 7, 64 , 125 , 216
[latex]20 \times {1}[/latex]	0, 1, 8, 27, 64, 125
[latex]22 \times {10}[/latex]	0, 1, 8, 27, 64, 125, 216, 343, 512, 729, 10 00, 1331, 1728, 2197, 2744, 3375, 4096, 4913 , 5832, 6859, 8000, 92 61, 10648, 12167, 1382 4, 15625, 17576, 19683 , 21952, 24389, 27000, _29791, 32768, 35937, 39304, 42875, 46656, 5

(Нижние подчеркивания в таблице добавил намеренно, там, где строка начинается с пробела, так как они автоматически убирались.)

Решение

Нетрудно заметить, что данная последовательность содержит кубы натуральных чисел, разделенные запятой с пробелом (единственное отличие, первое число — ноль). Очевидно, понадобится использовать 2 цикла, внешний (для строк) и внутренний (для столбцов). Для простоты я попробовал составить алгоритм так, чтобы:

а) во внешнем цикле не было ничего, кроме перехода на новую строку;

б) за один шаг внутреннего цикла печатался ровно 1 символ.

Проанализируем ключевые моменты. Во первых, числа надо будет выводить по одной цифре за раз. Так как мы не знаем длину числа, можно воспользоваться функцией [latex]log10[/latex], но намного проще выводить число в обратном порядке (используя деление по модулю 10), поэтому при вычислении очередного куба будем сохранять его во временную переменную, а в печатаемую переменную [latex]cube[/latex] будем сохранять это число, записанное в обратном порядке, и выводить его на экран также в обратном порядке (таким образом, получая исходный порядок).

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

Единственный недочет — числа вроде 1000, так как при инверсии получим 0001, то есть число 1. Я решил эту проблему, заведя переменную [latex]zeros[/latex], хранящую кол-во таких нулей. Начальное число ноль тоже учтено в коде (см. комментарии).

Код

#include <iostream>
using namespace std;

int main() 
{
	int n, m;
	cin >> n >> m;
	long num = 0, cube = 0;
	bool addSpacebar = false;
	int zeros = 0;
	for (int i = 0; i < m; i ++)
	{
		for (int j = 0; j < n; j ++)
		{
			if (addSpacebar) //если необходим пробел
			{
				cout << " ";
				addSpacebar = false;
			}
			else if (cube > 0 || num + j == 0) //печатаем текущую цифру пока число больше нуля, num + j == 0 позволяют напечатать число 0
			{
				cout << cube % 10;
				cube /= 10;
			}
			else if (zeros > 0) //если закончили печатать число, но у него остались "потерянные" нули, выводим их пока не закончатся
			{
				cout << 0;
				zeros --;
			}
			else //иначе
			{
				cout << ","; //печатаем запятую
				addSpacebar = true; //запоминаем, что нужен пробел
				num ++;
				long L = num * num * num; //получаем куб следующего числа
				while (L > 0) //записываем его в обратного порядке
				{
					cube *= 10;
					cube += L % 10;
					if (cube == 0) 
						zeros ++; //если число L заканчивалось на ноль, запоминаем его (ноль)
					L /= 10;
				}
			}
		}
		cout << endl;
	}
	return 0;
}

#include <iostream>

using namespace std;

int main()

{

int n, m;

cin >> n >> m;

long num = 0, cube = 0;

bool addSpacebar = false;

int zeros = 0;

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

{

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

{

if (addSpacebar) //если необходим пробел

{

cout << " ";

addSpacebar = false;

}

else if (cube > 0 || num + j == 0) //печатаем текущую цифру пока число больше нуля, num + j == 0 позволяют напечатать число 0

{

cout << cube % 10;

cube /= 10;

}

else if (zeros > 0) //если закончили печатать число, но у него остались "потерянные" нули, выводим их пока не закончатся

{

cout << 0;

zeros --;

}

else //иначе

{

cout << ","; //печатаем запятую

addSpacebar = true; //запоминаем, что нужен пробел

num ++;

long L = num * num * num; //получаем куб следующего числа

while (L > 0) //записываем его в обратного порядке

{

cube *= 10;

cube += L % 10;

if (cube == 0)

zeros ++; //если число L заканчивалось на ноль, запоминаем его (ноль)

L /= 10;

}

cout << endl;

}

return 0;

}

Ссылки

Рабочий код на Ideaone.

Тут можно посмотреть саму последовательность.

Related Images:

MLoop 1

31/10/2015 by Сплошнов Кирилл

Условие

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

График

Тесты

Точность [latex]\epsilon[/latex]	Корень на [latex](-4; -3)[/latex]	Корень на [latex](-3; -2)[/latex]	Корень на [latex](-1; 0)[/latex]	Корень на [latex](1; 2)[/latex]	Корень на [latex](2; 3)[/latex]	Корень на [latex](3; 4)[/latex]
0.1	-3.40625	-2.78125	-0.84375	1.21875	2.71875	3.40625
0.01	-3.42578	-2.75391	-0.839844	1.21484	2.72266	3.41016
0.001	-3.42627	-2.75439	-0.836426	1.21729	2.72021	3.41357
0.0001	-3.42636	-2.75443	-0.836884	1.21707	2.72061	3.41391

Код

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

double f(double x)
{
	return log(1 + x*x - sin(x)) - pow(3, cos(2*x));
}

double findRoot(double a, double b, double e) // функция, которая ищет ноль на промежутке от a до b
{
	while (b - a > e) // пока не будет достигнута необходимая точность
	{
		if (f(a) * f((b + a) / 2) == 0)
			break;
		else if (f(a) * f((b + a) / 2) > 0)
			a = (b + a) / 2;
		else
			b = (b + a) / 2;
	}
	return (b + a) / 2;
}

int main() 
{
	double e;
	cin >> e;
	cout << findRoot(-4, -3, e) << endl;
	cout << findRoot(-3, -2, e) << endl;
	cout << findRoot(-1, 0, e) << endl;
	cout << findRoot(1, 2, e) << endl;
	cout << findRoot(2, 3, e) << endl;
	cout << findRoot(3, 4, e) << endl;
	return 0;
}

#include <iostream>

#include<cmath>

using namespace std;

double f(double x)

{

return log(1 + x*x - sin(x)) - pow(3, cos(2*x));

}

double findRoot(double a, double b, double e) // функция, которая ищет ноль на промежутке от a до b

{

while (b - a > e) // пока не будет достигнута необходимая точность

{

if (f(a) * f((b + a) / 2) == 0)

break;

else if (f(a) * f((b + a) / 2) > 0)

a = (b + a) / 2;

else

b = (b + a) / 2;

}

return (b + a) / 2;

}

int main()

{

double e;

cin >> e;

cout << findRoot(-4, -3, e) << endl;

cout << findRoot(-3, -2, e) << endl;

cout << findRoot(-1, 0, e) << endl;

cout << findRoot(1, 2, e) << endl;

cout << findRoot(2, 3, e) << endl;

cout << findRoot(3, 4, e) << endl;

return 0;

}

Решение

Рассмотрим функцию [latex]f(x) = \ln{(1 + x^2 -\sin{x})} — 3^{\cos{2x}}[/latex]. По графику видно, что функция имеет 6 нулей. Таким образом, уравнение имеет 6 корней, которые находятся на интервалах [latex](-4; -3)[/latex], [latex](-3; -2)[/latex], [latex](-1; 0)[/latex], [latex](1; 2)[/latex], [latex](2; 3)[/latex], [latex](3; 4)[/latex] соответственно. Так как корней довольно много, чтобы не копировать 6 раз алгоритм поиска корня, вынесем его в отдельную функцию [latex]findRoot[/latex], у которой будет 3 параметра: начало отрезка [latex]a[/latex], его конец [latex]b[/latex] и заданная точность [latex]\epsilon[/latex].

Далее воспользуемся методом бисекции : рассмотрим значение функции на середине отрезка (в точке [latex]\frac{a + b}{2}[/latex]) и в точке [latex]a[/latex]. Если их произведение равно нулю, то [latex]\frac{a + b}{2}[/latex] — корень уравнения, если меньше, корень — на промежутке [latex](a; \frac{a + b}{2})[/latex], больше — на промежутке [latex](\frac{a + b}{2}; b)[/latex]. Меняем координаты начала и конца отрезка на соответствующие, продолжаем, пока не будет найден корень или достигнута необходимая точность.

Ссылки

Рабочая версия кода на Ideaone.com.

Related Images:

Mif 17.17

04/10/2015 by Сплошнов Кирилл

Условие :

Принадлежит ли точка [latex](x[/latex];[latex]y)[/latex] фигуре на рисунке? Варианты 1-20. Пожалуйста повторите в своём отчёте рисунок, выполнив его в формате SVG.

Рисунок :

Тесты :

[latex]x[/latex]	4	-5	0	3	-2.5	1	-3	2	-1.3
[latex]y[/latex]	3	0	-5	-2	-2.5	5	3	-4	2.7
Вывод :	Yes	Yes	Yes	Yes	Yes	No	No	No	Yes

Решение :

Во [latex]II[/latex], [latex]III[/latex] и [latex]IV[/latex] координатных четвертях данная фигура удовлетворяет неравенству [latex]|x| + |y| \leq 5[/latex], а в [latex]IV[/latex] — неравенству [latex]x^2 + y^2 \leq 25[/latex]. Программа должна проверять, подходят ли числа [latex]x[/latex] и [latex]y[/latex] соответствующему неравенству (в зависимости от координатной четверти, в которой они находятся).

Код :

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

int main() 
{
	double x, y;
	cin >> x >> y;
	cout << (abs(x) + abs(y) <= 5 || x > 0 && y > 0 && x*x + y*y <= 25 ? "Yes" : "No");
	return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main()

{

double x, y;

cin >> x >> y;

cout << (abs(x) + abs(y) <= 5 || x > 0 && y > 0 && x*x + y*y <= 25 ? "Yes" : "No");

return 0;

}

Рабочая версия кода на Ideone.

Related Images:

Mif 16

29/09/2015 by Сплошнов Кирилл

Условие :

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

Решение :

Команда ветвления (конструкция «if {} else {}» или тернарный оператор «?» ) разделяет код программы с какого-то момента ровно на 2 независимых алгоритма (даже при отсутствии блока «else {}», так как программа продолжает выполняться в зависимости от того, сработал блок «if {}», или нет). Таким образом, если понимать под «вариантов поведения» изолированный блок кода, выполняемый при совпадении набора условий, чтобы разбить программу на [latex]n[/latex] таких независимых вариантов, нужно использовать ровно [latex]n — 1[/latex] условную операцию.

Тесты :

Входные данные	12	7	1	0
Выходные данные	11	6	0	Ошибка ввода

Код :

#include <iostream>
using namespace std;

int main() 
{
	int n;
	cin >> n;
	if (n > 0)
		cout << n - 1 << endl;
	else
		cout << "Ошибка ввода" << endl;
	return 0;
}

#include <iostream>

using namespace std;

int main()

{

int n;

cin >> n;

if (n > 0)

cout << n - 1 << endl;

else

cout << "Ошибка ввода" << endl;

return 0;

}

Ссылка на рабочий код:

Ideone.com

Related Images:

e-olymp 109. Нумерация

22/09/2015 by Сплошнов Кирилл

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

Условие

Для нумерации [latex]M[/latex] страниц книги использовали [latex]N[/latex] цифр. По заданному [latex]N[/latex] вывести [latex]M[/latex] или [latex]0[/latex], если решения не существует. Нумерация начинается с первой страницы.

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

Единственное число [latex]N[/latex]. В книге не более [latex]1001[/latex] страницы.

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

Искомое количество страниц.

Тесты :

N	8	21	22	113	999	1001
M	8	15	0	61	369	0

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

#include <iostream>
using namespace std;

int main()
{
	int N;
	cin >> N;
	for (int i = 1; true; i++) // i - номер страницы, будем отнимать от N количество цифр в i
    {
		if (i < 10) // в i одна цифра
			N --;
		else if (i >= 10 && i < 100) // 2 цифры
			N -= 2;
		else if (i >= 100 && i < 1000) // 3 цифры
			N -= 3;
		else  // 4 цифры
			N -= 4;
		if (N == 0) // если лишних цифр у нас не осталось
		{
			cout << i << endl;
			break;
		}
		else if (N < 0) // иначе выводим "0"
		{
			cout << 0 << endl;
			break;
		}
    }
	return 0;
}

#include <iostream>

using namespace std;

int main()

{

int N;

cin >> N;

for (int i = 1; true; i++) // i - номер страницы, будем отнимать от N количество цифр в i

{

if (i < 10) // в i одна цифра

N --;

else if (i >= 10 && i < 100) // 2 цифры

N -= 2;

else if (i >= 100 && i < 1000) // 3 цифры

N -= 3;

else // 4 цифры

N -= 4;

if (N == 0) // если лишних цифр у нас не осталось

{

cout << i << endl;

break;

}

else if (N < 0) // иначе выводим "0"

{

cout << 0 << endl;

break;

}

return 0;

}

Примечание

Общее (и более компактное) решение можно написать, подключив библиотеку <cmath> и воспользовавшись функцией логарифма с основанием 10.

Код программы (вторая версия)

#include <iostream>
#include <cmath>
using namespace std;
 
int main()
{
	int N;
	cin >> N;
	for (int i = 1; true; i++) // i - номер страницы, будем отнимать от N количество цифр в i
    {
		N -= floor(log10(i) + 1);
		if (N == 0) // если лишних цифр у нас не осталось
		{
			cout << i << endl;
			break;
		}
		else if (N < 0) // иначе выводим "0"
		{
			cout << 0 << endl;
			break;
		}
    }
	return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main()

{

int N;

cin >> N;

for (int i = 1; true; i++) // i - номер страницы, будем отнимать от N количество цифр в i

{

N -= floor(log10(i) + 1);

if (N == 0) // если лишних цифр у нас не осталось

{

cout << i << endl;

break;

}

else if (N < 0) // иначе выводим "0"

{

cout << 0 << endl;

break;

}

return 0;

}

Ссылки

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

Рабочий код на Ideone.com .

Related Images:

Интересная последовательность

22/09/2015 by Сплошнов Кирилл

Условие (OCPC-2015)

Дана последовательность из [latex]n[/latex] чисел: [latex]x_0[/latex], [latex]x_1[/latex], [latex]x_2, \ldots, x_{n-1}[/latex], где [latex]x_0[/latex] — кол-во чисел [latex]0[/latex] в данной последовательности, [latex]x_1[/latex] — кол-во чисел [latex]1[/latex], и так далее…

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

Число [latex]n[/latex] — количество членов последовательности.

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

Искомая последовательность.

Размышления над решением:

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

[latex]x_0 + x_1 + [/latex]…[latex] + x_{n-1} = n[/latex] (1)

Далее заметим, что [latex]x_0[/latex] не может равняться нулю (ведь записав туда [latex]0[/latex], мы сразу же увеличиваем кол-во нулей до одного). Тогда [latex]x_0[/latex] равняется другому числу [latex]k[/latex], положим, большему чем 2. Тогда, [latex]x_k = 1[/latex].

Далее, положив [latex]x_1 = 2[/latex] и [latex]x_2 = 1[/latex], получаем последовательность, не нуждающуюся в дальнейших преобразованиях, в чем легко убедиться. Для наглядности:

Член последовательности	[latex]x_0[/latex]	[latex]x_1[/latex]	[latex]x_2[/latex]	…	[latex]x_k[/latex]	…
Чему равен	k	2	1	0	1	0
Комментарий	[latex]k[/latex] будет найдено ниже	Количество чисел [latex]1[/latex] равно двум	Количество чисел [latex]2[/latex] равно одному	На этом промежутке только нули	[latex]k[/latex] больше двух	На этом промежутке только нули

Теперь вычислим [latex]k[/latex]. По формуле (1):

[latex]k + 2 + 1 + 1 = n[/latex]; [latex]k = n — 4[/latex]

(Примечание: При попытки подставить другие значения вместо [latex]x_1[/latex] или [latex]x_2[/latex] получится нестабильная последовательность, членам которой не получится присвоить значения согласно условию. Положив, например, [latex]x_1 = 3[/latex], нам придется увеличить кол-во единиц, что приведет к необходимости использовать другие числа последовательности, что в итоге обязательно приведет к нарушению необходимого условия (1) — сумма уже присвоенных ненулевых чисел попросту превысит количество ее оставшихся членов. Аналогично, если присвоить [latex]x_2 = 2[/latex], и уж тем более, при внесении более «крупных» изменений в последовательность. Таким образом, найденное решение является единственным.)

Очевидно, минимальное «рабочее» значение [latex]n[/latex] равно семи (при [latex]k = 2 + 1 = 3[/latex]).

Тесты (1) :

[latex]n[/latex]	[latex]x_0[/latex]	[latex]x_1[/latex]	[latex]x_2[/latex]	[latex]x_3[/latex]	[latex]x_4[/latex]	[latex]x_5[/latex]	[latex]x_6[/latex]	[latex]x_7[/latex]	[latex]x_8[/latex]	…
7	3	2	1	1	0	0	0
8	4	2	1	0	1	0	0	0
9	5	2	1	0	0	1	0	0	0
…	[latex]n — 4[/latex]	2	1	0	…	…	…	…	…	…

Для [latex]n[/latex] меньше семи, решение (или их отсутствие) было найдено подбором.

Тесты (2) :

[latex]n[/latex]	[latex]x_0[/latex]	[latex]x_1[/latex]	[latex]x_2[/latex]	[latex]x_3[/latex]	[latex]x_4[/latex]	[latex]x_5[/latex]
1	Решений нет
2	Решений нет
3	Решений нет
4	1 2	2 0	1 2	0 0
5	2	1	2	0	0
6	Решений нет

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

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

#include <iostream>
using namespace std;

int main() 
{
	int n;
	cin >> n;
	if (n < 4 || n == 6) // особые случаи (1)
		cout << "Решений нет" << endl;
	else if (n == 4) // особые случаи (2)
    {
        cout << "1 2 1 0" << endl;
        cout << "2 0 2 0" << endl;
    }
	else if (n == 5) // особый случай (3)
		cout << "2 1 2 0 0" << endl;
	else // алгоритм для общего случая
	{
		int number[n]; // создаем массив членов последовательности
		for (int i = 0; i < n; i++) // приравниваем все числа к нулю
			number[i] = 0;
		number[0] = n - 4; // выставляем значения для ненулевых членов
		number[1] = 2;
		number[2] = 1;
		number[n - 4] = 1;
		for (int i = 0; i < n; i++) // выводим по очереди элементы последовательности на экран
			cout << number[i] << " ";
		cout << endl; 
	}
	return 0;
}

#include <iostream>

using namespace std;

int main()

{

int n;

cin >> n;

if (n < 4 || n == 6) // особые случаи (1)

cout << "Решений нет" << endl;

else if (n == 4) // особые случаи (2)

{

cout << "1 2 1 0" << endl;

cout << "2 0 2 0" << endl;

}

else if (n == 5) // особый случай (3)

cout << "2 1 2 0 0" << endl;

else // алгоритм для общего случая

{

int number[n]; // создаем массив членов последовательности

for (int i = 0; i < n; i++) // приравниваем все числа к нулю

number[i] = 0;

number[0] = n - 4; // выставляем значения для ненулевых членов

number[1] = 2;

number[2] = 1;

number[n - 4] = 1;

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

cout << number[i] << " ";

cout << endl;

}

return 0;

}

Также есть ссылка на рабочий код на Ideaone для желающих провести дополнительные тесты:

Ideaone.com

Related Images:

ML 24

18/09/2015 by Сплошнов Кирилл

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

Треугольник задан длинами сторон. Найти радиус вписанной [latex]r[/latex] и описанной [latex]R[/latex] окружностей.

Тесты :

[latex]a[/latex]	[latex]b[/latex]	[latex]c[/latex]	[latex]r[/latex]	[latex]R[/latex]
3	4	5	1	2.5
7.5	10	13	2.45012	6.52361
1	3	4	0	inf
1	1	3	Не существует!	Не существует!

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

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

int main() 
{
	double a, b, c;
	cin >> a >> b >> c;
	if (a + b >= c && b + c >= a && a + c >= b) //проверяем, существует ли треугольник 
	{
		double p = (a + b + c) / 2;
		double S = sqrt(p * (p - a) * (p - b) * (p - c)); //формула Герона 
		double r = S / p;
		double R = a* b * c / (4 * S);
		cout<<"Радиус вписанной окружности равен "<<r<<endl;
		cout<<"Радиус описанной окружности равен "<<R<<endl;
	}
	else //если не существует:
		cout<<"Треугольник с заданными сторонами не существует!"<<endl;
	return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main()

{

double a, b, c;

cin >> a >> b >> c;

if (a + b >= c && b + c >= a && a + c >= b) //проверяем, существует ли треугольник

{

double p = (a + b + c) / 2;

double S = sqrt(p * (p - a) * (p - b) * (p - c)); //формула Герона

double r = S / p;

double R = a* b * c / (4 * S);

cout<<"Радиус вписанной окружности равен "<<r<<endl;

cout<<"Радиус описанной окружности равен "<<R<<endl;

}

else //если не существует:

cout<<"Треугольник с заданными сторонами не существует!"<<endl;

return 0;

}

Алгоритм :

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

	if (a + b >= c && b + c >= a && a + c >= b)//проверяем, существует ли треугольник

9	if (a + b >= c && b + c >= a && a + c >= b)//проверяем, существует ли треугольник

…

	else //если не существует:
		cout<<"Треугольник с заданными сторонами не существует!"<<endl;

else //если не существует:

cout<<"Треугольник с заданными сторонами не существует!"<<endl;

Если треугольник существует, проводим следующие вычисления (порядок сохранен) :

Вычисляем полупериметр [latex]p[/latex] треугольника: [latex]p[/latex] = [latex]\frac{a + b + c}{2}[/latex]
Находим площадь [latex]S[/latex] по формуле Герона: [latex]S[/latex] = [latex]\sqrt{p(p-a)(p-b)(p-c)}[/latex]
Вычисляем радиус [latex]r[/latex] вписанной окружности по формуле: [latex]r[/latex] = [latex]\frac{S}{p}[/latex]
Вычисляем радиус [latex]R[/latex] описанной окружности по формуле: [latex]R[/latex] = [latex]\frac{abc}{4S}[/latex]

Работающая версия программы на Ideaone.com :

Ideone.com

Почитать про треугольник можно здесь :

Треугольник — Википедия

Related Images:

e-olymp 57. Бабочка-санитар

14/09/2015 by Сплошнов Кирилл

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

Условие

Школьники, идя из дому в школу или наоборот — со школы домой, любят кушать конфеты. Но, как всегда, это приятное дело иногда имеет неприятные последствия – детки часто выбрасывают обертки на школьном дворе.

Мурзик всегда следил за чистотой школьного двора и ему в этом с радостью помогали бабочки, благодарные за прекрасные фотографии, сделанные им. Бабочки могли использовать собственные крылышки как линзы, причем они могли изменять их фокусное расстояние. Заметив обертку от конфетки, лежавшую на школьном дворе в точке с координатами [latex]X_1[/latex], [latex]Y_1[/latex], бабочка перелетала в точку с координатами [latex]X_2[/latex], [latex]Y_2[/latex], [latex]Z_2[/latex], расположенную на пути солнечных лучей к обертке и, изменяя фокусное расстояние своих крылышек-линз, сжигали обертку от конфеты.

Какую оптическую силу [latex]D[/latex] имели крылышки-линзы бабочки в этот момент?

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

В первой строке 2 числа: координаты [latex]X_1[/latex], [latex]Y_1[/latex], обертки от конфетки. Во второй – 3 числа: координаты [latex]X_2[/latex], [latex]Y_2[/latex], [latex]Z_2[/latex] бабочки в момент сжигания обертки.

Все входные данные целые числа, не превышающие по модулю 1000.

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

Единственное число – оптическая сила крылышек-линз [latex]D[/latex], вычисленная с точностью до 3-х знаков после запятой за правилами математических округлений.

Тесты:

[latex]X_1[/latex]	[latex]Y_1[/latex]	[latex]X_2[/latex]	[latex]Y_2[/latex]	[latex]Z_2[/latex]	[latex]D[/latex]
10	20	10	20	100	0.010
10	30	10	30	50	0.020
10	30	20	40	110	0.009

Код:

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

int main() 
{
	int x1, y1;
	int x2, y2, z2;
	cin >> x1 >> y1;
	cin >> x2 >> y2 >> z2;
	double D = 1/sqrt((x2 - x1)*(x2 - x1) + (y2 - y1)*(y2 - y1) + z2*z2);
	cout << fixed << setprecision(3) << D << endl;
	return 0;
}

#include <iostream>

#include <iomanip>

#include <cmath>

using namespace std;

int main()

{

int x1, y1;

int x2, y2, z2;

cin >> x1 >> y1;

cin >> x2 >> y2 >> z2;

double D = 1/sqrt((x2 - x1)*(x2 - x1) + (y2 - y1)*(y2 - y1) + z2*z2);

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

return 0;

}

Ход решения:

Вычисляем оптическую силу линзы D по формуле [latex]D = \frac{1}{f}[/latex], где f — расстояние между бабочкой и обёрткой. вычисляем его по формуле: [latex]f[/latex] = [latex]\sqrt{(X_2-X_1)^2+(Y_2-Y_1)^2+Z_2^2}[/latex]. Вычисление в одну строку:

double D = 1/sqrt((x2 - x1)*(x2 - x1) + (y2 - y1)*(y2 - y1) + z2*z2);

13	double D = 1/sqrt((x2 - x1)(x2 - x1) + (y2 - y1)(y2 - y1) + z2*z2);

Далее округляем результат до требуемой точности и выводим на экран:

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

14	cout << fixed << setprecision(3) << D << endl;

Ссылки:

Зачитанный вариант на e-olimp.com: olymp.com

Рабочий код для тестирования на Ideaone.com: Ideaone.com