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 2214. Функция 9

Задача

Дана функция, аргументы которой — произвольные натуральные числа
$$f(M, N)=\begin{cases}
f(M-N, N), & \text{ npu } M>N \\
N, & \text{ npu } M=N \\
f(N-M, M), & \text{ npu } N>M
\end{cases}$$
Составить алгоритм (написать программу), вычисляющий значение функции.

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

Два натуральных числа $n$ и $m$ $(1\leq n, m \leq 10^{18}).$

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

Искомое значение функции.

Тесты

Входные данные Выходные данные
$6$ $3$ $3$
$12$ $12$ $12$
$126$ $98$ $98$
$10329$ $1501$ $1501$
$1008359$ $15113$ $15113$

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

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

Для решения задачи напишем функцию f. Именно эта функция и будет считать искомое значение. Из условия задачи видим, что для решения потребуется рекурсия. Для этого, если остаток от деления одного натурального числа на другое не равен нулю, то мы снова возращаемся в функцию (в зависимости от того, что больше $n$ или $m$). Это будет продолжаться до тех пор, пока остаток от деления одного натурального числа на другое не будет равен нулю (как только $n \mod m = 0$ или $m \mod n = 0,$ то функция возращает в переменную искомое значение). Задача решена.

Ссылки

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

e-olymp 2817. Двоичные числа

Задача

Для заданного положительного целого числа $n$, распечатать позиции всех $1$ в двоичном его представлении. Позиция младшего бита имеет номер $0$.
Позиции $1$ в двоичном представлении числа $13$ — это $0$, $2$, $3$.
Напишите программу, которая для каждого набора данных:

  • читает натуральное число $n$,
  • вычисляет позиции $1$ в двоичном представлении $n$,
  • выводит результат.

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

В первой строке входного файла содержится одно натуральное число $d$, указывающее количество наборов входных данных, $1 \leq d \leq 10$. Входные данные заданы ниже.

Каждый набор данных состоит ровно из одной строки, содержащей ровно одно целое число $n$, $0 \leq n \leq 10^6$.

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

Вывод должен состоять ровно из $d$ строк — по одной строке для каждого набора входных данных.

Строка $i$, $1 \leq i \leq d$, должна содержать возрастающую последовательность целых чисел, разделенных одним пробелом — позиции $1$ в двоичном представлении $i$-го числа, полученного во входных данных.

Тесты

 

Входные данные
Выходные данные
$3$
$17$
$7$
$5$
$0$ $4$
$0$ $1$ $2$
$0$ $2$
$4$
$1945$
$1337$
$1000000$
$999999$
$0$ $3$ $4$ $7$ $8$ $9$ $10$
$0$ $3$ $4$ $5$ $8$ $10$
$6$ $9$ $14$ $16$ $17$ $18$ $19$
$0$ $1$ $2$ $3$ $4$ $5$ $9$ $14$ $16$ $17$ $18$ $19$
$10$
$0$
$1$
$2$
$3$
$4$
$5$
$6$
$7$
$8$
$9$
$0$
$1$
$0$ $1$
$2$
$0$ $2$
$1$ $2$
$0$ $1$ $2$
$3$
$0$ $3$

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

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

Для решения этой задачи нужно понять, что остаток от деления $n$ на $2$ это последняя цифра в двоичном коде числа $n$, а деление целочисленной переменной $n$ на $2$ это отбрасывание последней цифры в двоичном коде. Цикл с счетчиком $i$ до момента, как $n$ не станет равняться $0$, очевиден, как и внешний цикл от $0$ до $d$, который реализовывает $d$ итераций ввода числа $n$. Стоит отметить, что тесты на e-olymp (все, кроме первого) чувствительны к пробелам в конце строки, из-за чего появляется необходимость каким-то образом его избежать.

Ссылки

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

e-olymp 7366. Сколько до Нового Года?

Задача

У Деда Мороза есть часы, которые в секундах показывают сколько осталось до каждого Нового Года. Так как Дед Мороз уже человек в возрасте, то некоторые математические операции он быстро выполнять не в состоянии. Помогите Деду Морозу определить сколько полных дней, часов, минут и секунд осталось до следующего Нового Года, если известно сколько осталось секунд, т.е. разложите время в секундах на полное количество дней, часов, минут и секунд.

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

В единственной строке целое число [latex]N \left(0 < N ≤ 31500000\right)[/latex] – количество секунд, которые остались до наступления Нового Года.

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

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

Тесты

# Входные данные Выходные данные
1 5217656 60 9 20 56
2 7999 0 2 13 19
3 30123456 348 15 37 36
4 7841186 90 18 6 26
5 899650 10 9 54 10

Код

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

Вспомним, что:
1 сутки = 86400с;
1 час = 3600с;
1 минута = 60с.

Сперва рассчитаем кол-во полных суток в данном кол-ве секунд [latex]n[/latex]: [latex]\frac{n}{86400}[/latex].
Затем уберём кол-во секунд в полных сутках из исходного числа, а из оставшихся вычислим кол-во полных часов: [latex]\frac{n\bmod86400}{3600}[/latex].
Далее снова уберём кол-во секунд в полных часах и найдём кол-во полных минут: [latex]\frac{\left(n\bmod8640\right)\bmod3600}{60}[/latex].
Остаток от деления общего кол-ва секунд на [latex]60[/latex] и будет искомым кол-вом секунд: [latex]n\bmod60[/latex].

Ссылки

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

e-olymp 1474. Сломанные часы

Задача

Broken Clocks

В электронных часах произошел сбой, и теперь каждую секунду увеличивается не счетчик секунд, а счетчик часов. При переполнении счетчика часов (то есть при достижении $24$) он сбрасывается в $0$ и увеличивается счетчик минут. Аналогично, при переполнении счетчика минут происходит его сброс и увеличивается счетчик секунд. При переполнении счетчика секунд он также сбрасывается в $0$, а остальные счетчики так и остаются равными $0$. Известно, что сбой произошел в $h_1$ часов $m_1$ минут $s_1$ секунд. В этот момент часы показывали правильное время.

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

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

В первой строке задаются три целых числа $h_1$, $m_1$, $s_1$, определяющие время поломки часов. Во второй строке записаны три числа $h_2$, $m_2$, $s_2$, которые определяют показания часов в текущий момент времени ( $0\;\le\;h_1,\;h_2\;\lt\;24$, $0\;\le m_1,\;m_2,\;s_1,\;s_2\;\lt\;60$ ).

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

В единственной строке выведите правильное время (т.е. число часов, минут и секунд) в момент, когда сломанные часы будут показывать $h_2$ часов $m_2$ минут $s_2$ секунд.

Тесты

Входные данные Выходные данные
$12\;0\;0$
$12\;1\;0$
$12\;0\;24$
$13\;59\;59$
$12\;59\;59$
$13\;59\;58$
$15\;12\;16$
$15\;12\;16$
$15\;12\;16$
$0\;0\;0$
$23\;59\;59$
$23\;59\;59$
$16\;0\;17$
$16\;0\;18$
$16\;24\;17$
$11\;0\;53$
$0\;0\;0$
$13\;48\;42$
$1\;13\;18$
$22\;51\;32$
$7\;4\;51$

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

Решение

Учитывая особенности хода сломанных часов, подсчитаем количество секунд в начальный и конечный моменты времени (  sum1  и sum2 ). Вычислим, сколько секунд прошло с момента поломки часов — для этого найдём разность sum2 - sum1 , прибавим $86400$ —  количество секунд в сутках (поскольку мог произойти переход через момент времени $0\; : \;0\; : \;0$) и найдём остаток от деления полученной суммы на $86400$.

Теперь найдём количество секунд, прошедших с начала суток, в которых поломались часы ( time1 ). Прибавим к нему количество секунд, прошедших с момента поломки часов и найдём остаток от деления на $86400$ полученного числа. Имеем  time2  — правильное время в секундах. Далее, находим значения счётчиков часов $h_3$, минут $m_3$ и секунд $s_3$ которые соответствуют моменту времени  time2.

Ссылки

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

Ввод данных: Scanner vs StreamTokenizer

Разберемся с одним из подходов к вводу данных из стандартного потока через класс java.util.Scanner. Сделаем это на примере простой задачи с очень полезного сайта e-olimp.com

Задача

Введите из стандартного потока одно число. В предположении, что это положительное двузначное целое число выведите в стандартный поток вывода каждую его цифру отдельно (через пробел). Порядок цифр менять не следует.

Тесты

Никаких специфических случаев в алгоритме не предполагается. Делаем три теста — самое маленькое число допустимого диапазона, самое большое и какое-нибудь значение из середины диапазона.

Вход Выход
10 1 0
99 9 9
54 5 4

Решение

Воспользуемся классом java.util.Scanner, чтобы ввести данные в формате целого числа. И вычислим обе его цифры.

Пояснения

  1. Описываем переменную i типа java.util.Scanner и тут же присваиваем ей значение нового объекта этого класса. Конструктор изготавливает объект Scanner‘а из стандартного потока ввода. Т.е. i становится надстройкой над стандартным потоком ввода. Это позволяет нам прочесть целое число, а не просто читать методом read() по одному байту.
  2. С помощью метода nextInt() читаем последовательность цифр и преобразуем её в целое число. Число запоминаем в переменной n.
  3. n / 10 — число десятков в числе. Десятков будет в десять раз меньше чем само число. Выполняется целочисленное деление — деление нацело.
  4. n % 10 — вычисляем остаток от деления на десять — число единиц — самая правая цифра числа.
  5. n / 10 + » » + n % 10 — вставляем между двумя целыми строку из одного пробела. В этом случае числа также преобразуются в строковое представление и все три строки сливаются — называется конкатенация строк. Так работает со строковыми данными операция «+».

Ускоряем ввод/вывод

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

Возможно, стоит посмотреть на этот шаблон для решений.

Далее

Попробуйте найти все цифры трёхзначного числа.

Если удалось справиться с трёхзначным числом, решаем задачи из категории Линейные алгоритмы. Как можно больше. Даже если все кажется понятным. Тем более если все кажется понятным. Нам ведь нужно уметь писать программы, а не понимать как это делается. Тем более, что в каждой задаче вероятно придется выяснить что-то новенькое для себя.