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 695. Range Variation Query

Условие

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

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

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

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

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

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

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

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

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

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

Тесты

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

Код

Решение

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

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

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

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

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

Ссылки

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

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

Условие

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

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

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

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

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

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

Тесты

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

Алгоритм

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

Код

Ссылки

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

AL15. Лабиринт

Условие

Матрица размера [latex]n*m[/latex] определяет некоторый лабиринт. B матрице элемент [latex]1[/latex] обозначает стену, а [latex]0[/latex] определяет свободное место. В первой строке матрицы определяются входы [latex]x_i[/latex], а в последней выходы [latex]y_i[/latex], [latex]i = 1, \ldots, k[/latex], [latex]k \leq n[/latex] которые должны быть нулевыми элементами.

Необходимо определить, можно ли:

а) провести [latex]k[/latex] человек от входа [latex]x_i[/latex] до выхода [latex]y_i[/latex] соответственно, [latex]i = 1, \ldots, k[/latex], таким образом, чтобы каждое свободное место посещалось не более одного раза.

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

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

Числа [latex]n[/latex] и [latex]m[/latex] определяющие кол-во строк и столбцов соответственно, [latex]1 \leq n, m \leq 10^4[/latex]. Количество входов [latex]k[/latex]  равно кол-ву выходов, [latex]1 \leq k \leq min(1000, n)[/latex]. Число [latex]k[/latex] не является частью входных данных (не подается на вход программы).

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

[latex]YES[/latex], если соответствующий набор маршрутов существует, [latex]NO[/latex] — в противном случае.

Замечания

  1. Легко заметить, что случай б) эквивалентен случаю а). Предположим, что [latex]k > 1[/latex] и мы провели первых [latex]i — 1[/latex] людей (возможно, никого) согласно условию а), [latex]1 \leq i < k[/latex]. Пусть человек под номером [latex]i[/latex] нарушил условие, например, вышел через выход с номером [latex]i + 1[/latex]. Тогда, т.к. его путь цельный и идет от самого первого ряда лабиринта до последнего, он образует «стену» из единичек, заблокировав выход [latex]i[/latex]. Тогда провести всех людей не возможно, ведь кол-ва входов и выходов равны. Следовательно, будем рассматривать как нашу задачу только случай а).
  2. Заполнение клеток каждого из пройденных маршрутов в матрице различными числами вместо единицы и функция

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

Тесты

№ теста Входные данные Выходные данные Пояснение (маршрут)
 1 6 8
1 0 1 0 1 1 0 1
1 0 1 0 0 0 0 1
1 0 1 1 0 0 1 1
1 0 0 0 0 0 0 1
1 0 0 1 1 0 0 1
1 0 0 1 1 1 0 1
 YES 1 a 1 b 1 1 c 1
1 a 1 b b c c 1
1 a 1 1 b c 1 1
1 a b b b c 0 1
1 a b 1 1 c c 1
1 a b 1 1 1 c 1
 2 5 7
1 0 0 0 1 1 0
0 0 0 0 0 0 0
0 0 0 0 0 1 1
0 0 0 0 0 0 0
0 0 0 1 1 1 0
YES 1 a b c 1 1 d
a a b c d d d
a b b c d 1 1
a b c c d d d
a b c 1 1 1 d
 3 7 7
1 1 0 0 1 1 1
0 0 0 0 0 0 0
0 0 0 0 0 0 0
1 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 1 0 0 0
1 1 1 1 0 1 0
YES 1 1 a b 1 1 1
a a a b 0 0 0
a a b b 0 0 0
1 a b b b b 0
a a a a a b 0
a a a 1 a b b
1 1 1 1 a 1 b
 4 5 5
0 1 0 1 0
0 0 0 0 0
0 0 0 0 0
0 0 1 0 0
0 1 0 1 0
 NO
 5 7 12
1 1 1 1 1 0 1 1 1 1 1 0
0 0 0 1 0 0 1 0 0 0 0 0
0 0 0 0 0 1 1 0 1 1 1 0
0 1 1 0 0 0 1 1 1 0 0 0
1 0 1 0 0 0 1 0 0 0 1 0
0 0 0 0 0 0 1 0 0 1 1 0
1 1 1 1 1 0 1 1 1 1 1 0
 YES 1 1 1 1 1 a 1 1 1 1 1 b
0 0 0 1 a a 1 0 0 0 0 b
0 0 0 a a 1 1 0 1 1 1 b
0 1 1 a 0 0 1 1 1 0 0 b
1 0 1 a 0 0 1 0 0 0 1 b
0 0 0 a a a 1 0 0 1 1 b
1 1 1 1 1 a 1 1 1 1 1 b
 6 3 6
1 1 1 1 1 0
0 0 0 0 0 0
1 0 1 1 1 1
 YES 1 1 1 1 1 a
0 a a a a a
1 a 1 1 1 1
 7 10 10
0 1 1 1 1 1 1 1 1 1
0 1 0 0 0 0 0 0 0 0
0 1 0 1 1 1 1 1 1 0
0 1 0 1 0 0 0 0 1 0
0 1 0 1 0 0 1 0 1 0
0 1 0 1 0 0 1 0 1 0
0 1 0 0 0 0 1 0 1 0
0 1 1 1 1 1 1 0 1 0
0 0 0 0 0 0 0 0 1 0
1 1 1 1 1 1 1 1 1 0
 YES a 1 1 1 1 1 1 1 1 1
a 1 a a a a a a a a
a 1 a 1 1 1 1 1 1 a
a 1 a 1 a a a a 1 a
a 1 a 1 a 0 1 a 1 a
a 1 a 1 a 0 1 a 1 a
a 1 a a a 0 1 a 1 a
a 1 1 1 1 1 1 a 1 a
a a a a a a a a 1 a
1 1 1 1 1 1 1 1 1 a
 8 10 10
0 1 1 1 1 1 1 1 1 1
0 1 0 0 0 0 0 0 0 0
0 1 0 1 1 1 1 1 1 0
0 1 0 1 0 0 0 0 1 0
0 1 0 1 1 0 1 0 1 0
0 1 0 1 0 1 1 0 1 0
0 1 0 0 0 0 1 0 1 0
0 1 1 1 1 1 1 0 1 0
0 0 0 0 0 0 0 0 1 0
1 1 1 1 1 1 1 1 1 0
 NO
 9 6 7
1 1 1 1 0 0 1
0 0 0 1 0 0 1
0 1 0 0 0 0 1
0 0 1 0 0 0 1
1 0 0 0 0 1 1
1 1 0 0 1 1 1
 YES 1 1 1 1 a b 1
a a a 1 a b 1
a 1 a a a b 1
a a 1 b b b 1
1 a a b 0 1 1
1 1 a b 1 1 1
 10 1 5
0 0 0 0 0
 YES a b c d e

Алгоритм

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

  1. Попытаться провести человека согласно описанной выше стратегии.
  2. В случае успеха, отметить все ячейки, пройденные ним, как недоступные. Иначе — будем кидать исключение, ловить которое будем непосредственно в основной функции, при поимке — выводим [latex]NO[/latex] и завершаем работу программы.

За поиск маршрута отвечают 2 функции. Функция

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

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

  1. Находим, в какую клетку мы попали при данном направлении. Определим все направления как подходящие константы и будем получать направление по формуле [latex]dir / 10, dir \mod 10[/latex], первая координата — по вертикали, вторая — по горизонтали. Так, например, для [latex]down = 10[/latex] получим вектор [latex](1, 0)[/latex], соответствующий перемещению на одну ячейку вниз в матрице (для остальных направлений значения подобраны аналогично).
  2. Проверяем, можем ли мы находиться в этой ячейке, если нет (она занята или находится вне матрицы) — не ищем дальше, возвращаем [latex]false[/latex].
  3. Добавляем координаты ячейки в стек route, проверяем, является ли данная точка выходом, если да — завершаем поиск успешно ([latex]true[/latex]).
  4. Составим массив направлений, от наиболее до наименее приоритетных, в зависимости от предыдущего направления. Например, текущее направление было [latex]down[/latex], мы пришли сверху, лучше всего будет попробовать пойти влево, иначе снова вниз, иначе вправо, наверх нельзя (уже были):

    Для других направлений — рассуждения аналогичны.
  5. Поочередно вызовем поиск из новой точки в каждом из направлений в порядке приоритета, при нахождении пути оставшиеся направления (с меньшим приоритетом) не рассматриваем, возвращаем [latex]true[/latex].
  6. Если ни в одном из направлений нельзя попасть к выходу (тупик) — удаляем вершину из стека, возвращаем [latex]false[/latex].

Код

 

Ссылки

Код для тестирования на ideone.

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

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

Условие

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

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

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

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

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

Решение

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

Тесты

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

Код

Ссылки

Код на ideaone.

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

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

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

Условие

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

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

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

Из условия:

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

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

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

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

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

Решение

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

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

Тесты

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

Код

Ссылки

Код на ideaone.

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

A299

Условие

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

Решение

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

Тесты

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

Код

Замечание

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

Ссылки

Код на ideaone (vector).

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

Условие

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

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

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

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

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

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

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

Решение

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

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

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

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

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

Тесты

Ввод Вывод
1 2
BEGIN
LOOP n
OP 4
LOOP 3
LOOP n
OP 1
END
OP 2
END
OP 1
END
OP 17
END

BEGIN
OP 1997 LOOP n LOOP n OP 1 END END
END
Program #1
Runtime = 3*n^2+11*n+17

Program #2
Runtime = n^2+1997

2 3
BEGIN
END

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

BEGIN OP 42
LOOP n LOOP 5 LOOP n
OP 7 END OP 2 END OP 1 END
OP 1 END
Program #1
Runtime = 0

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

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

Код

 

Ссылки

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

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

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

Условие

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

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

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

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

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

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

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

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

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

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

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

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

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

  1. Определяет, является ли символ цифрой.
  2. Определяет, является ли символ буквой в верхнем регистре.
  3. Определяет, является ли символ буквой в нижнем регистре.
  4. Будем хранить содержимое формулы используя структуру map (карта), ключами будут выступать названия элементов (строки), значениями — количества их вхождений. Если элемента в карте нет, добавляем пару <элемент, кол-во>, иначе — прибавляем к старом числу вхождений новое. За это отвечает следующая функция.
  5. Для простоты разобьем формулу на подформулы (по знаку [latex]+[/latex], если он встречается), и будем работать с каждой формулой по отдельности. Функция разбивает строку на подстроки по знаку [latex]+[/latex] и заполняет ими вектор [latex]storage[/latex] (так как мы не знаем кол-во подформул заранее, вектор предпочтительнее массива).
  6. По условию, перед каждой подформулой может идти множитель, относящейся ко всей подформуле. Функция возвращает множитель ( [latex]1[/latex], если множитель не записан явно).
  7. Основная функция. Добавляет в карту [latex]content[/latex] содержимое подформулы.
  8. Обрабатывает формулу. Просто вызывает функции №[latex]6[/latex] и №[latex]7[/latex] по очереди для каждой из подформул (элементов из [latex]subformulas[/latex]).

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

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

Тут:

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

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

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

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

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

  1. Находим первую открывающую скобку.
  2. Находим соответствующую ей закрывающую скобку.
  3. Для выражения в скобках вычисляем задний коэффициент (см. код), заносим в переменную [latex]newMultiplier[/latex] значение множителя для выражения внутри скобок.
  4. Рекурсивно вызываем функцию getContent() для:
    1. Выражения перед открывающей скобкой, если формула не начинается с нее.

      ([latex]begin[/latex] — номер первого символа внутри скобок.)
    2. Выражения внутри скобок.

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

      ([latex]afterEnd[/latex] — следующий после скобки/коэффициента символ.)

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

Тесты

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

Код

Ссылки

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

Код на ideaone.

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

Условие

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

Замечание

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

Тесты

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

Решение

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

Код

Ссылки

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

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

MLoops 23

Условие

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

Тесты

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

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

Решение

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

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

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

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

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

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

Код

Ссылки

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

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

MLoop 1

Условие

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

График

save (1)

Тесты

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

Код

 

Решение

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

 

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

Ссылки

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

Mif 17.17

Условие :

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

Рисунок :

picture

Тесты :

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

Решение :

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

Код :

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

Mif 16

Условие :

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

Решение :

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

Тесты : 

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

Код :

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

Ideone.com

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

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

Условие 

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

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

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

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

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

Тесты :

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

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

Примечание

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

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

 

Ссылки 

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

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

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Тесты (1) :

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

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

Тесты (2) :

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

2

2

0

1

2

0

0

5 2 1 2 0 0
6 Решений нет

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

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

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

Ideaone.com

ML 24

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

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

Тесты :

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

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

Алгоритм :

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

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

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

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

Ideone.com

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

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

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

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

Условие

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

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

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

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

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

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

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

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

Тесты:

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

Код:

 

Ход решения:

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

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

Ссылки:

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

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