e-olymp8287.Петро підприємець

Задача

Петро приватний підприємець і він продає різні цукерки. Петро помітив, що деякі цукерки шалено популярні, а інші взагалі не користуються попитом.

В голові приватного підприємця виникла ідея зробити асорті (змішати два види цукерок — популярні і не популярні). Взявши різну масу кожного виду цукерок Петро отримав асорті вартість [latex]1[/latex] кг якого [latex]А[/latex] грн.

Знаючи, що популярні цукерки коштують [latex]P[/latex] грн/кг а не популярні [latex]N[/latex] грн/кг, а також значення [latex]А[/latex], знайдіть скільки грам популярних цукерок в асорті.

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

Три дійсних числа [latex]P[/latex], [latex]N[/latex], [latex]А[/latex] ціна [latex]1[/latex] кг різних видів цукерок, що входять до складу асорті,та ціна асорті.

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

Одне дійсне число округлене до десятих — кількість грамів популярних цукерок в асорті, або [latex]-1[/latex] якщо визначити не можливо.

Тесты

# Входные данные Выходные данные
1 100 50 75 500.00
2 100 100 5 -1
3 50 25 20 -1
4 50 30 30 0.0

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

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

По условию задачи у нас единственное неизвестное это количество популярных конфет в ассорти.Таким образом составляем уравнение с одним неизвестным и получаем формулу.

Ссылки

Ссылка на e-olymp
Ссылка на ideone

e-olymp 12. Поврежденная картина

Задача

Римская цифра [latex]I[/latex], стоявшая на полу комнаты в точке с координатами [latex]X_0[/latex], [latex]Y_0[/latex], [latex]0[/latex] не выдержала отношения к решению задачи «Римские цифры» и упала на пол. Поскольку нижний конец был прикреплен шарнирно, то он остался на месте, а верхний оказался в точке с координатами [latex]X_1[/latex], [latex]Y_1[/latex], [latex]0[/latex]. В комнате стояла строго вертикально бумажная картина. Зная координаты концов нижнего основания [latex]X_2[/latex], [latex]Y_2[/latex], [latex]0[/latex] и [latex]X_3[/latex], [latex]Y_3[/latex], [latex]0[/latex] и высоту картины [latex]H[/latex] найти длину «разрыва бумаги» на картине.

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

Во входной строке записано 9 чисел [latex]X_0, Y_0, X_1, Y_1, X_2, Y_2, X_3, Y_3, H[/latex]. Все входные данные — целые числа, модуль которых не превышает [latex]10^9[/latex].

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

Программа выводит единственное число – искомую величину с точностью до [latex]0.001[/latex].

Тесты

Входные данные Выходные данные
1 1 6 1 4 0 4 5 6 4.000
0 0 6 0 2 0 5 0 5 2.397
2 0 5 0 0 0 6 0 5 4.172
0 0 5 0 2 0 6 0 1 2.058
0 0 10 0 2 0 6 0 1 0.000

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

Эта задача интересна тем, что для ее решения необходимо смоделировать большое количество разнообразных взаиморасположений картины и буквы. Далее  будут использоваться следующие обозначения: [latex]X_0[/latex]- основание буквы, [latex]X_1[/latex] — ее вершины, [latex]X_2[/latex] и [latex]X_3[/latex] — координаты основания картины, [latex]Н[/latex] — высота картины.

1. [latex]X_0 X_1[/latex] и [latex]X_2 X_3[/latex] лежат на одной прямой

1.1. [latex]X_0[/latex] принадлежит [latex]X_2[/latex][latex]X_3[/latex]

1.1.1. [latex]X_1[/latex]принадлежит [latex]X_2[/latex][latex]X_3[/latex]

1.1.1.1 [latex]X_0[/latex][latex]X_1[/latex] не превышает [latex]Н[/latex]

В таком случае искомая величина — дуга [latex]O X1[/latex], равная [latex]\frac{1}{4} [/latex] длины окружности с радиусом, равным высоте буквы: [latex]O[/latex][latex]X_1[/latex] = [latex]\frac{П\times X_0 X_1}{2} [/latex]

 

1.1.1.2 [latex]X_0[/latex][latex]X_1[/latex] больше, чем [latex]Н[/latex]

в таком случае нам необходимо найти дугу [latex]PB[/latex],для этого умножив радиус на величину центрального угла: [latex]PB[/latex] =[latex]X_0 X_1 \times arcsin \frac{X_0 X_1}{H}[/latex]

1.1.2 [latex]X_1[/latex] не принадлежит [latex]X_2 X_3[/latex]

1.1.2.1 [latex]X_2[/latex] принадлежит [latex]X_0 X_1[/latex]

1.1.2.1.1 [latex]X_0 X_1[/latex] не превышает [latex]H[/latex]

В таком случае нам нужно найти дугу [latex]OM[/latex] по схожему с случаем 1.1.1.2 алгоритму: [latex]OM[/latex] = [latex]X_0 X_1 \times arcsin \frac{X_0 X_2} {X_0 X_1} [/latex]

 

1.1.2.1.2 [latex]X_0[/latex][latex]X_1[/latex] больше [latex]H[/latex]

В таком случае искомая величина равна дуге1 [latex]MN[/latex]= [latex]X_0 X_1 \times  arcsin \frac{H}{X_0 X_1} — arccos \frac{X_0 X_2}  {X_0 X_1}[/latex])

1.1.2 [latex]X_3[/latex] принадлежит [latex]X_0 X_1[/latex]

Данный случай аналогичен предыдущему. Единственное отличие заключается в том, что в формулах необходимо заменить [latex]X_0[/latex][latex]X_2[/latex] на [latex]X_0[/latex][latex]X_3[/latex]

1.2 [latex]Х_1[/latex] принадлежит [latex]X_2[/latex][latex]X_3[/latex]

введем новую переменную [latex]A[/latex], равную расстоянию от [latex]X_0[/latex] до картины.

1.2.1 [latex]X_0 X_1[/latex] меньше, чем [latex]\sqrt{A^2 + H^2}[/latex]

В данном случае нам нужно найти дугу [latex]M X_1[/latex] = [latex]X_0 X_1 \times arccos \frac{A}{X_0 X_1}[/latex]

1.2.2 [latex]X_0[/latex][latex]X_1[/latex] не меньше, чем [latex]\sqrt{A^2 + H^2}[/latex]

в этом случае нам нужно найти дугу [latex]МХ_1[/latex]= [latex]X_0 X_1 \times arсsin \frac{A}{X_0 X_1}[/latex]

 

1.3 обе вершины цифры не принадлежат картине

Обозначим через [latex]A[/latex] расстояние от [latex]X_0[/latex] до дальней вершины картины.

1.3.1 [latex]X_0 X_1 < \sqrt{A^2 + H^2} [/latex]

Искомая величина — дуга [latex]MN[/latex] = [latex]X_0 X_1\times  arcsin \frac{H}{X_0 X_1}  —  arccos \frac{A}{X_0 X_1}[/latex]

2. [latex]X_0 X_1[/latex] и [latex]X_2 X_3[/latex] не лежат на одной прямой

2.1. [latex]X_0 X_1[/latex] пересекает [latex]X_2 X_3[/latex]

В этом случае длина разрыва будет равна длине отрезка [latex]MN[/latex] либо высоте картины, если она окажется меньше вышеупомянутого отрезка.

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

Ссылки

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

e-olymp 1624. Послезавтра

Задача

По заданной дате требуется определить, какое число будет послезавтра.

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

Дано число, месяц и год (год — число в промежутке от 1 до 10000).

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

Требуется вывести, какое число будет послезавтра, в формате входных данных.

Тесты

# Входные данные Выходные данные
1 1 8 2009 3 8 2009
2 30 12 2009 1 1 2010
3 28 2 2008 1 3 2008
4 29 03 2017 31 03 2017
5 20 05 2012 22 05 2012

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

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

Для начала мы просто должны к заданной дате прибавить 2 дня.
Далее необходимо определить високосный ли год.
Чтобы определить, является ли год високосным, нужно выполнить следующие действия.
1. Если год делится на 4, перейдите к шагу 2. В противном случае перейдите к шагу 5.
2. Если год делится на 100, перейдите к шагу 3. В противном случае перейдите к шагу 4.
3. Если года делится на 400, перейдите к шагу 4. В противном случае перейдите к шагу 5.
4. Год является високосным ( 366 дней ).
5. Год не является високосным ( 365 дней ).
Дальше начинаем проходиться по месяцам, в месяцах с 31 днями, если значение дня больше 31 то берём остаток от деления этого значения на 31 и добавляем к месяцу единицу, следовательно с 30 днями, остаток от деления на 30 и так же прибавляем к месяцу единицу.
Для февраля мы должны учитывать високосный ли год. Если да, то 29 дней, если нет, то 28. Проделываем тоже что и в прошлый раз, только с остатком 29 или 28, в зависимости от года.
Для декабря, так как это последний месяц, если значение даты выходит больше 31, мы должны взять остаток от деления даты на 31, сбросить значение месяца до 1 и прибавить к значению года единицу

Ссылки

Задача на сайте 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

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

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

Сначала вводим 7 переменных: [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](x + y + z)[/latex], и их возможным количеством [latex](a + b + c — n)[/latex]. Тем самым, мы найдем количество людей, которые знают одновременно 3 языка.

Если же после ввода данных, окажется, что количество людей знающих два языка равно нулю [latex](x + y + z == 0)[/latex], то программа выведет, что людей знающих одновременно три языка также нет.

 

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

Зайцы в клетках

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

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

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

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

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

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

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

Тесты

Входные данные Выходные данные
3 50 17
5 5 1
1070 589 1
34 49 2

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

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

Пусть [latex]n[/latex] — количество клеток, и [latex]m[/latex] — количество зайцев.
Найдем отношение [latex]\frac{m}{n}[/latex]. Если это отношение больше либо равно единице то [latex]{m}\geq{n}[/latex] и мы имеем ответ. [latex]\frac{(m+n-1)}{n}[/latex] — это формула выводит ответ в целом виде, если он целый, и округляет в большую сторону, если он дробный. Иначе [latex]{m}\leq{n}[/latex] и максимальное гарантированное количество зайцев в одной клетке равно единице. Это следует из условия задачи.

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

e-olymp 143. Точка и треугольник

Точка и треугольник

Принадлежит ли точка [latex]O[/latex] треугольнику [latex]ABC[/latex]?

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

Содержит координаты точек [latex]O, A, B, C[/latex]. Числовые значения не превышают по модулю 100.

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

Вывести 1, если точка [latex]O[/latex] принадлежит треугольнику [latex]ABC[/latex] и 0 в противоположном случае.

Входные данные Выходные данные
1 2 6 -9 3 8 1 5 11 1
2 -13 10 -12 5 99 80 17 13 0
3 98 -50 -87 7 5 3 23 17 0
4 5 15 7 12 5 3 2 54 1
5 2 2 3 1 1 3 9 11 1

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

Решение

Для того, чтобы точка [latex]M[/latex] принадлежала треугольнику, заданному точками [latex]D([/latex]$x_{1}$,$y_{1}$[latex]), [/latex] [latex]E([/latex]$x_{2}$,$y_{2}$[latex]), [/latex][latex]F([/latex]$x_{3}$,$y_{3}$[latex]), [/latex] необходимо, чтобы псевдоскалярное (косое) произведение соответствующих векторов было больше либо равно нулю или же меньше либо равно нуля. Пользуясь формулой для косого произведения, запишем произведения векторов.
[$\overline{DE}$,$\overline{MD}$]=($x_{1}$-$x_{0}$) $\cdot$ ($y_{2}$-$y_{1}$)-($x_{2}$-$x_{1}$) $\cdot$ ($y_{1}$-$y_{0}$)
[$\overline{EF}$,$\overline{ME}$]=($x_{2}$-$x_{0}$) $\cdot$ ($y_{3}$-$y_{2}$)-($x_{3}$-$x_{2}$) $\cdot$ ($y_{2}$-$y_{0}$)
[$\overline{FD}$,$\overline{MF}$]=($x_{3}$-$x_{0}$) $\cdot$ ($y_{1}$-$y_{3}$)-($x_{1}$-$x_{3}$) $\cdot$ ($y_{3}$-$y_{0}$)
Если [$\overline{DE}$,$\overline{MD}$], [$\overline{EF}$,$\overline{ME}$] и [$\overline{FD}$,$\overline{MF}$] больше либо равно нулю или же меньше либо равно нуля, то точка принадлежит треугольнику.

 

Ссылки

Ссылка на Ideone
Ссылка на e-olymp