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

Задача

Ученикам первого класса дополнительно дают стакан молока и пирожок, если вес первоклассника менее [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. Кружок хорового пения

Задача

В некотором учебном заведении функционирует кружок хорового пения. Начало кружка всегда происходит единообразно: по сигналу руководителя кружка все [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

e-olymp 441. Наиболее круглое число

Наиболее круглое число

Назовем число более круглым, чем другие числа, если оно имеет больше заключительных нулей. Если два числа имеют одинаковое количество заключительных нулей, то более круглым считается меньшее число.

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

В первой строке входных данных задано количество чисел $N$ $(1  ≤  N  ≤  100)$. Каждая из последующих $N$ строк содержит одно число в пределах от $1$ до $10^{9}$.

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

Вывести наиболее круглое число среди заданных $N$ чисел.

Тесты

ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
4
71200
10
200
10001
200
5
711
1
2
10001
234567
1
10
7
1
2
1
2
3
4
6
8
9
1
4
100000
200000
500000
800000
100000

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

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

Имеет смысл проверять каждое введенное число: не является ли оно меньше либо равно чем $p$, где $p$ — наименьшее число с количеством нулей равным $maxk$. $maxk$ — текущее наибольшее количество нулей. Для того, чтобы найти $p$, мы в цикле умножаем $1 maxk$-раз на $10$. Очевидно, что $p$ нужно менять только тогда, когда меняется $maxk$, также следует до цикла полагать $p = 1$. Для того чтобы $p$ не умножалось на $10$ лишнее количество раз. Таким образом мы отсеиваем заведомо негодные числа и ускоряем код.
Положим $maxn$ — наиболее круглое число.
Так как по условию числа не могут быть больше чем $10^{9}$, имеет смысл изначально поставить переменную $maxn = 10^{9}$. Это делается для того случая, когда во всех числах $m$ не будет нулей и нужно будет выбрать наименьшее. Если мы положим в переменную $maxn$ любое другое число то $maxn$ может быть меньше чем $m$ и мы не сможем выбрать ответ так как все $m$ будут больше его.

Условие задачи на e-olimp
Код решения 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
Ссылка на решение

MS9. Шифрование символов

Задача

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

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

Последовательность символов.

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

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

Тесты

Входные данные Выходные данные
pack my box with five dozen liquor jugs p 11 2 8 4b 4d 14 59 42 d 17 58 57 1e 1d 1c 48 46 f 1f 13 45 44 b 15 1f b 4e 4c 5 18 4 1a 1d 52 4a 1f 12 14

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

Решение

Объявляем 2 символьные переменные. Считываем первый символ и выводим его. Остальные символы будут считываться в цикле, пока не закончатся данные из потока ввода. По мере ввода запоминаем старый символ во 2 переменной и складываем их по модулю 2 и выводим результат в шестнадцатеричной системе.

Ссылки

Условие задачи
Код решения

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 4281. Невнимательность

Задача

Степан успешно прошёл собеседование и вот уже как четыре месяца работает в одной из самых престижных ИТ компаний. Пришло время сдавать проект менеджеру и Степан, как настоящий студент, всё делает в последнюю ночь перед сдачей. Набирает текст Степан необычно очень быстро, но невнимательно. Вот и в этот раз последнюю часть текста он набрал не обратив внимания, что случайно нажал клавишу $caps\;lock.$ Таким образом большие буквы были набраны маленькими, а маленькие — большими. Другие символы он набрал верно. Степан настолько устал, что нет сил исправить ошибки, и он решил несколько часов поспать.

Помогите Степану, пока он спит, напишите программу, которая исправляет невнимательно набранный текст.

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

В одной строке содержится невнимательно набранный Степаном текст. В строке не более $500$ символов.

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

Вывести исправленный текст.

Тесты

Входные данные Выходные данные
$sCHOOL$ $School$
$hOME$ $Home$
$hAPPY nEW yEAR$ $Happy New Year$
$uNIVERSITY$ $University$
$mERRY cHRISTMAS$ $Merry Christmas$

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

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

Для решения задачи считываем всю строку. Затем в цикле проверяем каждый символ строки на то, является ли символ маленькой буквой английского алфавита, если да, то увеличиваем букву (функция Character.toUpperCase(c.charAt(i)), если нет, то уменьшаем букву (функция Character.toLowerCase(c.charAt(i))). Складываем получаемые буквы в строку str. Выводи строку. Задача решена.

Ссылки

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

e-olymp 1317. Дни рождения


Задача

Известно, что в группе из [latex]23[/latex] или более человек вероятность того, что хотя бы у двух из них дни рождения (число и месяц) совпадут, превышает [latex]50 \% [/latex]. Этот факт может показаться противоречащим здравому смыслу, так как вероятность одному родиться в определённый день года довольно мала, а вероятность того, что двое родились в конкретный день – ещё меньше, но является верным в соответствии с теорией вероятностей. Таким образом, факт не является парадоксом в строгом научном смысле – логического противоречия в нём нет, а парадокс заключается лишь в различиях между интуитивным восприятием ситуации человеком и результатами математического расчёта.

Для заданного количества людей вычислить вероятность того, что двое из них родились в один день года. Год считать равным [latex]365[/latex] дням.

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

Каждая строка является отдельным тестом и содержит количество людей [latex]n[/latex] [latex](1 < n < 400)[/latex].

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

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

Тесты

Входные данные Выходные данные
[latex]12[/latex] [latex]16.70247888\%[/latex]
[latex]28[/latex] [latex]65.44614723\%[/latex]
[latex]399[/latex] [latex]100.00000000\%[/latex]

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

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

Посчитаем вероятность того, что дни рождения не совпадут. Вероятность того, что у двух людей дни рождения не совпадут равна [latex](1 — \frac{1}{365})[/latex]. Взяв третьего человека, вероятность того, что его день рождения не совпадет с предыдущими равна [latex](1 — \frac{2}{365})[/latex] и так далее до последнего человека, у которого вероятность не совпадения дня рождения с остальными равна [latex](1 — \frac{n-1}{365})[/latex]. Перемножив все эти значения через цикл получим вероятность того, что у всех [latex]n[/latex] человек из группы дни рождения не совпадут[latex]( \frac{365!}{(365-n)! \cdot 365^n})[/latex]. Так как вероятность не может быть больше [latex]1[/latex], то от [latex]1[/latex] отнимем кол-во неблагоприятных исходов и получим нужное. Но по условию ответ необходимо вывести в процентах, поэтому умножим на [latex]100[/latex] полученное. И так как [latex]n[/latex] будет вводиться пока пользователю угодно , запишем вышесказанное в цикл [latex]while[/latex].

Ссылки

Условие задачи на e-olymp.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