e-olymp 1210. Очень просто!!!

Задача

По заданным числам [latex]n[/latex] и [latex]a[/latex] вычислить значение суммы: [latex]\sum\limits_{i=1}^{n} {i \cdot a^i}[/latex]

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

Два натуральных числа [latex]n[/latex] и [latex]a[/latex].

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

Значение суммы. Известно, что оно не больше [latex]10^{18}[/latex].

Тесты

Входные данные Выходные данные
3 3 102
4 4 1252
9 3 250959
7 14 785923166
1009 1 509545

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

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

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

Для получения качественного решения распишем ряд подробно:
[latex]A[/latex] [latex]=[/latex] [latex]\sum\limits_{i=1}^{n} {i \cdot a^i}[/latex] [latex]=[/latex] [latex]a+2a^2+3a^3+\ldots+\left( n-1 \right) a^{n-1}+na^{n}[/latex] [latex]=[/latex] [latex]na^{n}[/latex] [latex]+[/latex] [latex]\left( n-1 \right)a^{n-1}[/latex] [latex]+[/latex] [latex]\ldots[/latex] [latex]+[/latex] [latex]3a^{3}[/latex] [latex]+[/latex] [latex]2a^2[/latex] [latex]+[/latex] [latex]a[/latex].
Очевидно, что из полученного выражения можно вынести [latex]a[/latex] за скобки. Применим данную операцию:
[latex]A[/latex] [latex]=[/latex] [latex] \left( na^{n-1}+\left( n-1 \right)a^{n-2}+\ldots+3a^{2}+2a+1\right) \cdot a[/latex]
Из полученной формулы видно, что аналогичное действие можно применить вновь, для внутреннего выражения [latex]na^{n-1}[/latex] [latex]+[/latex] [latex]\left( n-1 \right)a^{n-2}[/latex] [latex]+[/latex] [latex]\ldots[/latex] [latex]+[/latex] [latex]3a^{2}[/latex] [latex]+[/latex] [latex]2a[/latex]. Получим:
[latex]A[/latex] [latex]=[/latex] [latex] \left( \left( na^{n-2}+\left( n-1 \right)a^{n-3}+\ldots+3a+2 \right) \cdot a +1 \right) \cdot a[/latex].
После конечного количества вынесений за скобки, получим:
[latex]A[/latex] [latex]=[/latex] [latex]\left( \left( \ldots \left( \left(na+\left(n-1\right)\right) \cdot a + \left(n-2\right) \right) \ldots+2\right) \cdot a +1\right) \cdot a[/latex].

Таким образом, решение данной задачи сводится к вычислению суммы «изнутри» скобок.

Но из-за того, что в условии подано ограничение только на сумму, программа с реализованным вычислением суммы изнутри и асимптотикой [latex]O \left( n \right)[/latex] не пройдёт все тесты системы www.e-olymp.com в силу частного случая [latex]a = 1[/latex], так как значение [latex]n[/latex] может быть для него достаточно большим, ибо числа [latex]a[/latex] и [latex]n[/latex] компенсируют друг-друга по отношению к максимальному значению суммы. Но в случае [latex]a = 1[/latex] сумма данного ряда является суммой арифметической прогрессии, а именно — натурального ряда. Для вычисления этой суммы существует формула [latex]\sum\limits_{i=1}^{n} {i} = \frac{n \left( n+1 \right)}{2}[/latex]. Этот частный случай легко отсеять.

Асимптотика программы: [latex]const[/latex] при [latex]a = 1[/latex], и [latex]O \left( n \right)[/latex] иначе.

Ссылки

e-olymp 1078. Степень строки

Задача

Обозначим через [latex]a \cdot b[/latex] конкатенацию строк [latex]a[/latex] и [latex]b[/latex].

Например, если [latex]a =[/latex]«abc» и [latex]b =[/latex]«def» то [latex]a \cdot b =[/latex]«abcdef».

Если считать конкатенацию строк умножением, то можно определить операцию возведения в степень следующим образом:
[latex]a^{0} =[/latex]«» (пустая строка)
[latex]a^{n+1} = a \cdot a^{n}[/latex]

По заданной строке [latex]s[/latex] необходимо найти наибольшее значение [latex]n[/latex], для которого [latex]s = a^{n}[/latex] для некоторой строки [latex]a[/latex].

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

Каждый тест состоит из одной строки [latex]s[/latex], содержащей печатные (отображаемые) символы. Строка [latex]s[/latex] содержит не менее одного и не более миллиона символов.

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

Для каждой входной строки [latex]s[/latex] вывести в отдельной строке наибольшее значение [latex]n[/latex], для которого [latex]s[/latex] = [latex]a^{n}[/latex] для некоторой строки [latex]a[/latex].

Тесты

Входные данные Выходные данные
abcabc
gcdgcd
gcgcgc
gggggg
hhhh
2
2
3
6
4
BbbbBbbbBbbb
dogdogdog
aaaaaaaa
cstring
3
3
8
1

Код программы (c-string)

Решение задачи (c-string)

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

Для решения поставленной задачи используем функцию cstringpow, которая в качестве аргумента принимает строку, и возвращает её степень. Реализуем эту функцию следующим образом: вначале ищем делители значения переменной size (с использованием счётчика i в цикле), в которую было предварительно была сохранена длина строки, полученная функцией strlen. Числа, которые будут получатся из выражения size/i, будут предполагаемой максимальной степенью строки. Естественно, они будут находится в порядке убывания.
Найденные счётчиком делители будут представлять из себя длины подстрок, на которые можно полностью разбить данную строку. Затем, используя функцию strncmp, сравниваем каждую подстроку. В случае, если какие-то из подстрок не совпали, то предположенная максимальная степень строки не является верной, и необходимо искать следующую. Иначе (если несовпадающих подстрок не найдено, то) значение выражения size/i будет ответом на поставленную задачу. В крайнем случае, необходимое разбиение строки не будет найдено, и тогда совокупностью одинаковых подстрок будет сама строка, а следовательно её степень равна [latex]1[/latex].

Код программы (string)

Решение задачи (string)

Решение задачи с использованием класса string аналогично. Единственное отличие — замена функций strlen и strncmp, предназначенных для работы с c-string, на эквивалентные им методы класса string size и compare.

Ссылки

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

Задача

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

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

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

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

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

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

Тесты

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

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

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

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

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

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

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

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

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

Ссылки

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

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

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

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

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

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

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

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

Код класса


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

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

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

Аргументы:

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

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

read_and_construct Аргументы:

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

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

assign Аргументы:

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

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

result_on_segment Аргументы:

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

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

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

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

Построение:

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

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

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

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

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

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

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

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

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


Задача 2

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

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

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

Код класса

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

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

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

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

pop_back

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

insert

Аргументы:

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

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

erase

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

size

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

capacity

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

resize

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

Ссылки

ASCII ART

Task

In stations and airports you often see this type of screen:

Have you ever asked yourself how it might be possible to simulate this display on a good old terminal? We have: with ASCII art!

Your mission is to write a program that can display a line of text in ASCII art in a style you are given as input.

Input

Line 1: the width L of a letter represented in ASCII art. All letters are the same width.
Line 2: the height H of a letter represented in ASCII art. All letters are the same height.
Line 3: the line of text T, composed of N ASCII characters.
Following H lines: the string of characters ABCDEFGHIJKLMNOPQRSTUVWXYZ? Represented in ASCII art.

[latex]0 < [/latex] L[latex] < 30[/latex]
[latex]0 < [/latex] H[latex] < 30[/latex]
[latex]0 < [/latex] N[latex] < 200[/latex]

Output

The text T in ASCII art.
The characters a to z are shown in ASCII art by their equivalent in upper case.
The characters that are not in the intervals [a-z] or [A-Z] will be shown as a question mark in ASCII art.

Tests

Input Output
1
1
Encoding using ASCII? Hah!
?ZYXWVUTSRQPONMLKJIHGFEDCBA
WNYMXSNUAGISNUA?IYSSAAT?TA

Codes of the program

Solution of the task

After saving the string, we can convert the task to «semi-stream processing». After we read and save the first line of ASCII characters into alphabet array, we start to print the tops of the ASCII letters. Then the same procedure is repeated on the following lines, and new parts of ASCII letters are read over the old ones into alphabet.

Links

There is no Spoon — Episode 1

Task

The Goal

The game is played on a rectangular grid with a given size. Some cells contain power nodes. The rest of the cells are empty.

The goal is to find, when they exist, the horizontal and vertical neighbors of each node.

Rules

To do this, you must find each [latex]\left( x1, y1 \right)[/latex] coordinates containing a node, and display the [latex]\left(x2, y2\right)[/latex] coordinates of the next node to the right, and the [latex]\left(x3, y3\right)[/latex] coordinates of the next node to the bottom within the grid.

If neighbor does not exist, you must output the coordinates [latex]\left(-1, -1\right)[/latex] instead of [latex]\left(x2, y2\right)[/latex] and/or [latex]\left(x3, y3\right)[/latex].

You lose if:

  • You give an incorrect neighbor for a node.
  • You give the neighbors for an empty cell.
  • You compute the same node twice.
  • You forget to compute the neighbors of a node.

Game input

The program must first read the initialization data from standard input. Then, provide to the standard output one line per instruction.

Initialization input

Line 1: one integer width for the number of cells along the x axis.

Line 2: one integer height for the number of cells along the y axis.

Next height lines: A string line containing width characters. A dot . represents an empty cell. A zero 0 represents a cell containing a node.

[latex]0 <[/latex] width[latex]\le 30[/latex]
[latex]0 <[/latex] height[latex]\le 30[/latex]

Output for one game turn

One line per node. Six integers on each line: x1 y1 x2 y2 x3 y3
Where:

  • ( x1, y1) the coordinates of a node.
  • ( x2, y2) the coordinates the closest neighbor on the right of the node.
  • ( x3, y3) the coordinates the closest bottom neighbor.

[latex]0 \le[/latex] x1[latex]<[/latex] width
[latex]0 \le[/latex] y2[latex]<[/latex] height
[latex]-1 \le[/latex] x2, x3[latex]<[/latex] width
[latex]-1 \le[/latex] y2, y3[latex]<[/latex] height
Alloted response time to first output line [latex]\le 1[/latex]s.
Response time between two output lines [latex]\le 100[/latex]ms.

Tests

Input Output
2 2
00
0.
0 0 1 0 0 1
1 0 -1 -1 -1 -1
0 1 -1 -1 -1 -1
4 4
.0..
.000
000.
..0.
1 0 -1 -1 1 1
1 1 2 1 1 2
2 1 3 1 2 2
3 1 -1 -1 -1 -1
0 2 1 2 -1 -1
1 2 2 2 -1 -1
2 2 -1 -1 2 3
2 3 -1 -1 -1 -1

The code of the program

Solution of the task

First of all, we must pay attention, that we have to find the closest neighbor. It doesn’t mean, that if there is no neighbor on adjacent cells, then the answer will be negative, because the neighbor may be further. This leads to the fact, that the task can not be completed without memorization of the whole list of cells.

After storing every string in array, the task becomes simple: we go using the cycle through every cell, and if the cell contains a node, then we launch two cycles from it in two directions (to the right and to the bottom), and assume there are no neighbors with assigning value -1 to both variables ansX and ansY. If there will be no nodes found, the value will remain the same, otherwise variables will take values of the node coordinates. In any case, the result will be correct.

This process is optimized by usage of the following: the [latex]x[/latex] coordinate of the closest right neighbor (or the value of width) is saved in a variable x2. Whether we find a neighbor or no, we can start the further horizontal search right from the coordinate x2, because empty cells must be skipped anyway.

Links

Код Хаффмана

Задача

Дана строка, после которой следует символ перехода на следующую строку (далее — endl. Вывести:

  1. Код графа на языке DOT, иллюстрирующий кодирование символов строки;
  2. Символы строки и соответствующие им коды Хаффмана;
  3. Закодированную строку.

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

Некоторая последовательность символов и endl.

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

  1. Код графа на языке DOT, иллюстрирующий кодирование символов строки;
  2. Символы строки и соответствующие им коды Хаффмана;
  3. Закодированная строка.

Тест

Входные данные Выходные данные
MOLOKO KIPIT digraph G {
"'MLO KITP', 12, code: ''" -> "'MLO', 5, code: '0'" [ label = "0" ];
"'MLO KITP', 12, code: ''" -> "' KITP', 7, code: '1'" [ label = "1" ];
"'MLO', 5, code: '0'" -> "'ML', 2, code: '00'" [ label = "0" ];
"'MLO', 5, code: '0'" -> "'O', 3, code: '01'" [ label = "1" ];
"'ML', 2, code: '00'" -> "'M', 1, code: '000'" [ label = "0" ];
"'ML', 2, code: '00'" -> "'L', 1, code: '001'" [ label = "1" ];
"' KITP', 7, code: '1'" -> "' K', 3, code: '10'" [ label = "0" ];
"' KITP', 7, code: '1'" -> "'ITP', 4, code: '11'" [ label = "1" ];
"' K', 3, code: '10'" -> "' ', 1, code: '100'" [ label = "0" ];
"' K', 3, code: '10'" -> "'K', 2, code: '101'" [ label = "1" ];
"'ITP', 4, code: '11'" -> "'I', 2, code: '110'" [ label = "0" ];
"'ITP', 4, code: '11'" -> "'TP', 2, code: '111'" [ label = "1" ];
"'TP', 2, code: '111'" -> "'T', 1, code: '1110'" [ label = "0" ];
"'TP', 2, code: '111'" -> "'P', 1, code: '1111'" [ label = "1" ];
}

Codes of letters:
'O'(01) 'K'(101) 'I'(110) 'T'(1110) 'P'(1111) 'M'(000) 'L'(001) ' '(100)

Encoded string:
00001001011010110010111011111101110

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

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

Для начала считываем посимвольно строку и запоминаем её, параллельно запоминая частоты появлений символов в ней в массиве count. Останавливаем считывание, когда встречается endl. После этого отсортировуем массив count в порядке убывания частот.

После этого элементы массива count, которые имеют ненулевую частоту, преобразовываем в элементы вектора tree (при этом символы конвертируются в строки), который после сортируется в порядке возрастания частот. Затем обрабатываем массив по алгортиму Хаффмана, объединяя элементы вектора с номерами [latex]j[/latex], [latex]j+1[/latex] в новый (который будет представлять собой структуру из конкатенации строк ранее упомянутых элементов и суммы их частот, а так же номеров его «предков»). После этого вектор вновь сортируется по частотам/суммам частот в порядке возрастания начиная с номера[latex]j+2[/latex], при этом элементы, которые имеют больший размер строк будут иметь меньший приоритет.

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

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

Ссылки

Просто RSQ

Задача RSQ (Range Sum Query). Вам дан массив, необходимо отвечать на запросы получения суммы на отрезке и изменение одного элемента массива.

Ссылка на задачу на codeforces.com.

Имя входного файла: rsq.in
Имя выходного файла: rsq.out
Ограничение по памяти: 2 секунды
Ограничение по времени: 256 мегабайт

Формат входного файла

Входной файл в первой строке содержит два числа [latex]n[/latex] [latex]\left(1 \le n \le 10^{5} \right)[/latex] — размер массива и [latex]m[/latex] [latex]\left(1 \le m \le 10^{5} \right)[/latex] — количество запросов. Во второй строке задано начальное состояние массива [latex]a_{1}[/latex], [latex]a_{2}[/latex], [latex]\ldots[/latex], [latex]a_{n}[/latex] [latex]\left( -10^{5} \le a_{i} \le 10^{5} \right)[/latex].

Далее идёт [latex]m[/latex] строк с запросами вида [latex]t[/latex] [latex]x[/latex] [latex]y[/latex] [latex]\left( 0 \le t \le 1 \right)[/latex]. Если [latex]t = 0[/latex], тогда на запрос нужно вывести сумму элементов массива с индексами от [latex]x[/latex] до [latex]y[/latex] (в данном случае [latex]1 \le x \le y \le n[/latex]). Если [latex]t = 1[/latex], тогда надо присвоить элементу массива с индексом [latex]x[/latex] значение [latex]y[/latex] (в этом случае [latex]1 \le x \le n[/latex], [latex]-10^{5} \le y \le 10^{5}[/latex]).

Формат выходного файла

На каждый запрос суммы отрезка выведите одно число в новой строке — запрашиваемая сумма.

Примеры

rsq.in rsq.out
5 3
1 2 3 4 5
0 1 5
1 1 -14
0 1 5
15
0
8 2
7 3 -10 4 1 2 5 6
0 2 4
0 5 7
-3
8

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

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

Основная идея приведённого выше решения этой задачи заключается в оптимизации обработки запросов суммы построением дерева отрезков.
Сохраним сумму всех элементов массива в переменной sum. Теперь, если нам дан запрос суммы на отрезке [latex]\left[ x; y \right][/latex], то если [latex]y — x > \frac{n}{2}[/latex] (то есть если данный отрезок содержит больше элементов, чем половина всего отрезка) то считаем сумму элементов на отрезке [latex]\left[ 1; x-1 \right] \cup \left[ y+1; n \right] = \left[ 1; n \right] \setminus \left[ x; y \right][/latex] и отнимаем от суммы всех элементов, иначе (если [latex]y — x \le \frac{n}{2}[/latex], то) просто считаем сумму элементов на отрезке [latex]\left[ x; y \right][/latex]. Если же поступает запрос на замену значения элемента, то вычитаем из sum старое значение и прибавляем новое.

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

Ссылки

MS17. Самосинхронизирующийся скремблер

Задача

Рассматривая входной поток как последовательность бит, зашифруйте его при помощи восьмибитового самосинхронизирующегося скремблера. Начальное значение и обратные связи скремблера должны быть заданы в программе значениями двух переменных типа unsigned char. Как расшифровать полученный код.

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

Подзадача 1

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

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

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

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

Зашифрованная символьная последовательность.

Тесты

Входные данные Выходные данные
Dogs eat meat. ea 27 33 77 25 11 66 75 5 3b e0 89 6b fa
Scramble it! fc 5a 80 ef 75 43 1e 92 9b 46 57 6
Base, base, it’s cheeseburger 1. Can you hear me? ec 49 a0 c9 72 75 43 13 55 66 28 80 e7 ed d2 75 b7 bf 69 93 c7 df 4e d0 be 3f b1 de 5c f6 ea 6c 94 f5 8d 1f 86 80 aa 74 5e c7 9e 17 2 47 41 76 7c d4 a1

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

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

Для зашифровки будем использовать стандартный алгоритм скремблирования. Скремблером будет переменная key, которая изначально равна [latex]5[/latex]. Выбирать из скремблера будем нулевой и четвёртый биты. Входные данные будут поступать в переменную input, после чего на них и на скремблере будет применяться функция scram.
Так как входные данные имеют формат unsigned char, считывание не прекратится никогда вплоть до принудительной остановки программы, ведь любые входные данные могут быть восприняты как символы. Для предотвращения этого, необходим символ, который будет служить «сигналом» для остановки программы. В нашем случае, это будет символ перехода на следующую строку.
Основная проблема задачи заключается в выводе зашифрованных данных, так как в результате скремблирования некоторые символы могут оказаться не отображаемыми. Дабы избежать подобной ситуации, зашифрованные данные будем выводить в шестнадцатеричном (для кода на Java — в десятичном) числовом формате.

Подзадача 2

Расшифровать входные данные из предыдущей подзадачи.

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

Некие зашифрованные данные, записанные в виде последовательности чисел шестнадцатеричного (для кода на Java — десятичного) формата.

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

Расшифрованные данные.

Тесты

Входные данные Выходные данные
ea 27 33 77 25 11 66 75 5 3b e0 89 6b fa Dogs eat meat.
fc 5a 80 ef 75 43 1e 92 9b 46 57 6 Scramble it!
ec 49 a0 c9 72 75 43 13 55 66 28 80 e7 ed d2 75 b7 bf 69 93 c7 df 4e d0 be 3f b1 de 5c f6 ea 6c 94 f5 8d 1f 86 80 aa 74 5e c7 9e 17 2 47 41 76 7c d4 a1 Base, base, it’s cheeseburger 1. Can you hear me?

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

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

Для расшифровки будем применять обратный алгоритм к использованному в предыдущей задаче. Значение необходимого для расшифровки дескремблера нам известно из предыдущей задачи (а именно — [latex]5[/latex]), поэтому его мы и используем.
Входные данные будут считываться методом cin (для C++), где параметр hex будет указывать на то, что данные поданы в шестнадцатеричном формате. После считывания на входных данных будет применяться алгоритм дескремблирования, и итоговые данные будут выведены на экран.

Ссылки

A333. Наибольший общий делитель чисел последовательности

Примечание: [latex]GCD[/latex] — Greatest common divisor (Наибольший общий делитель, НОД).

Задача

Даны натуральные числа [latex]m[/latex], [latex]n_1[/latex], [latex]\ldots[/latex], [latex]n_m[/latex] [latex]m \ge 2[/latex]. Вычислить [latex]GCD \left( n, \ldots, n_m \right)[/latex], воспользовавшись для этого соотношением [latex]GCD \left( n, \ldots, n_k \right) = GCD \left( GCD \left( n, \ldots, n_{k-1} \right), n_k \right)[/latex] [latex]\left( k = 3, \ldots, n \right)[/latex] и алгоритмом Евклида.

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

Количество чисел [latex]m[/latex]; числа [latex]n_1[/latex], [latex]\ldots[/latex], [latex]n_m[/latex].

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

[latex]GCD \left( n_1, \ldots, n_m \right)[/latex].

Тесты

Входные данные Выходные данные
2 3 4 1
2 4 8 4
4 24 23 40 90 1
4 36 48 20 24 4
3 30 738 1926 6

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

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

Для решения данной задачи необходимо использовать данную в условии формулу [latex]GCD \left( n, \ldots, n_k \right) = GCD \left( GCD \left( n, \ldots, n_{k-1} \right), n_k \right)[/latex] [latex]\left(\right)[/latex].
Также необходимо воспользоваться алгоритмом Евклида для реализации рекурсивной функции [latex]GCD[/latex]:
Пусть [latex]m[/latex] и [latex]n[/latex] — одновременно не равные нулю целые неотрицательные числа и пусть [latex]m \ge n[/latex]. Тогда если [latex]n=0[/latex], то [latex]GCD\left(n, m\right)=m[/latex], а если [latex]n\ne0[/latex], то для чисел [latex]m[/latex], [latex]n[/latex] и [latex]r[/latex], где [latex]r[/latex] — остаток от деления [latex]m[/latex] на [latex]n[/latex], выполняется равенство [latex]GCD\left(m, n\right)=GCD\left(n, r\right)[/latex]. (задача 89 задачника С. Абрамова)
Программа записывает в переменную m число [latex]m[/latex], а в result — [latex]n_1[/latex].
Затем, используя формулу [latex]\left(
\right)[/latex], программа до окончания цикла считывает следующие числа из последовательности поверх предыдущих в переменную n и находит сперва [latex]GCD\left(n_1, n_2\right)=x_1[/latex], [latex]GCD\left(x_1, n_3 \right)=x_2[/latex], затем [latex]GCD\left(x_2, n_4\right)=x_3[/latex] и так далее, вплоть до нахождения [latex]GCD[/latex] всех чисел, постоянно записывая новые [latex]GCD[/latex] поверх старых в переменную result. В итоге, программа выводит результирующий [latex]GCD[/latex], который и является ответом.

Ссылки

D2655Б. Сумма ряда с заданной точностью

Задача

Сколько примерно надо взять членов ряда, чтобы найти его сумму с точностью до [latex]10^{-5}[/latex], если [latex]\sum\limits_{n=1}^\infty \frac{2^n}{\left(n+1\right)!}[/latex]?

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

Заданная точность.

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

Количество взятых членов ряда и их сумма.

Тесты

Входные данные Выходные данные
[latex]\varepsilon[/latex] [latex]k[/latex] [latex]\sum\limits_{n=1}^{k} \frac{2^n}{\left(n+1\right)!}[/latex]
1e-5 11 2.194527283416172
1 2 1.666666666666667
0.5 3 2.000000000000000

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

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

Для удобства введём обозначение: [latex]x_{n}=\frac{2^n}{\left(n+1\right)!}[/latex].
Чтобы доказать, что данный нам ряд [latex]\sum\limits_{n=1}^\infty \frac{2^n}{\left(n+1\right)!}[/latex] сходится, воспользуемся признаком Даламбера:
Пускай [latex]\lim\limits_{n \to \infty} \frac{x_{n+1}}{x_{n}} = D[/latex]. Ряд [latex]\sum\limits_{n=1}^\infty x_n[/latex] сходится, если [latex]D < 1[/latex]. В частности, если [latex]D = 0[/latex]
Найдём [latex]\lim\limits_{n \to \infty} \frac{x_{n+1}}{x_{n}}[/latex].
[latex]\lim\limits_{n \to \infty} \frac{x_{n+1}}{x_{n}} = \lim\limits_{n \to \infty} \left( \frac{2^{n+1}}{\left( n+2 \right)!} \div \frac{2^{n}}{\left( n+1 \right)!} \right) = \lim\limits_{n \to \infty} \left( \frac{2 \cdot 2^{n}}{\left( n+1 \right)! \cdot \left( n+2 \right)} \cdot \frac{\left( n+1 \right)!}{2^{n}} \right) = \lim\limits_{n \to \infty} \frac{2}{n+2} = 0[/latex]
Для доказательства последнего равенства [latex]\left( \lim\limits_{n \to \infty} \frac{2}{n+2} = 0 \right)[/latex] воспользуемся определением предела последовательности:
Число [latex]a[/latex] называют пределом последовательности, если для любой точности [latex]\varepsilon>0[/latex] найдётся/существует такой номер, зависящий от [latex]\varepsilon[/latex], начиная с которого все элементы последовательности попадают в интервал [latex]\left( a-\varepsilon; a+\varepsilon \right)[/latex].
В нашем случае число [latex]a[/latex] равно нулю. Поэтому доказательство будет следующим:
[latex]\forall \varepsilon>0[/latex] [latex]\exists N_{\varepsilon} \in \mathbb{N}[/latex]: [latex]\forall n\ge N_{\varepsilon}[/latex], [latex]\left| \frac{2}{n+2} \right| < \varepsilon[/latex]. Находим [latex]N_{\varepsilon}[/latex]:
[latex]\left| \frac{2}{n+2} \right| < \left| \frac{2}{n} \right| = \frac{2}{n} < \varepsilon [/latex]

[latex]\frac{2}{n} < \varepsilon[/latex]

[latex]n > \frac{2}{\varepsilon} \Rightarrow N_{\varepsilon} = \left[ \frac{2}{\varepsilon} \right] + 1 \Rightarrow \lim\limits_{n \to \infty} \frac{2}{n+2} = 0[/latex].

Итог:
Так как ряд сходится, сумма ряда стремится к некоторой константе, и можно определить точный номер [latex]k[/latex], при котором элемент (а следовательно — и сумма) ряда будет удовлетворять заданной точности. Этой точностью будет значение переменной epsilon, которое задаёт пользователь.

Ссылки

KM2. Радиус окружностей, удовлетворяющих условию

Задача

Дана сфера радиуса [latex]1[/latex]. На ней расположены равные окружности [latex]\gamma_0[/latex], [latex]\gamma_1[/latex], [latex]\ldots[/latex], [latex]\gamma_n[/latex] радиуса [latex]r \left(n \ge 3\right)[/latex]. Окружность [latex]\gamma_0[/latex] касается всех окружностей [latex]\gamma_1[/latex], [latex]\ldots[/latex], [latex]\gamma_n[/latex]; кроме того, касаются друг друга окружности [latex]\gamma_1[/latex] и [latex]\gamma_2[/latex]; [latex]\gamma_2[/latex] и [latex]\gamma_3[/latex]; [latex]\ldots[/latex]; [latex]\gamma_n[/latex] и [latex]\gamma_1[/latex].
При каких [latex]n[/latex] это возможно? Вычислить соответствующий радиус [latex]r[/latex].

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

Количество окружностей [latex]n[/latex].

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

Радиус окружностей [latex]r[/latex].

Тесты

Входные данные ([latex]n[/latex]) Выходные данные ([latex]r[/latex])
3 0.816497
4 0.707107
5 0.525731
6 Solution does not exist.

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

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

Каждой окружности на сфере можно сопоставить её «центр на сфере» — конец радиуса сферы, проходящего через центр окружности (никогда не лежащий на сфере). Эту точку мы будем называть «центром» окружности в кавычках, подчёркивающих, что это не «обычный» центр (рис. 2, а).

Заметим для точности, что такого определённого «центра» нет у окружностей больших кругов сферы. Но окружности, о которых идёт речь в условии задачи, заведомо не могут иметь радиус [latex]1[/latex], потому что окружности двух больших кругов не могут друг друга касаться, — они всегда пересекают друг друга в двух диаметрально противоположных точках сферы.

Точка касания двух окружностей, расположенных на сфере (см. рис. 2, б), лежит в плоскости [latex]P[/latex], проходящей через центры окружностей и центр сферы. Действительно, обе окружности симметричны относительно плоскости [latex]P[/latex], и если бы они имели общую точку по одну сторону плоскости [latex]P[/latex], то должны были бы иметь и симметричную ей общую точку по другую сторону [latex]P[/latex], а у них всего одна общая точка. Если эти окружности имеют один и тот же радиус [latex]r[/latex], то расстояние между их «центрами» равно [latex]2r[/latex], потому что на окружности большого круга, получающейся в пересечении сферы и плоскости [latex]P[/latex] (рис. 2, в), диаметры наших окружностей (чёрные отрезки) и отрезок, соединяющий их «центры» (красный), стягивают равные дуги.

Пусть [latex]A_0[/latex], [latex]A_1[/latex], [latex]A_2[/latex], [latex]\ldots[/latex], [latex]A_n[/latex] — «центры» окружностей [latex]\gamma_0[/latex], [latex]\gamma_1[/latex], [latex]\ldots[/latex], [latex]\gamma_n[/latex], о которых идёт речь в условии задачи. Тогда [latex]A_0 A_1=A_0 A_2=\ldots=A_0 A_n=A_1 A_2=A_2 A_3=\ldots=A_n A_1=2r[/latex], другими словами, [latex]A_0 A_1 A_2 \ldots A_n[/latex] — правильная [latex]n[/latex]-угольная пирамида с вершиной [latex]A_0[/latex], у которой все боковые грани — равносторонние треугольники со сторонами равными [latex]2r[/latex]. Итак, достаточно построить пирамиду, для которой выполнены эти условия, тогда точки [latex]A_0[/latex], [latex]A_1[/latex], [latex]\ldots[/latex], [latex]A_n[/latex] будут определять окружности радиуса [latex]r[/latex], с «центрами» [latex]A_0[/latex], [latex]A_1[/latex], [latex]\ldots[/latex], [latex]A_n[/latex], которые, очевидно, удовлетворяют условию задачи.

Поскольку сумма плоских углов выпуклого [latex]n[/latex]-гранного угла с вершиной [latex]A_0[/latex] меньше [latex]360^\circ[/latex]:
[latex]n\cdot60^\circ=[/latex]∠[latex]A_1 A_0 A_2+[/latex]∠[latex]A_2 A_0 A_3+\ldots+[/latex]∠[latex]A_n A_0 A_1<360^\circ[/latex], то [latex]n<6[/latex]. Для [latex]n=3[/latex], [latex]4[/latex] и [latex]5[/latex] нетрудно построить нужные пирамиды.

Пусть [latex]O[/latex] — центр сферы. Высота пирамиды [latex]h[/latex] и длина её рёбер [latex]2r[/latex] находятся из следующих соображений: радиус [latex]K A_1[/latex] основания пирамиды — катет [latex]\bigtriangleup A_0 K A_1[/latex] и боковая сторона [latex]\bigtriangleup A_1 K A_2[/latex], где ∠[latex]A_1 K A_2=2 \pi / n[/latex] (рис. 3, а , б),
[latex]\sqrt{4 r^2-h^2 \sin \frac{\pi}{n}}=r[/latex]

Из [latex]\bigtriangleup A_0 O A_1[/latex] имеем [latex]r=\frac{h}{2r}[/latex].

Отсюда [latex]h=2 r^2[/latex], [latex]r=\sqrt{1-\frac{1}{4 \sin^2 \frac{\pi}{n}}}[/latex]

Таким образом,
при [latex]n=3[/latex]: [latex]r=\sqrt{\frac{2}{3}}[/latex] [latex]\left( \sin \frac{\pi}{3}=\frac{\sqrt{3}}{2} \right)[/latex]
при [latex]n=4[/latex]: [latex]r=\sqrt{\frac{1}{2}}[/latex] [latex]\left( \sin \frac{\pi}{4}=\frac{\sqrt{2}}{2} \right)[/latex]
при [latex]n=5[/latex]: [latex]r=\sqrt{\frac{1-\sqrt{5}}{2}}[/latex]
(формулу [latex]\sin \frac{\pi}{5}=\frac{\sqrt{10-2 \sqrt{5}}}{4}[/latex] можно вывести из рисунка 4, с помощью которого строятся правильный десятиугольник и правильный пятиугольник).

Рисунки, использованные в решении

Рисунок 2:

Рисунок 3:

Рисунок 4:

Научно-популярный журнал «Квант», 1970 год, №7, страницы 51-53

Итоги:
Выведенная во время решения формула [latex]r=\sqrt{1-\frac{1}{4 \sin^2 \frac{\pi}{n}}}[/latex] справедлива только при [latex]n=3[/latex], [latex]4[/latex], [latex]5[/latex]. В случае, если задать значения больше этих, то выражение под корнем примет отрицательное значение, а в рамках данной задачи это будет говорить об отсутствии решения. Значения же меньше будут недопустимы, что было указано в условии.
Таким образом, программа выведет сообщение об отсутствии решения, если заданные значения [latex]n[/latex] отличны от вышеупомянутых. Если же условия будут соблюдаться, то задача выведет соответствующее значение радиуса.

Ссылки

Вывод чисел в обратном порядке

Задача

Вводятся некоторые числа вещественного типа. Вывести их в обратном порядке.

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

Некие числа вещественного типа.

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

Введённые числа в обратном порядке.

Тесты

Входные данные Выходные данные Входные данные Выходные данные Входные данные Выходные данные
2
4
1
1
4
2
4
9
-6
-6
9
4
0.568
0.925
-0.056
-0.056
0.925
0.568

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

Идея программы

Основная суть программы заключается в использовании рекурсивной функции. Главная функция main обращается к функции reverse, которая будет считывать поток чисел. Если поток чисел продолжается, то функция будет заново обращаться сама к себе и считывать следующие числа. Когда поток закончится, функция прекратит считывать данные, после чего начнётся вывод.

Принцип работы рекурсивной функции reverse:
Принцип работы рекурсивной функции reverse

Решение задачи №1001 на acm.timus.ru, основанное на этом принципе

Ссылки

KM208(a). Наибольшая разность чисел последовательности

Задача

Известно, что разность между наибольшим и наименьшим из вещественных чисел [latex]x_1[/latex], [latex]x_2[/latex], [latex]x_3[/latex], [latex]\ldots[/latex], [latex]x_{10}[/latex] равна [latex]1[/latex]. Какой наибольшей может быть разность между наибольшим и наименьшим из [latex]10[/latex] чисел [latex]x_1[/latex], [latex]\frac {x_1+x_2} {2}[/latex], [latex]\frac {x_1+x_2+x_3} {3}[/latex], [latex]\ldots[/latex], [latex]\frac {x_1+x_2+x_3+\ldots+x_{10}}{10}[/latex]?

Каков будет ответ, если чисел не [latex]10[/latex], а [latex]n[/latex]?

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

Количество элементов последовательности [latex]x_1[/latex], [latex]x_2[/latex], [latex]x_3[/latex], [latex]\ldots[/latex], [latex]x_n[/latex].

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

Наибольшая разность наибольшего и наименьшего элементов последовательности [latex]x_1[/latex], [latex]\frac {x_1+x_2} {2}[/latex], [latex]\frac {x_1+x_2+x_3} {3}[/latex], [latex]\ldots[/latex], [latex]\frac {x_1+x_2+x_3+\ldots+x_n} {n}[/latex].

Тесты

Входные данные Выходные данные
2 0.5
4 0.75
6 0.833333
8 0.875

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

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

Выведем формулу сразу для [latex]n[/latex] чисел. Сделаем несколько предварительных замечаний.

Обозначим через [latex]y_k[/latex] число [latex]\frac{x_1+x_2+ \ldots+x_k}{k}[/latex], где [latex]k=1, 2, 3, \ldots, n[/latex]. Если прибавить ко всем [latex]x_i[/latex] некоторое число [latex]a[/latex], то вместо чисел [latex]y_i[/latex] мы получим числа [latex]y_i+a[/latex]. Максимальные разности для чисел [latex]y_i[/latex] и для [latex]y_i+a[/latex] совпадают. Поэтому от набора [latex]f\{x_i\}[/latex] с помощью подходящего выбора [latex]a[/latex] можно перейти к такому набору [latex]f\{x_i’\}[/latex], что все [latex]x_i’\le0[/latex], наименьшие [latex]x_i[/latex] равны нулю, а наибольшие — единице. В дальнейшем мы будем рассматривать только такие наборы. Аналогично, если заменить числа [latex]x_i[/latex] на [latex]1-x_i[/latex], то [latex]y_i[/latex] заменятся на [latex]1-y_i[/latex]. Следовательно, от набора [latex]f\{x_i\}[/latex] можно перейти к набору [latex]f\{1-x_i\}[/latex]: максимальные разности между числами [latex]y_i[/latex] и числами [latex]1-y_i[/latex] одинаковы.

Решим задачу. Пусть [latex]y_k[/latex] — наименьшее, а [latex]y_t[/latex] — наибольшее из чисел [latex]f\{y_i\}[/latex].

Если [latex]k<l[/latex], то [latex]y_l-y_k=\frac{k y_k}{l}+\frac{x_{k+1}+\ldots+x_l}{l}-y_k[/latex][latex]=\frac{x_{k+1}+\ldots+x_l}{l}-\frac{l-k}{l} y_k[/latex][latex]\le\frac{x_{k+1}+\ldots+x_l}{l}\le\frac{l-k}{l}\le1-\frac{k}{l}\le1-\frac{1}{n}[/latex]

Если же [latex]k>l[/latex], то [latex]y_l-y_k=\frac{k-l}{k} y_l-\frac{y_{l+1}+\ldots+y_k}{k}\le1-\frac{l}{k}\le1-\frac{1}{n}[/latex].

Из вышесказанного следует, что максимальная разность не больше [latex]1-\frac{1}{n}[/latex]. Набор с такой разностью можно легко указать: [latex]x_1=0[/latex], [latex]x_2=x_3=\ldots=x_n=1[/latex].

Л. Г. Лиманов
Научно-популярный журнал «Квант», 1974 год, №3, страницы 38-39.

Итог:
Формула, которую необходимо использовать для решения этой задачи, это [latex]D=1-\frac{1}{n}[/latex], где D — наибольшая разность элементов последовательности [latex]x_1[/latex], [latex]\frac {x_1+x_2} {2}[/latex], [latex]\frac {x_1+x_2+x_3} {3}[/latex], [latex]\ldots[/latex], [latex]\frac {x_1+x_2+x_3+\ldots+x_n}{n}[/latex], а [latex]n[/latex] — их количество.

Ссылки

ML28. Объём тетраэдра

Задача

Найти объём тетраэдра три стороны которого образованы векторами [latex]\vec {a} = \left( x_a, y_a, z_a \right)[/latex], [latex]\vec {b} = \left( x_b, y_b, z_x \right)[/latex], [latex]\vec {c} = \left( x_c, y_c, z_c \right)[/latex].

Пояснительный рисунок

Пояснительный рисунок к ML28

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

Координаты векторов [latex]\vec {a}[/latex], [latex]\vec {b}[/latex], [latex]\vec {c}[/latex].

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

Объём тетраэдра.

Тесты

Входные данные Выходные данные
[latex]x_a[/latex] [latex]y_a[/latex] [latex]z_a[/latex] [latex]x_b[/latex] [latex]y_b[/latex] [latex]z_b[/latex] [latex]x_c[/latex] [latex]y_c[/latex] [latex]z_c[/latex] [latex]V[/latex]
0 0 1 0 1 0 1 0 0 0.166667
3 6 3 1 3 -2 2 2 2 3
0 0 0 1 3 -2 2 2 2 0

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

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

Так как тетраэдр построен на векторах [latex]\vec {a} = \left( x_a, y_a, z_a \right)[/latex], [latex]\vec {b} = \left( x_b, y_b, z_x \right)[/latex], [latex]\vec {c} = \left( x_c, y_c, z_c \right)[/latex], для данной задачи оптимальным решением будет использовать следующие формулы:

  1. [latex]V = \frac {|\Delta|} {6}[/latex], где [latex]V[/latex] — объём тетраэдра, а [latex]\Delta[/latex] — определитель матрицы.
  2. [latex]
    \Delta =
    \begin{vmatrix}
    x_a & y_a & z_a \\
    x_b & y_b & z_b \\
    x_c & y_c & z_c
    \end{vmatrix}
    = x_a \left(y_b z_c-z_b y_c \right)-x_b \left( y_a z_c-z_a y_c \right)+x_c \left( y_a z_b-z_a y_b \right)
    [/latex].

Итоги:

  • если значение определителя матрицы равно нулю, то либо некоторые из заданных векторов коллинеарны, либо нулевые, либо все они лежат в одной плоскости. Во всех этих случаях тетраэдр не может существовать, и программа выведет [latex]0[/latex];
  • если значение определителя не равно нулю, то программа вычислит объём тетраэдра. В случае, если определитель примет отрицательное значение, программа домножит значение объёма на [latex]-1[/latex], в результате чего оно станет положительным.

Ссылки