e-olymp 2060 Сказка о яблоке

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

Задача

Однажды царь наградил крестьянина яблоком из своего сада. Пошёл крестьянин к саду и видит: весь сад огорожен $n$ заборами, в каждом заборе только одни ворота, и в каждых воротах стоит сторож. Подошёл крестьянин к первому сторожу и показал царский указ, а сторож ему в ответ: «Иди возьми, но при выходе отдашь мне половину тех яблок, что несёшь, и ещё одно». То же ему сказали и второй, и третий сторож и т.д. Сколько яблок должен взять крестьянин, чтобы после расплаты со сторожами у него осталось одно яблоко?

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

Количество заборов $n (1 \leqslant n \leqslant 62)$ в саду.

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

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

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 1 4
2 3 22
3 30 50331646
4 60 3458764513820540926
5 62 13835058055282163710

Решение

Циклы

Последовательность необходимых количеств яблок задается формулой $x_{n+1}=2 \cdot (x_{n}+1);x_{1}=1.$ Мы можем поочередно вычислять элементы последовательности через цикл.

Линейное решение

Преобразуем исходное выражение для $x_{n+1}=2 \cdot x_{n}+2.$ Можно видеть, что каждая следующая итерация увеличивает степень всех двоек входящих в предыдущую на 1 и добавляет 2. Выпишем формулу для $x_{n+m}=2^{m}x_n+2^{m-1}x_n+\cdots+2.$ Можно увидеть, что $x_{n+m}$ содержит слагаемое $2^{m}x$, а так же сумму слагаемых вида $\displaystyle \sum_{i=1}^{m}2^i \displaystyle.$ Если учесть, что $x_{1}=1$, то $\displaystyle x_n=2^{n}+ \sum_{i=1}^{n}2^i \displaystyle=2^{n+1}+2^n-2=2^{n}\cdot(2+1) -2.$ Следовательно формула $n$-го члена — [latex]x_n=3\cdot 2^n-2.[/latex]

Решения на ideone

e-olymp 9. N-значные числа

Задача

Найти количество [latex]N[/latex]-значных чисел, у которых сумма цифр равна их произведению. Вывести наименьшее среди таких чисел для заданного [latex]N[/latex] ([latex]N < 10[/latex]).

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

Число [latex]N[/latex] не превышающее [latex]10[/latex].

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

В выходном файле через пробел вывести [latex]2[/latex] числа: количество искомых чисел и наименьшее среди них.

Тесты

Входные данные Выходные данные
[latex]1[/latex] [latex]10[/latex] [latex]0[/latex]
[latex]2[/latex] [latex]1[/latex] [latex]22[/latex]
[latex]4[/latex] [latex]12[/latex] [latex]1124[/latex]
[latex]5[/latex] [latex]40[/latex] [latex]11125[/latex]
[latex]9[/latex] [latex]144[/latex] [latex]111111129[/latex]

Код программы (Цикл)

Решение задачи (Цикл)

Для решения задачи напишем функции [latex]Sum[/latex] и [latex]Mult[/latex]. Первая считает сумму цифр [latex]N[/latex]-значного числа, а вторая — произведение цифр. С помощью цикла создаем последовательность [latex]N[/latex]-значных чисел и вводим каждое из них в функции [latex]Sum[/latex] и [latex]Mult[/latex]. Если возращаемые значения равны между собой, то мы выводим данное число и присваиваем переменной [latex]b[/latex] значение [latex]false[/latex]. Также продолжаем считать количество [latex]N[/latex]-значных чисел у которых сумма цифр равна их произведению. Также создаем случаи, когда [latex]N=1[/latex], [latex]N=8[/latex] и [latex]N=9[/latex], ибо в цикле эти значения долго считаются. Задача решена.

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

Решение задачи (Массив)

Для решения задачи заранее просчитали все ответы и записали их в массив [latex]x[/latex]. Так как ответы идут подряд составили формулу для вывода искомых значений: для количества чисел у которых сумма цифр совпадает с их произведением — [latex]2n-2[/latex], для минимального числа — [latex]2n-1[/latex]. Задача решена (также задачу можно решить с помощью циклов).

Ссылки

Условие задачи на e-olymp
Код решения на ideone.com (цикл)
Код решения на ideone.com (массив)

e-olymp 165. Симметрия

Задача

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

1) при длине ряда рисунка равной [latex]1[/latex] использовала бусинку первого цвета;

2) при длине ряда рисунка равной [latex]3[/latex] использовала бусинки двух цветов: [latex]1 2 1[/latex];

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

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

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

В первой строке целое число [latex]k[/latex] [latex] (1 ≤ k ≤ 10^9) [/latex] – номер бусинки, цвет которой нужно определить, в ряду рисунка. Нумерация бусинок в ряду начинается с единицы.

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

В первой строке одно целое число – номер цвета заданной бусинки.

 

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 [latex]10[/latex] [latex]2[/latex]
2 [latex]116[/latex] [latex]3[/latex]
3 [latex]1[/latex] [latex]1[/latex]
4 [latex]454[/latex] [latex]2[/latex]
5 [latex]12301230[/latex] [latex]2[/latex]

 

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

 

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

Рассматривая ряды с большим количеством цветов можно заметить закономерность: каждый чётный элемент равен единице, каждый последующий новый цвет будет на месте [latex]n·2[/latex]. Отсюда следует соответствие [latex]n[/latex] и [latex]2^{n-1}[/latex]. Формула для нахождения среднего элемента — [latex]\log_{2}n[/latex]. Программа будет искать средний элемент всегда, пока не найдёт нужный нам. Для чисел, из которых целый логарифм извлечь нельзя, найдем ближайший к нему и от числа отнимем [latex]2[/latex] в степени [latex]\log_{2}n[/latex]. К полученному ответу добавляем единицу, из-за приведённой ранее формулы [latex]2^{n-1}[/latex], и получаем правильный ответ.

Ссылки

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

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

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

Ссылки

A274. Среднее арифметическое всех членов последовательности, кроме одного

Задача из сборника задач по программированию Абрамова С.А. 2000г.
Даны действительные числа [latex]a_{ 1 }[/latex],…,[latex]a_{ 20 }[/latex]. Получить числа [latex]b_{ 1 }[/latex],…,[latex]b_{ 20 }[/latex], где [latex]b_{ i }[/latex] – среднее арифметическое всех членов последовательности [latex]a_{ 1 }[/latex],…,[latex]a_{ 20 }[/latex], кроме [latex]a_{ i }[/latex] ([latex]i[/latex] = 1,2,…,20).

Обобщим задачу для последовательности длины [latex]n[/latex]
Даны действительные числа [latex]a_{ 1 }[/latex],…,[latex]a_{ n }[/latex]. Получить числа [latex]b_{ 1 }[/latex],…,[latex]b_{ n }[/latex], где [latex]b_{ i }[/latex] – среднее арифметическое всех членов последовательности [latex]a_{ 1 }[/latex],…,[latex]a_{ n }[/latex], кроме [latex]a_{ i }[/latex] ([latex]i[/latex] = 1,2,…,[latex]n[/latex]).

Входные данные:
Последовательность действительных чисел.

Выходные данные:
[latex]n[/latex] чисел, [latex]i[/latex]-ое из которых является средним арифметическим всех членов последовательности, кроме [latex]i[/latex]-го ([latex]i[/latex] = 1,2,…,[latex]n[/latex]).

Тесты

Входные данные Выходные данные
1 4 The sequence must consist of at least two elements.
2 1 0 1 The arithmetic average of all elements of this series except the element №i is:
for i = 1: 0.5
for i = 2: 1
for i = 3: 0.5
3 10.1 2.4 11.3 0.8 The arithmetic average of all elements of this series except the element №i is:
for i = 1: 4.8(3)
for i = 2: 7.4
for i = 3: 4.4(3)
for i = 4: 7.9(3)
4 2.5 -1.5 4 -9 1.22 The arithmetic average of all elements of this series except the element №i is:
for i = 1: -1.32
for i = 2: -0.32
for i = 3: -1.695
for i = 4: 1.555
for i = 5: -1

Код на C++

Код на Java

Решение
Для начала, в первом цикле мы читаем числа из входного потока, помещаем их в вектор a и прибавляем к переменной sum, предназначенной для хранения суммы всех чисел последовательности. Последовательность должна состоять как минимум из двух элементов. Чтобы получить среднее арифметическое всех её членов, кроме [latex]i[/latex]-го, достаточно отнять [latex]i[/latex]-й элемент вектора a от значения переменной sum и разделить результат на количество членов такой неполной последовательности, а оно будет на единицу меньше размера вектора a. Таким образом заполняется вектор b, в котором хранятся элементы последовательности [latex]b_{ 1 }[/latex],…,[latex]b_{ n }[/latex], после чего требуемая последовательность выводится.

Код на ideone.com (C++)
Код на ideone.com (Java)
Условие задачи (с.118)

Просто 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, которое задаёт пользователь.

Ссылки

D2655B. Cумма ряда с заданной точностью

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

Тесты

Входные данные Выходные данные
Точность Кол-во взятых членов ряда Значение суммы
1 1 2 1.1666666667
2 1е-5 5 1.1752011684
3 100 1 1
4 1e-10 7 1.1752011936

Код на C++

Код на Java

Решение
Очевидно, ряд является положительным, и общий член ряда стремится к нулю. Ряд сходится по признаку Д’аламбера:
[latex] \lim\limits_{n \rightarrow \infty } \frac{ a_{n+1} }{a_{n}} = \lim\limits_{n \rightarrow \infty } \frac{ \big(2n-1\big)! }{ \big(2n+1\big)! } = \lim\limits_{n \rightarrow \infty } \frac{1}{2n \big(2n+1\big) } =0 < 1[/latex].
Оценим остаток ряда, исходя из того, что [latex]k! > \left( \frac{k}{e} \right) ^{k} , \big(k=1,2,\dots\big) [/latex]:
[latex]R_{N}<\sum\limits_{n=N+1}^\infty \left(\frac{e}{2n-1}\right)^{2n-1}\leq\sum\limits_{n=N+1}^\infty \left(\frac{e}{2N+1}\right)^{2n-1}=\left(\frac{e}{2N+1}\right)^{2N+1}\sum\limits_{i=0}^\infty \left(\frac{e}{2N+1}\right)^{2i}[/latex]
Поскольку при [latex]N\geq1[/latex] [latex]\frac{e}{2N+1}<1[/latex]:
[latex]R_{N} < \left(\frac{e}{2N+1}\right)^{2N+1}\frac{1}{1-\left(\frac{e}{2N+1}\right)^2}[/latex]

В переменной sum хранится текущее значение суммы ряда, в last — последний рассмотренный член ряда. В начале работы программы вводится требуемая точность eps. Можно заметить, что для получения [latex]n[/latex]-го члена ряда достаточно разделить предыдущий на [latex]\left(2n-2\right)\cdot\left(2n-1\right)[/latex], однако необходимо отдельно рассмотреть случай, когда [latex]n = 1[/latex]. В цикле увеличиваем [latex]n[/latex], находим значение следующего члена ряда и прибавляем к sum, пока остаток ряда не станет достаточно маленьким. Оцениваем остаток ряда при помощи функции Rn(int n). Во время её работы может потребоваться возведение числа в большую степень, делаем это по алгоритму бинарного возведения в степень.

Ссылка на код на ideone.com: здесь (C++) и здесь (Java).
Условие задачи (стр. 259)

KM210. Классы эквивалентности некоторой последовательности

Задача
Задача из журнала «Квант» №3, 1974 год (Задача составлена на основе задачи Гуревича)

Рассмотрим последовательности, состоящие из [latex]n[/latex] цифр 1 и 2. В такой последовательности разрешено поменять местами любые две соседние тройки цифр. Две последовательности называем эквивалентными, если одну из них можно перевести в другую несколькими такими перестановками. Сколько существует классов эквивалентности?

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

[latex]n[/latex] — целове число, [latex]k[/latex] — целое число ([latex]k \neq 0[/latex], [latex]k \leq n[/latex]).

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

[latex]m[/latex] — целое число, неполное частное от деления, [latex]q[/latex] — целое число, остаток от деления, [latex]N[/latex] — классы эквивалентности.

Тесты

[latex]n[/latex] [latex]k[/latex] [latex]m[/latex] [latex]q[/latex] [latex]N[/latex]
4 3 1 1 12
8 4 2 0 81

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

Код программы на С++

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

Решение

Решим задачу для последовательностей из [latex]3n[/latex] цифр. Чтобы не возникло путаницы, греческими буквами будем обозначать последовательности, а латинскими – элементы последовательностей. Пусть последовательность [latex]\alpha[/latex] состоит из [latex]3n[/latex] цифр [latex]{\alpha_1, \alpha_2,\ldots,\alpha_{3n}}[/latex]. Разобъем [latex]\alpha[/latex] на три подпоследовательности:
[latex]\alpha_1={\alpha_1,\alpha_4,\alpha_7,\ldots, \alpha_{3k+1},\ldots,\alpha_{3(n-1)+1}}[/latex],
[latex]\alpha_2={\alpha_2, \alpha_5, \alpha_8,\ldots, \alpha_{3k+2},\ldots,\alpha_{3(n-1)+2}}[/latex],
[latex]\alpha_3={\alpha_3, \alpha_6, \alpha_9,\ldots, \alpha_{3k},\ldots,\alpha_{3n}}[/latex].
Такое разбиение будем называть стандартным. Каждая из последовательностей [latex]\alpha_1[/latex], [latex]\alpha_2[/latex], [latex]\alpha_3[/latex] стандартного разбиения состоит из [latex]n[/latex] цифр. Пусть [latex]\beta[/latex] – произвольная последовательностей. Через [latex]|\beta|[/latex] обозначим число единиц в последовательности [latex]\beta[/latex]. Подсчет числа неэквивалентных последовательностей основывается на следующей теореме:
Теорема. Пусть [latex]\alpha[/latex] и [latex]\beta[/latex] – последовательности длины [latex]3n[/latex], ([latex]\alpha_1,\alpha_2,\alpha_3[/latex]) и ([latex]\beta_1,\beta_2,\beta_3[/latex]) – их стандартные разбиения. Для того чтобы последовательности [latex]\alpha[/latex] и [latex]\beta[/latex] были эквивалентны, необходимо и достаточно, чтобы подпоследовательности [latex]\alpha_1[/latex] и [latex]\beta_1[/latex], [latex]\alpha_2[/latex] и [latex]\beta_2[/latex], [latex]\alpha_3[/latex] и [latex]\beta_3[/latex] содержали одинаковое число единиц соответственно, то есть чтобы выполнялось условие
[latex]|\alpha_1|=|\beta_1|[/latex], [latex]|\alpha_2|=|\beta_2|[/latex], [latex]|\alpha_3|=|\beta_3|[/latex].
Покажем сначала, как на основе этой теоремы подсчитывается число неэквивалентных последовательностей, а затем докажем теорему. В силу теоремы каждый класс эквивалентных последовательностей однозначно определяются упорядоченной тройкой чисел ([latex]|\alpha_1|, |\alpha_2|, |\alpha_3|[/latex]). Эти числа смогут принимать любые значения от 0 до [latex]n[/latex]. Следовательно, число неэквивалентных последовательностей длины [latex]3n[/latex] равно числу различных упорядоченных троек целых чисел от 0 до [latex]n[/latex]. Нетрудно видеть, что число таких троек равно [latex] \left(n+1\right)^{3} [/latex].
Доказательство теоремы. Необходимость. Пусть мы переставили в последовательности [latex]\alpha={\alpha_1, \alpha_2,\ldots,\alpha_{3n}}[/latex] две соседние тройки цифр: [latex]a_k, a_{k+1}, a_{k+2}[/latex] и [latex]a_{k+3}, a_{k+4}, a_{k+5}[/latex]. Эту перестановку можно представить следующим образом: сначала поменяли местами цифры [latex]a_k[/latex] и [latex]a_{k+3}[/latex], затем поменяли местами цифры [latex]a_{k+1}[/latex] и [latex]a_{k+4}[/latex] и, наконец, поменяли местами цифры [latex]a_{k+2}[/latex] и [latex]a_{k+5}[/latex]. Число [latex]a_k[/latex] и [latex]a_{k+3}[/latex] – соседние цифры одной и той же подпоследовательности стандартного разбиения [latex]\alpha[/latex]; числа [latex]a_{k+1}[/latex] и [latex]a_{k+4}[/latex] – другой, а числа [latex]a_{k+2}[/latex] и [latex]a_{k+5}[/latex] – третьей. Таким образом, в каждой из подпоследоваетльностей [latex]\alpha_1, \alpha_2, \alpha_3[/latex] стандартного разбиения [latex]\alpha[/latex] мы пeреставили два соседних члена. Значит, если последовательность [latex]\beta[/latex] получена из последовательности [latex]\alpha[/latex] конечным числом перестановок, то есть, если последовательности [latex]\alpha[/latex] и [latex]\beta[/latex] эквивалентны, то подпоследовательности [latex]\beta_1, \beta_2, \beta_3[/latex] стандартного разбиения [latex]\beta[/latex] суть некоторые перестановки подпоследовательностей [latex]\alpha_1, \alpha_2, \alpha_3[/latex] соответственно. Отсюда вытекают равенства (1).
Достаточность. Нам надо доказать, что если последовательности [latex]\alpha[/latex] и [latex]\beta[/latex] длины [latex]3n[/latex] удовлетворяют условию (1), то эти последовательности эквиваленты. Удобнее доказывать более общее утверждение: если последовательности [latex]\alpha[/latex] и [latex]\beta[/latex] длины [latex]k[/latex] удовлетворяют условию (1), то эти последовательности эквивалентны. Доказательство будем вести индукцией по [latex]k[/latex].
1) При [latex]k=1[/latex] последовательности [latex]\alpha[/latex] и [latex]\beta[/latex] содержит по одной цифре. Из условия (1) следует, что эти цифры равны, то есть что последовательности [latex]\alpha[/latex] и [latex]\beta[/latex] просто совпадают.
2) Предположим, что в случае, когда [latex]k=p[/latex], утверждение уже доказано. Докажем его при [latex]k=p+1[/latex]. Итак, пусть [latex]\alpha[/latex] и [latex]\beta[/latex] – последовательности длины [latex]p+1[/latex] и пусть выполнено соотношение (1). Пусть далее, последовательность [latex]\alpha[/latex] состоит из цифр [latex]{\alpha_1, \alpha_2,\ldots,\alpha_{p+1}}[/latex], а последовательность [latex]\beta[/latex] — из цифр [latex]{\beta_1, \beta_2,\ldots,\beta_{p+1}}[/latex].
а) если [latex]\alpha_1 = \beta_1[/latex], то рассмотрим последовательности [latex]\alpha\prime={\alpha_2,\alpha_3,\ldots,\alpha_{p+1}}[/latex] и [latex]\beta\prime={\beta_2,\beta_3,\ldots,\beta_{p+1}}[/latex]. Ясно, что последовательности [latex]\alpha\prime[/latex] и [latex]\beta\prime[/latex] удовлетворяют условия (1). А так как длины этих последовательностей равны [latex]p[/latex], то можно воспользоваться индуктивным предположением. Таким образом, последовательности [latex]\alpha\prime[/latex] и [latex]\beta\prime[/latex] эквивалентны, то есть последовательность [latex]\alpha\prime[/latex] несколькими перестановками можно перевести в последовательность [latex]\beta\prime[/latex]. Эти же перестановки переводят [latex]\alpha[/latex] и [latex]\beta[/latex]. Значит, последовательности [latex]\alpha[/latex] и [latex]\beta[/latex] эквивалентны.
б) Пусть [latex]a_1\neq b_1[/latex], и пусть для определенности [latex]a_1=1[/latex], а [latex]b_1=2[/latex]. Так как [latex]a_1=1[/latex], то [latex]|\alpha|>0[/latex]. Тогда в силу (1) и [latex]|\beta|>0[/latex]. Следовательно, найдется число [latex]q[/latex] такое, что [latex]b_{3q+1} = 1[/latex]. В последовательности [latex]\beta[/latex] поменяем местами соседние тройки цифр [latex]b_{3(q-1)+1}, b_{3q+2}, b_{3q+3}[/latex] и [latex]b_{3(q-1)+1}, b_{3(q-1)+2}, b_{3(q-1)+3}[/latex]. В результате этой перестановки тройка [latex]b_{3(q-1)+1}, b_{3q+2}, b_{3q+3}[/latex] сдвигается на 3 цифры влево. Затем поменяем местами эту тройку с рядом стоящей тройкой цифр [latex]b_{3(q-2)+1}, b_{3(q-2)+2}, b_{3(q-2)+3}[/latex] и так далее; после [latex]q[/latex] перестановок получим последовательность [latex]\beta\prime\prime[/latex], первой цифрой которой будет [latex]b_{3q+1}[/latex], то есть 1. Последовательность [latex]\beta[/latex] и [latex]\beta\prime\prime[/latex] эквивалентны и поэтому, как было доказано выше, удовлетворяют условию (1). Значит, последовательности [latex]\alpha[/latex] и [latex]\beta\prime\prime[/latex] удовлетворяют условию (1). Но первые элементы этих последовательностей совпадают. Таким образом, случай б) свелся к уже разобранному случаю а). Теорема доказана.
Следовательно, если [latex]n=mk+q[/latex], где [latex]0<=q<k[/latex], то число классов эквивалентных последовательностей равно [latex] \left(m+1\right)^{k-q}\left(k+1\right)^{q} [/latex].

Ссылки

Условие задачи (стр.40-41)
Решение задачи на сайте Ideone.com (C++)
Решение задачи на сайте Ideone.com (Java)

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

Задача

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

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

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

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

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

Тесты

Входные данные Выходные данные Входные данные Выходные данные Входные данные Выходные данные
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] — их количество.

Ссылки

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

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

Это нормально чувствовать себя взволнованным и напряженным за день до олимпиады по программированию. Чтобы расслабиться, вы пошли выпить со своими друзьями в соседний паб. Для сохранения остроты ума до следующего дня, Вы решили сыграть в следующую игру. Для начала Ваши друзья написали последовательность [latex] n [/latex] целых чисел [latex] x_{1}, x_{2},\cdots , x_{n} [/latex]. Потом следует  [latex] k [/latex] раундов, на каждом из которых выполняется одна из следующих команд:

  • команда изменения, когда необходимо изменить одно значение в последовательности;
  • команда умножения, когда по заданным значениям [latex] i [/latex] и [latex] j [/latex] необходимо определить, является ли произведение [latex] x_{i}\cdot x_{i+1} \cdot \; \; \cdots \; \; \cdot x_{j-1} \cdot x_{j} [/latex] положительным, отрицательным или равным нулю.

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

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

Каждый тест состоит из нескольких строк. Первая строка каждого теста содержит два числа [latex] n [/latex]  и [latex] k [/latex]   ([latex] 1\leq n,k\leq 10^{5}[/latex]) — количество элементов в последовательности и число раундов в игре. Вторая строка содержит [latex] n [/latex] целых чисел [latex] x_{i} [/latex] — начальные значения последовательности ([latex] -100\leq x_{i}\leq 100[/latex] для [latex]i=1,2, \cdots ,n[/latex]). Каждая из следующих [latex] k [/latex]  строк описывает команду, начинающуюся заглавной буквой  [latex] C [/latex] или [latex] C [/latex]. Если это буква [latex] C [/latex], то строка содержит команду замены, за буквой следуют два числа [latex] i [/latex] и [latex] v [/latex], указывающих на то что [latex] x_{i} [/latex] необходимо заменить на [latex] v [/latex] ([latex] 1\leq i\leq n[/latex] и [latex]-100\leq v\leq 100[/latex]). Если это буква [latex] P [/latex], то строка задает команду умножения, за буквой следуют два числа [latex] i [/latex] и [latex] j [/latex] — необходимо вычислить произведение от [latex] x_{i} [/latex] до [latex] x_{i} [/latex] включительно ([latex] 1\leq i\leq j\leq n [/latex]) . Каждый тест содержит как минимум одну команду умножения.

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

Для каждого теста вывести одну строку, содержащую ответы на все команды умножения. [latex] i [/latex]-ый символ строки является результатом [latex] i [/latex]-ой команды умножения. Если произведение положительно, то вывести символ [latex] + [/latex] (плюс); если произведение отрицательно, то вывести [latex] — [/latex] (минус); если произведение равно нулю, то вывести [latex] 0 [/latex] (ноль).

Тесты

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

-2 6 0 -1

C 1 10

P 1 4

C 3 7

P 2 2

C 4 -5

P 1 4

5 9

1 5 -2 4 3

P 1 2

P 1 5

C 4 -5

P 1 5

P 4 5

C 3 0

P 1 5

C 4 -5

C 4 -5

0+-

+-+-0

5 5

10 -2 0 5 1

C 1 0

P 1 4

C 2 7

P 1 1

C 2 0

00
6 4

0 20 0 30 0 -10

P 2 2

P 2 3

P 3 6

P 2 6

4 3

0 -1 -2 0

P 2 3

C 1 9

P 1 2

3 3

5 2 0

C 1 7

C 3 0

C 1 0

6 5

100 10 55 11 0 -33

P 1 4

C 5 6

C 3 72

C 5 -20

P 5 6

+000

+-

 

++

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

Решение

Данная задача решается при помощи стандартного алгоритма по теме «Дерево отрезков» (данный алгоритм можно посмотреть на сайте e-maxx). Следовательно, при построении дерева сначала считывается массив, а после выполняется построение дерева (от корня). В том случае, если функция, строящая дерево, вызывалась от листа,  все значения элементов массива записываются в дерево как [latex]1[/latex], если элемент больше нуля, если меньше нуля, то записывается как [latex]-1[/latex], а в случае равенства элемента нулю, он записывается [latex]0[/latex] (нулём).  В ином случае (если функция вызывалась не от листа), она начинает вызываться рекурсивно от каждого из двух сыновей и перемножает вычесленные значения.

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

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

Далее  (в программе) идёт процесс построения дерева и выполнение действий, удовлетворяющих команды, описанные в уловии задачи.

Ссылки

  • Рабочий код на Ideone.com
  • Засчитанное решение на e-olymp.com
  • При ришении данной задачи был использован материал по структурам данных «дерево отрезков» с сайта e-maxx.ru
  • Задача взята с сайта e-olymp.com

A285

Задача

Даны действительные числа [latex]{ a }_{ 1 }[/latex]…[latex]{ a }_{ n }[/latex] .  Если в результате замены отрицательных членов последовательности [latex]{ a }_{ 1 }[/latex]…[latex]{ a }_{ n }[/latex] их квадратами члены будут образовывать неубывающую последовательность, то получить сумму членов исходной последовательности ; в противном случае получить их произведение.

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

Последовательность

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

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

Тесты

 

Последовательность Результат
1 1 2 3 4 10
2 1 2 -3 4 -24
3 1 -2 5 6 7 8 25
4 -1 -1 -2 -3 -4 -5 -16

Код

Решение

Предлагаю следующее решение. Записываем каждый член последовательности в элемент типа vector. Сразу находим их сумму и произведение. Затем заменяем каждый отрицательный элемент его квадратом и проверяем возрастающая ли последовательность. Если да — то выводим сумму, если нет — то произведение.

Код на ideone.

A287

Задача A287

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

Даны целые числа [latex] a_{1}\dots a_{n} [/latex]. Все члены последовательности с четными номерами, предшествующие первому по порядку члену со значением [latex] max(a_{1}\dots a_{n}) [/latex], домножить на  [latex] max(a_{1}\dots a_{n}) [/latex].

Тестирование

Входные данные Выходные данные
1. 1 2 3 4 3 2 1 1 8 3 4 3 2 1
2. 1 2 3 4 4 2 5 5 3 3 2 1 1 10 3 20 4 10 5 5 3 3 2 1
3. 11 4 6 7 9 11 4 6 7 9
4. 9 8 10 1 2 4 5 4 6 13 9 104 10 13 2 52 5 52 6 13
5. -10 -4 -6 -7 -3 0 -1 -20 -10 0 -6 0 -3 0 -1 -20

Реализация

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

Считываем все целые числа до конца входного потока и записываем их в вектор [latex] a [/latex]. Затем:

  1. Сравниваем между собой каждый элемент вектора, и если находится большее значение, то запоминается номер данного элемента.
  2. Далее проходим все члены последовательности, предшествующие первому по порядку члену с максимальным значением.
  3. Умножаем все элементы с четными номерами на  [latex] max(a_{1}\dots a_{n}) [/latex].

Ссылки

Код на ideaone.

A294

С.А.Абрамов. Задачи по программированию.

Задача

Даны действительные числа [latex]r_{1},\ldots,r_{n}[/latex], среди которых заведомо есть как отрицательные, так и не отрицательные. Получить [latex]x_{1}y_{1}+\ldots+x_{s}y_{s}[/latex], где [latex]x_{1},\ldots,x_{p}[/latex] — отрицательные члены последовательности [latex]r_{1},\ldots,r_{n}[/latex], взятые в порядке следования, [latex]y_{1},\ldots,y_{q}[/latex] — неотрицательные члены, взятые в обратном порядке, [latex]s=min\left ( p,q \right )[/latex] .

Тесты

 Входные данные Выходные данные
 -1 1  -1
 -1  0
-1 -1  0
 1 2 -5 10 -2  -54
 4 6 3 4 -8 2 7 5  -40

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

ideone.com

Решение

Считывая числа из входного потока, выполняем проверку и записываем положительные в вектор [latex]y[/latex], отрицательные — в вектор [latex]x[/latex]. Затем вычисляем [latex]s[/latex]. Вычисляем [latex]x_{1}y_{1}+\ldots+x_{s}y_{s}[/latex].

A293

Задача

Даны целые числа [latex]a_1,\ldots,a_n[/latex].
Если в данной последовательности ни одно четное число не расположено после нечетного,
то получить все отрицательные члены последовательности, иначе –все положительные. Порядок следования чисел в обоих случаях заменяется на обратный.

Тесты

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

 Алгоритм

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

Код

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).