e-olymp 4082. Произведение на отрезке

27/06/2016 by Настя Филипчук

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

Это нормально чувствовать себя взволнованным и напряженным за день до олимпиады по программированию. Чтобы расслабиться, вы пошли выпить со своими друзьями в соседний паб. Для сохранения остроты ума до следующего дня, Вы решили сыграть в следующую игру. Для начала Ваши друзья написали последовательность [latex] n [/latex] целых чисел [latex] x_{1}, x_{2},\cdots , x_{n} [/latex]. Потом следует [latex] k [/latex] раундов, на каждом из которых выполняется одна из следующих команд:

команда изменения, когда необходимо изменить одно значение в последовательности;
команда умножения, когда по заданным значениям [latex] i [/latex] и [latex] j [/latex] необходимо определить, является ли произведение [latex] x_{i}\cdot x_{i+1} \cdot \; \; \cdots \; \; \cdot x_{j-1} \cdot x_{j} [/latex] положительным, отрицательным или равным нулю.

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

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

Каждый тест состоит из нескольких строк. Первая строка каждого теста содержит два числа [latex] n [/latex] и [latex] k [/latex] ([latex] 1\leq n,k\leq 10^{5}[/latex]) — количество элементов в последовательности и число раундов в игре. Вторая строка содержит [latex] n [/latex] целых чисел [latex] x_{i} [/latex] — начальные значения последовательности ([latex] -100\leq x_{i}\leq 100[/latex] для [latex]i=1,2, \cdots ,n[/latex]). Каждая из следующих [latex] k [/latex] строк описывает команду, начинающуюся заглавной буквой [latex] C [/latex] или [latex] C [/latex]. Если это буква [latex] C [/latex], то строка содержит команду замены, за буквой следуют два числа [latex] i [/latex] и [latex] v [/latex], указывающих на то что [latex] x_{i} [/latex] необходимо заменить на [latex] v [/latex] ([latex] 1\leq i\leq n[/latex] и [latex]-100\leq v\leq 100[/latex]). Если это буква [latex] P [/latex], то строка задает команду умножения, за буквой следуют два числа [latex] i [/latex] и [latex] j [/latex] — необходимо вычислить произведение от [latex] x_{i} [/latex] до [latex] x_{i} [/latex] включительно ([latex] 1\leq i\leq j\leq n [/latex]) . Каждый тест содержит как минимум одну команду умножения.

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

Для каждого теста вывести одну строку, содержащую ответы на все команды умножения. [latex] i [/latex]-ый символ строки является результатом [latex] i [/latex]-ой команды умножения. Если произведение положительно, то вывести символ [latex] + [/latex] (плюс); если произведение отрицательно, то вывести [latex] — [/latex] (минус); если произведение равно нулю, то вывести [latex] 0 [/latex] (ноль).

Тесты

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

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

4 6

-2 6 0 -1

C 1 10

P 1 4

C 3 7

P 2 2

C 4 -5

P 1 4

5 9

1 5 -2 4 3

P 1 2

P 1 5

C 4 -5

P 1 5

P 4 5

C 3 0

P 1 5

C 4 -5

0+-

+-+-0

5 5

10 -2 0 5 1

C 1 0

P 1 4

C 2 7

P 1 1

C 2 0

6 4

0 20 0 30 0 -10

P 2 2

P 2 3

P 3 6

P 2 6

4 3

0 -1 -2 0

P 2 3

C 1 9

P 1 2

3 3

5 2 0

C 1 7

C 3 0

C 1 0

6 5

100 10 55 11 0 -33

P 1 4

C 5 6

C 3 72

C 5 -20

P 5 6

+000

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

#include <iostream>
using namespace std;
 
void sequence(int* tree, int* given, int position, int i, int j) // посторение дерева
{
    if (i == j)
        tree[position] = given[i] > 0 ? 1 : (given[i] < 0 ? -1 : 0); // заменяем элементы последовательности на "1","-1","0" в соответсвии с условием для команды "P" 
    else if (i!=j)  // для остальных элементов воспользуемся следующим алгоритмом
    {
        int m = (i + j) / 2;
        sequence(tree, given, position * 2, i, m);
        sequence(tree, given, position * 2 + 1, m + 1, j);
        tree[position] = tree[position * 2] * tree[position * 2 + 1]; // элемент с номером (pos * 2) – левый потомок, а с (pos * 2 + 1) - правый потомок
    }
}

void For_C_command(int* tree, int position, int i, int j, int nposition, int v) // функция изменения элемента (для выполнения команлы "С")
{
    if (i == j)
        tree[position] = v > 0 ? 1 : (v < 0 ? -1 : 0);
    else if (i!=j)
    {
        int m = (i + j) / 2;
        if (nposition <= m)
            For_C_command(tree, position * 2, i, m, nposition, v);
        else
            For_C_command(tree, position * 2 + 1, m + 1, j, nposition, v);
        tree[position] = tree[position * 2] * tree[position * 2 + 1];
    }
}
 
int For_P_command(int* tree, int position, int i, int j, int qi, int qj) // функция для выполнения команды "Р"
{
    if (i == qi && j == qj)
        return tree[position];
    else
    {
        int m = (i + j) / 2;
        if (qj <= m)
            return For_P_command(tree, position * 2, i, m, qi, qj);
        else if (qi >= m + 1)
            return For_P_command(tree, position * 2 + 1, m + 1, j, qi, qj);
        else
            return For_P_command(tree, position * 2, i, m, qi, m) * For_P_command(tree, position * 2 + 1, m + 1, j, m + 1, qj);
    }
}
 
int main() 
{
    ios::sync_with_stdio(false); // ускоряем чтение
    int n, k;
    while (cin >> n >> k)
    {
        int given[n];
        for (int i = 0; i < n; i++)
            cin >> given[i];
        int tree[n * 4];
        sequence(tree, given, 1, 0, n - 1);
        for (int i = 0; i < k; i++)
        {
            char command;
            int xi, xj;
            cin >> command >> xi >> xj;
            if (command == 'P')
            {   
                int x = For_P_command(tree, 1, 0, n - 1, xi - 1, xj - 1); // применяем функцию для команды "Р" и выполняем сравнения, соответствующие условию задачи
                if (x < 0)
                    printf("-");
                else if (x > 0)
                    printf("+");
                else 
                    printf("0");
            }
            else
                For_C_command(tree, 1, 0, n - 1, xi - 1, xj);
        }
        printf("\n");
    }
}

#include <iostream>

using namespace std;

void sequence(int* tree, int* given, int position, int i, int j) // посторение дерева

{

if (i == j)

tree[position] = given[i] > 0 ? 1 : (given[i] < 0 ? -1 : 0); // заменяем элементы последовательности на "1","-1","0" в соответсвии с условием для команды "P"

else if (i!=j) // для остальных элементов воспользуемся следующим алгоритмом

{

int m = (i + j) / 2;

sequence(tree, given, position * 2, i, m);

sequence(tree, given, position * 2 + 1, m + 1, j);

tree[position] = tree[position * 2] * tree[position * 2 + 1]; // элемент с номером (pos * 2) – левый потомок, а с (pos * 2 + 1) - правый потомок

}

void For_C_command(int* tree, int position, int i, int j, int nposition, int v) // функция изменения элемента (для выполнения команлы "С")

{

if (i == j)

tree[position] = v > 0 ? 1 : (v < 0 ? -1 : 0);

else if (i!=j)

{

int m = (i + j) / 2;

if (nposition <= m)

For_C_command(tree, position * 2, i, m, nposition, v);

else

For_C_command(tree, position * 2 + 1, m + 1, j, nposition, v);

tree[position] = tree[position * 2] * tree[position * 2 + 1];

}

int For_P_command(int* tree, int position, int i, int j, int qi, int qj) // функция для выполнения команды "Р"

{

if (i == qi && j == qj)

return tree[position];

else

{

int m = (i + j) / 2;

if (qj <= m)

return For_P_command(tree, position * 2, i, m, qi, qj);

else if (qi >= m + 1)

return For_P_command(tree, position * 2 + 1, m + 1, j, qi, qj);

else

return For_P_command(tree, position * 2, i, m, qi, m) * For_P_command(tree, position * 2 + 1, m + 1, j, m + 1, qj);

}

int main()

{

ios::sync_with_stdio(false); // ускоряем чтение

int n, k;

while (cin >> n >> k)

{

int given[n];

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

cin >> given[i];

int tree[n * 4];

sequence(tree, given, 1, 0, n - 1);

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

{

char command;

int xi, xj;

cin >> command >> xi >> xj;

if (command == 'P')

{

int x = For_P_command(tree, 1, 0, n - 1, xi - 1, xj - 1); // применяем функцию для команды "Р" и выполняем сравнения, соответствующие условию задачи

if (x < 0)

printf("-");

else if (x > 0)

printf("+");

else

printf("0");

}

else

For_C_command(tree, 1, 0, n - 1, xi - 1, xj);

}

printf("\n");

}

Решение

Данная задача решается при помощи стандартного алгоритма по теме «Дерево отрезков» (данный алгоритм можно посмотреть на сайте e-maxx). Следовательно, при построении дерева сначала считывается массив, а после выполняется построение дерева (от корня). В том случае, если функция, строящая дерево, вызывалась от листа, все значения элементов массива записываются в дерево как [latex]1[/latex], если элемент больше нуля, если меньше нуля, то записывается как [latex]-1[/latex], а в случае равенства элемента нулю, он записывается [latex]0[/latex] (нулём). В ином случае (если функция вызывалась не от листа), она начинает вызываться рекурсивно от каждого из двух сыновей и перемножает вычесленные значения.

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

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

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

Ссылки

Рабочий код на Ideone.com
Засчитанное решение на e-olymp.com
При ришении данной задачи был использован материал по структурам данных «дерево отрезков» с сайта e-maxx.ru
Задача взята с сайта e-olymp.com

Related Images:

e-olymp 2941. Дима и массив

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

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

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

Мама подарила мальчику Диме массив длины [latex]n[/latex]. Массив этот не простой, а особенный. Дима может выбрать два числа [latex]i[/latex] и [latex]d[/latex] ([latex]1\leq i\leq n[/latex], [latex]-1000\leq d\leq 1000[/latex]), и элемент с индексом [latex]i[/latex] магически становится равным [latex]d[/latex]. Дима играет со своим массивом, а мама время от времени задает ему вопросы — какова сумма всех чисел в массиве с индексами от [latex]f[/latex] до [latex]t[/latex]? Дима легко справился с этими вопросами, сможете ли Вы?

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

В первой строке находятся два целых числа [latex]n[/latex] и [latex]q[/latex] [latex]1\leq n\leq 5\cdot 10^{5},~1\leq q\leq 10^{5}[/latex] — количество элементов в массиве и суммарное количество операций и запросов соответственно. В следующей строке дано [latex]n[/latex] чисел [latex]a_{1},a_{2},\ldots,a_{n}[/latex] [latex]\left ( -1000\leq a_{i}\leq 1000 \right )[/latex] — начальное состояние массива. В следующих [latex]q[/latex] строках заданы операции и запросы. Первый символ в строке может быть [latex]=[/latex] или [latex]?[/latex]. Если строка начинается с [latex]=[/latex], то это операция присваивания. Далее следуют [latex]i[/latex] и [latex]d[/latex], ограничения на которые описаны в условии. Если строка начинается с [latex]?[/latex], то это запрос. Далее следуют числа [latex]f[/latex] и [latex]t[/latex] [latex]\left (1\leq f,~t\leq n \right )[/latex].

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

Для каждого запроса выведите сумму чисел в массиве с индексами от [latex]f[/latex] до [latex]t[/latex], по одному результату в строке.

Тесты

Входные данные	Выходные данные
3 3 1 2 3 ? 1 3 = 3 2 ? 1 3	6 5
5 3 1 2 3 4 5 ? 1 5 = 1 7 ? 1 3	15 12
5 6 1 2 3 4 5 ? 1 5 = 1 0 ? 1 5 = 2 7 ? 1 5 ? 1 3	15 14 19 10

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

#include <iostream>
using namespace std;
 
// построение дерева 
void build (int tree[], int arr[], int v, int left, int right) {   
    if (left != right) {
        int middle = (left + right) / 2;
        build (tree, arr, v*2, left, middle);
        build (tree, arr, v*2+1, middle+1, right);
        tree[v] = tree[v*2] + tree[v*2+1];
    } else tree[v] = arr[left];}
 
// запрос суммы
int sum (int tree[], int v, int left, int right, int from, int to) { 
    if (from > to) return 0;
    if (from == left && to == right) return tree[v];
    int middle = (left + right) / 2;
    return sum(tree,v*2,left,middle,from,min(to,middle))+sum(tree,v*2+1,middle+1,right,max(from,middle+1),to);
}
 
// операция присваивания
void update (int tree[], int v, int left, int right, int index, int new_val) { 
    if (left != right) {
        int middle = (left + right) / 2;
        if (index <= middle) update (tree, v*2, left, middle, index, new_val);
        else update (tree, v*2+1, middle+1, right, index, new_val);
        tree[v] = tree[v*2] + tree[v*2+1];
    } else tree[v] = new_val;
}

int main() {
    int n, q, i, d, from, to;
    char query;
    cin >> n >> q;
    int size = 2*n; /* максимальный размер дерева*/
    int arr[n], tree[size];
    for(int i = 0; i < n; i++) cin >> arr[i];
    /* передаем функции построения массив для записи дерева, исходный массив, 
       корень и границы отрезка, принадлежащего корню */
    build(tree, arr, 1, 0, n-1); 
    for (q; q>0; q--) {
        cin >> query;
        if (query == '=') {
            cin >> i >> d;
            update(tree, 1, 0, n-1, i-1, d); 
        } else if (query == '?') {
            cin >> from >> to;
            cout << sum(tree, 1, 0, n-1, from-1, to-1) << endl;
        }
    }
}

#include <iostream>

using namespace std;

// построение дерева

void build (int tree[], int arr[], int v, int left, int right) {

if (left != right) {

int middle = (left + right) / 2;

build (tree, arr, v*2, left, middle);

build (tree, arr, v*2+1, middle+1, right);

tree[v] = tree[v*2] + tree[v*2+1];

} else tree[v] = arr[left];}

// запрос суммы

int sum (int tree[], int v, int left, int right, int from, int to) {

if (from > to) return 0;

if (from == left && to == right) return tree[v];

int middle = (left + right) / 2;

return sum(tree,v*2,left,middle,from,min(to,middle))+sum(tree,v*2+1,middle+1,right,max(from,middle+1),to);

}

// операция присваивания

void update (int tree[], int v, int left, int right, int index, int new_val) {

if (left != right) {

int middle = (left + right) / 2;

if (index <= middle) update (tree, v*2, left, middle, index, new_val);

else update (tree, v*2+1, middle+1, right, index, new_val);

tree[v] = tree[v*2] + tree[v*2+1];

} else tree[v] = new_val;

}

int main() {

int n, q, i, d, from, to;

char query;

cin >> n >> q;

int size = 2*n; /* максимальный размер дерева*/

int arr[n], tree[size];

for(int i = 0; i < n; i++) cin >> arr[i];

/* передаем функции построения массив для записи дерева, исходный массив,

корень и границы отрезка, принадлежащего корню */

build(tree, arr, 1, 0, n-1);

for (q; q>0; q--) {

cin >> query;

if (query == '=') {

cin >> i >> d;

update(tree, 1, 0, n-1, i-1, d);

} else if (query == '?') {

cin >> from >> to;

cout << sum(tree, 1, 0, n-1, from-1, to-1) << endl;

}

ideone.com

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

Решение

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

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

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

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

Для решения данной задачи были использованы материалы сайта e-maxx.ru.

Related Images:

e-olymp 2307. The sum

24/05/2016 by Таран Таня

The array of [latex]n[/latex] elements is given. Find the sum of numbers on a segment.

Input

The first line contains two integers [latex]n[/latex] and [latex]k[/latex] [latex](1 \le n \le 10^5, 0 \le k \le 10^5)[/latex] — the number of elements in array and the number of queries. The next [latex]k[/latex] lines contain the queries of two forms:

[latex]A[/latex] [latex]l[/latex] [latex]r[/latex] [latex]x[/latex] — assign the value of [latex]x[/latex] to each element form position [latex]l[/latex] to [latex]r[/latex] [latex](1 \le l \le r \le n, 0 \le x \le 10^9)[/latex]
[latex]Q[/latex] [latex]l[/latex] [latex]r[/latex] — find the sum of array elements on positions from [latex]l[/latex] to [latex]r[/latex] [latex](1 \le l \le r \le n)[/latex]

Initially the array is filled with zeroes.

Output

For each query of the form «[latex]Q[/latex] [latex]l[/latex] [latex]r[/latex]» print the sum of numbers on a segment.

Tests

№	Input	Output
1	5 9 A 2 3 2 A 3 5 1 A 4 5 2 Q 1 3 Q 2 2 Q 3 4 Q 4 5 Q 5 5 Q 1 5	3 2 3 4 2 7
2	10 6 A 1 10 1 Q 1 10 A 1 5 2 Q 1 10 A 4 7 3 Q 1 10	10 15 21
3	100000 2 A 1 100000 1000000000 Q 1 100000	100000000000000

Algorithm

After reading the statement of the problem it is understandable that we should implement segment tree with support for multiple modification request — assignment. To make modifications to the whole segment and quickly answer for the amounts queries, we organize data structure in which each node store «colored» — if it is painted in any color or not and a sum on corresponding to this node segment.

struct Node {
    int color;
    long long sumOnSegment;
};

struct Node {

int color;

long long sumOnSegment;

};

Under the node coloring we will understand that all segment with all its subsegments should be colored in the appropriate color (assigned a specific number). Also define the mark that the node isn’t colored (in the code defined as WHITE), for example, any negative number, because queries contain only positive. This implementation allows us to do «delayed» update of the tree. Specifically, for each request of modification, instead of changing the values at all vertices where it is required, change only some of them, leaving «colored» markers for the other segments, which means that the whole segment with its subsegments should be painted in this color.
But if we do it so, after each modification request segment tree will stop being up to date. For resolving this problem, organise a function, that will «push» information from parents to children: void push(Node *tree, int currentNode, int left, int right) . This function is called during requests processing to update the appropriate values:

assign parent’s color to the children
recalculate the amount of the segment for children (as the length of the segment multiplied by the current color (number))
set parent node as uncolored

Thus, to solve this task, we need two usual for segment tree functions:

void update(Node *tree, int currentNode, int left, int right, int leftBorder, int rightBorder, int color)
long long sum(Node *tree, int currentNode, int left, int right, int leftBorder, int rightBorder)

With the difference that, when we are going down by the tree, pushes information only as far as necessary (it should be noted, that in this way the asymptotic doesn’t impair and remains standard [latex]O(\log n)[/latex]).

Rest details of the implementation can be found in the code of the program or in the sources of information listed at the end of the article.

Footnote: such realization, where the problem constraints too large queries, and in the current version when we update a range and only mark its child that it needs to be updated and update it when needed, usually calls lazy propagation. This approach allows us to solve a variety of new at first glance seemed complex tasks. More information listed at the end of the article.

Code

#include <cmath>
#include <iostream>
#define WHITE -1
using namespace std;

//  Function, that return lowest power of 2, bigger than a given number
int lowestBiggerPowOf2Than(int number) {                    
    int answer;
    answer = 1 << (int)(log2((double)number - 1) + 1);
    return answer;
}

//  The structure describing the components from which consists a tree
struct Node {
    int color;
    long long sumOnSegment;
    //  The default constructor
    Node() {
        color = WHITE;
        sumOnSegment = 0;
    }
    //  Construct the node by its color and sum on corresponding segment
    Node(int color, long long sumOnSegment) {
        this->color = color;
        this->sumOnSegment = sumOnSegment;
    }
    //  Define, if this node is painted in some color (some number is assigned)
    bool isColored() {
        return color != WHITE;
    }
};

//  Function, that pushes information from parent to the children
void push(Node *tree, int currentNode, int left, int right) {
    if (tree[currentNode].isColored()) {
        int middle = (left + right) / 2;
        int leftChild = 2 * currentNode;
        //  Pass color from parent to children
        tree[leftChild].color = tree[currentNode].color;
        tree[leftChild + 1].color = tree[currentNode].color;
        //  Execute recalculation of the amount in the corresponding segments at children
        tree[leftChild].sumOnSegment = (long long)(middle - left + 1) * tree[leftChild].color;
        tree[leftChild + 1].sumOnSegment = (long long)(right - middle) * tree[leftChild + 1].color;
        //  Note parent's node as uncolored
        tree[currentNode].color = WHITE;
    }
}

//  Function, that updates the value of all nodes on a segment for the specified 
void update(Node *tree, int currentNode, int left, int right, int leftBorder, int rightBorder, int color) {
    if (leftBorder == left && rightBorder == right) {
        tree[currentNode] = Node(color, (long long)(right - left + 1) * color);
    } else {
        //  Executes the delayed update (pushes information)
        push(tree, currentNode, left, right);
        int leftChild = 2 * currentNode;
        int middle = (left + right) / 2;
        if (rightBorder <= middle) {
            update(tree, leftChild, left, middle, leftBorder, rightBorder, color);
        } else if (leftBorder >= middle + 1) {
            update(tree, leftChild + 1, middle + 1, right, leftBorder, rightBorder, color);
        } else {
            update(tree, leftChild, left, middle, leftBorder, middle, color);
            update(tree, leftChild + 1, middle + 1, right, middle + 1, rightBorder, color);
        }
        //  Update the amount in corresponding to parent segment
        tree[currentNode].sumOnSegment = tree[leftChild].sumOnSegment + tree[leftChild + 1].sumOnSegment;
    } 
}

//  Function, that calculates the sum at a specified segment
long long sum(Node *tree, int currentNode, int left, int right, int leftBorder, int rightBorder) {
    if (left == leftBorder && right == rightBorder) {
        return tree[currentNode].sumOnSegment;
    } else {
        //  Executes the delayed update (pushes information)
        push(tree, currentNode, left, right);
        int leftChild = 2 * currentNode;
        int middle = (left + right) / 2;
        if (rightBorder <= middle) {
            return sum(tree, leftChild, left, middle, leftBorder, rightBorder);
        } else if (leftBorder >= middle + 1) {
            return sum(tree, leftChild + 1, middle + 1, right, leftBorder, rightBorder);
        } else {
            return sum(tree, leftChild, left, middle, leftBorder, middle) 
                + sum(tree, leftChild + 1, middle + 1, right, middle + 1, rightBorder);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    unsigned int quantityOfNumbers;
    cin >> quantityOfNumbers;
    unsigned int sizeOfTree = 2 * lowestBiggerPowOf2Than(quantityOfNumbers);
    Node *tree = new Node[sizeOfTree];
    unsigned int quantityOfRequests;
    cin >> quantityOfRequests;
    for (unsigned int indexOfRequest = 0; indexOfRequest < quantityOfRequests; indexOfRequest++) {
        char request;
        cin >> request;
        unsigned int leftBorder, rightBorder;
        if (request == 'A') {
            int value;
            cin >> leftBorder >> rightBorder >> value;
            update(tree, 1, 0, quantityOfNumbers - 1, leftBorder - 1, rightBorder - 1, value);
        } else if (request == 'Q') {
            cin >> leftBorder >> rightBorder;
            cout << sum(tree, 1, 0, quantityOfNumbers - 1, leftBorder - 1, rightBorder - 1) << endl;
        }
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

#include <cmath>

#include <iostream>

#define WHITE -1

using namespace std;

// Function, that return lowest power of 2, bigger than a given number

int lowestBiggerPowOf2Than(int number) {

int answer;

answer = 1 << (int)(log2((double)number - 1) + 1);

return answer;

}

// The structure describing the components from which consists a tree

struct Node {

int color;

long long sumOnSegment;

// The default constructor

Node() {

color = WHITE;

sumOnSegment = 0;

}

// Construct the node by its color and sum on corresponding segment

Node(int color, long long sumOnSegment) {

this->color = color;

this->sumOnSegment = sumOnSegment;

}

// Define, if this node is painted in some color (some number is assigned)

bool isColored() {

return color != WHITE;

}

};

// Function, that pushes information from parent to the children

void push(Node *tree, int currentNode, int left, int right) {

if (tree[currentNode].isColored()) {

int middle = (left + right) / 2;

int leftChild = 2 * currentNode;

// Pass color from parent to children

tree[leftChild].color = tree[currentNode].color;

tree[leftChild + 1].color = tree[currentNode].color;

// Execute recalculation of the amount in the corresponding segments at children

tree[leftChild].sumOnSegment = (long long)(middle - left + 1) * tree[leftChild].color;

tree[leftChild + 1].sumOnSegment = (long long)(right - middle) * tree[leftChild + 1].color;

// Note parent's node as uncolored

tree[currentNode].color = WHITE;

}

// Function, that updates the value of all nodes on a segment for the specified

void update(Node *tree, int currentNode, int left, int right, int leftBorder, int rightBorder, int color) {

if (leftBorder == left && rightBorder == right) {

tree[currentNode] = Node(color, (long long)(right - left + 1) * color);

} else {

// Executes the delayed update (pushes information)

push(tree, currentNode, left, right);

int leftChild = 2 * currentNode;

int middle = (left + right) / 2;

if (rightBorder <= middle) {

update(tree, leftChild, left, middle, leftBorder, rightBorder, color);

} else if (leftBorder >= middle + 1) {

update(tree, leftChild + 1, middle + 1, right, leftBorder, rightBorder, color);

} else {

update(tree, leftChild, left, middle, leftBorder, middle, color);

update(tree, leftChild + 1, middle + 1, right, middle + 1, rightBorder, color);

}

// Update the amount in corresponding to parent segment

tree[currentNode].sumOnSegment = tree[leftChild].sumOnSegment + tree[leftChild + 1].sumOnSegment;

}

// Function, that calculates the sum at a specified segment

long long sum(Node *tree, int currentNode, int left, int right, int leftBorder, int rightBorder) {

if (left == leftBorder && right == rightBorder) {

return tree[currentNode].sumOnSegment;

} else {

// Executes the delayed update (pushes information)

push(tree, currentNode, left, right);

int leftChild = 2 * currentNode;

int middle = (left + right) / 2;

if (rightBorder <= middle) {

return sum(tree, leftChild, left, middle, leftBorder, rightBorder);

} else if (leftBorder >= middle + 1) {

return sum(tree, leftChild + 1, middle + 1, right, leftBorder, rightBorder);

} else {

return sum(tree, leftChild, left, middle, leftBorder, middle)

+ sum(tree, leftChild + 1, middle + 1, right, middle + 1, rightBorder);

}

int main() {

ios::sync_with_stdio(false);

unsigned int quantityOfNumbers;

cin >> quantityOfNumbers;

unsigned int sizeOfTree = 2 * lowestBiggerPowOf2Than(quantityOfNumbers);

Node *tree = new Node[sizeOfTree];

unsigned int quantityOfRequests;

cin >> quantityOfRequests;

for (unsigned int indexOfRequest = 0; indexOfRequest < quantityOfRequests; indexOfRequest++) {

char request;

cin >> request;

unsigned int leftBorder, rightBorder;

if (request == 'A') {

int value;

cin >> leftBorder >> rightBorder >> value;

update(tree, 1, 0, quantityOfNumbers - 1, leftBorder - 1, rightBorder - 1, value);

} else if (request == 'Q') {

cin >> leftBorder >> rightBorder;

cout << sum(tree, 1, 0, quantityOfNumbers - 1, leftBorder - 1, rightBorder - 1) << endl;

}

return 0;

}

Related Images:

e-olymp 2906. Can you answer these queries — 1

23/05/2016 by Таран Таня

You are given an integer sequence.

[latex]a_1, a_2, \ldots, a_n (|a_i| \le 15007, 1 \le n \le 50000)[/latex].

A query is defined as follows:

[latex]Query(x, y) = MAX (a_i + a_{i+1} + \ldots + a_j, x \le i \le j \le y)[/latex]

Given [latex]m[/latex] queries, your program must output the results of these queries.

Input

The first line contains the integer [latex]n[/latex]. In the second line [latex]n[/latex] integers of the sequence are given. The third line contains the integer [latex]m[/latex]. Then [latex]m[/latex] lines follow, where line [latex]i[/latex] contains two numbers [latex]x_i[/latex] and [latex]y_i[/latex].

Output

Print the results of the [latex]m[/latex] queries, one query per line.

Tests

№	Input	Output
1	3 -1 2 3 1 1 2	2
2	5 1 2 3 4 5 1 1 5	15
3	5 -1 -2 -3 -4 -5 1 1 5	-1
4	8 1 2 -3 -2 10 1 -15 7 4 1 1 3 4 3 6 1 8	1 -2 11 11
5	9 1 -2 3 -4 5 -6 7 -8 9 3 1 9 2 8 2 4	9 7 3

Algorithm

After analyzing the condition of the problem, we can understand that we need on a given segments of array to find subsegment with a maximum amount. We can solve this task by using segment tree, but before this we should modify it a bit. Create a structure of which our tree consists:

struct Node {
    int answer;         
    int sumOnPrefix;
    int sumOnSuffix;
    int sumOnSegment;
}

struct Node {

int answer;

int sumOnPrefix;

int sumOnSuffix;

int sumOnSegment;

}

That is, in each vertex of tree we store [latex]4[/latex] values:

the answer to the task for the current subsegment
the maximum amount among all prefixes
the maximum amount among all suffixes
the sum on the segment

First we need to get the values in the leaves. It’s simple enough all [latex]4[/latex] fields take the value of the number, that corresponds to this leaf. Now, having values in the leaves, we need to learn how to get the values in parent. For this we use the function Node mergeNodes(Node leftChild, Node rightChild), which assign to parent’s fields such values:

Answer in the parent equal to the answer in the right or the left child (means that the best subsegment of the current node is entirely in the left or right child), or the maximum amount of the maximum suffix in the left child and the maximum prefix in the right child (which means that it is partially is in the left child and partially is in the right child).
The maximum amount of the parent on prefix is equal to the maximum prefix of left child or sum on segment of left child and maximum prefix of right child.
The maximum amount of the parent on suffix is equal to the maximum suffix of right child or sum on segment of right child and maximum suffix of right child.
Amount on segment of the parent is equal to the sum on segment of left child and sum on segment of right child.

Now, with all the auxiliary functions for working with a built data structure, we need only to construct a tree and learn to get an answer on it.
We need two more functions:

void build(int *base, Node *tree, int currentNode, int left, int right) — recursive construction of a tree from the leaves to the root by initial sequence numbers.
Node answer(Node *tree, int currentNode, int left, int right, int leftBorder, int rightBorder) — as in the usual tree segments we get an answer going down by the tree, but instead of any associative function (eg sum or maximum) we execute the merger of nodes described earlier. Resulting node will store an answer corresponding to a given in the query segment.

Rest details of the implementation can be found in the code of the program or in the sources of information listed at the end of the article.

Code

#include <cmath>
#include <iostream>
#define INF -15008
using namespace std;

//  Function, that teturn lowest power of 2, bigger than a given number
int lowestBiggerPowOf2Than(int number) {                    
    int answer;
    answer = 1 << (int)(log2((double)number - 1) + 1);
    return answer;
}

//  The structure describing the components from which consists a tree
struct Node {
    int answer;         
    int sumOnPrefix;
    int sumOnSuffix;
    int sumOnSegment;
    //  Empty node takes the value less by 1 than what we can get, because we are looking for maximum subsegment
    Node() {
        answer = INF;
        sumOnPrefix = INF;
        sumOnSuffix = INF;
        sumOnSegment = INF;
    }
    // Constructs a node by a value of the initial sequence of numbers
    Node(int value) {
        answer = value;
        sumOnPrefix = value;
        sumOnSuffix = value;
        sumOnSegment = value;
    }
};

//  Function, that merges two nodes (childs) and returns new node (parent)
Node mergeNodes(Node leftChild, Node rightChild) {
    Node crossedNode;
    crossedNode.sumOnSegment = leftChild.sumOnSegment + rightChild.sumOnSegment;
    crossedNode.sumOnPrefix = max(leftChild.sumOnPrefix, leftChild.sumOnSegment + rightChild.sumOnPrefix);
    crossedNode.sumOnSuffix = max(rightChild.sumOnSuffix, leftChild.sumOnSuffix + rightChild.sumOnSegment);
    crossedNode.answer = max(leftChild.sumOnSuffix + rightChild.sumOnPrefix, max(leftChild.answer, rightChild.answer));
    return crossedNode;
}

//  Function, that building a tree recursive
void build(int *base, Node *tree, int currentNode, int left, int right) {
    if (left == right) {
        tree[currentNode] = Node(base[left]);
    } else {
        int leftChild = 2 * currentNode;
        int middle = (left + right) / 2;
        build(base, tree, leftChild, left, middle);
        build(base, tree, leftChild + 1, middle + 1, right);
        // Use the previously described function to get the value of parent by his children
        tree[currentNode] = mergeNodes(tree[leftChild], tree[leftChild + 1]);
    }
}

//  Function, that return node, storing the answer to the problem (subsegment with a maximum amount)
Node answer(Node *tree, int currentNode, int left, int right, int leftBorder, int rightBorder) {
    if (left == leftBorder && right == rightBorder) {
        return tree[currentNode];
    }
    int leftChild = 2 * currentNode;
    int middle = (left + right) / 2;
    if (rightBorder <= middle) {
        return answer(tree, leftChild, left, middle, leftBorder, rightBorder);
    }
    if (leftBorder > middle) {
        return answer(tree, leftChild + 1, middle + 1, right, leftBorder, rightBorder);
    }
    return mergeNodes(answer(tree, leftChild, left, middle, leftBorder, middle),
        answer(tree, leftChild + 1, middle + 1, right, middle + 1, rightBorder));
}

int main() {
    std::ios::sync_with_stdio(false);
    unsigned int quantityOfNumbers;
    cin >> quantityOfNumbers;
    int *base = new int[quantityOfNumbers];     //  A given sequence of numbers 
    for (unsigned int indexOfNumber = 0; indexOfNumber < quantityOfNumbers; indexOfNumber++) {
        cin >> base[indexOfNumber];
    }
    int sizeOfTree = 2 * lowestBiggerPowOf2Than(quantityOfNumbers);
    Node *tree = new Node[sizeOfTree];
    build(base, tree, 1, 0, quantityOfNumbers - 1);
    unsigned int quantityOfRequests;
    cin >> quantityOfRequests;
    for (unsigned int indexOfRequest = 0; indexOfRequest < quantityOfRequests; indexOfRequest++) {
        unsigned int leftBorder, rightBorder;
        cin >> leftBorder >> rightBorder;
        cout << answer(tree, 1, 0, quantityOfNumbers - 1, leftBorder - 1, rightBorder - 1).answer << endl;
    }
    return 0;
}

#include <cmath>

#include <iostream>

#define INF -15008

using namespace std;

// Function, that teturn lowest power of 2, bigger than a given number

int lowestBiggerPowOf2Than(int number) {

int answer;

answer = 1 << (int)(log2((double)number - 1) + 1);

return answer;

}

// The structure describing the components from which consists a tree

struct Node {

int answer;

int sumOnPrefix;

int sumOnSuffix;

int sumOnSegment;

// Empty node takes the value less by 1 than what we can get, because we are looking for maximum subsegment

Node() {

answer = INF;

sumOnPrefix = INF;

sumOnSuffix = INF;

sumOnSegment = INF;

}

// Constructs a node by a value of the initial sequence of numbers

Node(int value) {

answer = value;

sumOnPrefix = value;

sumOnSuffix = value;

sumOnSegment = value;

}

};

// Function, that merges two nodes (childs) and returns new node (parent)

Node mergeNodes(Node leftChild, Node rightChild) {

Node crossedNode;

crossedNode.sumOnSegment = leftChild.sumOnSegment + rightChild.sumOnSegment;

crossedNode.sumOnPrefix = max(leftChild.sumOnPrefix, leftChild.sumOnSegment + rightChild.sumOnPrefix);

crossedNode.sumOnSuffix = max(rightChild.sumOnSuffix, leftChild.sumOnSuffix + rightChild.sumOnSegment);

crossedNode.answer = max(leftChild.sumOnSuffix + rightChild.sumOnPrefix, max(leftChild.answer, rightChild.answer));

return crossedNode;

}

// Function, that building a tree recursive

void build(int *base, Node *tree, int currentNode, int left, int right) {

if (left == right) {

tree[currentNode] = Node(base[left]);

} else {

int leftChild = 2 * currentNode;

int middle = (left + right) / 2;

build(base, tree, leftChild, left, middle);

build(base, tree, leftChild + 1, middle + 1, right);

// Use the previously described function to get the value of parent by his children

tree[currentNode] = mergeNodes(tree[leftChild], tree[leftChild + 1]);

}

// Function, that return node, storing the answer to the problem (subsegment with a maximum amount)

Node answer(Node *tree, int currentNode, int left, int right, int leftBorder, int rightBorder) {

if (left == leftBorder && right == rightBorder) {

return tree[currentNode];

}

int leftChild = 2 * currentNode;

int middle = (left + right) / 2;

if (rightBorder <= middle) {

return answer(tree, leftChild, left, middle, leftBorder, rightBorder);

}

if (leftBorder > middle) {

return answer(tree, leftChild + 1, middle + 1, right, leftBorder, rightBorder);

}

return mergeNodes(answer(tree, leftChild, left, middle, leftBorder, middle),

answer(tree, leftChild + 1, middle + 1, right, middle + 1, rightBorder));

}

int main() {

std::ios::sync_with_stdio(false);

unsigned int quantityOfNumbers;

cin >> quantityOfNumbers;

int *base = new int[quantityOfNumbers]; // A given sequence of numbers

for (unsigned int indexOfNumber = 0; indexOfNumber < quantityOfNumbers; indexOfNumber++) {

cin >> base[indexOfNumber];

}

int sizeOfTree = 2 * lowestBiggerPowOf2Than(quantityOfNumbers);

Node *tree = new Node[sizeOfTree];

build(base, tree, 1, 0, quantityOfNumbers - 1);

unsigned int quantityOfRequests;

cin >> quantityOfRequests;

for (unsigned int indexOfRequest = 0; indexOfRequest < quantityOfRequests; indexOfRequest++) {

unsigned int leftBorder, rightBorder;

cin >> leftBorder >> rightBorder;

cout << answer(tree, 1, 0, quantityOfNumbers - 1, leftBorder - 1, rightBorder - 1).answer << endl;

}

return 0;

}

Related Images:

AL16

31/03/2016 by Таран Таня

Algolist. Data structures. Task 16.

There is a Ministry, that includes [latex]N[/latex] officials ([latex]N[/latex] is a natural number). Each official possibly has subordinates and chiefs. What is more, there are some rules:

Subordinates of my subordinate are my subordinates.
Chiefs of my chief — my chiefs.
My chief is not my subordinate.
Each official has no more than one direct chief.

In order to get a license for the export of copper, necessary to obtain a signature of the 1st official — сhief of all the сhiefs. But the situation complicated by the fact, that each official, generally speaking, can require «visas» — signatures some of his immediate subordinates and a bribe — a certain amount of dollars. Non-empty list of possible visas and corresponding to this list bribe are known for each official. The empty list means that the official doesn’t require a visa in this case. The official will put his signature, only if he receives all signatures from one of the visas list and the appropriate bribe.

You need to define and output the permissible and minimal for sum of bribes order and its cost.

Input

The input data is the following sequence of lines:

Quantity of officials [latex]N[/latex] ([latex]N < 100[/latex] ).
List of subordinates for current visa, which consists of their indeces, suitable to the order in which they came to input (could be empty, it suggests that the official doesn’t require a visa in this case).
«bribe» — signalyze, that input of current visa end. In next line you will recieve the cost of bribe — real number [latex]B[/latex] ([latex]0 < B < 10^6[/latex]) .
«next_official» — determine that information about previous official ended and next line will contain empty or not empty list of next official’s visas (there is no such command before 1st official. If there is no command «next_official « after the number, that determine a bribe, you will recieve next visa of the current official).

More info about input data you can find in test examples.

Output

You need to output in the separate lines the minimum sum of bribes for getting a license and the order. This is a string with the consecutive indices of the officials, who participated in the payment of the minimum bribe, (in order of raising in the hierarchical system, from left to right (arranging in entering the appropriate official)) separated with delimetr /.

Tests

№	Input	Output
1	2 2 bribe 50 next_official	50 2/1
2	5 2 bribe 100 3 bribe 200 4 bribe 150 next_official 5 bribe 10 next_official next_official next_official	110 5/2/1
3	7 2 bribe 150 3 bribe 50 next_official 4 bribe 40 5 bribe 20 next_official 6 bribe 150 7 bribe 200 next_official next_official next_official next_official	170 5/2/1
4	5 2 bribe 50 next_official 3 bribe 40 4 bribe 10 next_official next_official 5 bribe 10 next_official	70 5/4/2/1
5	8 2 bribe 100 next_official 3 bribe 200 4 bribe 150 3 4 bribe 50 next_official 7 bribe 25 next_official 5 bribe 10 6 bribe 80 next_official next_official next_official 8 bribe 35 next_official	220 8/7/5/3/4/2/1

Illustration for the test №3Illustration for the test №4

Illustration for the test №5

Algorithm

In order to implement solution of this problem, we construct two data structures Visa and Official. First of these stores fields vector <unsigned int> listOfSubordinatesForBribe — indices of subordinates, whose signatures are needed in this bribe and directly bribe. Every official, in their turn, has Id (serial number) and a list of all his visas — vector <Visa> listOfRequiredVisas. Also, we need two functions:

bool isBypassed(Official currentOfficial, string order) — determines whether the official is bypassed. It is realized on the condition that every official has no more than one direct chief. Therefore to find out if we take into account this official, we need to check whether there is in the list of bypassed at least one of his subordinates. Implementing a check directly on the current official Id is not possible, because we will go recursively from the leaves to the root.
void findCheapestWay(Official *listOfOfficials, Official currentOfficial, string &order, unsigned int &minimumBribe) — the main function dedicated to the search of the answer. Consider its job in detail:
Because there is no point in considering the officials, who don’t require any visa, we will process only those,who have non-empty list of visas and haven’t been visited yet. Otherwise, we will just go up to a higher level in the tree. For each official store vector <unsigned int> possibleSumsOfBribes and vector <string> possibleOrdersOfBypassing — possible variants of bribes and the order by which it was achieved. Also, we need two variables passed by reference in function — number minimumBribe and string order. They will help us to maintain a minimum bribe and its order at each hierarchy level, when we will call the recursive search for each subordinate in the visa.

Let us turn to the main executable part of the program. Organize the correct reading of the incoming data stream and save each official with its corresponding Id.
Start the search function of the first and the most important official — root. Getting in the first visa and starting a recursive search for all the subordinates we descend directly to the leaves of the tree. Leaning into a dead end, we start to climb from the bottom up, and for each official we find minimum possible bribe and order directly at his level. Thus we will be able consistently for each branch find it mimimum and pick it up by going to the root of the tree. Doing this for every possible visas, we fill the vector of potential bribes values, in which by searching the minimum element we can select required value. This will be the lowest possible price for a license.
Further details of the implementation can be seen in the comments to the code.

Code

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

const char DELIMITER = '/';                                                                                     // Delimiter character for the correct accumulation of order

struct Visa {
    vector <unsigned int> listOfSubordinatesForBribe;                                                         // Storage of subordinates' indices whose signature is required
    double bribe;                                                                                               // Required bribe
};
 
struct Official {
    unsigned int id;                                                                                                // Official id (sequence number in the input stream, starting at one)
    vector <Visa> listOfRequiredVisas;                                                                            // Storage of possible variants of visas
};
 
bool isBypassed(Official currentOfficial, string order) {                                                       // Return true, if this official is already bypassed
    bool isBypassed = false;
    for (auto currentVisa : currentOfficial.listOfRequiredVisas) {
        for (auto currentSubordinate : currentVisa.listOfSubordinatesForBribe) {
            if (order.find(to_string(currentSubordinate) + DELIMITER) != string::npos) {                            // We are looking we are looking for the presence of at least one subordinate including a separator
                isBypassed = true;                                                                              // In the string of previously accumulated order of bypass 
                break;
            }
        }
    }
    return isBypassed;
}
 
void findCheapestWay(Official *listOfOfficials, Official currentOfficial, string &order, unsigned int &minimumBribe) {
    vector <unsigned int> possibleSumsOfBribes;                                                                   // Stores all the possible sums of bribes for the current official
    vector <string> possibleOrdersOfBypassing;                                                                    // Stores all the possible orders for the current of
    if (!currentOfficial.listOfRequiredVisas.empty() && !isBypassed(currentOfficial, order)) {
        int currentSumOfBribes = 0;                                                                             // Current sum of bribes for current official
        for (auto currentVisa : currentOfficial.listOfRequiredVisas) {
            for (auto currentSubordinate : currentVisa.listOfSubordinatesForBribe) {
                findCheapestWay(listOfOfficials, listOfOfficials[currentSubordinate], order, minimumBribe);     // Recursively call the function for finding the minimum required bribe
                currentSumOfBribes = minimumBribe;                                                              // Store the detected minimum as a current
            }                                                                                                   // For each official we get down to the lower level
            string currentOrder;                                                                                    // Remember all the officials, that we bypassed to the current bribe 
            currentSumOfBribes = currentVisa.bribe;                                                             // Remember the bribe required by the current official as the current sum of bribes
            for (auto currentSubordinate : currentVisa.listOfSubordinatesForBribe) {
                currentOrder += to_string(currentSubordinate) + DELIMITER;
            }                                                                                                   // Remember the current oder for each visa (isn't necessary an order to get the minimum sum of bribes) with delimiter
            possibleOrdersOfBypassing.push_back(order + currentOrder);                                          // Adding one of the possible orders, including previously accumulated value
            possibleSumsOfBribes.push_back(minimumBribe + currentSumOfBribes);                                  // Adding one of the possible sums, including value that we get from lower level
        }                                                                                                       // Executes processing for each visa in visas list
        vector<unsigned int>::iterator iteratorToCurrentMinBribe = min_element(possibleSumsOfBribes.begin(), possibleSumsOfBribes.end());
        unsigned int indexOfCurrentMinBribe = distance(possibleSumsOfBribes.begin(), iteratorToCurrentMinBribe);// Find the index of the lowest possible variant in the resulting vector
        minimumBribe = possibleSumsOfBribes[indexOfCurrentMinBribe];                                                // This variant will be the smallest by sum of bribes, remember it
        order = possibleOrdersOfBypassing[indexOfCurrentMinBribe];                                              // And remember corresponding to minimum bribe order
    }                                                                                                           // Executes processing only if the list of visas isn't empty and the official isn't bypassed
}
 
int main() {
    string order;                                                                                               // The order of bypass, that we're looking for
    string typeOfCommand;                                                                                       // Technical variable for processing the input stream
    unsigned int quantityOfOfficials;                                                                           // User-defined number of officials
    unsigned int minimumBribe = 0;                                                                              // Minimum sum of bribes to get a license
    cin >> quantityOfOfficials;
    Official *listOfOfficials = new Official[quantityOfOfficials + 1];                                          // Keeps all the officials in the array with the corresponding index
    unsigned int indexOfOfficial = 1;
    while (cin >> typeOfCommand) { 
        Official currentOfficial;
        while (typeOfCommand != "next_official") { 
            Visa currentVisa;
            vector <unsigned int> requiredSubordinates;
            while (typeOfCommand != "bribe") { 
                requiredSubordinates.push_back(atoi(typeOfCommand.c_str()));                                        // Before recording convert the input string to the number
                cin >> typeOfCommand;
            }                                                                                                   // Read the current visa (indices of subbordinates for bribe)
            currentVisa.listOfSubordinatesForBribe = requiredSubordinates;
            cin >> typeOfCommand;                                                                             // Read directly bribe
            currentVisa.bribe = atoi(typeOfCommand.c_str());                                                        // Before recording convert the input string to the number
            currentOfficial.listOfRequiredVisas.push_back(currentVisa);                                         // Add current visa to the current official visas list
            cin >> typeOfCommand;
        }                                                                                                       // Read the current official
        currentOfficial.id = indexOfOfficial;
        listOfOfficials[indexOfOfficial] = currentOfficial;                                                     // Put all the read data into an array
        indexOfOfficial++;                                                                                      // Go to read the next official, if present
    }                                                                                                           // Read to the end of the input stream
    findCheapestWay(listOfOfficials, listOfOfficials[1], order, minimumBribe);                                  // Call the function from main official(first) and accumulate the required values
    order.push_back('1');                                                                                       // Add the first official explicitly, cause he hasn't chief, so doesn't participate in the bypassing
    cout << minimumBribe << endl << order << endl;
    return 0;
}

#include <ctime>

#include <string>

#include <vector>

#include <iostream>

#include <algorithm>

using namespace std;

const char DELIMITER = '/'; // Delimiter character for the correct accumulation of order

struct Visa {

vector <unsigned int> listOfSubordinatesForBribe; // Storage of subordinates' indices whose signature is required

double bribe; // Required bribe

};

struct Official {

unsigned int id; // Official id (sequence number in the input stream, starting at one)

vector <Visa> listOfRequiredVisas; // Storage of possible variants of visas

};

bool isBypassed(Official currentOfficial, string order) { // Return true, if this official is already bypassed

bool isBypassed = false;

for (auto currentVisa : currentOfficial.listOfRequiredVisas) {

for (auto currentSubordinate : currentVisa.listOfSubordinatesForBribe) {

if (order.find(to_string(currentSubordinate) + DELIMITER) != string::npos) { // We are looking we are looking for the presence of at least one subordinate including a separator

isBypassed = true; // In the string of previously accumulated order of bypass

break;

}

return isBypassed;

}

void findCheapestWay(Official *listOfOfficials, Official currentOfficial, string &order, unsigned int &minimumBribe) {

vector <unsigned int> possibleSumsOfBribes; // Stores all the possible sums of bribes for the current official

vector <string> possibleOrdersOfBypassing; // Stores all the possible orders for the current of

if (!currentOfficial.listOfRequiredVisas.empty() && !isBypassed(currentOfficial, order)) {

int currentSumOfBribes = 0; // Current sum of bribes for current official

for (auto currentVisa : currentOfficial.listOfRequiredVisas) {

for (auto currentSubordinate : currentVisa.listOfSubordinatesForBribe) {

findCheapestWay(listOfOfficials, listOfOfficials[currentSubordinate], order, minimumBribe); // Recursively call the function for finding the minimum required bribe

currentSumOfBribes = minimumBribe; // Store the detected minimum as a current

} // For each official we get down to the lower level

string currentOrder; // Remember all the officials, that we bypassed to the current bribe

currentSumOfBribes = currentVisa.bribe; // Remember the bribe required by the current official as the current sum of bribes

for (auto currentSubordinate : currentVisa.listOfSubordinatesForBribe) {

currentOrder += to_string(currentSubordinate) + DELIMITER;

} // Remember the current oder for each visa (isn't necessary an order to get the minimum sum of bribes) with delimiter

possibleOrdersOfBypassing.push_back(order + currentOrder); // Adding one of the possible orders, including previously accumulated value

possibleSumsOfBribes.push_back(minimumBribe + currentSumOfBribes); // Adding one of the possible sums, including value that we get from lower level

} // Executes processing for each visa in visas list

vector<unsigned int>::iterator iteratorToCurrentMinBribe = min_element(possibleSumsOfBribes.begin(), possibleSumsOfBribes.end());

unsigned int indexOfCurrentMinBribe = distance(possibleSumsOfBribes.begin(), iteratorToCurrentMinBribe);// Find the index of the lowest possible variant in the resulting vector

minimumBribe = possibleSumsOfBribes[indexOfCurrentMinBribe]; // This variant will be the smallest by sum of bribes, remember it

order = possibleOrdersOfBypassing[indexOfCurrentMinBribe]; // And remember corresponding to minimum bribe order

} // Executes processing only if the list of visas isn't empty and the official isn't bypassed

}

int main() {

string order; // The order of bypass, that we're looking for

string typeOfCommand; // Technical variable for processing the input stream

unsigned int quantityOfOfficials; // User-defined number of officials

unsigned int minimumBribe = 0; // Minimum sum of bribes to get a license

cin >> quantityOfOfficials;

Official *listOfOfficials = new Official[quantityOfOfficials + 1]; // Keeps all the officials in the array with the corresponding index

unsigned int indexOfOfficial = 1;

while (cin >> typeOfCommand) {

Official currentOfficial;

while (typeOfCommand != "next_official") {

Visa currentVisa;

vector <unsigned int> requiredSubordinates;

while (typeOfCommand != "bribe") {

requiredSubordinates.push_back(atoi(typeOfCommand.c_str())); // Before recording convert the input string to the number

cin >> typeOfCommand;

} // Read the current visa (indices of subbordinates for bribe)

currentVisa.listOfSubordinatesForBribe = requiredSubordinates;

cin >> typeOfCommand; // Read directly bribe

currentVisa.bribe = atoi(typeOfCommand.c_str()); // Before recording convert the input string to the number

currentOfficial.listOfRequiredVisas.push_back(currentVisa); // Add current visa to the current official visas list

cin >> typeOfCommand;

} // Read the current official

currentOfficial.id = indexOfOfficial;

listOfOfficials[indexOfOfficial] = currentOfficial; // Put all the read data into an array

indexOfOfficial++; // Go to read the next official, if present

} // Read to the end of the input stream

findCheapestWay(listOfOfficials, listOfOfficials[1], order, minimumBribe); // Call the function from main official(first) and accumulate the required values

order.push_back('1'); // Add the first official explicitly, cause he hasn't chief, so doesn't participate in the bypassing