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 112. Торт

Latest posts by Илья Черноморец (see all)

В честь дня рождения наследника Тутти королевский повар приготовил огромный праздничный торт, который был подан на стол Трем Толстякам. Первый толстяк сам мог бы целиком его съесть за $t_1$ часов, второй — за $t_2$ часов, а третий — за $t_3$ часов.

Сколько времени потребуется толстякам, чтобы съесть весь праздничный торт вместе?

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

Единственная строка содержит три целых неотрицетельных числа $t_1$, $t_2$ и $t_3$, каждое из которых не превосходит $10000$.

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

Вывести время в часах, за которое толстяки вместе могут съесть торт. Результат округлить до двух десятичных знаков.

TESTS

$t_1$

$t_2$

$t_3$

$t$

3 3 3 1.00
4 67 50 3.51
228.22 8 2.28 1.76
1577 157.7 15.77 14.21

C ветвлением:

Без ветвления:

 

Решение с ветвлением

Первый толстяк ест со скоростью один торт за $t_1$ часов. Аналогично и с остальными толстяками. Тогда из торта следует вычесть те части, которые съест каждый, чтобы торта не осталось. Получается уравнение
$1-\frac{t}{t1}-\frac{t}{t2}-\frac{t}{t3}=0;$
$\frac{t}{t1}+\frac{t}{t2}+\frac{t}{t3}=1;$
$\frac{tt_2t_3+tt_1t_3+tt_1t_2}{t_1t_2t_3}=1;$
$t(t_1t_2+t_2t_3+t_1t_t3)=t_1t_2t_3;$
$t = \frac{t_1t_2t_3}{t_1t_2+t_2t_3+t_1t_t3};$
Рассматриваем случай, при котором одна из переменных равна нулю, тогда выводим ноль. В противном случае выводим значение $t$ с округлением до сотых.

Решение без ветвления

Так как по условию задачи первый толстяк съедает весь торт за $t_1$ часа, второй — за $t_2$ часа и третий — за $t_3$ часа, то их скорость поедания торта составит $\frac{1}{t_1}$, $\frac{1}{t_2}$ и $\frac{1}{t_3}$ торта в час соответсвенно. Если толстяки будут есть торт одновременно, то в час они будут съедать $(\frac{1}{t_1}+\frac{1}{t_2}+\frac{1}{t_3})$ часть торта. Тогда весь торт будет съеден за $\frac{1}{\frac{1}{t_1}+\frac{1}{t_2}+\frac{1}{t_3}}$ часов.
Затем нужно вывести результат, округлённый до двух десятичных знаков. Для этого воспользуемся функцией setprecision() и её аргументом fixed

Ссылки

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

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]. Этот побочный эффект данного нами определения массива решает эту ситуацию и завершает решение задачи.

Ссылки

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] отличны от вышеупомянутых. Если же условия будут соблюдаться, то задача выведет соответствующее значение радиуса.

Ссылки

KM63

Курьянов Павел
Курьянов Павел

Latest posts by Курьянов Павел (see all)

Задача М63 из журнала «Квант» №1 за 1971 год, стр.39. Автор А.А. Кириллов.
Можно ли из плиток размером 1х2 сложить четырехугольник размером [latex] M\times N [/latex] так, чтоб при этом не было ни одного прямого «шва», соединяющего стороны квадрата и идущие по краям плиток.
km63

Изображение как на рисунке не годиться так как тут есть «шов» [latex] AB [/latex].

Входные данные
Размеры четырёхугольника [latex] M [/latex] и [latex] N [/latex].

Выходные данные
Возможно ли это сделать [latex] Yes [/latex] или не возможно [latex] No [/latex].

Тесты

вводимые данные выводимые данные
M N возможно || не возможно
2 16 no
6 6 no
66 69 yes
16 5 yes
99 71 no
7 7 no
78 77 yes
7 8 yes

Код задачи

Решение
Легко доказать, что прямоугольники [latex] {2\times m}, [/latex] [latex] {3\times m}, [/latex] [latex] {4\times m} [/latex] разрезать таким образом нельзя. Если же [latex] {m\geq{5}}, [/latex] [latex] {n\geq{5}} [/latex] и [latex] mn [/latex] четно (последнее условие разумеется необходимо), то во всех случаях кроме [latex]{6\times 6}[/latex] нужное разбиение существует.
Ссылки
ideone