e-olymp 52. Сыр для Анфисы

Сыр для Анфисы

Готовя обед для Анфисы — символа 2008 года, хозяин использовал для разрезания сыра специальный нож, который разрезал сыр на одинаковые прямоугольные паралелепипеды с основанием в виде квадрата со стороной [latex]a[/latex] и высотой [latex]b[/latex].
Но Анфиса, как и подобает даме года, любила употреблять сыр несколько меньших размеров, для чего она всегда разрезала предложенный кусочек деликатеса на две части, предварительно установив его строго вертикально квадратом к столу. При разрезании нож всегда размещался по диагонали квадрата, но Анфисе не всегда удавалось разрезать кусочек пополам, так как плоскость лезвия ножа образовывала двугранный угол [latex]z^o[/latex] с плоскостью основания.
Найти площадь [latex]s[/latex] созданного Анфисой сечения.

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

Целые числа [latex]a[/latex], [latex]b[/latex], [latex]z[/latex], не превышающие [latex]90^o[/latex].

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

Площадь [latex]s[/latex] образованного сечения с точностью до трех десятичных знаков.

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 [latex]2[/latex] [latex]3[/latex] [latex]90[/latex] [latex]8.485[/latex]
2 [latex]2[/latex] [latex]4[/latex] [latex]0[/latex] [latex]0.000[/latex]
3 [latex]1[/latex] [latex]2[/latex] [latex]3[/latex] [latex]0.501[/latex]
4 [latex]1[/latex] [latex]1[/latex] [latex]100[/latex] [latex]1.615[/latex]
5 [latex]3[/latex] [latex]10[/latex] [latex]48[/latex] [latex]6.725[/latex]

 

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

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

Для решения данной задачи нам нужно рассмотреть 4 случая:
1) Если [latex]\cot[/latex] заданного угла не будет превышать [latex]\frac{a} {\sqrt{2} \cdot b}[/latex] и также не будет равен [latex]0^o[/latex] и [latex]90^o[/latex], то фигурой сечения получится треугольник. Его площадь мы сможем найти по формуле [latex]s = \frac {a^{2}} {2 \cos (z \cdot \frac {\pi} {180})}[/latex].
2) Заданный угол = [latex]0^o[/latex], следовательно площадь сечения также будет = 0, так как сыр нормально и не порежут.
3) Заданный угол = [latex]90^o[/latex], фигурой сечения будет прямоугольник, площадь которого мы сможем найти по формуле [latex]s = a \cdot b \cdot \sqrt{2}[/latex].
4) В любом другом случае, получится трапеция, площадь которой мы найдем по формуле [latex]s = \frac {a \cdot \sqrt{2} — b \cdot 1} {tan(z \cdot \frac{\pi}{180})} \cdot \frac {b} {sin (z \cdot \frac {\pi}{180})}[/latex].

Ссылки

• Задача на e-olymp.

• Решение на сайте ideone.

e-olymp 8288. Олимпиада по программированию

Олимпиада по программированию

На АСМ-олимпиаду прибыло [latex]N[/latex] участников. В результате анкетированные члены жури установили, что [latex]A[/latex] участников программируют на Cи, [latex]B[/latex] на Python, [latex]C[/latex] на Pascal, [latex]X[/latex] одновременно знают Cи и Python, [latex]Y[/latex] — Python и Pascal, [latex]Z[/latex] — Cи и Pascal. Имея значения [latex]N, A, B, C, X, Y, Z[/latex] установите количество участников, которые программируют на трёх языках программирования.

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

В одной строке через пробел сем действительных чисел [latex]N, A, B, C, X, Y, Z[/latex] значения которых не превышают [latex]100[/latex].

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

Единственное число – количество участников, которые программируют на трёх языках программирования.

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 100 40 50 60 15 20 25 10
2 100 50 60 60 20 40 25 15
3 80 50 40 60 20 30 25 5
4 80 50 40 60 0 0 0 0
5 40 20 30 0 5 0 10 5

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

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

Алгоритм решения данной задачи состоит в том, чтоб найти разность между числом участников, что одновременно знают по два языка $(X + Y + Z)$, и числом, что показывает на сколько языков больше чем людей (разностью между общим количеством языков и участников) $(A + B + C — N)$. Тем самым, мы найдем количество людей, которые знают одновременно 3 языка. Его также можно объяснить используя диаграмму Эйлера-Венна, на которой отмечено семь областей. Из условия следует, что:

$\begin {cases} x_1 &+ &x_2 &+ &x_3 &+ &x_4 &+ &x_5 &+ &x_6 &+ &x_7 &=N \newline x_1 &+ & & & &&x_4 &+ & & &x_6 &+ &x_7 &=A \newline & & &&x_3 &+ &x_4 &+ &x_5 &+ & & &x_7 &=B\newline & &x_2 &+ & & & & &x_5 &+ &x_6 &+ &x_7 &=C \newline & & &&& &x_4 && && &+ &x_7 &=X \newline & & & & && & &x_5 & & &+ &x_7 &=Y \newline & & & & & & & & & &x_6 &+ &x_7 &=Z \end{cases}$

Нам нужно найти количество участников в [latex]x_7[/latex] области (области одновременного пересечения всех трех кругов). И получается, что:

$(X + Y + Z)-(A + B + C — N)=x_7$

Если же после ввода данных, окажется, что количество людей знающих два языка равно нулю $(X + Y + Z == 0)$, то программа выведет, что людей знающих одновременно три языка также нет.

  • Задача на сайте e-olymp
  • Код решения в Ideone

e-olymp 74. Паук и муха — 2

Задача

В пустой прямоугольной комнате длины [latex]А[/latex], ширины [latex]В[/latex] и высоты [latex]С[/latex] муха упала на пол и уснула. Паук, находящийся на одной из стен, или на полу, или на потолке, начал двигаться к ней по кратчайшему пути.

spayder-and-fly-2-task

На какое расстояние он при этом переместится? Известно, что паук может передвигаться только по поверхности комнаты или же спускаться на паутине с потолка на пол, но только под прямым углом.

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

В первой строке заданы размеры комнаты [latex]A[/latex], [latex]B[/latex], [latex]C[/latex]. Во второй строке – координаты мухи на полу [latex]X1[/latex], [latex]Y1[/latex], [latex](0 ≤ X1 ≤ A[/latex], [latex]0 ≤ Y1 ≤ B)[/latex]. В третьей строке – координаты паука [latex]X2[/latex], [latex]Y2[/latex], [latex]Z2[/latex], [latex](0 ≤ X2 ≤ A[/latex], [latex]0 ≤ Y2 ≤ B[/latex], [latex]0 ≤ Z2 ≤ C)[/latex]. Все входные данные – целые не отрицательные числа, не превосходящие [latex]500[/latex].

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

Одно число – расстояние, на которое переместится паук, посчитанное с точностью до 2-х знаков после запятой.

Тесты

Входные данные Выходные данные
[latex]A[/latex] [latex]B[/latex] [latex]C[/latex] [latex]X1[/latex] [latex]Y1[/latex] [latex]X2[/latex] [latex]Y2[/latex] [latex]Z2[/latex] [latex]S[/latex]
[latex]4[/latex] [latex]7[/latex] [latex]3[/latex] [latex]2[/latex] [latex]1[/latex] [latex]3[/latex] [latex]7[/latex] [latex]2[/latex] [latex]8.06[/latex]
[latex]145[/latex] [latex]26[/latex] [latex]306[/latex] [latex]12[/latex] [latex]24[/latex] [latex]0[/latex] [latex]0[/latex] [latex]305[/latex] [latex]309.34[/latex]
[latex]26[/latex] [latex]18[/latex] [latex]53[/latex] [latex]24[/latex] [latex]15[/latex] [latex]24[/latex] [latex]1[/latex] [latex]53[/latex] [latex]58.52[/latex]
[latex]89[/latex] [latex]89[/latex] [latex]189[/latex] [latex]12[/latex] [latex]24[/latex] [latex]0[/latex] [latex]89[/latex] [latex]16[/latex] [latex]70.77[/latex]
[latex]18[/latex] [latex]26[/latex] [latex]145[/latex] [latex]14[/latex] [latex]2[/latex] [latex]17[/latex] [latex]26[/latex] [latex]141[/latex] [latex]147.14[/latex]

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

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

Данная задача решается с помощью «разверток» комнаты: переход от трёхмерного пространства к двумерному.
Вид комнаты:
room_3d
Рассмотрим такие случаи:

  1. Паук находится на полу ([latex]Z_2 = 0[/latex]);
  2. Паук находится на одной из стенок ([latex]X_2 = 0[/latex], или [latex]X_2 = A[/latex], или [latex]Y_2 = 0[/latex], или [latex]Y_2 = B[/latex] и [latex]Z_2 \neq 0[/latex]) либо на потолке ([latex]X_2 \neq 0[/latex], и [latex]X_2 \neq A[/latex], и [latex]Y_2 \neq 0[/latex], и [latex]Y_2 \neq B[/latex], и [latex]Z_2 = C[/latex]).

Первый случай тривиален и вычисляется по формуле [latex]\sqrt{(X_1 — X_2)^2 + (Y_1 — Y_2)^2}[/latex].
В случае, когда паук сидит на стенке, мы можем построить 3 развертки:
Допустим, паук находится на левой боковой стенке ([latex]X_2 = 0[/latex]). Остальные случаи аналогичны этому.

  • Паук ползет по этой стенке, затем по полу. Тогда развертка будет такой:
    deploy1
  • Паук ползет через ближнюю к нам стенку и по полу. Тогда развертка следующая:
    deploy2
  • Аналогичен предыдущему случаю, только через дальнюю от нас стенку.

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

  • Паук спускается с потолка на паутине, затем ползет точно так же, как и в самом первом случае.
  • Паук ползет по потолку, по одной из стенок и по полу. Тогда развертка будет выглядеть следующим образом (потолок можно развернуть в 4 стороны — отсюда 4 случая):
    deploy3
  • Паук ползет по потолку, а затем по двум соседним стенкам и по полу. Таких случаев 8, поскольку порядок следования стенок, по которым тот ползет, также важен. Развертка одного из них:
    deploy4

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

Ссылки

Условие задачи на e-olymp
Задача Дьюдени о пауке и мухе
Код решения

e-olymp 7107. Без лифта

Задача

Три друга – Андрей, Борис и Владимир живут соответственно на $a$, $b$ и $v$ этажах многоэтажного дома. Они занимаются спортом, поэтому никогда не пользуются лифтом. Однажды им потребовалось срочно встретиться у кого-то из них дома.

Составьте программу, которая определяла бы номер этажа, на котором они встретятся, при чем время до встречи было бы минимальным. Учтите, что скорость спуска по лестнице в $\frac{47}{31}$ раза больше, чем скорость подъема.

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

Программа получает на вход три натуральных числа – номера этажей, на которых живут друзья ($1 \leq a, b, v \leq 28$).

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

Программа выводит номер этажа, на котором они встречаются.

Тесты

Входные данные Выходные данные
$1$ $5$ $8$ $5$
$1$ $1$ $2$ $1$
$4$ $11$ $14$ $4$
$6$ $3$ $2$ $3$
$2$ $9$ $1$ $2$

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

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

По условию скорость спуска по лестнице в $\frac{47}{31}$ раза больше, чем скорость подъема. Назовем эту величину коэффициентом подъема.
Примем, что человек спускается на один этаж за единицу времени. Тогда он поднимается на один этаж за единицу времени, умноженную на коэффициент подъема.
Вначале необходимо установить, какой из этажей является максимальным, какой — минимальным, какой — промежуточным.
Очевидно, что друг, живущий на промежуточном этаже доберется до максимального этажа быстрее, чем тот, кто живет на минимальном, а также доберется до минимального этажа быстрее, чем тот, кто живет на максимальном. Кроме того, друг, живущий на максимальном этаже, быстрее спустится на минимальный этаж, чем живущий на минимальном поднимется на максимальный. Отсюда получаем, что если друзья будут подниматься на максимальный этаж, то потраченное время не будет наименьшим возможным. То есть друзья могут встретиться либо на минимальном, либо на промежуточном этаже. Время, потраченное на спуск на минимальный этаж, численно равно разнице между максимальным и минимальным этажом. Время, потраченное на путь к промежуточному этажу, численно равно максимуму между разницей между минимальным и промежуточным этажами, умноженной на коэффициент подъема и разницей между максимальным и промежуточным этажами. Так как разница между максимальным и промежуточным этажами всегда не превышает разницы между максимальным и минимальным этажами, то для определения искомого этажа нам достаточно сравнивать разницу между максимальным и минимальным этажами и разницу между минимальным и промежуточным этажами, умноженной на коэффициент подъема.
В случае, если первая величина будет меньше второй, то друзья должны встретиться на минимальном этаже, в противном случае — на промежуточном.

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

Ссылки

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

e-olymp 7337. Discounts

Task

In the supermarket of electronics, if you believe in TV commercials, there is a system of discounts: from two purchased goods fully paid only the cost of a higher-value product, and the other is provided free of charge. What amount of money is enough to pay for the purchase of three goods, if the price of each is known.

Input data:

Three natural numbers [latex]a, b, c[/latex] are prices of three products [latex]\left(1 ≤ a, b, с ≤ 10000\right)[/latex].

Output data:

Purchase cost.

Tests

# Input data Output data
1 2 2 2 4
2 78 2 45 80
3 452 89 88 540
4 50 4 67 71
5 15 37 20 52

Code

Solution of the problem

Algorithm: you will have to pay the highest price, so let’s find it at first and save it in the variable s. Next, you need to select the product for free receipt, which you put in a couple of the most expensive. To obtain the least amount of money, the remaining goods must be the cheapest.

Links

The task at e-olymp
The decision code at ideone

e-olymp 918. Какая четверть?

Задача

Задана точка с координатами [latex]x[/latex] и [latex]y[/latex]. Определить, в какой координатной четверти она расположена.

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

В единственной строке через пробел заданы [latex]2[/latex] вещественных числа — координаты точки, значения координат по модулю не превышают [latex]100[/latex].

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

Единственное число — номер соответствующей четверти, либо [latex]0[/latex] , если однозначно определить четверть невозможно.

Тесты

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

Выходные данные
[latex]x[/latex] [latex]y[/latex] Четверть
12 31 1
-10 18 2
-15 -25 3
13 -13 4
0 0 0

Решение

В прямоугольной системе координат на плоскости выделяют 4 четверти: 1, 2, 3, 4.
1-й четветри соответствуют точки, имеющие обе ([latex]x[/latex] и [latex]y[/latex]) положительные координаты.
2-ая четверть: [latex]x \lt 0[/latex], [latex]y \gt 0[/latex].
3-ая четверть: [latex]x \lt 0[/latex], [latex]y \lt 0[/latex].
4-ая четверть: [latex]x \gt 0[/latex], [latex]y \lt 0[/latex].
Точка с координатами ([latex]0[/latex];[latex]0[/latex]), находится в начале координат.
Если точка лежит на оси [latex]«Oy»[/latex], то её абсцисса равна [latex]0[/latex].
Если точка лежит на оси [latex]«Ox»[/latex], то её ордината равна [latex]0[/latex].

Ссылки

e-olymp
Ideone

e-olymp 2999. Функция — 10

Задача

Дана функция, аргументы которой – неотрицательные целые числа [latex]m[/latex] и [latex]n[/latex] [latex](m \leqslant n):[/latex]

$$f(m,n)=\begin{cases} 1, \text{ npu } m=0 \\\\ f(m-1,n-1)+f(m,n-1), \text{ npu } 0<m<n \\\\ 1, \text{ npu } m=n \end{cases}$$

Вычислить значение функции.

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

Два целых неотрицательных числа [latex]n[/latex] и [latex]m[/latex] [latex](0 \leqslant n, m \leqslant 20).[/latex]

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

Выведите искомое значение заданной функции [latex]f(m, n).[/latex]

Тесты

# Входные данные Выходные данные
1 4 2 6
2 7 7 1
3 12 0 1
4 15 5 3003
5 10 6 210

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

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

Для того, чтобы решить задачу, нам необходимо составить алгоритм, который будет вычислять значение заданной функции в зависимости от значения её аргументов. Для этого создадим специальную функцию [latex]func.[/latex] Строки 16 — 19 кода составляют тело функции. Программа выбирает, какую операцию ей нужно выполнить, в зависимости от определенного условия:

  1. Если [latex]m = 0[/latex] или [latex]m = n[/latex], то программа возвращает единицу.
  2. Если [latex]m < n[/latex], то программа вычисляет значение функции по формуле [latex]f(m-1,n-1)+f(m,n-1)[/latex]

Затем в главной функции вызываем нашу вспомогательную функцию [latex]func[/latex] с помощью новой переменной [latex]d[/latex] и выводим результат.

Ссылки

Ссылка на e-olymp

Ссылка на ideone

e-olymp 2370. Автоматизированная Телефонная Станция

Задача

В Санкт-Петербурге телефонные номера имеют формат “XXX — XX — XX” , где первые три цифры представляют собой индекс Автоматизированной Телефонной Станции (АТС). Каждая АТС имеет в точности $10000$ уникальных телефонных номеров. Петр только что приобрел новую квартиру и хочет установить телефонную линию. По его мнению телефонный номер является счастливым, если значение арифметического выражения, которое он собой представляет, равно нулю. Например, телефонный номер $102—40—62$ является счастливым $\left ( 102 — 40 — 62 = 0\right )$, а номер $157—10—47$ таковым не является $\left ( 157 — 10 — 47 \neq 0\right )$.
Петр знает индекс АТС, которая обслуживает его дом. Он хочет подсчитать количество счастливых номеров, которое она может иметь.

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

Единственное целое число $n$ — индекс АТС Петра $\left ( 100 \leq n \leq 999 \right )$.

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

Одно число — количество счастливых телефонных номеров, которые имеются у АТС Петра.

Тесты

Входные данные Выходные данные
$196$ 3
$239$ $0$
$101$ $98$

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

Решение

Рассмотрим случай, когда номер абонентской группы Петра $100,$ тогда счастливых номеров будет $ 99 \left ( 99+1, 98+2, \dots \right ).$ Далее рассмотрим случай, когда индекс $101,$ теперь количество счастливых номеров — $98 \left ( 99+2, 98+3, \dots \right ).$ В этом случае, если первые $2$ цифры после индекса и последние $2$ цифры номера будут равны $01,$ то этот номер уже не будет являться счастливым номером. Теперь на замену счастливому номеру $100 — 50 — 50$ идут $2$ счастливых номера: $101 — 50 — 51$ и $101 — 51 — 50.$ Суммарно количество счастливых номеров уменьшилось на $1.$ Пользуясь данной логикой, в каждой последующей абонентской группе будет на $1$ счастливый номер меньше. Для $n < 198$ счастливых номеров не будет. Следовательно, количество счастливых телефонных номеров, которые имеются у АТС Петра мы можем вычислить по формуле $199 — n$.

Ссылки

Ссылка на e-olymp

Ссылка на ideone

e-olymp-7410.Маршрутне таксі

Задача

У годину пік на зупинку одночасно під’їхали три маршрутних таксі, які слідують по одному маршруту, в які тут же набилися пасажири. Водії виявили, що кількість людей у ​​різних маршрутках різна, і вирішили пересадити частину пасажирів так, щоб у кожній маршрутці було порівну пасажирів. Потрібно визначити, яку найменшу кількість пасажирів доведеться при цьому пересадити.

Вхідні дані

Три натуральних числа, що не перевищують [latex]100[/latex] — кількості пасажирів у першій, другій і третій маршрутках відповідно.

Вихідні дані

Виведіть одне число — найменшу кількість пасажирів, яку потрібно пересадити. Якщо це неможливо, виведіть слово [latex]IMPOSSIBLE[/latex] (великими літерами).

Тести

Вхідні дані Вихідні дані
[latex]1[/latex] [latex]1[/latex] [latex]4[/latex] [latex]2[/latex]
[latex]1[/latex] [latex]2[/latex] [latex]4[/latex] [latex]IMPOSSIBLE[/latex]
[latex]1[/latex] [latex]3[/latex] [latex]5[/latex] [latex]2[/latex]
[latex]9[/latex] [latex]3[/latex] [latex]9[/latex] [latex]4[/latex]

Код програми

Рішення завдання

Спочатку відріжемо усі варіанти при яких розподілити пасажирів порівну не вийде так, що коли іх загальна кількість не ділиться націло на [latex]3[/latex] виводимо [latex]IMPOSSIBLE[/latex]. Коли розподілити пасажирів можна, розглядаємо [latex]4[/latex] випадки : коли у різних маршрутках кількість людей різна та коли у будь-яких двох маршрутках кількість однакова. Коли кількість різна, від максимальної кількості людей у трьох маршрутках віднімаємо число, яке дорівнює [latex]{{1}\over{3}}[/latex] від загальної кількості людей(у кінці ми маємо отримати це число, як кількість пасажирів у всіх маршрутних таксі), коли у двох маршрутках кількість однакова , то від кількості людей(у маршрутці, де іх більше або менше) віднімаємо число, яке дорівнює [latex]{{1}\over{3}}[/latex] від загальної кількості людей. Якщо відповідь менше [latex]0[/latex] то помножуюмо на [latex]-1[/latex].

Посилання

Умова завдання на e-olymp.com.

Код рішення на ideone.com.

e-olymp 130. Прямоугольник

Задача

Заданы координаты трёх вершин прямоугольника. Найдите координаты четвертой вершины.

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

В единственной строке записано шесть чисел — координаты трёх точек.

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

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

Тесты

Входные данные Выходные данные
[latex]0[/latex] [latex]0[/latex] [latex]0[/latex] [latex]1[/latex] [latex]2[/latex] [latex]1[/latex] [latex]2[/latex] [latex]0[/latex]
[latex]1\, 4\, 4\, 0\, 0\, 2[/latex] [latex]5\, 2[/latex]
[latex]-100[/latex] [latex]-100[/latex] [latex]100[/latex] [latex]100[/latex] [latex]100[/latex] [latex]-100[/latex] [latex]-100[/latex] [latex]100[/latex]
[latex]2[/latex] [latex]-1[/latex] [latex]3[/latex] [latex]1[/latex] [latex]-2[/latex] [latex]1[/latex] [latex]-1[/latex] [latex]3[/latex]
[latex]8\, 0\, 1\, 6\, 0\, 4[/latex] [latex]9\, 2[/latex]

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

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

Прямоугольник

Прямоугольник

Координаты четвертой вершины будут равны сумме координат прилежащих вершин минус координаты противоположной вершины, т. е: [latex]x_4=x_1+x_3-x_2[/latex] и [latex]y_4=y_1+y_3-y_2[/latex]. Но мы не знаем какая из входных вершин противоположна четвертой, а какие — прилежащие. Так как наша фигура это прямоугольник, то противоположная вершина будет при угле [latex]90^{\circ}[/latex]. Произведение перпендикулярных векторов дает [latex]0[/latex]. Перебрав три варианта произведения векторов, заданных входными вершинами, находим вершину при угле [latex]90^{\circ}[/latex]. Остальные две, соответственно, будут прилежащими. Находим координаты четвертой вершины по формуле, заданной выше.

Ссылки

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