e-olymp 1281. Простая задачка Шарика

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

«Сколько разных последовательностей длины [latex]n[/latex] можно составить из клеток распиленных шахматных досок, если ни в одной из последовательностей никакие три белых поля не должны идти подряд»?

Матроскин так и не решил ещё эту задачку, так что ваша задача помочь ему.

Входные данные
Длина последовательности [latex]n[/latex] ([latex]n ≤ 64[/latex]).

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

Тесты

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

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

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

Решение
Для решения задачи воспользуемся рекуррентным соотношением [latex]f \left( n \right) = f \left( n-1 \right)+f \left( n-2 \right)+f \left( n-3 \right)[/latex], где [latex]f[/latex] — функция, возвращающая ответ на поставленную задачу. Из условия следует, что для любой последовательности рассматривать следует только три варианта её последних элементов: …Ч, …ЧБ, …ЧББ (где Ч — чёрная клетка, Б — белая), так как в случае, если конец последовательности квадратов содержит только чёрный квадрат, чёрный и белый или чёрный и два белых, то нарушить последовательность могли только предшествующие этим окончаниям, которые имеют длины 1, 2, и 3 соответственно, последовательности. Именно это и влечёт справедливость указанного выше рекуррентного соотношения. Значения [latex]f \left( n \right)[/latex] при [latex]n \le 3[/latex] можно вычислить вручную и сохранить, а остальные вычислять в цикле с использованием предыдущих, вплоть до получения требуемого.

Ссылки
Код на ideone.com (C++)
Код на ideone.com (Java)
Задача с сайта e-olymp.com.
Засчитанное решение.

e-olymp 4493. Трое из Простоквашино 3

Задача

[latex]-[/latex] Печкин, а я научился работать с деревом отрезков.

[latex]-[/latex] Заняться тебе нечем просто, Шарик. Лучше бы помог мне письма разносить.

[latex]-[/latex] Ну, Печкин, я уже даже выполнил задания Дяди Федора и Кота Матроскина, только этот Матроскин не захотел проверять, правильно ли я сделал.

[latex]-[/latex] Ну ладно, давай я проверю, что там надо было сделать?

[latex]-[/latex] У меня был массив чисел и множество запросов – представляющих собой либо запрос на изменение в массиве, либо содержащий число, для которого мне нужно было найти такой промежуток [[latex]l;r[/latex]], что максимум на этом промежутке был бы равен заданному числу. Можешь прочитать предыдущую задачу.

[latex]-[/latex] Разберемся…

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

В первой строке содержится одно число [latex]N[/latex] ([latex]1≤N≤106[/latex]) – количество элементов в массиве. В следующей строке находится [latex]N[/latex] целых, неотрицательных чисел, не превосходящих 109 – сами элементы массива. Затем следует число [latex]M[/latex] ([latex]1≤M≤105[/latex]) – количество запросов. Затем [latex]М[/latex] строк, первое число в каждой из которых означает тип запроса: если оно равно единице, то далее следует единственное число [latex]x[/latex], и Шарику надо было найти два числа [latex]l[/latex] и [latex]r[/latex], такие, что максимум на промежутке [[latex]l;r[/latex]], был равен [latex]x[/latex]. Если же тип запроса равен двум, то далее следует два числа [latex]pos[/latex] и [latex]val[/latex] и это значит, что элемент массива, стоящий на позиции [latex]pos[/latex], теперь изменен и он стал равен значению [latex]val[/latex]. Далее для каждого запроса с номером один содержится по строке с двумя числами [latex]l[/latex] и [latex]r[/latex] – ответы Шарика.

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

Для каждого ответа Шарика выведите [latex]»Yes»[/latex], если он ответил правильно и [latex]»No»[/latex], если Шарик ошибся. Заметьте, что хотя в предыдущей задаче было необходимо найти минимальные числа [latex]l[/latex] и [latex]r[/latex], здесь Печкин проверять этого не будет.

Тесты

Входные данные Выходные данные
5
1 2 4 3 1
5
1 4
1 5
2 3 5
1 1
1 4
1 3
1 5
5 5
2 4
Yes
No
Yes
No

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

Решение

Учитывая то, что максимум является ассоциативной операцией, для решения задачи
воспользуемся универсальным деревом отрезков.
Так как во входном потоке сперва идут требуемые результаты максимума на
отрезке, затем модификации отрезка и в конце отрезки, для которых необходимо
совпадение требуемого и реального максимума, то не обойтись без
запоминания/меморизации входных данных.
После этого задача упрощается, и для решения остаётся только пересматривать
все события, и сопоставлять требуемые резальтаты максимума на заданных
отрезках с реальными.

Ссылки
Код на ideone.com
Задача с сайта e-olymp.com.
Засчитанное решение.

e-olymp 131. Слова

Задача
Из слова «молоко» можно составить слово «коло». Сколько слов из заданного словаря можно составить, используя буквы заданного слова, причем каждую букву можно использовать не более одного раза.

Тесты

Входные данные Выходные данные
молоко
4
мило
коло
коліно
око
2
приветствие
8
ветер
треск
спирт
трепет
перерыв
север
текст
привести
5

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

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

Решение
Создаем вектор [latex]D[/latex], в котором будем хранить количество каждого символа в слове, и обнуляем его. Тип [latex]char[/latex] вмещает максимум [latex]256[/latex] значений (в диапазоне от [latex]-127[/latex] до [latex]126[/latex]). Класс [latex]string[/latex] состоит из символов типа [latex]char[/latex], поэтому для того, чтобы «вернуть» значения этих символов к положительным (в чём возникает необходимость при обращении к элементам вектора), к ним прибавляется [latex]127[/latex].
Потом считаем число каждого символа в слове. Создаем переменную, в которой будем хранить число слов из словаря, которое можно составить, используя символ первого входного слова. Предполагаем, что слово [latex]words[/latex] составить можно ([latex]words=true[/latex]). Считаем использованные символы из первой входной строки и, если вдруг число стало отрицательным, то слово составить нельзя, обнуляем переменную [latex]words[/latex] и останавливаем цикл. К переменной [latex]rez[/latex] прибавляем переменную [latex]words[/latex] и выводим [latex]rez[/latex].

Ссылки
Код на ideone.com (C++)
Код на ideone.com (Java)
Задача с сайта e-olymp.com.
Засчитанное решение.

А273. Центр тяжести системы

Задача. Задача из сборника задач по программированию С.А.Абрамова за 2000 год.
Система из 25 материальных точек в пространстве задана с помощью последовательности действительных чисел [latex]x_{1}, y_{1}, z_{1}, p_{1}, x_{2}, y_{2}, z_{2}, p_{2},\ldots,x_{25}, y_{25}, z_{25}, p_{25}[/latex], где [latex]x_{i}, y_{i}, z_{i}[/latex] — координаты [latex]i[/latex]-ой точки, а [latex]p_{i}[/latex] — ее вес ([latex]i=1,2,\ldots,25[/latex]). Получить координаты центра тяжести системы, а также расстояние от центра тяжести до всех точек системы.

Входные данные:
[latex]x, y, z, p[/latex] — координаты и вес точки.

Выходные данные:
[latex]sum(x,y,z)[/latex] — координаты центра тяжести системы, [latex]l[/latex] — расстояние от центра тяжести до одной из точек.

Тесты:

Входные данные Выходные данные
[latex]x[/latex] [latex]y[/latex] [latex]z[/latex] [latex]p[/latex] [latex]sum[/latex]
[latex](x[/latex]
[latex]y[/latex]
[latex]z)[/latex]
[latex]l[/latex]
2 2 1 2
3 1 2 1
2.33333 1.66667 1.33333 0.57735
1.1547
7 10 5 20
1 0 3 1
43 50 6 3
0 9 0 200
4 8 15 66
1.84138 9.23448 3.83103 5.34452
9.3099
57.9704
4.25705
11.4424

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

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

Решение
В цикле «[latex]while[/latex]» читаем числа из входного потока и запоминаем координаты точек в векторе [latex]а[/latex], к переменной [latex]sum[/latex] прибавляем эти координаты, умноженные на [latex]p[/latex].
Потом подсчитываем координаты центра тяжести системы и выводим эти координаты.
В цикле «[latex]for[/latex]» берем из вектора координаты одной из точек системы, считаем расстояние от центра тяжести до одной из точек системы и выводим это расстояние.

Ссылки
Код в ideone.com (C++)
Код в ideone.com (Java)
Условие задачи (с.117)

MS10. Зашифровка текста

Задача

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

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

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

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

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

Тесты

Входные данные Выходные данные
Where is the table? a8 c0 a5 d7 b2 92 fb 88 a8 dc b4 d1 f1 85 e4 86 ea 8f b0
What a nice day! a8 c0 a1 d5 f5 94 b4 da b3 d0 b5 95 f1 90 e9 c8

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

Решение

Выделяем участки памяти для символьных переменных, считываем первый символ и его инвертируем, затем выводим в шестнадцатеричной системе счисления с пробелом.
Используем цикл «while»: пока считываются данные в переменную x2, XORим предыдущий и новый символы, выводим новый символ и запоминаем новый зашифрованный символ, который становится предыдущим.

Ссылки

Условие задачи
Решение задачи на сайте Ideone.com

A324. Делители одного числа, взаимно простые с другим

Задача

Даны целые числа [latex]p[/latex] и [latex]q[/latex]. Получить все делители числа [latex]q[/latex], взаимно простые с числом [latex]p[/latex].

Тесты

[latex]q[/latex] [latex]p[/latex] Все делители числа [latex]q[/latex], взаимно простые с числом [latex]p[/latex]
40 15 1 2 4 8
87 3 1 29

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

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

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

Решение

Воспользуемся рекурсивной реализацией алгоритма Евклида. Пусть [latex]m[/latex] и [latex]n[/latex] — не равные нулю целые неотрицательные числа, и пусть [latex]m\geq n[/latex]. Тогда, если [latex]n=0[/latex], [latex]GCD(n,m)=m[/latex], а если [latex]n\neq 0[/latex], то для числе [latex]m[/latex], [latex]n[/latex] и [latex]k[/latex], где [latex]k[/latex] — остаток от деления [latex]m[/latex] и [latex]n[/latex], выполняется равенство [latex]GCD(m,n)=GCD(n,k)[/latex].
Для нахождения делителей числа [latex]q[/latex] взаимно простых с [latex]p[/latex], программа проверяет остатки от деления [latex]q[/latex] на все числа [latex]i[/latex] от [latex]1[/latex] до [latex]q[/latex]. Если остаток равен нулю, то число [latex]i[/latex] является делителем [latex]q[/latex]. Для каждого такого числа выполняется поиск наибольшего общего делителя (НОД — Greatest common divisor, GCD) [latex]i[/latex] и [latex]p[/latex] по алгоритму Евклида. Если найденный наибольший делитель равен 1, то числа [latex]i[/latex] и [latex]p[/latex] взаимно простые.

Ссылки

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

D2580. Сходимость ряда

Задача. Пользуясь признаками сравнения, Даламбера или Коши, исследовать сходимость ряда: [latex]\frac{1!}{1}+\frac{2!}{2^2}+\frac{3!}{3^3}+\ldots+\frac{n!}{n^n}+\ldots[/latex]

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

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

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

[latex]sum[/latex] — сумма.

Тесты

Входные данные Выходные данные
1 Сумма: 1
Числитель: 1
Знаменатель: 1
3 Сумма: 1.72222
Числитель: 6
Знаменатель: 9
20 Сумма: 1.87985
Числитель: 2.4329e+18
Знаменатель: 5.24288e+24

Код на C++

Код на Java

Решение

Используем цикл [latex]for[/latex]: высчитываем [latex]i[/latex]-тый слагаемый, и добавляем его в сумму. В цикле высчитываем числитель, добавляем в сумму [latex]i[/latex]-тый слагаемый и домножаем числитель [latex]i[/latex]-того слагаемого на значение счётчика.
Воспользуемся веб-приложением и посчитаем сумму ряда.

Ссылки

Условие задачи (стр.251)
Решение задачи на сайте Ideone.com (C++)
Решение задачи на сайте Ideone.com (Java)
Сходимости ряда

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)

KM11. 44 дерева по чижу на каждом

Задача
Задача из журнала «Квант» №11-1970г.

На 44 деревьях, расположенных по окружности, сидели 44 веселых чижа (на каждом дереве по чижу). Время от времени два чижа одновременно перелетают на соседние деревья в противоположных направлениях (один – по часовой стрелке, второй – против). Докажите, что чижи никогда не соберутся на одном дереве. А если чижей и деревьев [latex]n[/latex]?

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

[latex]n[/latex] – количество деревьев.

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

«Yes» или «No».

Тесты

Входные данные Выходные данные
10 No
15 Yes

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

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

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

Решение

Решаем задачу сразу для [latex]n[/latex] чижей и [latex]n[/latex] деревьев. Обозначим количество чижей на [latex]k[/latex]-м дереве в какой-нибудь момент времени через [latex]a_{k}[/latex] (на первом дереве – [latex]a_{1} [/latex], на втором – [latex]a_{2}[/latex] и т.д.). Рассмотрим выражение [latex]S=1a_{1}+2a_{2}+\ldots+ka_{k}+\ldots+na_{n}[/latex]. Когда два чижа перелетают на соседние деревья в противоположных направлениях, то [latex]S[/latex] либо не меняется, либо меняется на [latex]n[/latex].
Действительно, пусть какой-то один чиж перелетает с [latex]k[/latex]-го дерева на следующее по часовой стрелке. Тогда в сумме [latex]S[/latex] меняются два слагаемых. Если [latex]k<n[/latex], то меняются [latex]k-1[/latex] и [latex]k+1[/latex] — е слагаемые, и их сумма становится равной [latex]k(a_{k}-1)+(k+1)(a_{k+1}+1)=ka_{k}+(k+1)a_{k+1}+1[/latex], то есть увеличивается нa 1. Если [latex]k=n[/latex], то меняется [latex]n[/latex] -е и первое слагаемые, а их сумма [latex]n(a_{n}-1)+1(a_{1}+1)=na_{n}+a_{1}-(n-1)[/latex] уменьшается на [latex]n-1[/latex]. Наоборот, если чиж перелетает на соседнее дерево против часовой стрелки, то сумма или уменьшается на 1, или увеличивается на [latex]n-1[/latex]. Поэтому, когда два чижа одновременно перелетают на соседние деревья (один по часовой стрелки, другой — против), то сумма [latex]S[/latex] или не меняется вовсе, или меняется на [latex]n[/latex]. В начальный момент времени на каждом дереве сидело по одному чижу, [latex]S=1\cdot1+2\cdot1+\ldots+n\cdot1=1+2+\ldots+n=\frac{n\left(n+1\right)}{2}[/latex].
Таким образом, после любого числа перелетов сумма будет равна [latex]\frac{n(n + 1)}{2} + np[/latex], где [latex]p[/latex] – некоторое целое число. Если бы все чижи собрались на каком-то одном [latex]q[/latex]-дереве, то [latex]S[/latex] было бы равно [latex]nq[/latex], то есть выполнялось бы равенство [latex]\frac{n(n + 1)}{2} + np = nq[/latex], откуда [latex]n + 1 + 2p = 2q[/latex], [latex]n=2(q-p)-1[/latex].
Таким образом, если [latex]n[/latex] четно, например, [latex]n[/latex] = 44, то чижи не смогут собраться на одном дереве. Покажем, что при нечетных [latex]n[/latex] это может случиться.
Рассмотрим исходную ситуацию, когда на каждом дереве сидело по одному чижу. «Прикажем» одному чижу сидеть на месте и назовем его «неподвижным». Разобьем оставшихся чижей на пары сидящих на одинаковом расстоянии в [latex]r[/latex] перелетов от неподвижного в ту и другую сторону ([latex]r=1,2,\ldots,\frac{n-1}{2}[/latex]).
Ясно, что каждая такая пара может за [latex]r[/latex] перелетов попасть на то дерево, гдe сидит неподвижный чиж.
Приведенное решение типично для задач, в которых требуется выяснить, можно ли в результате ряда каких-то преобразований получить определенный результат. В данном случае преобразование – это перелет двух чижей в противоположных направлениях, и мы хотим выяснить, могут ли в результате все чижи собраться на одном дереве. Чтобы доказать, что можно, достаточно привести пример, как это делать. Доказать, что ни при каких преобразованиях нельзя получить требуемый результат, часто бывает удобно так: найти какую-то величину, которая сохраняется при всех рассматриваемых преобразованиях и для которой начальное значение отличается от требуемого в конечном состоянии (такая величина называется инвариантом данных преобразований). В нашей задаче такой величиной является остаток от деления суммы [latex]S[/latex] на [latex]n[/latex].

Ссылка: Условие задачи
Ccылка: Решение задачи на сайте Ideone.com (C++)
Ccылка: Решение задачи на сайте Ideone.com (Java)

ML25. Расстояние между двумя точками

Задача

Вычислить расстояние между двумя точками [latex]A\left(x_a,y_a,z_a\right)[/latex] и [latex]B\left(x_b,y_b,z_b\right)[/latex] по известным координатам.

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

Координаты: [latex]x_a, y_a, z_a, x_b, y_b, z_b[/latex].

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

[latex]|AB|[/latex] — расстояние между точками [latex]A[/latex] и [latex]B[/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]|AB|[/latex]
0 1 0 1 0 1 1.73205
0 0 0 0 0 0 0
6 6 4 4 2 8 6

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

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

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

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

Вычисляем [latex]|AB|[/latex] между точками [latex]A\left(x_a,y_a,z_a\right)[/latex] и [latex]B\left(x_b,y_b,z_b\right)[/latex] по такой формуле : [latex]|AB|=\sqrt{(x_b-x_a)^2+(y_b-y_a)^2+(z_b-z_a)^2}[/latex] и получаем результаты.

Ссылка: Условие задачи
Ссылка: Решение задачи на сайте Ideone.com (C++)
Ссылка: Решение задачи на сайте Ideone.com (Java)