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

Related Images:

e-olymp 7460. Поездка на экскурсию

14/11/2017 by Андрей Святозар Чернецкий

Задача

Ученики 10-Б класса на осенние каникулы решили поехать на экскурсию в столицу. Зная количество мальчиков [latex]n[/latex] и девочек [latex]m[/latex], определить, сколько необходимо заказать комнат в отеле, в котором имеются комнаты на [latex]k[/latex] мест каждая, при условии что мальчиков и девочек поселять вместе запрещено.

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

В одной строке записаны три числа [latex]n[/latex], [latex]m[/latex], [latex]k[/latex] ([latex]n, m, k ≤ 100[/latex]).

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

Вывести одно число — количество комнат, которое необходимо забронировать в отеле.
Continue reading →

Related Images:

e-olymp 8. Спички

12/11/2017 by Алиса Ворохта

Задача

Какое минимальное количество спичек необходимо для того, чтобы выложить на плоскости [latex]n[/latex] квадратов со стороной в одну спичку? Спички нельзя ломать и класть друг на друга. Вершинами квадратов должны быть точки, где сходятся концы спичек, а сторонами – сами спички.

Напишите программу, которая по количеству квадратов [latex]n[/latex], которое необходимо составить, находит минимальное необходимое для этого количество спичек.

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

Одно целое число [latex]n[/latex] [latex](1 ≤ n ≤ 10^9)[/latex].

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

Вывести минимальное количество спичек, требуемых для составления [latex]n[/latex] квадратов.

Тесты

Входные данные	Выходные данные
[latex]1[/latex]	[latex]4[/latex]
[latex]2[/latex]	[latex]7[/latex]
[latex]4[/latex]	[latex]12[/latex]
[latex]7[/latex]	[latex]20[/latex]
[latex]150[/latex]	[latex]325[/latex]
[latex]10000[/latex]	[latex]20200[/latex]

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

#include <iostream>
#include <cmath>
using namespace std;
 
int main() {
    long long  n, k;
    long double length, width;
    cin >> n;
    length = floor(sqrt(n));
    width = ceil(n/length);
    k = 2*n + length + width;
    cout << k << endl;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

long long n, k;

long double length, width;

cin >> n;

length = floor(sqrt(n));

width = ceil(n/length);

k = 2*n + length + width;

cout << k << endl;

return 0;

}

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

Один квадрат можно составить из [latex]4[/latex] спичек. Два квадрата — из [latex]7[/latex] спичек. Очевидно, что квадраты следует располагать так, чтобы они образовывали прямоугольник, “близкий” к квадрату.
Например, на рисунке 1 мы использовали меньшее количество спичек, чем на рисунке 2, хотя количество квадратов одинаковое:

Зададим размеры прямоугольника. Пусть [latex]width = \sqrt n[/latex] — его ширина. Округлим значение [latex]width[/latex] к наибольшему целому числу, не превышающему данное. Тогда его длина будет [latex]length = \frac {n} {width}[/latex]. Если округлить значение [latex]length[/latex] к наибольшему целому числу, не превышающему данное, то мы сможем построить лишь те квадраты, которые входят в наш прямоугольник. Округляя же значение [latex]length[/latex] к наименьшему целому числу, которое не меньше данного, мы сможем достроить квадраты, не поместившиеся в наш прямоугольник.
Если отложить вниз количество спичек, равное [latex]width[/latex], и вправо — [latex]length[/latex], получается следующий рисунок (разумеется, количество отложенных спичек меняется в зависимости от [latex]n[/latex]):

Очевидно, что достроить треубемые квадраты можно, положив «уголки» из двух спичек, начиная с левого верхнего угла и двигаясь сверху вниз и слева направо.
«Уголок»:

Отсюда и получается формула: [latex]k = 2 \cdot n + length + width [/latex], где [latex]k[/latex] — количество спичек, требуемое в задаче.

Ссылки

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

Related Images:

KM31. Бумажные многоугольники

02/10/2016 by Тимур Фирсов

Задача

Задача из журнала «Квант» №7 1970 г.
Квадратный лист бумаги разрезают по прямой на две части. Одну из полученных частей снова разрезают на две части, и так делают много раз. Какое наименьшее число разрезов [latex]r[/latex] нужно сделать, чтобы среди полученных частей оказалось [latex]n[/latex] [latex]k[/latex] -угольников?

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

Количество многоугольников [latex]n[/latex].
Количество углов многоугольника [latex]k[/latex].

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

Количество разрезов [latex]r[/latex].

Пример получения двух шестиугольников за 5 разрезов

Тесты

	Входные данные		Выходные данные
№	[latex]n[/latex]	[latex]k[/latex]	[latex]r[/latex]
1	100	20	1699
2	14	3	13
3	1	3	1
4	40	360	14279
5	2	6	5

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

#include <iostream>
using namespace std;
 
int main() {
    int r, n, k;
    cin>>n>>k;
    r=k>3? n*(k-3)-1 : n>1? n-1 : 1;
    cout<<r;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int r, n, k;

cin>>n>>k;

r=k>3? n*(k-3)-1 : n>1? n-1 : 1;

cout<<r;

return 0;

}

Решение

При каждом разрезе количество кусков бумаги [latex]n[/latex] увеличивается на [latex]1[/latex]. Общее количество вершин [latex]k[/latex] будет увеличиваться в зависимости от места разреза. Таким образом при разрезе через две стороны общее количество вершин будет увеличиваться на [latex]4[/latex]. При разрезе через две вершины общее количество вершин увеличивается на [latex]2[/latex], а при разрезе через сторону и вершину — на [latex]3[/latex].

При [latex]k>3[/latex] сначала разделим лист на [latex]n[/latex] четырёхугольников при помощи разрезов через противоположные стороны. На это нам понадобиться [latex]n-1[/latex] разрезов. Затем можем, при помощи разрезов через соседние стороны, превращать каждый четырехугольник в [latex]k[/latex] — угольник, на что понадобиться [latex]k-4[/latex] разрезов.Выходит, что на получение [latex]n[/latex] [latex]k[/latex]- угольников нужно сделать не меньше [latex]n(k-4)+n-1[/latex] разрезов, значит [latex]r=n(k-3)-1[/latex].

Если же [latex]k=3[/latex], то нам нужно, наоборот, уменьшить количество вершин. Тогда первый разрез сделаем через две вершины квадрата — получаем два треугольника, затем каждым разрезом через вершину и сторону увеличиваем количество треугольников на [latex]1[/latex] пока не получим [latex]n[/latex]. В таком случае [latex]r= n-1 [/latex]. Исключение: если [latex]n=1[/latex], то [latex]r=1.[/latex]

Ссылки

Код программы.
Условие задачи (страница 47).

Related Images:

e-olymp 2061. Юные программисты

30/09/2015 by Андрей Яроцкий

Задача

Известно, что в школе не менее чем [latex]k_1[/latex] учеников, но не более чем [latex]k_2[/latex] учеников. Также известно, что каждый мальчик дружит с [latex]n[/latex] девочками, а каждая девочка с [latex]m[/latex] мальчиками. Какое минимальное количество учеников может быть в школе, и сколько в школе мальчиков и девочек?

Тесты:

№	Ввод	Вывод
1	20 30 4 5	27 15 12
2	40 50 5 4	45 20 25

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

#include <iostream>
using namespace std;
 
int main() {
   int k1, k2, n, m;
   int b, g; //b-boys;g-girls
   cin >> k1 >> k2 >> n >> m;
   for (g = n; true; g++)
   {
      b = g * m / n;
      if (((g * m) % n) == 0 && b + g >= k1) break; // перебираем варианты пока количество мальчиков не станет целым а сумма всех учеников будет больше k1
   }
   cout << b + g << " " << b << " " << g << endl;
   return 0;
}

#include <iostream>

using namespace std;

int main() {

int k1, k2, n, m;

int b, g; //b-boys;g-girls

cin >> k1 >> k2 >> n >> m;

for (g = n; true; g++)

{

b = g * m / n;

if (((g * m) % n) == 0 && b + g >= k1) break; // перебираем варианты пока количество мальчиков не станет целым а сумма всех учеников будет больше k1

}

cout << b + g << " " << b << " " << g << endl;

return 0;

}

Решение:

Увеличиваем количество девочек на 1 пока количество мальчиков по формуле [latex]b = g \cdot m / n[/latex] не станет целочисельным значением и сумма мальчиков и девочек будет больше или равна минимальному возможному количеству учеников [latex]k_1[/latex].

Условие задачи можно найти на сайте e-olymp.
Ссылка на решение задачи на ideone.com здесь.
Ссылка на полностью решенную задачу здесь.

Related Images:

Mif 16

29/09/2015 by Сплошнов Кирилл

Условие :

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

Решение :

Команда ветвления (конструкция «if {} else {}» или тернарный оператор «?» ) разделяет код программы с какого-то момента ровно на 2 независимых алгоритма (даже при отсутствии блока «else {}», так как программа продолжает выполняться в зависимости от того, сработал блок «if {}», или нет). Таким образом, если понимать под «вариантов поведения» изолированный блок кода, выполняемый при совпадении набора условий, чтобы разбить программу на [latex]n[/latex] таких независимых вариантов, нужно использовать ровно [latex]n — 1[/latex] условную операцию.

Тесты :

Входные данные	12	7	1	0
Выходные данные	11	6	0	Ошибка ввода

Код :

#include <iostream>
using namespace std;

int main() 
{
	int n;
	cin >> n;
	if (n > 0)
		cout << n - 1 << endl;
	else
		cout << "Ошибка ввода" << endl;
	return 0;
}