e-olymp 219. Центральное отопление

Задача

Кар Карыч с Пином восемнадцать часов подряд распивали холодные молочные коктейли и закусывали их мороженым. После этого Кар Карыч свалился со страшной простудой, а Пин решил провести в домик своему другу центральное отопление. Расчет количества отопительных приборов необходимо производить строго по ГОСТу 800333-90-06*. Для простоты Пин решил купить простые батареи. Согласно таблице 14.1.3 этого ГОСТа, каждая батарея обогревает определённый объём воздуха — ровно [latex]d[/latex] кубометров. Комната, которую собирается для своего друга обогреть Пин, имеет следующие размеры:

• высота [latex]a[/latex],

• ширина [latex]b[/latex],

• длина [latex]c[/latex].

Определите минимальное количество батарей, которое необходимо купить Пину. Учтите только, что если в домике у Кар Карыча температура будет ниже, чем по ГОСТу, Кар Карыч никогда не поправится.

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

Четыре целых числа [latex]a, b, c, d (a, b, c \leq 10^{5}, d \leq 2 \cdot 10^{9})[/latex].

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

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

Тесты

# Входные данные Выходные данные
1 2 3 4 2 12
2 4 5 7 3 47
3 75 61 88 50 8052
4 986 764 390 54 5440529
5 1 1 1 2000000 1

Алгортм решения

  1. Находим объём комнаты по заданным сторонам по формуле [latex]V=a \cdot b \cdot c[/latex].
  2. Делим полученный объём на объём, обогреваемый одной батареей.
  3. Округляем при необходимости полученный ответ вверх, чтобы найти минимальное количество батарей.

Округление

Если разделить объём [latex]V[/latex] на [latex]d[/latex] нацело, то в остатке у нас может получиться [latex]0, 1, 2, \ldots , d-1[/latex]. Добавив [latex]d-1[/latex] к объёму [latex]V[/latex] мы получим в делении нацело остатки [latex]d-1, d, d+1, \ldots , 2d-2[/latex]. Первое число [latex]d-1<d[/latex], поэтому при делении нацело оно даёт [latex]0[/latex]. Остальные числа больше либо равны [latex]d[/latex], но меньше [latex]2d[/latex], значит любое из них при делении нацело на [latex]d[/latex] даст [latex]1[/latex].

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

e-olymp 500. Ремонт

Задача

Ваш любимый дядя – директор фирмы, которая делает евроремонты в офисах. В связи с финансово-экономическим кризисом, дядюшка решил оптимизировать свое предприятие.

Давно ходят слухи, что бригадир в дядюшкиной фирме покупает лишнее количество стройматериалов, а остатки использует для отделки своей новой дачи. Ваш дядя заинтересовался, сколько в действительности банок краски необходимо для покраски стены в офисе длиной $L$ метров, шириной $W$ и высотой $H$, если одной банки хватает на $16$ метров квадратных, а размерами дверей и окон можно пренебречь? Заказов много, поэтому дядя попросил написать программу, которая будет все это считать.

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

В первой строке содержится количество заказов. Описание каждого заказа состоит из трех натуральных чисел $L$, $W$, $H$ — длины, ширины и высоты офиса в метрах соответственно, каждое из которых не превышает $1000$.

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

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

Тесты

 

Входные данные
Выходные данные
$1$
$1$ $1$ $1$
$1$
$3$
$8$ $7$ $10$
$15$ $8$ $4$
$3$ $5$ $4$
$19$
$12$
$4$
$2$
$27$ $88$ $19$
$999$ $999$ $999$
$274$
$249501$

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

читаем площадь стен комнаты как сумму площадей $4$ прямоугольников: $$hw + hl + hw + hl = 2hw + 2hl = 2h \cdot (w + l)$$ Теперь, зная площадь стен, рассчитаем количество банок краски. Для этого поделим площадь стен на $16$ и округлим вверх. Для округления вверх можно использовать тернарный условный оператор: если $s$ делится нацело на $16$, то ответ будет $\displaystyle \frac{s}{16}$, в противном случае – $\displaystyle \frac{s}{16} + 1$ (деление переменной int – целочисленное). Так как в задаче необходимо обрабатывать несколько таких примеров подряд, то все вычисления взяты в цикл от $0$ до $r$ (название переменной $r$ в самой задаче не указано, оно выбрано произвольно).

Ссылки

Условие задачи на 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 7369. Километровые столбы (Mileposts)

Задача

Андрей очень любит ездить по железной дороге. Он садится у окна и внимательно следит за местностью, которую он проезжает. Особенно он обращает внимание на километровые столбы. Каждый столб с километражем, который при делении на $7$ дает в остатке $3$, он считает «счастливым». Составьте программу, которая бы определяла количество «счастливых» столбов, если во время езды он проезжает столбы с отметками от $a$ до $b.$

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

Два натуральных числа $a$ и $b$ ($0 \leq a \lt b \leq 10^9$).

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

Вывести количество «счастливых» столбов.

Тесты

Входные данные Выходные данные
$0$ $5$ $1$
$26$ $49$ $3$
$73$ $80$ $2$
$5$ $8$ $0$
$17$ $37$ $3$

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

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

Количество «счастливых» столбцов $l$ от $0$ до $n$, то есть количество натуральных чисел $k$ от $0$ до $n$, таких, что $k \mod7 = 3$, равно количеству чисел от $0$ до $n-3$, делящихся нацело на $7$, увеличенному на $1.$ То есть $l = \lfloor \frac{n-3}{7} \rfloor +1 = \lfloor \frac{n+4}{7} \rfloor$. Тогда количество «счастливых» столбов на промежутке от $a$ до $b$ равно разности количества «счастливых» столбов на промежутке от $0$ до $b$ и количества «счастливых столбов» на промежутке от $0$ до $a$ не включительно. Отсюда получаем итоговую формулу решения, указанную в коде программы.
Поясним теперь использование класса java.io.BufferedReader вместо java.util.Scanner. Класс Scanner предоставляет удобный высокоуровневый инструментарий для парсинга целых чисел из входного потока, за что приходится расплачиваться производительностью. В силу достаточно малого ограничения по времени на работу программы мы вынуждены использовать более низкоуровневый инструментарий для чтения строки с параметрами из входного потока и самостоятельно парсить ее.

Ссылки

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

Решение задачи на 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.
Это увеличит объем кода, но сэкономит время.

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

Далее

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

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