Псевдо строчная таблица

Задача

В тридесятом государстве объявлено новое соревнование. Каждому участнику дается лист бумаги, ширина которого строго равна одному магическому метру, на котором надо начертить таблицу, имеющую размер $m \times n$. При этом для каждой ячейки таблицы указана минимальная площадь, которую должна эта ячейка занимать. Все строки таблицы равны между собой. Задача участников — начертить таблицу наименьшей высоты. Алиса снова очень хочет победить, но она все еще плохо знает математику, поэтому она просит Вас помочь ей в этом непростом деле.

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

Первая строка содержит два натуральных числа $m$ и $n$, $(1 \leqslant m,n \leqslant 100).$ Далее идут $m$ строк содержащие по $n$ натуральных чисел — $s_1, s_2, \cdots , s_{n-1}, s_n$ — минимальные площади каждой ячейки $(1 \leqslant s_i \leqslant 100).$

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

Вывести минимальную высоту таблицы.

Тесты

$2 \ 3$ $12$
$1 \ 2 \ 3 \\ 1 \ 2 \ 3$
$1 \ 3$ $10$
$2 \ 3 \ 5$
$4 \ 4$ $96$
$3 \ 5 \ 7 \ 9 \\ 3 \ 5 \ 7 \ 9 \\ 3 \ 5 \ 7 \ 9 \\ 3 \ 5 \ 7 \ 9$
$3 \ 1$ $6$
$2 \\ 2 \\ 2$
$5 \ 3$ $430$
$46 \ 28 \ 12 \\ 46 \ 28 \ 12 \\ 46 \ 28 \ 12 \\ 46 \ 28 \ 12 \\ 46 \ 28 \ 12$
$2 \ 6$ $216$
$7 \ 32 \ 3 \ 23 \ 12 \ 31 \\ 7 \ 32 \ 3 \ 23 \ 12 \ 31$
$7 \ 5$ $945$
$5 \ 21 \ 23 \ 8 \ 78 \\ 5 \ 21 \ 23 \ 8 \ 78 \\ 5 \ 21 \ 23 \ 8 \ 78 \\ 5 \ 21 \ 23 \ 8 \ 78 \\ 5 \ 21 \ 23 \ 8 \ 78 \\ 5 \ 21 \ 23 \ 8 \ 78 \\ 5 \ 21 \ 23 \ 8 \ 78$
$1 \ 1$ $5$
$5$
$3 \ 7$ $210$
$10 \ 10 \ 10 \ 10 \ 10 \ 10 \ 10 \\ 10 \ 10 \ 10 \ 10 \ 10 \ 10 \ 10 \\ 10 \ 10 \ 10 \ 10 \ 10 \ 10 \ 10$
$2 \ 2$ $202$
$100 \ 1 \\ 100 \ 1$

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

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

Так как все строки равны между собой, тогда решение задачи состоит в том, чтобы разбить таблицу на строки размером $1 \times n$ и найти их минимальную высоту. Как находить высоту $h$ для каждой такой строки было показано тут. Тогда минимальная высота всей таблицы равна $m \cdot h.$

Ссылки

Код решения

Строчная таблица

Задача

В тридесятом государстве объявлено соревнование. Каждому участнику дается лист бумаги, ширина которого строго равна одному магическому метру, на котором надо начертить таблицу, имеющую размер $1 \times n$. При этом для каждой ячейки таблицы указана минимальная площадь, которую должна эта ячейка занимать. Задача участников — начертить таблицу наименьшей высоты и вычислить ширину каждой ячейки. Алиса очень хочет победить, но она плохо знает математику, поэтому она просит Вас помочь ей в этом непростом деле.

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

Первая строка содержит натуральное число $n, \ (1 \leqslant n \leqslant 100).$ Вторая строка содержит $n$ натуральных чисел — $s_1, s_2, \cdots , s_{n-1}, s_n$ — минимальные площади каждой ячейки $(1 \leqslant s_i \leqslant 100).$

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

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

Тесты

Входные данные Выходные данные
$3$ $0.1333 \ 0.3333 \ 0.5333$
$2 \ 5 \ 8$
$6$ $0.0736 \ 0.2638 \ 0.3313 \ 0.0736 \ 0.1963 \ 0.0613$
$12 \ 43 \ 54 \ 12 \ 32 \ 10$
$2$ $0.3333 \ 0.6667$
$1 \ 2$
$3$ $0.3333 \ 0.3333 \ 0.3333$
$10 \ 10 \ 10$
$7$ $0.1250 \ 0.1250 \ 0.1250 \ 0.1250 \ 0.1250 \ 0.1250 \ 0.2500$
$1 \ 1 \ 1 \ 1 \ 1 \ 1 \ 2$
$1$ $1.0000$
$2$
$4$ $0.5102 \ 0.1735 \ 0.2653 \ 0.0510$
$100 \ 34 \ 52 \ 10$
$2$ $0.9901 \ 0.0099$
$100 \ 1$
$6$ $0.0702 \ 0.2515 \ 0.3158 \ 0.0351 \ 0.1287 \ 0.1988$
$12 \ 43 \ 54 \ 6 \ 22 \ 34$
$2$ $0.5000 \ 0.5000$
$2 \ 2$
$10$ $0.0182 \ 0.0364 \ 0.0545 \ 0.0727 \ 0.0909 \ 0.1091 \ 0.1273 \ 0.1455 \ 0.1636 \ 0.1818$
$1 \ 2 \ 3 \ 4 \ 5 \ 6 \ 7 \ 8 \ 9 \ 10$
$3$ $0.0098 \ 0.9804 \ 0.0098$
$1 \ 100 \ 1$

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

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

Пусть $h=\displaystyle\frac{1}{\gamma}$ — высота таблицы, а $x_1, \ x_2, \ \cdots, \ x_{n-1}, \ 1-x_1-x_2- \cdots -x_{n-1}$ – ширина каждой клетки. Тогда $\displaystyle\frac{x_1}{\gamma} \geqslant s_1, \ \displaystyle\frac{x_2}{\gamma} \geqslant s_2, \ \cdots, \ \displaystyle\frac{x_{n-1}}{\gamma} \geqslant s_{n-1}, \ \displaystyle\frac{1-x_1-x_2- \cdots -x_{n-1}}{\gamma} \geqslant s_n.$ Получаем $x_1 \geqslant s_1\gamma, \ x_2 \geqslant s_2\gamma, \ \cdots, \ x_{n-1} \geqslant s_{n-1}\gamma, \ 1-x_1-x_2- \cdots -x_{n-1} \geqslant s_n\gamma.$
Сделаем из неравенств равенства: $x_1=s_1\gamma+\varepsilon_1, \ x_2=s_2\gamma+\varepsilon_2, \ \cdots, \ x_{n-1}=s_{n-1}\gamma+\varepsilon_{n-1}.$
Имеем
$1-(s_1\gamma+\varepsilon_1)-(s_2\gamma+\varepsilon_2)- \cdots -(s_{n-1}\gamma+\varepsilon_{n-1}) \geqslant s_n\gamma \\
1 \geqslant (s_1+s_2+ \cdots +s_{n-1}+s_n)\gamma+\varepsilon_1+\varepsilon_2+ \cdots +\varepsilon_{n-1}
\\
\gamma \leqslant \displaystyle\frac{1-\varepsilon_1-\varepsilon_2- \cdots -\varepsilon_{n-1}}{s_1+s_2+ \cdots +s_{n-1}+s_n}.$
Максимальное значение $\gamma$ достигается при $\varepsilon_1=\varepsilon_2= \cdots =\varepsilon_{n-1}=0.$ Следовательно $\gamma \leqslant \displaystyle\frac{1}{s_1+s_2+ \cdots +s_{n-1}+s_n},$ а $h=s_1+s_2+ \cdots +s_{n-1}+s_n.$ Тогда ширина каждой ячейки будет равняться $\displaystyle\frac{s_i}{h}$

Ссылки

Код решения

e-olymp 48. Красные и синие квадраты

Задача

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

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

В первой строке находится количество синих квадратов $n$ ($0 < n < 40404$). Далее идут $n$ строк, каждая из которых содержит координаты $x$, $y$ ($-101 \leq x, y \leq 101$) левых нижних углов синих квадратов.

Каждый синий квадрат имеет хотя бы одну общую точку хотя бы с одним другим синим квадратом. Фигура, образованная синими квадратами, является связной.

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

Вывести количество красных квадратов.

Тесты

Входные данные
Выходные данные
$3$
$1$ $2$
$2$ $1$
$3$ $1$
$3$
$3$
$1$ $1$
$2$ $2$
$1$ $3$
$6$
$10$
$1$ $1$
$2$ $2$
$1$ $3$
$2$ $4$
$1$ $5$
$2$ $6$
$1$ $7$
$2$ $8$
$1$ $9$
$2$ $10$
$90$

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

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

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

Чтобы доказать это, пусть сторона квадрата равна $1$. Тогда периметр фигуры, составленной из этих квадратов, всегда будет делится на $2$ (это легко понять, строя такие фигуры на листке бумаги: добавление каждого нового квадрата в фигуру может изменить периметр только на $-4, -2, 0, 2, 4$). А так как периметр прямоугольника равен $2 * (a + b)$, где $a, b$ – стороны прямоугольника, то для существования прямоугольника с таким-же периметром должно выполняться условие $\forall p \in \mathbb{N} , p > 2 \rightarrow \exists a,b \in \mathbb{N} : 2p = 2*( a + b )$. Очевидно, что условие действительно выполняется для всех $p>2$.

Запишем нашу фигуру в массив squares. После чего посчитаем ее периметр: каждый непустой квадратик фигуры добавляет $1$ к периметру за каждую пустую клеточку слева, справа, сверху или снизу от него. Далее будем искать все подходящие прямоугольники, записывая максимальную площадь в переменную max: перебирая значения первой стороны $j$, высчитываем через периметр вторую сторону $i = \displaystyle \frac{p}{2} — j$. Площадь будем считать, как разницу площади прямоугольника и изначальной фигуры (число $n$ равно площади фигуры, потому что площадь каждого квадрата равна $1$).
В конце, выводим разницу максимальной площади и площади изначальной фигуры (площадь изначальной фигуры равна $n$, ведь площадь каждого квадрата равна $1$).

Ссылки

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

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 239. Треугольники

Задача

На плоскости задано [latex]n[/latex] точек с целочисленными координатами. Никакие три точки не лежат на одной прямой. Определить [latex]k[/latex] — количество треугольников с вершинами в заданных точках и целочисленной площадью.

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

В первой строке содержится число [latex]n[/latex]. В последующих [latex]n[/latex] строках содержаться пары целых чисел — координаты очередной точки [latex](x_i, y_i)[/latex]. Известно, что [latex]0 < n, |x_i|,|y_i| \leq 5000 [/latex].

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

Искомое число [latex]k[/latex].

Тесты

Входные данные Выходные данные
5
2 -1
3 0
0 4
-3 0
-2 1
6
5
0 0
2 4
6 6
10 34
-42 -48
10
4
0 0
0 1
1 0
1 1
0
8
0 0
2 2
1 1
3 3
0 1
2 1
1 0
1 2
24
5
0 0
0 1
-1 0
-1 -1
3 -3
3

 

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

Учитывая теорему Пика, получаем, что площадь каждого из треугольников, которые можно составить, либо равна целому числу, либо помимо целой части содержит [latex]\frac{1}{2}[/latex].  Нас интересует лишь четность псевдоскалярного(косого) произведения. Берем у всех координат остаток от деления на [latex]2[/latex]. Получаем не более [latex]4[/latex] различных точек: [latex] (0;0), (0;1), (1;0), (1;1)[/latex]. Составляем все возможные треугольники из полученных точек, и считаем те, у которых формула дает четное число, учитывая количество координат каждого типа.

Ссылки

Условие задачи на сайте  E-Olymp

код задачи на Ideone

описание теоремы Пика на Wikipedia

описание псевдоскалярного произведения на Wikipedia

e-olymp 1503. Вписанные треугольники

Задача

Пример первого теста на графике

На границе окружности с центром в начале координат и радиусом $r$ заданы $n$ различных точек. Поскольку все точки расположены на одной окружности, то любые три из них не коллинеарны, и поэтому образуют треугольник. Вам необходимо вычислить суммарную площадь всех этих $C_{n}^3$ треугольников.

Входные данные
Состоит из не более чем $16$ тестов. Каждый тест начинается двумя целыми числами $n \left(0 ≤ n ≤ 500\right)$ и $r \left(0 < r ≤ 100\right)$. Через $n$ обозначено количество точек, а через $r$ радиус окружности. Центр окружности находится в центре координат. Дальше следуют $n$ строк, каждая из которых содержит действительное число $θ \left(0 ≤ θ < 360 \right)$, которое определяет угол в градусах между точкой и направлением $x$-оси. Например, если $θ$ равно $30$ градусов, то соответствующая точка имеет декартовы координаты $\left(r \cdot \cos(30°), r \cdot \sin(30°) \right)$. Последняя строка содержит $n = r = 0$ и не обрабатывается.

Выходные данные
Для каждого теста в отдельной строке вывести целое число — суммарную площадь (округленную до ближайшего целого) всех возможных треугольников, образованных заданными $n$ точками.

Тесты

Входные данные Выходные данные
5 10
10
100
300
310
320
3 20
10
100
300
0 0
286
320
3 5
25
176
243
0 0
25
4 20
30
80
130
330
0 0
822
2 7
30
230
0 0
0

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

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

Радианная мера точек заносится в массив, после чего массив сортируется по возрастанию с помощью функции  sort().

В переменную res  изначально заносится площадь, равная площади кругов радиуса $r$,
то есть значение $C_{n}^3 \cdot \pi \cdot r^2 = n(n-1)(n-2)(n-2)\pi \cdot \frac{r^2} {6}$. Значение $\frac{r^2} {2}$ присваивается переменной r2, а sq – площадь одного круга, то есть $\pi \cdot r^2$.

Перебираются пары точек, а затем вычисляется угол.
Если угол меньше, то проходимся по меньшему сегменту, площадь которого равна $\pi r^2-0.5r^2(\alpha-\sin \alpha)$, $\alpha = 2\pi -\alpha$. В ином случае мы проходим по большему сегменту.
В любом случае переменной s  присваивается площадь сегмента, который мы проходим от $P_{i}$ к $P_{j}$ при движении против часовой стрелки.

Количество точек, лежащих на сегменте, равно $n-(j-i+1)$.
Значит, из переменной res необходимо вычесть площадь сегмента s такое количество раз, которому равно количество точек, то есть pts .

Количество точек, которые лежат на сегменте площади s , равно $n-2-  $  pts.
Площадь противоположного сегмента равна разности площади круга и сегмента. Для получения ответа вычитаем площадь противоположного сегмента из переменной res такое количество раз, которое равно значению переменной  pts и выводим полученное значение.

Ссылки

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