MS1.Количество чисел в потоке

Антон Куперман
Антон Куперман

Latest posts by Антон Куперман (see all)

Задание

Сосчитайте количество чисел во входном потоке.

Тесты

Вход Выход
20 16 11 3
17 22.4 41.9 74.5 4
122 347 1567 21 40 5
13 28 17 8 2 5

Код на C++

Код на Java

 

Решение

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

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)

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^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^{k-q}(k+1)^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=11+21+\ldots+n*1=1+2+\ldots+n=\frac{n(n+1)}{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)