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

Задача

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

Например, для [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 3843. Простые

Задача

Пусть $m$ и $n$ $\left(2 ≤ m < n ≤ 107\right)$ — целые числа. Рассмотрим следующее множество:

Prime $\left(m, n\right) = \lbrace{ p | p\;простое, m ≤ p ≤ n \rbrace}$.

Вычислить мощность множества Prime$\left(m, n\right)$.

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

Состоит из нескольких тестов. Два последовательных теста разделены пустой строкой. Для каждого теста в отдельной строке заданы числа $m$ и $n$.

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

Для каждого теста вывести результат в отдельной строке. Результаты соседних тестов разделять пустой строкой. Для каждого теста вывести мощность множества Prime$\left(m, n\right)$.

Тесты

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

70 110

5 150

8

10

33

7 2056

14 181

27 367

307

36

64

77 777

55 555

33 333

116

85

56

Код решения

Решение

Для решения этой задачи требуется завести большой массив типа bool и присвоить ему значение true. Затем проверяется, простое ли число, если это не так, то присваиваем значение false.
Затем нужно последовательно сосчитать мощность каждого множества простых чисел, то есть количество простых чисел от n до m, с помощью массива-счётчика: записывается в него прошлые и последующие элементы множества простых чисел.
После этого в цикле задаются нужные значения, считается ответ и выводится.

Ссылки

Ссылка на E-olymp
Ссылка на решение

e-olymp 176. Выбор вождя

Условие задачи
Орки – одна из рас, населяющих мир Драэнор. Не отличаясь высоким интелектом, орки все же славятся своею силой и отвагой в бою. Ежегодно орки из разных кланов собираются в Долине Силы для того, чтобы избрать вождя всей Орды. В отличие от глупых людей, орки презирают выборы посредством голосования (да и, скажем прямо, все эти бюлетени, урны и избирательные участки чужды и непонятны орку, не державшему в руках ничего, кроме дубины и топора). Кандидаты в вожди сражаются друг с другом в честных поединках. В каждом поединке участвуют два претендента, один из которых выходит из него победителем, а другой оказывается поверженным. Проигравший в одном поединке орк выбывает из числа претендентов и не может участвовать в последующих поединках. Оставшийся в конце концов после всех боев кандидат и становит вождем Орды.

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

Старейшины обратились к вам с просьбой написать программу для определения количества претендентов, которые могут стать вождями.
Входные данные
В первой строке входного файла записано количество $N$ претендентов на звание вождя в этом году $(1 ≤ N ≤ 1000000)$, а во второй – $N$ целых чисел в пределах от $1$ до $10000$, каждое из которых определяет силу соответствующего кандидата.
Выходные данные
Выходной файл должен содержать одно число – количество претендентов, которые могут стать вождями.
Тесты

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

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

Решение задачи
Так как задача на потоковую обработку создаем цикл, который работает пока у нас вводится число «Сила Орков». В самом цикле происходит следующее:

  1. Если «Сила Орков» больше max, то мы в переменную max присваиваем значение из «Силы Орков» и счетчику присваиваем единицу.
  2. Если «Сила Орков» равна max то мы прибавляем к счетчику $1$.

Выводим счетчик на экран.
Ссылки
Задача на сайте e-olymp
Код решения в Ideone

e-olymp 992. Города и дороги

Задача

В галактике «Milky Way» на планете «Neptune» есть n городов, некоторые из которых соединены дорогами. Император «Maximus» галактики «Milky Way» решил провести инвентаризацию дорог на планете «Neptune». Но, как оказалось, он не силен в математике, поэтому он просит Вас сосчитать количество дорог.

Вводные данные

В первой строке записано число $n$ $(0 \leq n \leq 100)$. В следующих $n$ строках записано по $n$ чисел, каждое из которых является единичкой или ноликом. Причем, если в позиции $(i, j)$ квадратной матрицы стоит единичка, то $i$-ый и $j$-ый города соединены дорогами, а если нолик, то не соединены.

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

Вывести одно число — количество дорог на планете «Neptune».

Тесты

Входные данные Выходные данные
$3$
$0$ $1$ $1$
$1$ $0$ $1$
$1$ $1$ $0$
$3$
$3$
$0$ $1$ $0$
$1$ $0$ $0$
$0$ $0$ $0$
$1$
$5$
$0$ $1$ $0$ $1$ $1$
$1$ $0$ $0$ $0$ $0$
$0$ $0$ $0$ $0$ $0$
$1$ $0$ $0$ $0$ $0$
$1$ $0$ $0$ $0$ $0$
$3$

Код программы(использование матрицы смежности)

Решение задачи(использование матрицы смежности)

Для решения задачи вводим матрицу смежности. Далее в цикле проходим верхнюю треугольную часть матрицы смежности и если попадается $1$, то увеличиваем число дорог на $1$. Выводим количество дорог. Задача решена.

Код программы(потоковая обработка)

Решение задачи(потоковая обработка)

Для решения задачи вводим числа пока они вводятся. Поскольку дороги идут с одного города в другой и наоборот, то их количество будет равно половине единичек в матрице смежности, то есть половине единичек входящих во входной поток. Cчитаем их количество и делим на $2$. Выводим количество дорог. Задача решена.

Ссылки

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

e-olymp 97. Числа Белла

Задача

Bell
Число Белла $B_n$ равно количеству разбиений множества из $n$ элементов на произвольное количество непересекающихся непустых подмножеств. Например, $B_3 = 5$, так как существует $5$ возможных разбиений множества $\lbrace a, b, c\rbrace$: $\lbrace\lbrace a\rbrace, \lbrace b\rbrace, \lbrace c\rbrace\rbrace, \lbrace\lbrace a, b\rbrace, \lbrace c\rbrace\rbrace, \lbrace\lbrace a, c\rbrace, \lbrace b\rbrace\rbrace, \lbrace\lbrace a\rbrace, \lbrace b, c\rbrace\rbrace, \lbrace\lbrace a, b, c\rbrace\rbrace$. Дополнительно считаем, что $B_0 = 1$.
Рассмотрим определитель $D_n$:
$$D_n = \begin{vmatrix}
B_0& B_1& B_2&\ldots& B_n\\
B_1& B_2& B_3&\ldots& B_{n+1}\\
\ldots& \ldots& \ldots& \ldots& \ldots\\
B_n& B_{n+1}& B_{n+2}&\ldots& B_{2n}
\end{vmatrix}$$
Для заданного простого числа $p$ найти наибольшее целое $k$, для которого $D_n$ делится на $p^k$.

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

Каждая строка ввода содержит два целых числа $n$ и $p$ ($0\leq\; n,\;p \;\leq\; 10000$). Известно, что $p$ – простое.

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

Для каждой пары входных значений $n$ и $p$ в отдельной строке выведите наибольшее целое $k$, для которого $D_n$ делится на $p^k$.

Тесты

Входные данные Выходные данные
1 5
3 2
4 2
4 3
10000 3
0
2
5
2
24962375
18 2
465 1009
9998 9221
548 11
134
0
778
14412
1093 1093
1103 1723
3931 617
4868 6113
9534 71
1
0
10635
0
639989
617 17
42 11
0 5
11295
63
0

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

Решение

Числа Белла обладают интересным свойством:
$$D_n = \begin{vmatrix}
B_0& B_1& B_2&\ldots& B_n\\
B_1& B_2& B_3&\ldots& B_{n+1}\\
\ldots& \ldots& \ldots& \ldots& \ldots\\
B_n& B_{n+1}& B_{n+2}&\ldots& B_{2n}
\end{vmatrix} = \prod_{i=1}^n i!$$
Воспользуемся этим свойством для решения данной задачи. Найдём степень числа $p$
в разложении на простые множители. Для этого узнаем степень вхождения этого числа в каждый из факториалов. Суммой полученных значений и будет являться искомое число $k$.

Ссылки

Условие задачи на e-olymp
Решение на ideone
Решение на e-olymp
Число Белла на wikipedia

e-olymp 1000. Задача a + b

Задача

Вычислите сумму $a+b$.

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

В каждой строке задано два целых числа $a$ и $b$ $(|a|,|b| \leq 30000)$.

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

Для каждого теста выведите сумму $a+b$ в отдельной строке.

Тесты

Входные данные Выходные данные
$4$ $8$
$5$ $0$
$-6$ $8$
$12$
$5$
$2$
$-3$ $3$ $0$
$12$ $8$
$10$ $10$
$20$
$20$
$30000$ $30000$
$3000$ $3000$
$300$ $300$
$30$ $30$
$3$ $3$
$60000$
$6000$
$600$
$60$
$6$
$10$ $23$
$613$ $2$
$-200$ $300$
$33$
$615$
$100$

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

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

Пока вводятся пары чисел, они считываются и на экран выводится их сумма.

Ссылки

Условие на e-olymp
Решение на языке C++ с описанием решения
Код на java

e-olimp 7365

Ссылка на оригинал задачи

Задача «Молоко и пирожок»

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

Тесты:

Количество детей Вес Количество упаковок молока Количество пирожков
3 30 29 30 1 1
5 25 41 56 20 20 1 3
4 30 30 30 30 0 0
7 25 26 27 28 29 23 24 2 7

Код:

Алгоритм:

  1. Объявление и ввод значений переменных.
  2. Используем цикл for для подсчета необходимого количества пирожков.
  3. На основе предыдущих данных и округления в большую сторону (метод  Math.ceil ), подсчитываем необходимое количество пакетов молока.
  4. Окончание работы программы.

Работающая версия программы на Ideone.com

Ссылка на источник

А136л

Постановка задачи

Даны натуральное число $latex n$, действительные числа $latex a_1,\cdots,a_n$. Вычислить: $latex |a_1*a_2*\cdots*a_n|$.

Тесты

$latex n$ $latex a_1$ $latex a_2$ $latex a_3$ $latex a_4$ $latex a_5$ $latex a_6$ $latex a_7$ $latex a_8$ $latex k$
4 5 -3 2 1 5.477225575051661
5 2 7 4 3 5 28.982753492378876
3 4 4 0 0
5 3 8 6 2.8 1.3 22.894541

Код

 

Описание решения

Объявляем переменную $latex n$ (количество элементов — это целое число, поэтому используем тип int) и переменную $latex p$ (произведение), она может быть вещественной, поэтому выбираем тип double.

В цикле for считываются элементы $latex a_1,\cdots,a_n$, где   вычисляется их произведение.

После цикла вычисляется корень из модуля произведений элементов.

Посмотреть, как работает программа можно на сайте  ideone.
Задача была переделана из данного решения.

MS 7. Средняя зарплата

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

Входные данные
Фамилия работника name и величина его зарплаты salary.

Выходные данные
Средняя зарплата по компании.

Тесты

Входные данные Выходные данные
name salary  totalSalary/employeesNum
1. Ivanov 100 100
Ivanov 300 200
2. Smirnov 150 150
3. Popov 200 200

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

Пояснение

С потока данных считывается первое значение и записывается в переменную name. Затем считывается заработная плата и записывается в переменную sal. В переменную total записывается общая полученная сумма работниками, увеличивается счетчик количества выплат sum. Средняя зарплата считается по формуле среднего арифметического: [latex]x = \frac{total}{sum}[/latex] и выводится потоком вывода.

Ссылка на код по тесту 1.

Ссылка на источник.

 

MS1. Сумма всех нечетных чисел в диапазоне.

Задача

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

Тесты

Начало диапазона Конец диапазона Вывод
1 11 36
2 8 15
7 30 216

Решение

Задача(2)