Category Archives: 4. Потоковая обработка

В этот раздел входят задачи, читающие и обрабатывающие некоторый поток входных данных. В основном данные будут поступать или записываться в стандартные потоки ввода вывода. Основная особенность этих задач состоит в том, что поступающие данные не следует запоминать — после обработки очередного значения программа никогда к нему не возвращается. Такие задачи следует отличать от задач в которых входные данные необходимо сначала сохранить в памяти, а потом выполнить их обработку.
Например, если Вам нужно отыскать самое большое число во входном потоке, то это потоковая задача — запоминать нужно только текущее предполагаемое максимальное значение.
Если же в задаче, например, требуется вывести числа из входного потока в измененном порядке (в обратном порядке, по возрастанию или убыванию), то задача к потоковым не относится. Все числа нужно хранить в оперативной памяти во время выполнения программы. Такие задачи относятся к разделу «Массивы» или другим структурам данных.
В некоторых задачах требуется, например, поменять местами чётные и нечётные буквы вводимого текста. Естественно, хранить весь текст необходимости нет, но нужно запоминать предыдущую букву. Это тоже потоковая задача — используется всего одна или несколько переменные простых типов,
Формально задачи этого типа определяются так — последовательная обработка входного потока данных сколь угодно длинного потока входных данных при использовании постоянного объёма оперативной памяти.

e-olymp 9104. Плоская земля

by

0

Условие

Система образования Вас снова подвела — Ваше предложение о включении модели «Плоская Земля» в программу старшей школы было отклонено в шестой раз подряд. Коррумпированные ученые Круглой Земли отказываются прислушиваться к Вашим аргументам и игнорируют кучу данных, подтверждающих Ваши заявления.

Настало время урегулировать этот конфликт раз и навсегда. Вы путешествовали по всему земному шару и встречались с ведущими учеными Плоской Земли. Вместе Вы разработали блестящий план.

Ради противоречия предположим, что Земля — это сфера в трехмерном пространстве. Тогда, если предположить, что небо является бесконечной плоскостью в пространстве, такая Земля явно бросит на него тень! Эта тень была бы ортогональной проекцией Земли на небо. Поскольку в действительности на небе нет видимой тени, мы достигаем противоречия.

Осталось только выполнить расчеты. По заданным центру и радиусу Земли, а также уравнению небесной плоскости в виде [latex]ax + by + cz + d = 0[/latex] необходимо определить площадь ортогональной проекции Земли на небо. Обратите внимание, что в некоторых Ваших экспериментах Земля может пересекать небо — Вы не хотели бы вводить слишком много ненужных предположений, не так ли?

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

Первая строка содержит количество тестов [latex]n[/latex] [latex]\left(1\leqslant n\leqslant 10\right)[/latex]. Далее следует описание тестов.

Каждый тест описывается строкой, содержащей восемь целых чисел [latex] x, y, z, r, a, b, c, d [/latex]. Они обозначают координаты центра Земли, его радиус и уравнение неба соответственно. Все числа от [latex]1[/latex] до [latex]1000[/latex] включительно.

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

Для каждого теста выведите одно число: площадь проекции с не менее [latex]6[/latex] десятичными цифрами.

Тесты

№ Входные данные Выходные данные
1 1
2 3 5 7 1 2 4 8		 153.938040026
2 2
2 3 5 7 1 2 4 8
4 5 3 9 2 6 8 10		 153.938040026
254.469004941
3 3
2 3 5 7 1 2 4 8
4 5 3 9 2 6 8 10
23 45 87 8 100 200 65 89		 153.938040026
254.469004941
201.06192983

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

Решение

Для начала, определимся, чего от нас хотят авторы задачи.  По сути, самой важной частью условия является третий абзац, из которого мы узнаем, что Земля — сфера, а также, что ортогональная проекция Земли на небо — это тень от Земли на небесную плоскость. Но, если существует тень, значит существует и светило (Солнце). Для того, что бы стало более понятно, проведём эксперимент. Представим, что Земля — это сфера, Солнце — это настольная лампа (Важно! Лампа будет давать параллельный пучок лучей), а небесная плоскость — это обычный лист бумаги. (Важно! В данном эксперименте размеры светила и размеры «Земли» будут совпадать). При направлении света на сферу, на лист бумаги будет отбрасываться тень (площадь которой нам и надо найти). Итак, как мы видим на рисунке, площадь проекции — это ничто иное, как площадь сечения сферы, проходящее по центральной оси этой сферы. А площадь сечения сферы по центральной оси — это площадь круга, которая вычисляется по формуле [latex]S=\pi r^2[/latex]. Таким образом, что бы рассчитать площадь проекции, из всех входящих данных нам понадобится только радиус Земли. Что бы у нас было число [latex]\pi[/latex], мы воспользуемся классом Math.

e-olymp 6261. Устройство для анализа бюллетеня

by

0

Задача

Избирательная комиссия Флатландии готовится к президентским выборам. Чтобы свести к минимуму человеческий фактор при подсчете голосов, они решили разработать автоматическое устройство для анализа бюллетеней (УАБ).

На пост президента баллотируются $n$ кандидатов. Бюллетень содержит одно квадратное поле для каждого кандидата. Избиратель должен отметить ровно одно из полей. Если поле не помечено или имеется два или более отмеченных поля, бюллетень недействителен. Каждый избиратель ставит свой бюллетень на специальный сканер в УАБ. Сканер анализирует отметки в бюллетене и создает специальную строку голосования из $n$ символов: ‘X’ для отмеченного поля и ‘.’ для немаркированного. Теперь строки голосования должны быть проанализированы, чтобы получить отчет. Ваша задача — разработать генератор отчетов для УАБ.

С учетом строк голосования для всех бюллетеней Ваша программа должна распечатать отчет о голосовании. Кандидаты в протоколе должны быть расположены в порядке убывания количества голосов. Если два кандидата имеют одинаковое количество голосов, они должны иметь тот же порядок, что и в бюллетене для голосования. Для каждого кандидата рассчитайте его / ее результат в процентах (если кандидат получил $p$ голосов, результат в процентах составляет $\frac{100 \cdot p}{m}$ ). В последней строке отчета должен быть указан процент недействительных бюллетеней.

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

Первая строка содержит два целых числа $n$ и $m (2 \leqslant n \leqslant 10, 1 \leqslant m \leqslant 1000$) — количество кандидатов и количество бюллетеней. Следующие $n$ строк содержат фамилии кандидатов. Каждое имя представляет собой строку не более $100$ английских букв. Нет ни одного кандидата с именем «Invalid».

Затем следуют $m$ строк, каждая из которых содержит одну строку голосования.

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

Выведите $n+1$ строк. Сначала выведите результаты для кандидатов в процентах. Для каждого кандидата выведите его / ее фамилию, затем пробел, а затем его / ее результат в процентах и знак процента ‘$\%$’. В последней строке должен быть указан процент недействительных бюллетеней: слово «Invalid», за которым следуют пробел, процент недействительных бюллетеней и знак процента.

Округлите все числа до двух цифр после десятичной точки. Если число находится точно посередине двух представимых чисел, выведите большее (например, выведите $«12.35»$ для $12.345$).

Тесты

№

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

Выходные данные
1 4 7
Loudy
Apples
Dogman
Miller
.X..
X…
….
..X.
..XX
..X.
..X.		 Dogman 42.86%
Loudy 14.29%
Apples 14.29%
Miller 0.00%
Invalid 28.57%
2 4 10
Loudy
Apples
Dogman
Miller
X………………..
X…………………..
X………………
X………………….
X…………..
x………………………..
X……………….
X……………
X..x
xxxx		 Loudy 70.00%
Apples 0.00%
Dogman 0.00%
Miller 0.00%
Invalid 30.00%

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

 

Решение

Чтобы решить задачу создадим структуру с именами и результатами кандидатов. Сначала создадим массив кандидатов и заполним его. По вводу бюллетеней будем проверять не испорчены ли они. Если кроме «X» есть любой другой символ, или буква, или еще символы «X», то бюллетень испорчен, в остальных случаях он не испорчен. Если он не испорчен, добавляем к результату кандидата единицу, если нет — добавляем к счетчику испорченых бюллетеней единицу. Выводим в процентном соотношении с количеством бюллетеней результат каждого кандидата и количество испорченых бюллетеней.

Ссылки

Условие задачи на e-olymp

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

e-olymp 8674. Игра

by

0

Задача

Мурад и Ибрагим играют в следующую игру. Изначально дается число $1$. На своем ходу каждый игрок должен умножить текущее число на одно из целых чисел от $2$ до $9$ включительно. Цель состоит в том, чтобы получить число не меньше заданного целого числа $n$. Игрок, получивший такой номер первым, объявляется победителем. Мурад всегда начинает первым. Выясните, кто победит, если Мурад и Ибрагим будут играть оптимально.

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

Первая строка содержит одно число $t$ $(1 \leqslant t \leqslant 2500)$ — количество тестов. Каждая из следующих $t$ строк содержит одно целое число $n$ $(2 \leqslant n \leqslant 10^9)$.

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

Для каждого теста выведите в отдельной строке $1$, если Мурад выиграет игру, и $2$ иначе.

Тесты

№

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

Выходные данные
1 4
9
10
1149729
999999999		 1
2
2
1
2 3
6
163
1234567		 1
2
2
3 3
42
100
1000		 1
1
1

 

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

Решение с циклом для каждого отдельного теста:

 

Решение без цикла для каждого отдельного теста:

 

Решение

Для начала заметим, что победит тот игрок, чей ход выпадет на число из промежутка $[\frac{n}{9},n)$, так как любое число из этого промежутка можно умножить на соответствующее целое число из $[2,9]$ и получить число не меньшее чем $n$. Назовем такой промежуток «зеленой зоной» (в общем виде будет $[\frac{2n}{18^k},\frac{n}{18^{k-1}})$, $k \in \mathbb {N}$). Тогда очевидно, что проиграет тот игрок, чей ход выпадает на число из промежутка $[\frac{n}{18},\frac{n}{9})$, так как при умножении числа из этого промежутка на любое целое число из $[2,9]$, приводит к тому, что получается число из «зеленой зоны». Назовем такой промежуток «красной зоной» (в общем виде будет $[\frac{n}{18^k},\frac{2n}{18^k})$, $k \in \mathbb {N}$). Получаем, что промежуток $(0,n)$ делится на «красные» и «зеленые зоны». Тогда задача сводится к нахождению вида «зоны» в которой находится $1$.

Используя в реализации цикл для каждого отдельного теста, получить результат достаточно несложно. Однако, для заданного $n$ можно получить исход игры используя лишь линейные вычисления.

Рассмотрим цепочку неравенств (учитывая, что $2 \leqslant n$ ):  $$\lfloor \log _{18} n \rfloor \leqslant \log _{18} n \leqslant \lceil  \log _{18} n \rceil$$

$$ 18^{\lfloor \log _{18} n \rfloor} \leqslant n \leqslant 18^{\lceil  \log _{18} n \rceil}$$

$$\frac{1}{18^{\lceil  \log _{18} n \rceil}} \leqslant \frac{1}{n} \leqslant \frac{1}{18^{\lfloor \log _{18} n \rfloor}}$$

$$\frac{n}{18^{\lceil  \log _{18} n \rceil}} \leqslant 1 \leqslant \frac{n}{18^{\lfloor \log _{18} n \rfloor}}$$

Из общего вида «красной зоны» видно, что левый ее конец это число вида $\frac{n}{18^k}$, значит $\frac{n}{18^{\lceil  \log _{18} n \rceil}}$ является левым концом «красной зоны», обозначим его как $l$. Тогда, $2l$ будет правым концом «красной зоны» исходя из её общего вида. Из полученного неравенства видно, что $1$ лежит между левыми концами соседних «красных зон». Получаем, что если $2l \leqslant 1$, то единица лежит в «зеленой зоне», а иначе — в «красной».

Ссылки

Условие задачи на e-olymp

Решение без цикла для каждого отдельного теста на ideone

Решение с циклом для каждого отдельного теста на ideone

e-olymp 4142. Большой XOR

by

0

Задача

Для заданного целого $x$ найти количество таких $a$, удовлетворяющих условию:

  • $ a $ xor $x > x $
  • $ 0 < a < x $

где $a$ и $x$ — целые, xor — битовый XOR оператор.

Имеются $q$ запросов, каждый из которых содержит целое число $x$. Для каждого запроса выведите общее количество значений $a$, удовлетворяющих условиям выше.

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

Первая строка содержит число запросов $q$ $(1 \leqslant q \leqslant 10^5)$. Каждая из следующих $q$ строк содержит значение $x$ $(1 \leqslant x \leqslant 10^{10})$.

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

Для каждого теста выведите в отдельной строке количество значений $a$, удовлетворяющих приведенным условиям.

Тесты

№ Входные данные Выходные данные
1 2
2
10		 1
5
2 3
13
3
16		 2
0
15
3 5
1
7
4294967295
42
451		 0
0
0
21
60

Код

Решение

XOR выдаёт число, биты которого равны $1$, когда лишь у одного из чисел соответствующий бит равен $1$. Числа большие чем $x$ получаем лишь тогда, когда $2^{k}\leqslant a<2^{k+1}$, где $k$- номер бита числа $x$, который равен нулю. Таких $a$ существует $2^k$ штук для каждого такого бита.

  • Задача на e-olymp
  • Код программы на ideone
  • Засчитанное решение

    • e-olymp 124. Квадрат

    by

    0

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

    Найдите периметр и площадь квадрата.

    Входные данные:
    Каждая строка является отдельным тестом и содержит одно целое число — длину стороны квадрата $n$ (1 $\leqslant$ $n$ $\leqslant$ 1000).

    Выходные данные:
    Для каждого теста выведите в одной строке периметр и площадь квадрата.

    Тесты

    № Входные данные Выходные данные
    1 3
    5
    10    		 12 9
    20 25
    40 100
    2 3
    3
    3    		 12 9
    12 9
    12 9
    3 1000
    1
    500    		 4000 1000000
    4 1
    2000 250000

    Код

    Решение

    У нас дана сторона квадрата $n$.

    • Находим периметр квадрата, используя формулу $P = 4n$.
    • Находим площадь квадрата, используя формулу $S = n^{2}$.
    • Так как каждая новая строка — новое значение для стороны квадрата и таких строк неизвестное количество то используем myObj.hasNext() для потоковой обработки данных.

    Ссылки

    • Задача на сайте e-olymp
    • код решения Ideone

    e-olymp 566. Письмо почтальона Печкина

    by

    0

    Задача

    Дорогие ребята!
    Наблюдая за тем, как Шарик распиливал нестандартную шахматную доску, я также решил задать для вас задачку: “А сколько разных квадратных и прямоугольных (не считая квадратных) досок мог бы получить при распиливании Шарик из найденной им нестандартной прямоугольной шахматной доски размером $M\times N$?”

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

    В первой строке количество заданий Печкина $K$, в последующих $K$ строках по два целых числа $M$ и $N$ $(1 \leqslant K, M, N \leqslant 100)$, разделённых пробелом.

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

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

    Тесты

    № Входные данные Выходные данные
    1. 1
    3 2    		 8 10
    2. 2
    4 4
    2 2    		 30 70
    5 4
    3. 4
    3 3
    25 46
    100 100
    1 1    		 14 22
    12350 338975
    338350 25164150
    1 0

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

    Объяснение

    Ответом на каждый запрос будет количество квадратов и прямоугольников которые можно получить из нашей шахматной доски размера $M\times N$. Для вычисления количества квадратов нам надо посчитать, сколько квадратов каждого возможного размера поместится в нашей шахматной доске. Аналогично для прямоугольников. Пример с доской $3\times 2$ разобран на картинке.

    Пояснение к первому тесту

    Для подсчёта квадратов, нам следует отдельно считать их количество для каждого возможного размера. Таким образом сначала идут квадраты $1\times 1$, то есть $M\cdot N$ квадратов. Далее, квадратов $2\times 2$ помещаются ровно на $1$ меньше горизонтально и на $1$ меньше вертикально, значит получаем $(M-1)\times (N-1)$. Соответственно, $(M — 2)\times (N — 2)$ для квадратов $3\times 3$. И так продолжаем пока квадрат помещается в нашу доску.

    Аналогично мы поступаем и с прямоугольниками. Однако считая количество прямоугольников каждого размера, нам нужно считать сколько поместится прямоугольников размера $(1\times 1), (1\times 2)\dots (1\times N)$. Также $(2\times 1), (2\times 2)\dots (2\times N)$. И так до $(M\times 1), (M\times 2)\dots (M\times N)$. Это довольно просто реализовать используя вложенный цикл.

    Не стоит забывать, что квадрат — тот же прямоугольник, но с равными сторонами и в нашем цикле мы считаем все прямоугольники. А так как квадраты мы не должны учитывать, то после нахождения числа прямоугольников, нам нужно вычесть из него количество квадратов. В коде после нахождения и вывода числа квадратов, мы домножили это число на $(-1)$ и и уже после прибавили к нему количество прямоугольников, таким образом не учитывая квадраты.

    Ссылки

    Условие на e-olymp.

    Код на ideone.

     

    e-olymp 913. Используй подпрограмму

    by

    0

    Задача

    Вычислить сумму и произведение $n$ пар заданных вещественных чисел, воспользовавшись подпрограммой $SumDob$ для вычисления суммы и произведения двух вещественных чисел.

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

    В первой строке задано натуральное число $n$ — количество пар чисел. В последующих $n$ строках через пробел задано по $2$ вещественных числа. Все входные данные по модулю не превышают $100$.

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

    В $n$ строках вывести через пробел по два числа: сначала сумму, а потом произведение очередной пары чисел. Результат выводить с точностью $4$ знака после десятичной точки.

    Тесты

    # Входные данные Выходные данные
    1 2
    6 7.5
    2.1 2.0    		 13.5000 45.0000
    4.1000 4.2000
    2 4
    2 5
    3 5
    4 5
    5 5    		 7.0000 10.0000
    8.0000 15.0000
    9.0000 20.0000
    10.0000 25.0000
    3 2
    100 100
    56 65    		 200.0000 10000.0000
    121.0000 3640.0000
    4 6
    10 10
    20 20
    40 40
    50 50
    70 70
    80 80    		 20.0000 100.0000
    40.0000 400.0000
    80.0000 1600.0000
    100.0000 2500.0000
    140.0000 4900.0000
    160.0000 6400.0000
    5 1
    2 2    		 4 4

    Решение

    Как и было указано в условии задачи, при решении задачи использовалась подпрограмма $SumDob$, которая возвращает сумму и произведение двух вещественных чисел $a$ и $b$. Потом мы с помощью цикла выводим пару чисел, полученных из подпрограммы $SumDob$ $n$ раз с $n$ пар введенных значений.

    Условие задачи можно найти на e-olymp
    Код решения — ideone

    e-olymp 419. Задача 3n + 1

    by

    0

    Задача

    Рассмотрим следующий алгоритм генерации последовательности чисел:

    Например, для [latex]n = 22[/latex] будет сгенерирована следующая последовательность чисел:

    22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

    Полагают (но это еще не доказано), что этот алгоритм сойдется к [latex]n = 1[/latex] для любого целого [latex]n[/latex]. По крайней мере, это предположение верно для всех целых [latex]n[/latex], для которых [latex]0 < n < 1,000,000[/latex].
    Длиной цикла числа [latex]n[/latex] будем называть количество сгенерированных чисел в последовательности включая [latex]1[/latex]. В приведенном примере длина цикла числа [latex]22[/latex] равна [latex]16[/latex].
    Для двух заданных чисел [latex]i[/latex] и [latex]j[/latex] необходимо найти максимальную длину цикла среди всех чисел между [latex]i[/latex] и [latex]j[/latex] включительно.

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

    Каждый тест задается в отдельной строке и содержит пару целых чисел [latex]i[/latex] и [latex]j[/latex]. Входные числа будут меньше [latex]1000000[/latex] и больше [latex]0[/latex]. Считайте, что для вычислений достаточно использовать [latex]32[/latex] битный целочисленный тип.

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

    Для каждой пары чисел [latex]i[/latex] и [latex]j[/latex] выведите числа [latex]i[/latex] и [latex]j[/latex] в том же порядке, в каком они поступили на вход. После чего выведите максимальную длину цикла среди всех целых чисел между [latex]i[/latex] и [latex]j[/latex] включительно. Для каждого теста три числа следует выводить в отдельной строке, разделяя одним пробелом.

    Тесты

    Входные данные Выходные данные
    1 10
    100 200
    201 210
    900 1000    		 1 10 20
    100 200 125
    201 210 89
    900 1000 174
    1 10
    10 1    		 1 10 20
    10 1 20
    5 25
    70 54
    38 250    		 5 25 24
    70 54 113
    38 250 128

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

    Решение

    Алгоритм, описанный в условии задачи используется для построения сиракузской последовательности. Интересный факт — какое бы число не взять, в конце получаем единицу. Нам же надо посчитать сколько раз должен сработать алгоритм для подсчитывания «длины цикла». Считывая пару чисел из потока ввода я высчитывал «длину цикла» для каждого числа из заданного введенной парой промежутка. После чего сравнивал количество итераций для каждого такого числа и находил максимальное. И так для каждой пары чисел.

    Ссылки

    Ссылка на e-olymp.
    Ссылка на Ideone

    e-olymp 7365. Молоко и пирожок

    by

    0

    Задача

    Ученикам первого класса дополнительно дают стакан молока и пирожок, если вес первоклассника менее [latex]30 [/latex] кг. В первых классах школы учится [latex]n[/latex] учеников. Стакан молока имеет емкость [latex]200 [/latex] мл, а упаковки молока — [latex]0,9 [/latex] л. Определить количество дополнительных пакетов молока и пирожков, необходимых каждый день.

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

    В первой строке задано целое число [latex]n[/latex] [latex](0 < n ≤ 100)[/latex]. В следующей строке идут [latex]n[/latex] положительных действительных чисел – массы первоклассников.

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

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

    Тесты

    # Входные данные Выходные данные
    1 4 30 36 29 47 1 1
    2 5 30 36 29 47 26 1 2
    3 8 30 36 29 47 26 27 30 31 1 3
    4 1 29 1 1
    5 5 26 27 28 29 25 2 5

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

    Решение

    Для решения задачи мы должны узнать: сколько упаковок молока и пирожков нужно для детей.
    Чтобы узнать количество пирожков мы заводим счетчик, который увеличивает на единицу, если появился подходящий ребенок.
    А для молока будем использовать целые числа (0,2 домножим на 10 и 0,9 также домножим на 10). Будем считать сколько всего тратится молока, затем поделим на 9 и узнаем сколько пачек молока нужно. Результат подсчета количества молока может не быть целым, соответственно придется округлять вверх.
    Рассмотрим аспекты синтаксиса:

    • Функция округления вверх:

    • В результате выполнения программы мы получим данные в виде [latex]n.0[/latex], где [latex]n[/latex]- любое целое число. Ответ является правильным, но, при проверке кода с помощью сайта e-olymp, мы сталкиваемся с проблемой, что во всех тестах ошибка. Для того, чтобы этого избежать используем:
      из библиотеки java.text.DecimalFormat;
      Данная ошибка возникла из-за того, что был использован тип double.

    Ссылки

    Задача на e-olymp

    Код задачи на ideone

    e-olymp 1154. Кружок хорового пения

    by

    0

    Задача

    В некотором учебном заведении функционирует кружок хорового пения. Начало кружка всегда происходит единообразно: по сигналу руководителя кружка все [latex]N[/latex] участников становятся в круг и каждый [latex]M[/latex]-й для распевки поёт гамму.

    Руководитель кружка заметил, что размять голосовые связки не всегда удаётся всем участникам кружка. По заданным [latex]N[/latex] и [latex]M[/latex] помогите ему определить, или в очередной раз в разминке примут участие все участники хора.

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

    Входные данные состоят из нескольких тестовых случаев. Каждый тестовый случай расположен в отдельной строке и содержит два целых числа [latex]N[/latex] и [latex]M[/latex]. ([latex]1 ≤ N, M ≤ 103[/latex]).

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

    Для каждого тестового случая в отдельной строке выведите «YES», если в разминке примут участие все участники хора, в противном случае выведите «NO».

    Тесты

    Входные данные Выходные данные
    1000 1000
    1 1    		 NO
    YES
    2 5
    3 7
    14 15
    49 37    		 YES
    YES
    YES
    YES
    14 16
    891 6
    441 9
    777 111    		 NO
    NO
    NO
    NO
    4 1
    6 3    		 YES
    NO

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

    Решение

    Пусть у нас есть [latex]N[/latex] певцов. Пронумеруем их по порядку от [latex]0[/latex] до [latex]N — 1[/latex]. Распевается каждый [latex]M[/latex]-й. И пусть НОД ([latex]M, N) = k \geq 2[/latex]. Тогда, например, [latex]k — 1[/latex]-ый певец никогда не распоется.

    Ссылки

    Условие задачи на сайте E-Olymp

    код задачи на Ideone