e-olymp 1610. Зайцы в клетках

13/09/2018 by Руслан Масальский

Задача взята с сайта e-olymp

Задача

Всем известен, так называемый, принцип Дирихле, который формулируется следующим образом:

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

В данной задаче мы рассмотрим более общий случай этого классического математического факта. Пусть имеется [latex]n[/latex] клеток и [latex]m[/latex] зайцев, которых рассадили по этим клеткам. Вам требуется расcчитать максимальное количество зайцев, которое гарантированно окажется в одной клетке.

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

В одной строке заданы два натуральных числа [latex]n[/latex] и [latex]m[/latex] (1 ≤ [latex]n[/latex], [latex]m[/latex] ≤ [latex]\ 10^{9}[/latex]).

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

Максимальное количество зайцев, которое гарантированно окажется в одной клетке.

Тесты

#	Входные данные	Выходные данные
1	3 4	2
2	15 144	10
3	1 7	7
4	100 123456	1235
5	222 222	1

Код

#include < iostream > 
#include < cmath > 
using namespace std;

int main() {
    long long n, m;
    cin >> n >> m;
    long long res = ceil(m / (double) n);
    cout << res;
    return 0;
}

#include < iostream >

#include < cmath >

using namespace std;

int main() {

long long n, m;

cin >> n >> m;

long long res = ceil(m / (double) n);

cout << res;

return 0;

}

Решение

Распределяя всех [latex] m [/latex] зайцев равномерно по клеткам [latex] n [/latex] получаем что максимальное количество зайцев в одной клетке равно [latex]\lceil \frac{m}{n}\rceil[/latex]

Ссылки

ideone
e-olymp

Related Images:

e-olymp 500. Ремонт

29/06/2018 by Павел Жуков

Задача

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

Давно ходят слухи, что бригадир в дядюшкиной фирме покупает лишнее количество стройматериалов, а остатки использует для отделки своей новой дачи. Ваш дядя заинтересовался, сколько в действительности банок краски необходимо для покраски стены в офисе длиной $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$

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

#include <iostream>
using namespace std;

int main() {
    int r;
    cin >> r;
    for(int i = 0; i < r; ++i){
        int l, w, h; 
        cin >> l >> w >> h;
        int s = 2 * h * (w + l);
        cout << (s % 16 != 0 ? s / 16 + 1 : s / 16) << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int r;

cin >> r;

for(int i = 0; i < r; ++i){

int l, w, h;

cin >> l >> w >> h;

int s = 2 * h * (w + l);

cout << (s % 16 != 0 ? s / 16 + 1 : s / 16) << endl;

}

return 0;

}

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

Рассчитаем площадь стен комнаты как сумму площадей $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

Related Images:

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

18/03/2018 by Никита Пушкин

Задача

Кар Карыч с Пином восемнадцать часов подряд распивали холодные молочные коктейли и закусывали их мороженым. После этого Кар Карыч свалился со страшной простудой, а Пин решил провести в домик своему другу центральное отопление. Расчет количества отопительных приборов необходимо производить строго по ГОСТу 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

#include <iostream>
using namespace std;
 
int main () {
    unsigned long long  a, b, c, d, v;
    cin>>a>>b>>c>>d;
    v = a * b * c;
    cout<<( v + d - 1 ) / d;
    return 0;
}

#include <iostream>

using namespace std;

int main () {

unsigned long long a, b, c, d, v;

cin>>a>>b>>c>>d;

v = a * b * c;

cout<<( v + d - 1 ) / d;

return 0;

}

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

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

Округление

Если разделить объём [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