e-olymp 972. Сортировка времени

Задача

Отсортируйте время согласно заданному критерию

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

Сначала задано число $n\, \left ( 1\leqslant n\leqslant 100 \right )$, а затем n моментов времени. Каждый момент времени задается 3 целыми числами — часы (от 0 до 23), минуты (от 0 до 60) и секунды (от 0 до 60)

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

Выведите моменты времени, упорядоченные в порядке неубывания (момент времени также выводится в виде трех чисел, ведущие нули выводить не нужно)

Тесты

Входные данные Выходные данные
1 [latex]\begin{matrix}
4 & & \\
10 &20 &30 \\
7 &30 &00 \\
23&59 &59 \\
13&30 &30
\end{matrix}[/latex]
[latex]\begin{matrix}
7 & 30 &00 \\
10&20 &30 \\
13&30 &30 \\
23& 59 & 59
\end{matrix}[/latex]
2 $\begin{matrix}
6\\
12 &55 &59 \\
8 &33 &34 \\
6 &56 &46 \\
10 &23 &52 \\
3 &20 &00 \\
19 &31 &0\\
10&23&52
\end{matrix}$
$\begin{matrix}
3 &20 &0 \\
6 &56 &46 \\
8 &33 &34 \\
10 &23 &52 \\
12 &55 &59 \\
19 &31 &0
\end{matrix}$

Решение

Создадим 4 массива где мы будем хранить время(отдельно часы, минуты, секунды), а также четвертый в котором мы будем хранить все время в одной удобной для нас единице измерения — секундах. Читаем поток ввода и переводим полученные данные, сравниваем их потом сортируем полученные результаты и выводим ответ.

Ссылки

e-olymp
ideone

e-olymp 972. Сортировка времени

Задача

Отсортируйте время согласно заданному критерию.

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

Сначала задано число $n$ $\left(1 \leqslant n \leqslant 100 \right),$ а затем $n$ моментов времени. Каждый момент времени задается $3$ целыми числами — часы (от $0$ до $23$), минуты (от $0$ до $60$), и секунды (от $0$ до $60$).

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

Выведите моменты времени, упорядоченные в порядке неубывания (момент времени также выводится в виде трех чисел, ведущие нули выводить не нужно).

Тесты

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

1

4
10 20 30
7 30 00
23 59 59
13 30 30
7 30 0
10 20 30
13 30 30
23 59 59

2

5
12 40 45
23 56 12
7 45 34
8 23 34
2 56 45
2 56 45
7 45 34
8 23 34
12 40 45
23 56 12

3

3
23 56 45
21 45 54
6 45 23
6 45 23
21 45 54
23 56 45

Код 1

Код 2

Решение задачи (код 1)

Для решения задачи переведём в секунды каждый момент времени и введём их в массив d[i]. Далее, в этом массиве проверяем какой элемент больше if (d[i] > d[j]) и упорядочиваем эти элементы в порядке возрастания используя swap().

Решение задачи (код 2)

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

Ссылки

  • Условие задачи на e-olymp
  • Код программы (1) на ideone
  • Код программы (2) на ideone

e-olymp 8688. Количество чисел без 8

Задача

Напишите программу, которая определяет количество чисел от $1$ до $n$, в записи которых нет цифры $8$.

Входные данные:
В первой строке задано число $n$ $(1 \le n \le 10^{18})$.

Выходные данные:
Выведите одно число — количество чисел от $1$ до $n$, в записи которых нет цифры $8$.

Тесты

Входные данные Вывод программы
10 9
25833798135522720 4918510377816614
88888888888888 20334926626631

Continue reading

e-olymp 4749. Выручка театра

Задача

В театре [latex]n[/latex] рядов по [latex]m[/latex] мест в каждом. Даны две матрицы — в первой записаны стоимости билетов. Вторая сообщает, какие билеты проданы, а какие — нет ([latex]1[/latex] — соответствующий билет продан, [latex]0[/latex] — не продан).
Определите общую выручку от спектакля.

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

Сначала записано число [latex]n[/latex], затем число [latex]m[/latex] ([latex]n[/latex], [latex]m \leqslant 500[/latex]). После задана матрица стоимостей билетов ([latex]n[/latex] строк по [latex]m[/latex] чисел, каждое из чисел от [latex]0[/latex] до [latex]10000[/latex]). Далее задана матрица проданных билетов — снова [latex]n[/latex] строк по [latex]m[/latex] чисел.

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

Выведите общую выручку от продажи билетов.

Тесты

Входные данные Выходные данные
1 3 3 25
1 2 3
4 5 6
7 8 9
1 0 1
0 1 0
1 0 1
2 2 2 0
1 1
2 2
0 0
0 0
3 4 5 380
15 16 17 18 19
19 18 17 16 15
19 20 21 22 23
23 22 21 20 19
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1

Код программы с использованием одномерных массивов

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

Описываем целочисленный одномерный массив x [500*500] для хранения матрицы стоимостей билетов. Описываем целочисленные переменные [latex]n[/latex] и [latex]m[/latex] (количество строк и столбцов матрицы) и считываем их. Описываем целочисленную переменную [latex]nm[/latex] (количество мест в зале) и инициализируем ее произведением [latex]n \cdot m[/latex]. Цикл инициализирует [latex]nm[/latex] элементов массива [latex]x[/latex]. Описываем целочисленную переменную [latex]k[/latex], которая принимает значения [latex]0[/latex] или [latex]1[/latex] (билет не продан или продан), и целочисленную переменную [latex]v[/latex] — стоимость проданных билетов ([latex]v[/latex] имеет тип long long int, так как максимальное значение, которое она может принять, составляет [latex]500 \cdot 500 \cdot 10000=2500000000[/latex]). Цикл считывает значения [latex]k[/latex] и увеличивает [latex]v[/latex] на k*x[i].

Код программы с использованием многомерных массивов

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

По условию заданы количество строк [latex]n[/latex] и количество столбцов [latex]m[/latex] матрицы стоимости театральных билетов ( [latex] n,m\leqslant 500[/latex], каждое из чисел от [latex]0[/latex] до [latex]10000[/latex] ). Описываем целочисленную матрицу x[500][500]. Объявляем целочисленные переменные [latex]n[/latex] и [latex]m[/latex] и вводим их значения с клавиатуры. Считываем матрицу x. Объявляем переменную unsigned long long v = 0 — стоимость проданных билетов. Целочисленная переменная [latex]p = 1[/latex], если билет на ( [latex]i,j[/latex] )-е место продан, и [latex]p = 0[/latex] — в противном случае. Во вложенных циклах считываем значение [latex]p[/latex] из матрицы проданных билетов. Проверяем [latex]p[/latex] на положительность и увеличиваем [latex]v[/latex] на стоимость билета на ( [latex]i,j[/latex] )-е место.

Ссылки

e-olymp
ideone (код с одномерными массивами)
ideone (код с многомерными массивами)

e-olymp 8530. Печать матрицы

Задача

Условие

Задана матрица $n \cdot n$ — назовем ее $[1..n] \cdot [1..n]$ массивом. Для заданных $r$ и $c$ следует вывести $[1..r] \cdot [1..c]$ массив ($r$ строк и $c$ столбцов исходного массива).

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

Первая строка содержит число $n (1 \leq n \leq 100)$. Следующие строки содержат матрицу $n \cdot n$. Последняя строка содержит два числа $r$ и $c$ $(1 \leq r, c \leq n)$. Все числа в матрице не превышают по модулю $100$.

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

Выведите матрицу $r \cdot c$.

Тесты

Входные данные Выходные данные
1 4
1 2 3 4
5 6 7 8
9 1 2 3
4 5 6 7
3 2
1 2
5 6
9 1
2 5
18 25 34 44 -43
54 65 75 85 -32
95 15 25 35 -3
-4 15 -6 37 0
44 43 23 3 -12
4 3
18 25 34
54 65 75
95 15 25
-4 15 -6
3 2
0 -1
23 69
1 1
0
4 3
1 2 3
-4 -5 -6
7 8 9
3 1
1
-4
7

Решение

Для решения данной задачи необходимо ввести в массив все имеющиеся данные и вывести необходимые, соответственно заданным параметрам. Можно использовать как одномерные массивы, так и двухмерные.
В реализации с одномерными вводим все данные в массив $n \cdot n$, а затем выводим, используя вложенные циклы. Цикл проходит от $0$ до $r$ и от $(j \cdot n)$ — первого элемент необходимой строки до $(c + j \cdot n)$ — последнего элемента. В реализации с двумерными массивами заводим все данные в один массив и после выводим необходимые.

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

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

Ссылки

e-olymp 7368. Средний балл для фигуристов

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

Задача

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

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

В первой строке находятся два целых числа: количество судей [latex]n[/latex] и количество спортсменов [latex]m[/latex]. В следующих [latex]m[/latex] строках находятся [latex]n[/latex] целых чисел – оценки всех судей[latex]\left( 0 \lt n \leqslant 10, 0 \lt m \leqslant 100 \right)[/latex] для каждого из фигуристов.

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

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

Тесты

#   ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 5 4
7 8 9 8 10
6 5 5 4 7
9 9 10 7 7
7 7 10 9 8
8.33 5.33 9.00 8.50
2 3 4
1 2 3
3 5 2
7 1 6
9 8 3
2.00 3.00 6.00 8.00
3 10 2
1 2 3 4 5 6 7 8 9 10
1 1 1 2 2 2 3 3 3 4
5.50 2.50

Код программы (Потоковая обработка)

Решение

Читая каждую оценку:

  1. Добавляем оценку к общей сумме;
  2. Если введенная оценка равна минимальной, то добавляем ее к сумме минимальных и увеличиваем счётчик количества минимальных.
  3. Если введенная оценка меньше минимальной, то минимальной становится введённая оценка. Счетчик количества минимальных равен [latex]1.[/latex] Сумма минимальных равна введённой оценке.
  4. Если введенная оценка равна максимальной, то добавляем ее к сумме максимальных и увеличиваем счётчик количества максимальных.
  5. Если введенная оценка больше максимальной, то максимальной становится введённая оценка. Счетчик количества максимальных равен [latex]1.[/latex] Сумма максимальных равна введённой оценке.

Тогда после введения всех [latex]n[/latex] оценок имеем:

  •  [latex]sumMax[/latex] — сумма максимальных оценок.
  •  [latex]sumMin[/latex] — сумма минимальных оценок.
  •  [latex]countMax[/latex] — количество максимальных оценок.
  •  [latex]countMin[/latex] — количество минимальных оценок.
  •  [latex]sumGl[/latex] — общая сумма оценок.

Для нахождения среднего арифметического значения оценок, соответствующего условию будем применять формулу:  [latex]S_с = \frac{sumGL-sumMin-sumMax}{n-countMin-countMax}[/latex]

Код программы (Массивы)

Решение

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

Ссылки

Условие задачи на e-olymp

Код программы на ideone (Потоковая обработка)

Код программы на ideone (Массивы)

e-olymp 458. Черно-белая графика

Задача

Одна из базовых задач компьютерной графики – обработка черно-белых изображений. Изображения можно представить в виде прямоугольников шириной $w$ и высотой $h,$ разбитых на $w × h$ единичных квадратов, каждый из которых имеет либо белый, либо черный цвет. Такие единичные квадраты называются пикселами. В памяти компьютера сами изображения хранятся в виде прямоугольных таблиц, содержащих нули и единицы.

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

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

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

Первая строка содержит два целых числа $w$ и $h$ $(1 \leq w, h \leq 100).$ Последующие $h$ строк описывают первое изображение и каждая из этих строк содержит $w$ символов, каждый из которых равен нулю или единице. Далее следует описание второго изображения в аналогичном формате. Последняя строка содержит описание логической операции в виде четырех чисел, каждое из которых – ноль или единица. Первое из них есть результат применения логической операции в случае, если оба аргумента нули, второе – результат в случае, если первый аргумент ноль, второй единица, третье – результат в случае если первый аргумент единица, второй ноль, а четвертый – в случае, если оба аргумента единицы.

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

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

Тесты

Входные данные Выходные данные
 1 5 3
01000
11110
01000
10110
00010
10110
0110
11110
11100
11110
2 2 3
010
111
000
101
1010
11
10
10
3 4 4
1111
0101
0000
1110
0011
0101
0111
1111
0011
1111
0101
0000
1110
4 3 6
100011
000111
000000
111011
001100
010101
1000
000
100
110
000
101
010

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

( использован одномерный массив)

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

(использован двумерный массив)

Решение

Объявляем два булевых динамических массива под две пиксельные таблицы и один статический для таблицы истинности, вводим входные данные. Затем поочерёдно сравниваем соответствующие элементы массивов с помощью функции my_operation, которая принимает две переменные a и b булевского типа и булев массив res с таблицей истинности, и возвращает соответствующее значение из таблицы для комбинации значений a и b. Результат сравнения выводим.

Ссылки

Анаграммы

Анаграммы

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

После того как он закончил выписывать все перестановки Игорь устал и пошел учиться. Он взял словарь и начал учить новые слова. Через некоторое время Игорь заметил что некоторые из слов в словаре совпадают с записанными им перестановками на листке и задался вопросом, — а какие можно получить слова переставляя буквы из других в словаре.

Игоря будут интересовать только слова которые записаны в словаре, так как других он не знает.

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

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

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

Задан словарь английских слов. Каждое слово в новой строке. Длинна слова не более $255$ символов. Количество слов любое.

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

Вывести все слова что имеют максимальное количество анаграмм в нем.

Решение

Прочитаем словарь. Запишем в структуру pair строку с исходным словом в first и отсортированную в second. Анаграммами будут являться слова с одинаковыми second строками. Так как они будут состоять из одних и тех же букв, которые выстроены в одинаковом порядке. Отсортируем множество слов из словаря по second. Таким образом все слова анаграммы будут находиться рядом.

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

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

Тесты

Ввод Вывод
 

1

 

2500 слов английского языка

trace react crate

dear dare read

post stop spot

Код

Код на ideone

e-olymp 54. Мурзик

Задача

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

Одной ночью ему приснилось, что он судья на математических соревнованиях крыс (да, в наш век цифровых технологий даже крысы не остаются за гранью научно-технического прогресса). Соревнования проводятся среди [latex]N[/latex] команд по [latex]K[/latex] крыс в каждой. Соревнования проводятся в [latex]К[/latex] раундов, в каждом из которых представитель команды называет число. Побеждает та команда, у которой произведение всех чисел наибольшее. Почему крысы не называют каждый раз максимально возможное число? На то они и крысы, что в отличии от Мурзика, обделены интеллектом. Но и Мурзик понимает, что сам подсчитать результат не сможет из-за недостачи математических способностей и поэтому просит вашей помощи.

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

Первая строка содержит два целых числа [latex]N[/latex] и [latex]K[/latex] [latex](0 < N ≤ 20, 0 < K ≤ 100000)[/latex]. Следующие [latex]K[/latex] строк содержат по N чисел, которые называют представители команд. Причем крысы, как представители образованного вида, знают только 32-битовые знаковые числа.

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

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

Тесты

# Входные данные Выходные данные
1 3 3
20 10 30
15 20 20
30 30 20
3
2 3 3
20 -10 -30
15 25 20
30 -30 20
1
1 3 3
0 -10 -30
15 25 20
30 -30 20
2

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

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

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

Ссылки

Ссылка на e-olymp
Ссылка на ideone

e-olymp 1482. Умножение матриц

Задача

Пусть даны две прямоугольные матрицы $A$ и $B$ размерности $m \times n$ и $n \times q$ соответственно:
$$A = \begin{bmatrix} a_{11} & a_{12} & \ldots & a_{1n} \\ a_{21} & a_{22} & \ldots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \ldots & a_{mn} \end{bmatrix} \; , \; B = \begin{bmatrix} b_{11} & b_{12} & \ldots & b_{1q} \\ b_{21} & b_{22} & \ldots & b_{2q} \\ \vdots & \vdots & \ddots & \vdots \\ b_{n1} & b_{n2} & \ldots & b_{nq} \end{bmatrix} .$$
Тогда матрица $C$ размерностью $m \times q$ называется их произведением:
$$C = \begin{bmatrix} c_{11} & c_{12} & \ldots & c_{1q} \\ c_{21} & c_{22} & \ldots & c_{2q} \\ \vdots & \vdots & \ddots & \vdots \\ c_{m1} & c_{m2} & \ldots & c_{mq} \end{bmatrix} ,$$
где: $$c_{i,j} = \sum_{r=1}^{n} a_{i,r}b_{r,j} \; \left(i = 1, 2, \ldots m; j = 1, 2, \ldots q\right).$$
Операция умножения двух матриц выполнима только в том случае, если число столбцов в первом сомножителе равно числу строк во втором; в этом случае говорят, что форма матриц согласована.

Задано две матрицы $A$ и $B$. Найти их произведение.

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

В первой строке задано $2$ натуральных числа $n_a$ и $m_a$ – размерность матрицы $A$. В последующих $n_a$ строках задано по $m_a$ чисел – элементы $a_{ij}$ матрицы $A$. В $\left(n_a + 2\right)$-й строке задано $2$ натуральных числа $n_b$ и $m_b$ – размерность матрицы $B$. В последующих $n_b$ строках задано по $m_b$ чисел – элементы $b_{ij}$ матрицы $B$. Размерность матриц не превышает $100 \times 100$, все элементы матриц целые числа, не превышающие по модулю $100$.

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

В первой строке вывести размерность итоговой матрицы $C$: $n_с$ и $m_c$. В последующих $n_с$ строках вывести через пробел по $m_c$ чисел – соответствующие элементы $c_{ij}$ матрицы $C$. Если умножать матрицы нельзя — в первой и единственной строке вывести число $\; -1$.

Тесты

Входные данные Выходные данные
2 3
1 3 4
5 -2 3
3 3
1 3 2
2 1 3
0 -1 1
2 3
7 2 15
1 10 7
3 3
1 5 3
2 6 1
7 -1 -3
3 2
3 6
-1 1
3 1
3 2
7 14
3 19
13 38
4 4
4 8 -18 16
3 7 14 -42
2 1 1 7
4 9 5 -2
4 4
1 0 0 0
0 1 0 0
0 0 1 0
4 4
4 8 -18 16
3 7 14 -42
2 1 1 7
4 9 5 -2
3 3
5 7 -1
8 9 3
0 -6 17
2 3
7 -15 1
8 8 2
-1
2 3
57 -49 31
89 11 -37
3 1
19
-19
0
2 1
2014
1482

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

 

Решение

Для начала, считываем данные матрицы $A$ из входного потока и записываем их в двумерный динамический массив. Далее, получив данные о размерности второй матрицы, мы можем определить, выполнима ли операция умножения, и если нет, то прервать выполнение программы. Если операция умножения данных матриц выполнима, то считываем и записываем данные второй матрицы, после чего, по приведённой выше формуле вычисляем произведение матриц $C = A \times B.$ Наконец, выводим полученную матрицу $C.$

Ссылки

Условие задачи на e-olymp
Код задачи на ideone
Умножение матриц на Wikipedia

e-olymp 2669. Поворот

Поворот

Дан массив [latex]n[/latex] × [latex]m[/latex]. Требуется повернуть его по часовой стрелке на [latex]90[/latex] градусов.

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

В первой строке даны натуральные числа [latex]n[/latex] и [latex]m[/latex] [latex](1 ≤ n, m ≤ 50)[/latex]. На следующих [latex]n[/latex] строках записано по [latex]m[/latex] неотрицательных чисел, не превышающих [latex]109[/latex] — сам массив.

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

Выведите перевернутый массив в формате входных данных.

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 2 2

1 2

3 4

2 2

3 1

4 2

2 3 3

1 2 3

4 5 6

7 8 9

3 3

4 7 1

8 5 2

9 6 3

3 3 4

4 5 7 8

3 6 8 7

2 2 4 5

4 3

2 3 4

2 6 5

4 8 7

5 7 8

4 1 2

5 4

2 1

5

4

5 1 1

2

1 1

2

 

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

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

e-olymp 930. Номер мобильного телефона

Задача

Задан номер мобильного телефона. Определить, какие цифры отсутствуют в этом номере.

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

В единственной строке задан номер мобильного телефона.

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

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

Тесты

Входные данные Выходные данные
0631562976 2
4 8
2139087 3
4 5 6
1111111111 9
0 2 3 4 5 6 7 8 9
7 9
0 1 2 3 4 5 6 8 9
4848 8
0 1 2 3 5 6 7 9
0921234567 1
8
6723545 4
0 1 8 9
9867453210 0
 

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

Решение

Объявим массив на $10$ элементов, в котором будем хранить количество вхождений каждой цифры в номер телефона. Далее, посимвольно читаем входной поток и увеличиваем соответствующие каждой цифре элементы массива на $1$. После этого, находим количество нулевых элементов массива — это будет количество цифр, которые отсутствуют в номере. Наконец, выводим индексы нулевых элементов массива.

Ссылки

Условия задачи на e-olymp
Код задачи на ideone

e-olymp 2261. Защита королевства

Защита королевства

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

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

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

Первая строка содержит три целых числа: [latex]w[/latex] — ширина сетки, [latex]h[/latex] — высота сетки и [latex]n[/latex] — количество арбалетных башен [latex](1 ≤ w, h ≤ 40000; 0 ≤ n ≤ min(w, h))[/latex].

Каждая из следующих n строк содержит два целых числа [latex]x_i[/latex] и [latex] y_i[/latex] — координаты клетки с башней [latex](1 ≤ x_i ≤ w; 1 ≤ y_i ≤ h)[/latex].

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

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

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 10 10 3

1 1

2 2

3 3

49
2 15 15 4

4 4

5 5

7 8

13 15

30
3 30 30 5

13 14

16 27

29 30

5 5

10 15

132
4 100 100 2

1 1

100 100

9604
5 3 3 3

1 1

2 2

3 3

0

 

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

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

Алгоритм решения задачи состоит в том, чтобы найти максимальное количество незащищенных клеток между соседними башнями по координатам абсцисс и ординат (которые будет на [latex]1[/latex] меньше чем сама разность координат) и перемножить полученные числа тем самым найдя площадь образованного ими прямоугольника.

Для решения данной задачи нужно создать два массива в [latex]x[/latex] и [latex]y[/latex] (в первом будут находится [latex]x_i[/latex] координаты, а во втором [latex]y_i[/latex]) размера на [latex]2[/latex] больше чем количество заданных башен, так как нужно учитывать рамки поля, для чего достаточно добавить две башни c координатами [latex]\left(0;0\right)[/latex] и [latex]\left(x_{max}+1; y_{max}+1\right).[/latex]  Далее нужно отсортировать эти массивы и найти максимальную разность между соседними элементами ([latex]a[/latex] — максимальная разность между [latex]x_i[/latex] элементами, [latex]b[/latex] — максимальная разность между [latex]y_i[/latex]). Далее, по формуле [latex]\left(a-1\right)\cdot\left(b-1\right)[/latex] находим площадь самого большого незащищенного прямоугольника, которая равна количеству клеток в нем, что и является ответом задачи.

 

e-olymp 239. Треугольники

Задача

На плоскости задано [latex]n[/latex] точек с целочисленными координатами. Никакие три точки не лежат на одной прямой. Определить [latex]k[/latex] — количество треугольников с вершинами в заданных точках и целочисленной площадью.

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

В первой строке содержится число [latex]n[/latex]. В последующих [latex]n[/latex] строках содержаться пары целых чисел — координаты очередной точки [latex](x_i, y_i)[/latex]. Известно, что [latex]0 < n, |x_i|,|y_i| \leq 5000 [/latex].

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

Искомое число [latex]k[/latex].

Тесты

Входные данные Выходные данные
5
2 -1
3 0
0 4
-3 0
-2 1
6
5
0 0
2 4
6 6
10 34
-42 -48
10
4
0 0
0 1
1 0
1 1
0
8
0 0
2 2
1 1
3 3
0 1
2 1
1 0
1 2
24
5
0 0
0 1
-1 0
-1 -1
3 -3
3

 

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

Учитывая теорему Пика, получаем, что площадь каждого из треугольников, которые можно составить, либо равна целому числу, либо помимо целой части содержит [latex]\frac{1}{2}[/latex].  Нас интересует лишь четность псевдоскалярного(косого) произведения. Берем у всех координат остаток от деления на [latex]2[/latex]. Получаем не более [latex]4[/latex] различных точек: [latex] (0;0), (0;1), (1;0), (1;1)[/latex]. Составляем все возможные треугольники из полученных точек, и считаем те, у которых формула дает четное число, учитывая количество координат каждого типа.

Ссылки

Условие задачи на сайте  E-Olymp

код задачи на Ideone

описание теоремы Пика на Wikipedia

описание псевдоскалярного произведения на Wikipedia

e-olymp 922. Сдвинь элементы

Условие задачи
Задан массив целых чисел длины [latex]n[/latex]. Сдвинуть элементы массива вправо циклически на [latex]1[/latex] шаг.

Входные данные
В первой строке задано количество элементов массива [latex]n[/latex] [latex](n ≤ 100)[/latex]. Во второй строке заданы сами элементы массива, значение каждого из которых по модулю не превышает [latex]100[/latex].

Выходные данные
В одной строке вывести [latex]n[/latex] чисел — новые значения элементов массива.

Continue reading

e-olymp 1494. Санта Клаус

Задача

Санта Клаус

Санта Клаус

Санта Клаус готовится к Рождеству. В этот праздник он хочет вручить подарки [latex]n[/latex] детям. Его помощники Эльфы уже собрали два мешка, с которыми он отправится в новогоднее путешествие по всем странам мира. И чтобы Санта не запутался, Эльфы составили список детей, чьи подарки уже лежат в каждом из мешков. Санта хочет помочь Эльфам, и поэтому решил положить в третий мешок подарки для тех детей, которым они еще не подготовлены.

Помогите Санте, составьте список детей, чьи подарки надо положить в третий мешок.

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

Первая строка входного файла содержит три целых числа: [latex]n[/latex] — число детей, [latex]m[/latex] и [latex]k[/latex] — число подарков в первом и втором мешке соответственно [latex](1\leq n,\;m,\;k\leq 100;m+k\leq n)[/latex]. Вторая строка входного файла содержит [latex]m[/latex] целых чисел — номера детей, подарки для которых лежат в первом мешке. Третья строка входного файла содержит [latex]k[/latex] целых чисел — номера детей, подарки для которых лежат во втором мешке.

Гарантируется что Эльфы положили для каждого ребенка не более одного подарка. Номера всех детей являются целыми положительными числами не превосходящими [latex]n[/latex]. Все дети должны получить подарок на Рождество, иначе Санта расстроится.

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

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

Тесты

Входные данные Выходные данные
2 1 1
2
1
0
3 1 2
1
2 3
0
7 2 1
7 3
1
4
2 4 5 6
100 14 4
2 93 30 56 17 19 75 22 23 5 49 11 8 33
91 40 81 54
82
1 3 4 6 7 9 10 12 13 14 15 16 18 20 21 24 25 26 27 28 29 31 32 34 35 36 37 38 39 41 42 43 44 45 46 47 48 50 51 52 53 55 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 76 77 78 79 80 82 83 84 85 86 87 88 89 90 92 94 95 96 97 98 99 100
10 3 5
2 5 8
3 7 1 4 9
2
6 10
61 40 5
61 20 5
3 4 9 8 49 31 20 33 35 34 61 1 32 53 51 7 21 44 46 47
2 60 50 19 25
36
5 6 10 11 12 13 14 15 16 17 18 22 23 24 26 27 28 29 30 36 37 38 39 40 41 42 43 45 48 52 54 55 56 57 58 59
12 3 3
1 2 3
11 10 8
6
4 5 6 7 9 12

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

Решение

Создадим массив типа  bool , в котором каждому [latex]i[/latex]-ому ребёнку соответствует элемент с индексом [latex]i — 1[/latex], принимающий значение [latex]0[/latex], если для ребёнка ещё нет подарка, и [latex]1[/latex], если подарок уже имеется в одном из мешков. Далее, отмечаем детей, подарки для которых уже лежат в мешках. Наконец, выводим номера тех детей, подарки для которых не были найдены ни в одном из мешков.

Ссылки

Условия задачи на e-olymp
Код задачи на ideone

e-olymp 7492. Будильник

Задача

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

Часы Алисы содержат четыре цифры: две для часов и две для минут. Например, часы ниже показывают [latex]9[/latex]:[latex]30[/latex] (ведущий ноль высвечивается).

Часы имеют следующее представление цифр:

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

Одно целое число [latex]n (0≤ n ≤30)[/latex] — количество подсвеченных сегментов на часах Алисы во сне.

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

Вывести пять символов в формате [latex]hh:mm[/latex] — время, показываемое часами Алисы во сне. Время должно быть корректным: [latex]0 ≤ hh < 24[/latex] and [latex]0 ≤ mm < 60[/latex]. Если существует несколько решений, то вывести любое. Если решения не существует, то вывести [latex]Impossible[/latex].

Тесты

Входные данные Выходные данные
23 00:02
28 Impossible
0 Impossible
15 01:12

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

Решение

Перебираем i и j (от 0 до 24 и 60 соответственно). a=seg[i/10] (для десятков) и a=seg[i%10] (для остальных чисел) то же самое делаем для j. Тем самым, мы перебираем все возможные варианты количества сегментов. Если a==n (количество сегментов) при переборе и в входных данных совпадает, то выводим наше время и выходим из цикла. Если же при переборе не было такого же числа сегментов, как в входных данных, то решения нет и мы, соответственно, выводим [latex]Impossible[/latex].

Ссылки

e-olymp
Ideone

e-olymp 179. Распределение

Распределение

Для нападения на некоторые поселения людей, эльфов и карликов вождь Орды Оргрим Думхаммер сформировал из всех имеющих в наличии воинов [latex]N[/latex] различных отрядов, которые были отправлены на завоевания. Однако прибывшие лишь только сейчас разведчики донесли о силах противников, скопленных в этих поселениях, что естественно скорректировало планы Оргрима. И теперь он хочет произвести перераспределение войск по отрядам, переводя воинов из одного отряда в другой. При этом, чтобы не создавать неразбериху в рядах своей армии и выполнить перераспределение как можно быстрее, количество таких переводов должно быть минимально возможным (за один раз переводится один солдат из некоторого отряда в другой).

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

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

Первая строка входного файла содержит целое число [latex]N[/latex] [latex](1 ≤ N ≤ 10000)[/latex] – количество отрядов. Вторая строка содержит изначальное распределение воинов по отрядам – [latex]N[/latex] чисел, каждое из которых определяет количество воинов в соответствующем отряде. А в третьей строке – требуемое распределение солдат. Количество солдат в одном отряде не превышает [latex]10^6[/latex]. Гарантируется, что общее число воинов в изначальном распределении и требуемом совпадает.

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

В выходной файл выведите минимально возможное количество переводов.

Тесты

ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
2
4 2
5 1
1
1
4
4
0
3
2 2 2
4 1 1
2
3
6 3 1
0 0 10
9

 

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

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

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

Ссылки

• Задача на e-olymp.

• Решение на сайте ideone.

e-olymp 595. Новый Лабиринт Амбера

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

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

Как-то Корвину – принцу Амбера, по каким-то важным делам срочно понадобилось попасть в самую далекую тень, которую он только знал. Как всем известно, самый быстрый способ путешествия для принцев Амбера – это Лабиринт Амбера. Но у Корвина были настолько важные дела, что он не хотел тратить время на спуск в подземелье (именно там находится Амберский Лабиринт). Поэтому он решил воспользоваться Новым Лабиринтом, который нарисовал Дворкин. Но этот Лабиринт не так прост, как кажется…

Новый Лабиринт имеет вид последовательных ячеек, идущих друг за другом, пронумерованных от [latex]1[/latex] до [latex]N[/latex]. Из ячейки под номером [latex]i[/latex] можно попасть в ячейки под номерами [latex]i+2[/latex] (если [latex]i+2 ≤ N[/latex]) и [latex]i+3[/latex] (если [latex]i+3 ≤ N[/latex]). На каждой ячейке лежит какое-то количество золотых монет [latex]{ k }_{ i }[/latex]. Для того чтобы пройти лабиринт нужно, начиная ходить из-за границ лабиринта (с нулевой ячейки) продвигаться по выше описанным правилам, при этом подбирая все монетки на ячейках, на которых вы делаете промежуточные остановки. Конечная цель путешествия – попасть на ячейку с номером [latex]N[/latex]. Дальнейшее путешествие (в любое место Вселенной) возможно лишь тогда, когда достигнув ячейки с номером [latex]N[/latex], вы соберете максимально количество монеток. Напишите программу, которая поможет Корвину узнать, какое максимальное количество монеток можно собрать, проходя Новый Лабиринт Амбера.

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

В первой строке входного файла содержится натуральное число [latex]N (2 ≤ N ≤ 100000)[/latex], а во второй [latex]N[/latex] целых чисел, разделенных одним пробелом, [latex]{ k }_{ i }[/latex] – количество монеток, лежащих в ячейке с номером [latex]i[/latex] [latex](0 ≤ i ≤ 1000)[/latex].

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

В выходной файл вывести одно целое число – максимальное количество монеток, которое можно собрать, проходя лабиринт.

Тесты

Входные данные Выходные данные
1 5
1000 2 3 1 3
6
2 2
1 2
2
3 4
1 3 100 0
3

Решение с использованием цикла

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

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

Описание

Для хранения количества монет в каждой ячейке лабиринта используем массив [latex]dp[/latex] длиной [latex]n+1[/latex] элементов. При этом каждой ячейке лабиринта соответствует ячейка массива с тем же индексом, а нулевой элемент массива понимаем как точку перед входом в лабиринт. В цикле считываем количество монет в каждой ячейке, после чего обнуляем значение нулевого элемента массива, поскольку ячейка, соответствующая ему, находится вне лабиринта, и первого, поскольку в ячейку, соответствующую ему, невозможно попасть никаким образом. Далее в цикле для каждой ячейки лабиринта находим, какое максимальное количество монет может быть у Корвина после её посещения. В ячейку с номером [latex]i[/latex] он может попасть или из ячейки с номером [latex]i-2[/latex], или из ячейки с номером [latex]i-3[/latex]. При этом он несёт с собой все собранные ранее монеты, и добавляет к ним те, что находятся в данной ячейке. Таким образом, формула для нахождения максимального количества монет после посещения [latex]i[/latex]-й ячейки имеет вид [latex]dp[i] = dp[i] + max(dp[i-2], dp[i-3])[/latex], и ответ к задаче хранится в [latex]n[/latex]-й ячейке массива. Дополнительно требуется проводить проверку на выход за границы массива.

Код на ideone.com.

Решение с использованием рекурсивной функции

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

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

Описание

В данном случае используется функция [latex]f[/latex], принимающая номер ячейки массива и возвращающая максимальное количество монет после посещения ячейки с этим номером. Сначала объявляются два глобальных массива:
[latex]dp[/latex], в [latex]i[/latex]-й ячейке которого изначально хранится количество монет в [latex]i[/latex]-й ячейке лабиринта, и [latex]used[/latex], элементы которого принимают значения [latex]0[/latex] или [latex]1[/latex] (значение [latex]0[/latex] в [latex]i[/latex]-й ячейке означает, что максимальное количество монет после посещения
ячейки лабиринта с тем же номером рассчитано ещё не было). Далее всё происходит как в решении с использованием цикла, но одновременно с чтением входных данных обнуляются элементы [latex]used[/latex], а вместо второго цикла происходит вызов функции [latex]f[/latex]. Сама же функция [latex]f[/latex], если значение параметра меньше двух, возвращает [latex]0[/latex], а иначе, если этого не было сделано ранее, вычисляет максимальное количество монет после посещения ячейки с номером [latex]i[/latex] по формуле [latex]dp[i] = dp[i] + max(dp[i-2], dp[i-3])[/latex] и возвращает его.

Код на ideone.com.
Кроме того, об идее решения данной задачи можно почитать здесь.

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

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

Обобщённое условие задач на дерево отрезков, как правило, выглядит так:
«Пусть дан моноид [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], если новый размер базы превысил вместимость дерева или является меньше, чем старый, и константа в противном случае.

Ссылки