e-olymp-1456. Барбос и Мухтар

Задача Барбос и Мухтар

Условие

На одной Большой Поляне росли два Больших Дерева – Большой Дуб и Большой Платан. К Большому Дубу были привязаны две собаки Барбос, длина цепи которого была равна $x$ метров, и Мухтар, длина его цепи $y$ метров. Однажды Барбосу надоело сидеть рядом с Мухтаром и он отбежал от Большого Дуба натянув свою цепь, Мухтар следуя примеру Барбоса, тоже решил подальше отбежать от Большого Дуба и тоже натянул свою цепь. Так они и сидели с натянутыми цепями, пока не заметили, что сидят на концах Прямой Тропы, на которой рос Большой Платан. Еще они заметили, что расстояние от Большого Дуба до Большого Платана равно расстоянию от Большого Дуба до Прямой Тропы. Также они не могли не заметить, что Барбосу в $z$ раз дальше бежать до Большого Платана по Прямой Тропе, чем Мухтару.

Каждая собака на Большой Поляне знает, что Большие Деревья – это материальные точки, а Прямая Тропа – отрезок прямой.

Помогите Барбосу и Мухтару узнать расстояние от Большого Дуба до Большого Платана.

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

Три вещественных числа $x$, $y$, $z$ (0 < $x, y, z $<[latex]10^7[/latex]) .

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

Вывести расстояние от Большого Дуба до Большого Платана с 9 десятичными знаками. Если это расстояние найти невозможно, то вывести слово IMPOSSIBLE.

 

Входные данные Выходные данные
1 12 23 3 24.023426067
2 11 10 120 9.999927078
3 1 3 3 3.162277660

 Решение

Решение

Пусть о — расстояние между Дубом и большим Платаном. После введения $x$, $y$ и $z$ проверяем первое условие if: если длины цепей Барбоса и Мухтара совпадают, то, когда обе собаки добежали до прямой тропы, треугольник, образованный их натянутыми цепями и прямой тропой является равнобедренным. Расстояние от Дуба до прямой тропы — высота треугольника, проведенная его основанию. Также основание высоты — Большой Платан (по условию). По свойству высоты, проведенной из вершины равнобедренного треугольника к его основанию, получим, что расстояние от Барбоса до Большого Платана равно расстоянию от Мухтара до Большого Платана, что противоречит условию (Барбосу в $z$ раз больше бежать до Большого Платана по Прямой Тропе, чем Мухтару). Также равенство расстояний до Большого Платана мы проверяем далее в условии: $(z==1)$. Если $z$ равен $1$, то эти отрезки равны, и утверждение, написанное выше, будет неверным. Проходя эту проверку, мы смотрим, удовлетворяют ли введенные данные условию задачи. Если утверждения в if выполняются — выводим IMPOSSIBLE, так как условия задачи не выполняются. В противном случае пропускаем первый if — данные введены корректно. Следующий условный оператор проверяет, равен ли $z$ нулю. Если да, то выводим y, потому что в таком случае расстояние от Дуба до Бльшого Платана равно длине цепи Мухтара. Именно Мухтара, так как, по условию, Барбосу бежать до Большого Платана дольше. Если данное условие не выполняется, вычисляем расстояние между деревьями по формуле: $\frac{(yy-xxzz)}{double(1-zz)}$
Затем выводим расстояние, округлив его до 9 знаков после запятой .

Ссылки

Ссылка на e-olymp

Ссылка на ideone

e-olymp-248. Юный садовод

Задача Юный садовод

Условие

Мама попросила Васю полить все молодые деревца в саду. Вася знает, что пока деревья маленькие, их надо очень хорошо поливать. А вот сколько поливать — неизвестно. Но Вася — очень умный мальчик. Он внимательно прочитал весь учебник ботаники для средней школы и выяснил, что полив прямо пропорционален количеству листьев на дереве. Для хорошего роста деревьев достаточно выливать под дерево ежедневно по одному литру воды на каждый лист.prb248

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

 

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

Количество ярусов [latex] n(0≤n≤1000)[/latex]  на дереве.

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

Вывести количество литров воды для полива этого дерева.

Тесты

Входные данные Выходные данные
1. 10 111
2. 0 1
3. 5 31
4. 123 15253

Линейное вычисление

Решение

Что бы решить эту задачу, необходимо найти сумму арифметической прогрессии, где [latex]  a_1=2[/latex] и   [latex] d=2 [/latex] и добавить к ней единицу (лист с верхушки).  Для этого можно воспользоваться формулой суммы арифметической прогрессии $S_n=\frac{2a_1+d(n-1)}{2}n$

Ссылки

Ссылка на e-olymp

Ссылка на ideone

e-olymp 93. Truck driving

Task

Umidsh Izadish is a truck driver and wants to drive from a city to another city while there exists a dedicated straight road between each pair of cities in that country. Amount of consumed fuel is the distance between two cities which is computed from their coordinates. There is a gas station in each city, so Umidsh can refuel the gas container of his truck. Your job is to compute the minimum necessary volume of gas container of Umidsh’s Truck.

Input data

The first line of input contains an integer, the number of test cases. Following, there are data for test cases. Each test case begins with a line containing one integer, $C$ $(2 ≤ C ≤ 200)$, which is the number of cities. The next $C$ lines each contain two integers $x$, $y$ $(0 ≤ x, y≤ 1000)$ representing the coordinate of one city. First city is the source city and second is the destination city of Umidsh.

Output data

There should be one line for each test case in output. Each line should contain one floating point number which is the minimum necessary volume of truck’s gas container, printed to three decimals.

Tests

Input Output
$2$
$2$
$0$ $0$
$3$ $4$
$3$
$17$ $4$
$19$ $4$
$18$ $5$
$5.000$
$1.414$
$1$
$3$
$4$ $5$
$4$ $6$
$4$ $7$
$1.000$
$2$
$4$
$0$ $1$
$0$ $-1$
$1$ $0$
$-1$ $0$
$3$
$8$ $9$
$0$ $1$
$14$ $14$
$1.414$
$11.314$
$3$
$2$
$1$ $1$
$1$ $2$
$5$
$8$ $6$
$3$ $3$
$4$ $1$
$7$ $7$
$5$ $0$
$3$
$1$ $1$
$1$ $3$
$2$ $5$
$1.000$
$5.657$
$2.000$

Code

Solution

We can interpretate the set of the cities as weighted graph, which vertices represent cities and weight of each edge between two vertices is the gas volume required for passing the distance between corresponding cities.
The volume of truck’s gas container depends on the gas volume required for arrival to the each next station of the Umidsh’s way. The maximum between gas volume required to get to the city $A$ and gas volume required to pass the way from the city $A$ to the city $B$ represents the minimum necessary gas volume required to get to the city $B$ through the city $A$. So the volume of truck’s gas container would turn to minimum, when the maximum gas volume required for passing the distance between each two stations of his way would turn to minimum. Thus we could use modified Dijkstra’s algorithm to find the biggest value among the weights of an edges between each two stations of the way between vertice 0 and vertice 1.

References

The task at E-Olymp
My solution at ideone

e-olymp 4493. Трое из Простоквашино 3

Задача

[latex]-[/latex] Печкин, а я научился работать с деревом отрезков.

[latex]-[/latex] Заняться тебе нечем просто, Шарик. Лучше бы помог мне письма разносить.

[latex]-[/latex] Ну, Печкин, я уже даже выполнил задания Дяди Федора и Кота Матроскина, только этот Матроскин не захотел проверять, правильно ли я сделал.

[latex]-[/latex] Ну ладно, давай я проверю, что там надо было сделать?

[latex]-[/latex] У меня был массив чисел и множество запросов – представляющих собой либо запрос на изменение в массиве, либо содержащий число, для которого мне нужно было найти такой промежуток [[latex]l;r[/latex]], что максимум на этом промежутке был бы равен заданному числу. Можешь прочитать предыдущую задачу.

[latex]-[/latex] Разберемся…

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

В первой строке содержится одно число [latex]N[/latex] ([latex]1≤N≤106[/latex]) – количество элементов в массиве. В следующей строке находится [latex]N[/latex] целых, неотрицательных чисел, не превосходящих 109 – сами элементы массива. Затем следует число [latex]M[/latex] ([latex]1≤M≤105[/latex]) – количество запросов. Затем [latex]М[/latex] строк, первое число в каждой из которых означает тип запроса: если оно равно единице, то далее следует единственное число [latex]x[/latex], и Шарику надо было найти два числа [latex]l[/latex] и [latex]r[/latex], такие, что максимум на промежутке [[latex]l;r[/latex]], был равен [latex]x[/latex]. Если же тип запроса равен двум, то далее следует два числа [latex]pos[/latex] и [latex]val[/latex] и это значит, что элемент массива, стоящий на позиции [latex]pos[/latex], теперь изменен и он стал равен значению [latex]val[/latex]. Далее для каждого запроса с номером один содержится по строке с двумя числами [latex]l[/latex] и [latex]r[/latex] – ответы Шарика.

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

Для каждого ответа Шарика выведите [latex]»Yes»[/latex], если он ответил правильно и [latex]»No»[/latex], если Шарик ошибся. Заметьте, что хотя в предыдущей задаче было необходимо найти минимальные числа [latex]l[/latex] и [latex]r[/latex], здесь Печкин проверять этого не будет.

Тесты

Входные данные Выходные данные
5
1 2 4 3 1
5
1 4
1 5
2 3 5
1 1
1 4
1 3
1 5
5 5
2 4
Yes
No
Yes
No

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

Решение

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

Ссылки
Код на ideone.com
Задача с сайта e-olymp.com.
Засчитанное решение.

e-olymp 4496. Приключение Незнайки и его друзей

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

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

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

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

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

В первой строке содержится количество человечков [latex]n (1 ≤ n ≤ { 10 }^{ 6 })[/latex] в цветочном городе. Во второй строке заданы веса каждого из человечков в том порядке, в котором они будут садиться в шар. Все веса натуральные числа и не превышают [latex]{ 10 }^{ 9 }[/latex]. Далее следует количество запросов [latex]m (1 ≤ m ≤ { 10 }^{ 5 })[/latex]. Каждый запрос представляет собой одну строку. Если первое число в строке равно единице, то далее следует еще одно число [latex]v (1 ≤ v ≤ { 10 }^{ 9 })[/latex] – грузоподъемность воздушного шара. Если же оно равно двум, то далее следует два числа [latex]x (1 ≤ x ≤ n)[/latex] и [latex]y (1 ≤ y ≤ { 10 }^{ 9 })[/latex] — это значит, что вес человечка, стоящего на позиции [latex]x[/latex], теперь равен [latex]y[/latex].

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

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

Тесты

Входные данные Выходные данные
1 5
1 2 3 4 5
5
1 7
1 3
2 1 5
1 7
1 3
3
2
2
0
2 2
1 2
3
1 4
2 1 10
1 4
2
0
3 2
999999999 1000000000
4
1 999999999
2 1 1000000000
1 999999999
1 1000000000
1
0
1

Код на C++

Код на Java

Описание

В данной задаче требуется эффективно выполнять две операции: изменять значение одного из элементов массива и находить, сколько человечков поместится в шар при заданной грузоподъёмности. Это было реализовано при помощи структуры segment_tree. В функции main сначала вводится значение n и заполняется массив весов человечков weights, после чего по нему выполняется построение дерева отрезков tr. В его вершинах хранятся частичные суммы элементов массива. Да и в целом функции для построения и выполнения запроса модификации у него такие же, как и у обычного дерева отрезков для нахождения суммы на отрезке. Для удобства в массиве weights и в самом дереве используются элементы с первого по [latex]n[/latex]-й, а не с нулевого по [latex]\left( n-1 \right) [/latex]-й. Далее в ходе работы функции main в цикле выполняется обработка запросов. Сначала вводится тип запроса type. Если запрос второго типа, вводятся позиция человечка x, его новый вес y и вызывается метод update, пересчитывающий значения суммы в вершинах, на которые влияет это изменение. Иначе вводится грузоподъемность воздушного шара v и вызывается метод find_numb_of_p, который находит количество человечков, поместившихся в шар. Работает он следующим образом: если выполняется условие tree_l == tree_r, значит, рассматриваемый отрезок состоит из одного элемента, и функция возвращает [latex]1[/latex], если человечек может поместиться в шар, и [latex]0[/latex], если он слишком тяжёлый. Если отрезок больше, вычисляется индекс элемента, находящегося посередине tree_m. Далее, если сумма весов человечков в левом поддереве tree[v*2] больше, чем грузоподъёмность шара, то никто из правого поддерева уже не поместится, и искать следует только в левом поддереве. Иначе в шар следует посадить всех человечков из левого поддерева (их количество равно tree_m - tree_l + 1) и посмотреть, сколько поместится человечков из правого поддерева. При этом необходимо от максимально допустимого веса отнять вес человечков из левого поддерева, уже сидящих в шаре ( max_w-tree[v*2]).

Код на ideone.com. (C++)
Засчитанное решение на e-olymp.com. (C++)
Код на ideone.com. (Java)
Засчитанное решение на e-olymp.com. (Java)
При решении задачи был использован материал с сайта e-maxx.ru.

e-olymp 3358. Чёрный ящик

Задача

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

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

Первая строка содержит количество событий [latex]n[/latex] [latex]\left(1 \le n \le 2 \times 10^{5} \right)[/latex]. Каждая из следующих n строк содержит описание одного события:

  • [latex]+ x[/latex] — положен листок с числом [latex]x[/latex] [latex]\left(1 \le x \le 10^{6} \right)[/latex];
  • [latex]- x[/latex] — исчез листок с числом [latex]x[/latex] (гарантируется, что в ящике был хотя бы один листок с числом [latex]x[/latex]).

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

Вывести в точности [latex]n[/latex] строк — по одной для каждого события. Каждая строка должна содержать одно число — ответ к задаче. Если после какого-то события ящик оказался пуст, следует вывести [latex]0[/latex].

Тесты

Входные данные Выходные данные
3
+ 1
— 1
+ 2
1
0
2
6
+ 1
+ 1000000
— 1
+ 4
+ 4
— 1000000
1
1
1000000
4
4
4
8
+ 71
+ 91
+ 99
+ 71
— 71
— 91
— 71
— 99
71
71
71
71
71
71
99
0

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

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

Проанализируем задачу: так как требуется вывести число, которое встречается чаще всего на листках, находящихся в ящике после запроса удаления/добавления, а если таких чисел несколько, то вывести наименьшее, то задачу можно переформулировать следующим образом:

«Даётся последовательность (массив) объектов leaf [latex]x_{1}[/latex], [latex]x_{2}[/latex], [latex]x_{3}[/latex], [latex]\ldots[/latex], [latex]x_{999999}[/latex], [latex]x_{1000000}[/latex], представляющих из себя пару (number, amount)[latex]=x_{i}=\left(i, a_{i}\right) \in {\mathbb{N}_{0}}^{2}[/latex], где первые элементы пар [latex]i[/latex] представляет из себя число/номер листка, а вторые элементы [latex]a_{i}[/latex] — число листков с этим номером. Изначально все элементы пар [latex]a_{i}[/latex] равны нулю (так как изначально ящик пуст). Для запросов первого типа [latex]+ x[/latex] необходимо увеличивать на единицу число [latex]a_{i}[/latex] объекта, у которого номер [latex]i[/latex] равен [latex]x[/latex], а для запросов второго типа — уменьшать. Для каждого запроса необходимо вывести число [latex]j[/latex], удовлетворяющее условию [latex]j = \min\limits_{i \in \mathbb{K}}{i}[/latex], где [latex]\mathbb{K} = \{i \mid a_{i} = \max\limits_{k \in \{1, 2, \ldots, 1000000\}}{a_{k}} \}[/latex]».

Иными словами, число [latex]i[/latex] соответствует некоторому элементу [latex]x_{i} = \left(i, a_{i}\right)[/latex], который в свою очередь определяется операцией такой, что [latex]i[/latex] и [latex]a_{i}[/latex] удовлетворяют приведённым выше условиям. Очевидно, что данная операция является ассоциативной (как объединение минимума и максимума на заданных множествах), а потому для решения задачи воспользуемся универсальным деревом отрезков.

Создадим дерево отрезков box методом read_and_construct из объектов leaf. Так как нумерация листков начинается с единицы, а их число не превышает [latex]10^{6}[/latex], зададим размер базы дерева отрезков [latex]10^{6}+1[/latex], добавив неё элемент с индексом [latex]0[/latex]. Модифицируем метод read_and_construct таким образом, чтобы в функцию-препроцессор передавался номер элемента [latex]i[/latex], дабы была возможность задавать элементам [latex]x_{i}[/latex] их первоначальные значения [latex]\left(i, 0\right)[/latex]. Вышеупомянутую операцию назовём max_leafs и определим таким образом, чтобы она принимала два аргумента [latex]x_{i} = \left(i, a_{i}\right)[/latex] и [latex]x_{j} = \left(j, a_{j}\right)[/latex] и возвращала тот из них, у которого значение [latex]a[/latex] является большим, а в случае равенства этих значений — аргумент с меньшим индексом. Нейтральным элементом относительно данной операции будет, очевидно, пара [latex]\left(+\infty, 0\right)[/latex], но в силу того, что номера элементов не превышают [latex]10^6[/latex], вместо неё мы будем пользоваться парой [latex]\left(2 \times 10^{6}, 0\right)[/latex].

Далее при запросах вида [latex]+ x[/latex] будем увеличивать соответствующее значение [latex]a_{x}[/latex] пары [latex]\left(x, a_{x}\right)[/latex] на единицу, а при запросах вида [latex]- x[/latex] — уменьшать. Для обоих запросов будем выводить номер заданного листка, который удовлетворяет приведённым в задаче условиям, с использованием метода result_on_segment на всём отрезке [latex]\left[0, 10^{6}\right][/latex]. Ответом для каждого запроса будет значение number пары, которую вернёт метод.

Примечание: ситуация когда ящик становится пустым нигде не обрабатывается, но в силу того, что мы определили массив на отрезке [latex]\left[0, 10^{6}\right][/latex] вместо [latex]\left[1, 10^{6}\right][/latex] в нём всегда есть пара [latex]\left(0, 0\right)[/latex] (листки с номером [latex]0[/latex], число (значение [latex]b[/latex]) которых всегда равно [latex]0[/latex] в силу того, что листки с номером [latex]0[/latex] в ящик не добавляются). Так как определённая нами операция всегда возвращает минимальный номер листка, число которого максимально, то в случае, когда ящик пуст (т.е. значения всех [latex]a_{i} = 0, i = 0, 1, \ldots, 10^{6}[/latex]) будет выводится номер листка [latex]0[/latex]. Этот побочный эффект данного нами определения массива решает эту ситуацию и завершает решение задачи.

Ссылки

Универсальное дерево отрезков

Некоторые теоретические сведения

Обобщённое условие задач на дерево отрезков, как правило, выглядит так:
«Пусть дан моноид [latex]\left(\mathbb{G}, \circ\right)[/latex], где [latex]\mathbb{G}[/latex] — некоторое непустое множество, [latex]\circ[/latex] — ассоциативная бинарная алгебраическая операция на этом множестве, имеющая нейтральный элемент, [latex]A[/latex] — последовательность (массив) элементов из [latex]\mathbb{G}[/latex], содержащая [latex]n[/latex] элементов ([latex]n \in \mathbb{N}[/latex]; с математической точки зрения [latex]A[/latex] — вектор, построенный из элементов [latex]\mathbb{G}[/latex], или [latex]А = \left( x_{0}, x_{1}, \ldots, x_{n-1} \right) \in \mathbb{G}^{n}[/latex]).
Даётся [latex]m[/latex] ([latex]m \in \mathbb{N}[/latex]) запросов двух типов:
1) вычислить значение выражения [latex]x_{i} \circ x_{i+1} \circ \ldots \circ x_{j-1} \circ x_{j}[/latex] с заданными [latex]i[/latex], [latex]j[/latex] ([latex]0 \le i \le j \le n-1[/latex], [latex]i, j \in \mathbb{N} \cup \{ 0 \}[/latex]) и вывести его;
2) заменить значение элемента с индексом [latex]k[/latex] на [latex]y[/latex] ([latex]k \in \mathbb{N} \cup \{ 0 \}[/latex], [latex]k \le n-1[/latex], [latex]y \in \mathbb{G}[/latex]).»

Как правило, человек, впервые увидевший задачу подобного рода, решает её следующим образом: для запросов первого типа (далее — запросы значения на отрезке [latex]\left[i, j\right][/latex]) создаётся вспомогательная переменная, изначально равная нейтральному элементу моноида (к примеру, если [latex]\left( \mathbb{G}, \circ \right) = \left( \mathbb{Z}, + \right)[/latex] то нейтральным элементом относительно [latex]+[/latex] является [latex]0[/latex]), и запускается цикл на заданном отрезке, который «прибавляет» к ней новые «слагаемые», а обработка запросов из пункта 2 реализуется через простое присваивание элементу массива с заданным индексом [latex]i[/latex] значения [latex]y[/latex]. Таким образом вычислительная сложность запросов замены составляет [latex]O\left(1\right)[/latex], а запросов поиска значения на отрезке [latex]\left[i, j\right][/latex] в лучшем случае составляет [latex]O\left(1\right)[/latex], когда [latex]i = j[/latex], а в худшем [latex]O\left(n\right)[/latex], когда [latex]i = 0[/latex], [latex]j = n-1[/latex].

Дерево отрезковструктура данных, которая позволяет сбалансировать операции замены и вычисления значения на заданном отрезке до вычислительной сложности [latex]O\left(\log_{2}{n}\right)[/latex] и значительно улучшить общую сложность программы с [latex]O\left(n+n\cdot m\right) = O\left(n\cdot m\right)[/latex] до [latex]O\left(n+m\cdot\log_{2}{n}\right)[/latex].

Определение: массив/последовательность элементов/вектор, над которым построено дерево отрезков, называется базой дерева или просто базой, а число её элементов — её размерностью.

Задача 1: единичная модификация

Написать класс «дерево отрезков», применимый к любой задаче на моноиде, в которой присутствуют запросы замены элемента и результата операции на отрезке,
и таблицу его базовых функций и параметров.

Код класса


Описание класса

Далее [latex]n[/latex] — размерность базы дерева.

Название объекта Описание
Параметр
TYPE Тип объектов дерева, над которыми будут проводится вычисления.
Внутренние объекты
SegmentTree Массив, хранящий в себе дерево отрезков.
base_capacity Переменная, хранящая округлённую к ближайшей большей степени двойки размерность базы дерева отрезков.
g Указатель на функцию, которая представляет из себя ассоциативную бинарную операцию. Формально определяется как функция/операция.
neutral Нейтральный элемент относительно бинарной операции g.
Методы класса
construct

Аргументы:

  1. Адрес начала полуинтервала [latex]a[/latex];
  2. Адрес конца полуинтервала [latex]b[/latex];
  3. Ассоциативная бинарная операция f;
  4. Нейтральный элемент относительно f.

Генерирует базу на основе полуинтервала [latex]\left[a; b\right)[/latex], копируя его элементы внутрь дерева, и строит на основе этой базы дерево отрезков.
Вычислительная сложность: [latex]O\left(n\right)[/latex].

read_and_construct Аргументы:

  1. Размер базы дерева;
  2. Функция-препроцессор;
  3. Ассоциативная бинарная операция f;
  4. Нейтральный элемент относительно f.

Генерирует базу на основе элементов, возвращаемых функцией-препроцессором, и строит на их основе дерево отрезков.
Вычислительная сложность: [latex]O\left(n\right)[/latex].

assign Аргументы:

  1. Индекс элемента;
  2. Новое значение элемента.

Заменяет значение элемента с заданным индексом на новое.
Вычислительная сложность: [latex]O\left(\log_{2}{n}\right)[/latex].

result_on_segment Аргументы:

  1. Индекс левого конца отрезка;
  2. Индекс правого конца отрезка.

Возвращает результат функции на заданном отрезке.
Вычислительная сложность: [latex]O\left(\log_{2}{n}\right)[/latex].

Инструкция по применению

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

Построение:

  • Создать тип объектов (структуру данных), который будет использоваться в дереве для вычислений; (в зависимости от задачи. Вполне может быть, что необходимый для решения задачи класс уже создан. Например — int или double.)
  • Инициализировать дерево отрезков, передав классу segments_tree в качестве параметра тип объектов, над которыми будут проводиться вычисления, и задав дереву имя. (инициализация класса segments_tree происходит аналогично инициализации класса vector)
  • Построить дерево отрезков на основе заданных элементов при помощи метода construct или read_and_construct, передав методу соответствующие параметры (упомянутые в таблице выше);

Далее для вычисления результатов на отрезках и модификаций элементов с заданным индексом использовать методы result_on_segment и assign соответственно.

Пример использования

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

Решение задачи №4082 на www.e-olymp.com

Так как в задаче необходимо выводить знак или произведения на заданных отрезках (либо нуль), то очевидно, что сами числа не интересуют нас. Тогда каждое из них можно представить в виде пары (zero, plus)[latex]= \left(a, b\right) \in \mathbb{B}^{2}[/latex] (где [latex]\mathbb{B}[/latex] — булево множество), где первый элемент пар [latex]a[/latex] будет характеризовать равенство числа нулю, а [latex]b[/latex] — его положительность. Назовём структуру данных пар такого типа number_sign. Функция make_number_sign будет преобразовывать числа типа short в number_sign. Затем определим для этой структуры функцию умножения prod формулой prod(number_sign a, number_sign b)[latex]=[/latex] (a.zero|b.zero, !(a.plus^b.plus));. В первой части формулы используется дизъюнкция, так как произведение нуля и произвольного числа всегда должно возвращать нуль, а во второй части — эквиваленция, так как результат произведения является отрицательным, если оба аргумента различны по знаку.

Затем, предварительно считав размер базы, конструируем дерево отрезков методом read_and_construct, передавая ему число элементов базы, анонимную функцию-препроцессор, которая считывает элементы базы из входного потока и которая преобразует их в тип данных number_sign, функцию произведения prod и её нейтральный элемент number_sign(), являющийся парой [latex]\left(0, 1\right)[/latex], который по сути представляет из себя число [latex]+1[/latex] (нейтральный элемент умножения).

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

Фрагмент кода


Задача 2

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

  • параметры «вместимость» и «размер»;
  • функции добавления нового элемента в базу;
  • функции, возвращающие размер базы и вместимость дерева;
  • функция изменения размера базы.

Написать таблицу новых функций и параметров.

Код класса

Описание дополнительных объектов класса

Название объекта Описание
Новый внутренний объект
base_size Переменная, хранящая размерность базы дерева отрезков.
Новые методы класса
begin

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

end Аргументы: отсутствуют.
Возвращает адрес конца базы.
Вычислительная сложность: константа.
push_back Аргумент: значение нового элемента базы.
Добавляет новый элемент в конец базы.
Вычислительная сложность: если база заполнена, то [latex]O\left(n\right)[/latex], иначе — [latex]O\left(\log_{2}{n}\right)[/latex].

pop_back

Аргументы: отсутствуют.
Удаляет элемент в конце базы.
Вычислительная сложность: [latex]O\left(\log_{2}{n}\right)[/latex].

insert

Аргументы:

  1. Индекс нового элемента;
  2. Значение нового элемента.

Добавляет на заданную позицию базы новый элемент с заданным значением.
Вычислительная сложность: [latex]O\left(n\right)[/latex].

erase

Аргумент: индекс удаляемого элемента.
Удаляет из базы элемент с заданным индексом.
Вычислительная сложность: [latex]O\left(n\right)[/latex].

size

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

capacity

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

resize

Аргумент: новый размер базы.
Изменяет размер базы дерева, и преобразовывает незадействованные элементы в нейтральные
Вычислительная сложность: [latex]O\left(n\right)[/latex], если новый размер базы превысил вместимость дерева или является меньше, чем старый, и константа в противном случае.

Ссылки

e-olymp 4481. В стране невыученных уроков

Задача

Витя попал в страну невыученных уроков. Для того, чтобы вернуться домой ему нужно выполнить множество заданий. В этой задаче он должен выиграть у стражей в НОД-игру. Правила этой игры очень простые: есть массив натуральных чисел, после чего игроки выбирают два числа [latex]l[/latex] и [latex]r[/latex], и им надо посчитать наибольший общий делитель (НОД) всех элементов в массиве с индексами от [latex]l[/latex] до [latex]r[/latex] включительно. Кто быстрее посчитает, тот и выиграл. Чтобы избежать нечестных игр, они иногда заменяют некоторые числа в массиве на другие.

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

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

Первая строка содержит количество элементов [latex]n[/latex] [latex](1\leq n\leq 10^5)[/latex] в массиве. Во второй строке находится [latex]n[/latex] чисел – элементы [latex]a_i[/latex] [latex](1\leq a_i\leq 10^9)[/latex] массива. В третьей строке находится количество запросов [latex]m[/latex] [latex](1\leq m\leq 10^5)[/latex]. Далее в [latex]m[/latex] строках находятся по три числа [latex]q[/latex], [latex]l[/latex], [latex]r[/latex] [latex](1\leq l\leq r\leq n)[/latex]. Если [latex]q=1[/latex], требуется посчитать НОД элементов на промежутке [latex][l,r][/latex], если [latex]q=2[/latex], то надо заменить элемент в позиции [latex]l[/latex] на число [latex]r[/latex].

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

Для каждого запроса с номером [latex]l[/latex] в отдельной строке выведите ответ на запрос.

Тесты

Входные данные: Выходные данные:
5
2 4 6 10 8
6
1 1 5
1 2 3
2 5 15
2 3 10
1 3 5
1 1 5
2
2
5
1

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

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

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

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

Для получения подробной информации о структуре данных «Дерево отрезков» можно перейти по данной ссылке
Ссылка на засчитанное решение на e-olymp
Ссылка на условие задачи
Ссылка на решение задачи на ideone.com

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

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

Это нормально чувствовать себя взволнованным и напряженным за день до олимпиады по программированию. Чтобы расслабиться, вы пошли выпить со своими друзьями в соседний паб. Для сохранения остроты ума до следующего дня, Вы решили сыграть в следующую игру. Для начала Ваши друзья написали последовательность [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

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

00
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

+-

 

++

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

Решение

Данная задача решается при помощи стандартного алгоритма по теме «Дерево отрезков» (данный алгоритм можно посмотреть на сайте 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

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

Задача взята с сайта 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

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

ideone.com

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

Решение

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

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

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

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

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

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

Условие

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

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

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

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

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

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

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

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

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

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

Условие

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

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

  • [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

Код

Решение

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

(Тут [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], для остальных узлов подотрезки массива, отвечающие им, только подразумеваются).
graph1
Теперь разберемся, как эффективно создавать новые версии массива. Пусть у нас уже есть [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]. Вот, что мы получим в результате (черный цвет — первая версия, красный — вторая, синий — третья):

graph2

Рассмотрим, как получилась вторая версия. Создаем корень {[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); можно очень просто избавиться от рекурсии:

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

e-olymp 978. Получи дерево

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

Условие

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

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

Первая строка содержит количество вершин [latex]n[/latex] (1 ≤ [latex]n[/latex] ≤ 100) и количество ребер [latex]m[/latex] графа. Следующие [latex]m[/latex] пар чисел задают ребра графа. Гарантируется, что граф связный.

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

Выведите [latex]n — 1[/latex] пару чисел — ребра, которые войдут в дерево. Ребра можно выводить в любом порядке.

Код

Тесты

Ввод Вывод
4 4
1 2
2 3
3 4
4 1
1 2
2 3
3 4
6 7
1 2
2 3
3 4
4 5
5 6
6 1
1 2
2 3
3 4
4 5
5 6
6 5
1 2
2 3
3 4
4 5
5 6
1 2
2 3
3 4
4 5
5 6
4 5
4 3
2 4
2 3
1 2
1 3
4 3
2 4
1 2
6 9
1 2
1 3
1 5
2 5
2 4
3 5
3 6
4 5
5 6
1 2
1 3
1 5
2 4
3 6

Решение

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

Данную задачу я решил, применяя упрощенный алгоритм Краскала, учитывая, что данное дерево не является взвешенным и сортировку применять не нужно.  Для начала объявляем наш исходный граф используя вектор ребер (edge). Структура ребер является простой и содержит в себе только информацию о вершинах, которое ребро соединяет. Алгоритм Краскала заключается в том, что мы каждую вершину помещаем в свое множество. Затем при просмотре каждого ребра исходного графа мы проверяем принадлежат ли вершины ребра одному множеству. Если нет, то добавляем данное ребро в наше дерево (предварительно его создав с помощью вектора ребер), после добавления мы добавляем все вершины, которые принадлежали тому же множеству, что и вторая вершина ребра, в множество первой вершины. Если же вершины уже принадлежат одному множеству, то переходим к следующему этапу цикла. После этой процедуры нам достаточно вывести на экран значения из нашего дерева — это и будут необходимые ребра.

UPD: обновил код, тесты, описание решения и ссылки.

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

Условие

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

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

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

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

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

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

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

Код

Ideone

Код на Java:

 

Решение

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

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

e-olimp 3837. Выражения

Задача

Арифметические выражения, как правило, записываются с операторами между двумя операндами (такая запись называется инфиксной нотацией). Например, (x + y) * (zw) — арифметическое выражение в инфиксной нотации. Однако легче написать программу, вычисляющую значение выражения, когда оно находится в постфиксной нотации (известная как обратная польская нотация). В постфиксной нотации оператор записывается за своими двумя операндами, которые и сами в могут быть выражениями. Например, x y + z w — * является постфиксной нотацией приведенного выше выражения. Заметим, что для такой записи скобки не нужны.

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

  1. push: число кладется на верх стека.
  2. pop: число снимается с вершины стека.

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

a := pop();

b := pop();

push(b O a);

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

Предположим, что мы используем вместо стека очередь. Очередь также имеет операции push иpop, но их смысл немного другой:

  1.    push: число вставляется в конец очереди.
  2.    pop: из начала очереди извлекается число.

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

 

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

Если задана правильная строка в постфиксной нотации, то алгоритм её вычисления на основе стека выглядит следующим образом:

  1. Просматриваем строку слева направо
  2. Если встречаем переменную, помещаем её в конец стека/очереди
  3. Если встречаем символ оператора  * , то выполняем следующие действия: снимаем со стека a, снимаем со стека b  и  кладём на стек  b * a.

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

Постфиксную запись, рассчитанную на обработку посредством стека, будем называть s-постфиксной, а рассчитанную на обработку очередью — q-постфиксной.

Две записи «вычислятся одинаково» в том и только в том случае, когда соответствующие им деревья синтаксического разбора (англ.: parse tree, далее — ДСР) одинаковы. Идея приведённого ниже алгоритма состоит примерно в следующем: на основе s-постфиксной записи строим ДСР, обходя которое специальным образом, получаем q-постфиксную запись. Нужно обходить дерево по уровням справа налево (под уровнем дерева подразумевается множество всех вершин дерева, равноудалённых от корня; уровни дерева естественным образом нумеруются: корень расположен на уровне 0 и так далее). В приведённом ниже коде функция  get_levels  генерирует уровни ДСР на основе s-постфиксной нотации в виде вектора строк, k-ая компонента которого соответствует k-му уровню ДСР заданной строки, вершины которого (если таковые имеются) перечислены справа налево. Поскольку у ДСР может быть не больше уровней, чем символов в строке, то создаём вектор как раз с таким числом компонент и инициализируем его компоненты пустыми строками.

Корректность функции get_levels можно доказать индукцией по длине строки, отметим, что если строка содержит более одного элемента, то она имеет вид ФGО, где Ф и G — правильные строки, О — символ оператора. Запустить рекурсивно функцию с предпоследней позиции — всё равно, что применить её к строке G. ДСР этой строки является левым поддеревом для ДСР исходной строки и k-ый уровень этого дерева является (k+1)-ым уровнем ДСР исходной строки (именно поэтому вызываем функцию с параметром depth на 1 больше). По индукционному предположению, дойдя до начала строки G, функция корректно «расставит» уровни ДСР этой строки (с учётом + 1) и завершит свою работу.  Аналогично будут правильно расставлены уровни ДСР строки Ф, которое является правым поддеревом исходной строки. Таким образом, все вершины ДСР исходной строки будут правильно расставлены, а поскольку рекурсия вызывается сначала для левого, а потом для правого её поддерева, то и перечислены вершины на каждом уровне будут справа налево.

 

Код на С++

Ссылка на программу в ideone.