e-olymp 1507. История Лаурела-Харди

Задача

Лаурел и Харди — два известных киногероя $50$-ых. Они известны своей разницей в весе, как можно увидеть на картинке. Если Вы еще не разобрались, кто из них кто, то я добавлю, что Лаурел легче. В свои юношеские годы Лаурел и Харди любили играть со странными качелями, и когда качели находились в равновесии, то Харди всегда был у земли. Мы рассмотрим двумерную версию качель.

Качели, которыми пользовались Лаурел и Харди, представляют собой часть окружности радиуса $r$, как показано на картинке (они закрашены серым и имеют вид буквы $D$). Харди сел на точку $B$ (самая правая точка качель), а Лаурел сел на точку $A$ (самая левая точка отрезка $AB$). $d = EF$ — расстояние между центром отрезка $AB$ и дуги $AFB$. То есть $E$ — середина отрезка $AB$, а $F$ — середина дуги $AFB$. $MN$ — основа качель, является горизонтальной прямой. $BD = h_1$ — расстояние от Харди до земли. Вам необходимо найти расстояние от Лаурела до земли (обозначаемое $h_2 = AC$).

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

Первая строка содержит количество тестов $N (0 < N ≤ 1000)$. Каждая из следующих $N$ строк представляет собой отдельный тест, который имеет следующий формат:

Каждая строка содержит три целых числа $r (10 ≤ r ≤ 100)$, $d (5 ≤ d ≤ r)$, $h_1 (5 ≤ h_1 ≤ d)$. Значение этих чисел приведено выше.

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

Для каждого теста в отдельной строке вывести его номер и действительной число — значение $h_2$. Это число должно содержать четыре десятичных знака. Формат вывода приведен в примере.

Тесты

Входные данные Выходные данные
2
10 10 10
10 7 6
Case 1: 10.0000
Case 2: 8.0342
3
12 7 7
11 11 8
54 12 6
Case 1: 7.0000
Case 2: 14.0000
Case 3: 19.7383
5
94 21 12
23 9 8
5 4 3
2 2 1
43 26 20
Case 1: 32.1226
Case 2: 10.0439
Case 3: 5.0440
Case 4: 3.0000
Case 5: 32.4231

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

Решение

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

В $10$ строке введем число $N$ из входного потока, а в $12$ — запустим цикл, который будет работать $N$ раз. Далее за каждый проход цикла будем читать по $3$ следующих числа из входного потока и выводить на экран номер текущего теста. Перед тем, как идти дальше, разберемся в рисунке. Так как по условию отрезок $EF$ делит сегмент $AFB$ пополам, то по свойствам хорд и дуг окружности, он является частью радиуса $r$ нашей окружности с центром в точке $O$ и перпендикулярен хорде $AB$, что и показано на чертеже. Кроме того, я дорисовал радиусы $OA$ и $OB$ окружности к соответствующим точкам и начертил отрезок $BH$, как продолжение $AB$, от точки $B$ до прямой $MN$. Также, я построил прямоугольный треугольник $\triangle OGB$, в котором катет $OG = r-BD$.
Достроив все необходимые отрезки, легко заметить, что мы имеем прямоугольный треугольник $\triangle ACH$ с катетом $AC$, длину которого нам и нужно найти по условию задачи. Предлагаю сделать это, воспользовавшись формулой $AC = AH \cdot \sin(\angle AHC)$. Найдем значения сомножителей.

Из рисунка очевидно, что $\angle AHC = \angle BHD = \angle EBG = \angle OBG-\angle OBE.$
Сначала найдем $\angle OBG$. Для этого рассмотрим треугольник $\triangle OGB$. Длины его гипотенузы и противолежащего к искомому углу катета нам уже известны, так что можем сразу найти $\angle OBG = \arcsin \frac{OG}{OB}$.
Теперь найдем $\angle OBE$. Рассмотрим прямоугольный треугольник $\triangle OEB$. В нем противолежащий искомому углу катет $OE = r-d$, а гипотенуза $OB = r$. Значит, $\angle OBE = \arcsin \frac{OE}{OB}$.
В итоге остаётся только найти разницу этих углов, которая и будет являться величиной искомого $\angle AHC$. В коде же значение этого угла считается в $17$ строке и присваивается переменной $a$.

Стоит заметить, что если $\angle OBG-\angle OBE = 0$, то длины отрезков $AC$ и $BD$, очевидно, совпадают. В таком случае можем сразу вывести на экран $h_2 = h_1$, как мы и поступили в $19$ строке, и перейти к нахождению $AC$ уже для следующего тестового случая.

Если же величина $\angle AHC$ отлична от $0$, то нам все еще предстоит посчитать длину гипотенузы $AH$ треугольника $\triangle ACH$. Она состоит из хорды $AB$ и отрезка $BH$.
Сперва найдем длину хорды. Известно, что $OF$ делит ее на $2$ одинаковых по длине отрезка, значит, следует опять рассмотреть треугольник $\triangle OEB$. Длину его гипотенузы и одного из катетов мы уже находили, так что просто применим теорему Пифагора и найдем $EB = \sqrt{OB^2-OE^2}$. Тогда $AB = 2 \cdot EB$.
Для нахождения длины $BH$, рассмотрим треугольник $\triangle BDH$, в котором этот отрезок является гипотенузой. Длину катета $BD$ и величину угла $\angle BHD$ мы уже знаем, значит, можем применить формулу $BH = \frac{BD}{\sin(\angle BHD)}$.
Сложим найденные значения длин хорды $AB$ и отрезка $BH$, чтобы получить $AH$. В коде эта длина находится в $17$ строке и присваивается переменной $b$.

Теперь остается только подставить найденные значения в ранее приведенную формулу и получить наконец длину $h_2$, которую выведем на экран в $23$ строке.

Ссылки

Условие задачи на e-olymp
Код решения на Ideone
Решение этой же задачи на C++

e-olymp 61. Уборка снега

Задача

Зимой, когда дни стают короче, а ночи длиннее, необходимо задуматься об уборке снега с улиц. Поскольку бюджет нашего города очень маленький, у нас в распоряжении только один снегоход. Несмотря на это дороги должны быть прочищены. И каждый раз, когда выпадает много снега, ночью снегоход нашего города выезжает со своего гаража и объезжает весь город, очищая дороги. Какое минимальное время нужно снегоходу, чтобы очистить все проезжие полосы всех дорог и вернуться назад?

При этом известно, что:

  • Снегоход может очищать только одну проезжую полосу дороги за один проход.
  • Все дороги прямые с одной полосой движения в каждом направлении.
  • Снегоход может поворачивать на любом перекрестке в любую сторону, а также может развернуться в тупике.
  • Во время очистки снега снегоход двигается со скоростью 20 км/час, и со скоростью 50 км/час по уже очищенной дороге.
  • Возможность проехать все дороги всегда существует.

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

Первая строка содержит два числа $x$ и $y$ ($-30000 \leq x, y \leq 30000$) — координаты ангара (в метрах), откуда начинает свое движение снегоход. Далее в каждой отдельной строке заданы координаты (в метрах) начала и конца улиц (по $4$ числа в строке). В городе может быть до $100$ улиц.

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

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

Тесты

Входные данные Выходные данные
$0$ $0$
$0$ $0$ $-1000$ $2000$
$0$ $0$ $1000$ $2000$
$0:27$
$0$ $1000$
$0$ $0$ $0$ $3000$
$0$ $0$ $1000$ $1000$
$0$ $0$ $3000$ $0$
$3000$ $0$ $3000$ $3000$
$3000$ $3000$ $0$ $3000$
$0$ $3000$ $1000$ $2000$
$3000$ $0$ $2000$ $1000$
$3000$ $3000$ $2000$ $2000$
$1:46$
$-500$ $0$
$-1000$ $0$ $0$ $0$
$0$ $0$ $1000$ $0$
$-1000$ $1000$ $0$ $0$
$-1000$ $1000$ $0$ $2000$
$0$ $2000$ $1000$ $1000$
$1000$ $1000$ $0$ $1000$
$0$ $1000$ $0$ $0$
$0:49$
$1000$ $500$
$-1000$ $0$ $1000$ $0$
$-1000$ $1000$ $1000$ $1000$
$-1000$ $0$ $-1000$ $1000$
$1000$ $0$ $1000$ $1000$
$-1000$ $0$ $1000$ $1000$
$1000$ $0$ $-1000$ $1000$
$-1000$ $1000$ $0$ $2000$
$0$ $2000$ $1000$ $1000$
$1:20$
$500$ $-500$
$0$ $0$ $1000$ $-1000$
$1000$ $-1000$ $2000$ $0$
$2000$ $0$ $3000$ $-1000$
$3000$ $-1000$ $4000$ $0$
$4000$ $0$ $5000$ $-1000$
$5000$ $-1000$ $6000$ $0$
$0$ $0$ $8000$ $0$
$1:39$

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

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

Пусть граф $G = \left \langle V, U \right \rangle$ — граф, ребра которого — указанные в задаче дороги, а вершины — перекрестки. Граф $G$ — ориентированный, при чем, в силу того, что все дороги имеют двустороннее движение, из того, что $\left ( v_i, v_j \right ) \in U$ следует, что $\left ( v_j, v_i \right ) \in U.$ Из этого следует, что полустепень захода каждой вершины равна ее полустепени исхода, из чего, по критерию существования Эйлерова цикла, граф $G$ содержит Эйлеров цикл, т.е. существует путь, такой, что снегоход сможет очистить все дороги, пройдя по каждой ровно один раз в каждую сторону, следовательно длина такого пути будет равна удвоенной длине дорог. Снегоход всегда двигается со скоростью $V = 20 \text{км/час} = \frac{1000}{3} \text{м/мин}.$ По каждой из дорог снегоход проезжает два раза, таким образом общее искомое время минутах: $t = \frac{2L}{V} = \frac{3L}{500},$ где $L$ — длина всех дорог.
Замечание. Как видно из алгоритма решения, не имеет значения, где конкретно расположена точка начала движения, главное, чтобы она располагалась на одной из улиц.

Ссылки

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

Решение задачи на e-olymp

Код решения

e-olymp 520. Сумма всех

Сумма всех

Вычислите сумму всех заданных чисел.

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

Содержит [latex]n[/latex] [latex] (1 ≤ n ≤ 10^5) [/latex] целых чисел. Все числа не превосходят [latex]10^9[/latex] по абсолютной величине.

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

Выведите сумму всех заданных чисел.

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 [latex]2[/latex] [latex]4[/latex] [latex]6[/latex]
2 [latex]3[/latex] [latex]3[/latex]
3 [latex]1[/latex] [latex]2[/latex] [latex]3[/latex] [latex]2[/latex] [latex]1[/latex] [latex]9[/latex]
4 [latex]1[/latex] [latex]2[/latex] [latex]3[/latex] [latex]4[/latex] [latex]10[/latex]
5 [latex]0[/latex] [latex]0[/latex] [latex]0[/latex] [latex]0[/latex] [latex]0[/latex]

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

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

Пользователь вводит числа до тех пор, пока программа не завершит работу. Как только это случается, программа выдаёт ответ в виде суммы всех ранее введённых чисел. Также, стоит использовать переменную типа long из-за того, что сумма чисел может быть довольно большой и явно превышать максимальное допустимое значение для переменной типа int.

Ссылки

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

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

А137б

Задача

Даны натуральное [latex]n[/latex], действительные числа [latex]a_{1},\ldots,a_{n}[/latex]. Вычислить: [latex]a_{1}^{2},a_{1}a_{2},\ldots,a_{1}a_{n}[/latex]

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

Натуральное [latex]n[/latex], действительные числа [latex]a_{1},\ldots,a_{n}[/latex].

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

[latex]a_{1}^{2},a_{1}a_{2},\ldots,a_{1}a_{n};[/latex]

Тесты

Входные данные Выходные данные
6 4 -2 1.5 3 7 9 16 -8 6 12 28 36
12 7 5 -1 2.7 5 49 35 -7 18.9 35

Решение

Для решения этой задачи воспользуемся циклом for . Сначала прочитаем n . После этого прочитаем первую переменную и напечатаем ее квадрат. Далее в цикле будем cчитывать остальные $latex n$ переменных и выводить их произведения на первую переменную.

Пример работы программы можно увидеть на ideone.

e-olimp 7365

Ссылка на оригинал задачи

Задача «Молоко и пирожок»

Ученикам первого класса дополнительно дают стакан молока и пирожок, если вес первоклассника менее 30 кг. В первых классах школы учится [latex]n[/latex] учеников. Стакан молока имеет емкость 200 мл, а упаковки молока – 0.9 л. Определить количество дополнительных пакетов молока и пирожков, необходимых каждый день.

Тесты:

Количество детей Вес Количество упаковок молока Количество пирожков
3 30 29 30 1 1
5 25 41 56 20 20 1 3
4 30 30 30 30 0 0
7 25 26 27 28 29 23 24 2 7

Код:

Алгоритм:

  1. Объявление и ввод значений переменных.
  2. Используем цикл for для подсчета необходимого количества пирожков.
  3. На основе предыдущих данных и округления в большую сторону (метод  Math.ceil ), подсчитываем необходимое количество пакетов молока.
  4. Окончание работы программы.

Работающая версия программы на Ideone.com

Ссылка на источник

А136л

Постановка задачи

Даны натуральное число $latex n$, действительные числа $latex a_1,\cdots,a_n$. Вычислить: $latex |a_1*a_2*\cdots*a_n|$.

Тесты

$latex n$ $latex a_1$ $latex a_2$ $latex a_3$ $latex a_4$ $latex a_5$ $latex a_6$ $latex a_7$ $latex a_8$ $latex k$
4 5 -3 2 1 5.477225575051661
5 2 7 4 3 5 28.982753492378876
3 4 4 0 0
5 3 8 6 2.8 1.3 22.894541

Код

 

Описание решения

Объявляем переменную $latex n$ (количество элементов — это целое число, поэтому используем тип int) и переменную $latex p$ (произведение), она может быть вещественной, поэтому выбираем тип double.

В цикле for считываются элементы $latex a_1,\cdots,a_n$, где   вычисляется их произведение.

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

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

MS 7. Средняя зарплата

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

Входные данные
Фамилия работника name и величина его зарплаты salary.

Выходные данные
Средняя зарплата по компании.

Тесты

Входные данные Выходные данные
name salary  totalSalary/employeesNum
1. Ivanov 100 100
Ivanov 300 200
2. Smirnov 150 150
3. Popov 200 200

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

Пояснение

С потока данных считывается первое значение и записывается в переменную name. Затем считывается заработная плата и записывается в переменную sal. В переменную total записывается общая полученная сумма работниками, увеличивается счетчик количества выплат sum. Средняя зарплата считается по формуле среднего арифметического: [latex]x = \frac{total}{sum}[/latex] и выводится потоком вывода.

Ссылка на код по тесту 1.

Ссылка на источник.

 

MS1. Сумма всех нечетных чисел в диапазоне.

Задача

Необходимо суммировать все нечётные целые числа в диапазоне, который введёт пользователь с клавиатуры.

Тесты

Начало диапазона Конец диапазона Вывод
1 11 36
2 8 15
7 30 216

Решение

Задача(2)

MS13. Решение квадратных уравнений

Постановка задачи
Каждая четвёрка чисел входного потока представляет собой квадратное уравнение в такой форме [latex]ax^2+bx+c=d.[/latex] Выпишите через запятую решения этих уравнений (если это возможно).

Входные данные:
значения переменных

Выходные данные:
корни [latex]x_{1}[/latex], [latex]x_{2}[/latex], [latex]x_{3}[/latex] и нет корней

Тесты

Входной поток чисел Корни уравнений
1 2 -3 4 1 0 13 10 0 нет корней;
2 2 -0.5 2.2 0 5 0 -25 0 нет корней; -2.23607, 2.23607;
3 1 3 -4 -1 2 -7 11 0 -3.79128784747792, 0.7912878474779199; нет корней;

Решение

Ссылка на решение задания на онлайн компиляторе Ideone.com

Описание решения

Объявляем переменные a, b, c, d, D, x1x2, x3 типа double, где a, b, c, d — коефициенты квадратического уравнения, D — дискриминант, а x1x2, x3 — корни. Создаем цикл while, в котором производится решение квадратического уравнения. В нем проверяем, если дискриминант больше нуля, выводим корни x1 и x2. Если дискриминант равен нулю, то находим x3, иначе, если дискриминант отрицателен — не имеем корней (no roots).

А170

Постановка задачи

Даны натуральные числа [latex]n, a_{1}, a_{2},\ldots, a_{n} (n\geq 4)[/latex]. Числа [latex]a_{1}, a_{2},\ldots , a_{n}[/latex] — это измеренные в сотых долях секунды результаты [latex]n[/latex] спортсменов в беге на [latex]100[/latex] м. Составить команду из четырех лучших бегунов для участия в эстафете [latex]4\times100[/latex], т.е. указать одну из четверок натуральных чисел [latex]i, j, k, l[/latex], для которой [latex]1\leq i\leq j\leq k\leq l\leq n[/latex] и [latex]a_{i}+a_{j}+a_{k}+a_{l}[/latex] имеет наименьшее значение.

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

[latex]n[/latex] — количество бегунов [latex](n\geq 4)[/latex].
[latex]a_{1}, a_{2},\ldots, a_{n}[/latex] — результаты спортсменов в беге на [latex]100[/latex] м.

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

[latex]i, j, k, l[/latex] — номера спортсменов, избранных для команды [latex](1\leq i\leq j\leq k\leq l\leq n)[/latex]

Тесты

Входные данные Выходные данные
Количество спортсменов [latex](n)[/latex] Результаты бега спортсменов Номера спортсменов, избранных для команды
1 3 2.1  3.7  1.1 [latex]n[/latex] не должно быть меньше 4
2 4 1.4  2.1  0  0.2 Результаты должны быть больше 0
3 6 6.5  4.1  1.2  8  9.1  4.9 1  2  3  6
4 12 2.5  9  14  7.1  1.3  4.9  6.7  1.9  10.01  2.45  0.01  13 5  8  10  11

Посмотреть работу программы на примере четвертого теста можно на сайте ideone.

Решение

Описание решения

Отличительной особенностью задач из категории «потоковая обработка» является то, что обработка большого объема данных происходит циклически, без их запоминания. То есть, когда пользователь вводит в программу массив значений, программа запоминает очередное значение, обрабатывает его соответствующим образом, а потом заменяет новым поступившим значением. Это дает преимущество в использовании памяти перед программами, которые запоминают весь массив целиком.

Так как по условию размер отбираемой команды — [latex]4[/latex] бегуна ( final int teamSize = 4;), введем ограничение на количество бегунов в целом — их должно быть [latex]4[/latex] или больше, иначе программа выдаст сообщение об ошибке и завершит работу.

Введя количество бегунов n, пользователь после этого будет вводить результат каждого. Программа запоминает этот результат ровно на один шаг цикла ( double a = in.nextDouble();), за который разберется, что с ним делать, а затем заменит следующим результатом.

Так как программа не запоминает весь массив целиком, найти [latex]4[/latex] наименьших значения перебором не получится. Поэтому инициализируем [latex]2[/latex] массива, один из которых ( double[] resRun = new double[teamSize];) будет хранить результаты бегунов, отобранных в команду, а другой ( int[] nRun = new int[teamSize];) — их номера.

Результаты бегунов, отобранных в команду изначально равны нулю; это говорит о том, что еще ни один бегун в команду отобран не был. Результаты и номера первых [latex]4[/latex] бегунов мы запомним в этих массивах, так как иначе мы просто потеряем эти данные и больше не сможем сравнить их со следующими. Теперь, когда 4 бегуна отобраны, следует найти номер бегуна с наихудшим результатом (с помощью функции public static int FindMax(double[] resRun, int[] nRun)). Этот бегун — первый в очереди на замену, если очередной полученный результат вдруг окажется лучшим (меньшим). Следует отметить, что программа будет искать номер наихудшего бегуна лишь в тех случаях, когда этот бегун будет заменен; в ином случае, когда результат очередного бегуна хуже, мы замены в команде не производим, соответственно, худший бегун в команде остается тем же.

Таким образом, с каждым шагом цикла результаты отобранных в команду бегунов становятся либо меньше, либо остаются прежними. После обработки последнего введенного результата, мы получим массив resRun лучших результатов и массив nRun номеров этих бегунов. Остается лишь отсортировать номера бегунов ( Arrays.sort(nRun);), как того требует условие, и вывести их значения.