e-olymp 8371. Четное или нечетное

Задача

Задано натуральное число $n$. Определить его четность.

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

Одно натуральное число $n$ $\left(1 \leq n \leq 10^{9}\right)$.

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

Если число $n$ четное, то вывести EVEN. Если нечетное, то вывести ODD.

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 1 ODD
2 99 ODD
3 500 EVEN
4 1000000000 EVEN

Код программы (Линейные вычисления)

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

Если число четное, то будет выполняться условие n%2==0, тогда выводим EVEN. Если число нечетное, то будет выполняться условие n%2==1, тогда выводим ODD.

Код программы (Ветвление)

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

Число четное, если оно делится на $2$ без остатка, значит выполняется условие: n % 2 == 0. В противном случае, число будет нечетным.

Ссылки

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

Код программы на IdeOne (Линейные вычисления)

Код программы на IdeOne (Ветвление)

e-olymp 1326. В хоккей играют настоящие…

Задача

prb1326 Лесные жители решили провести хоккейный турнир между $N$ командами. Сколькими способами могут быть распределены комплекты золотых, серебряных и бронзовых медалей, если одно призовое место может занять только одна команда?

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

В единственной строке расположено единственное натуральное число $N$, не превышающее 100.

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

Единственное число — искомое количество способов.

Тесты

Ввод Вывод
1 1 1
2 2 2
3 3 6
4 5 60
5 56 166320
6 100 970200

Код

Решение

Чтобы рассчитать количество способов воспользуемся формулой размещения из комбинаторики $A_N^k = \frac{N!}{(N−k)!}$, где $k = 3$, так как существует всего 3 призовых места и следовательно комплекты медалей можно распределить $N$$(N — 1)$$(N — 2)$ способами, при $N >= 3$. При $N < 3$ существует всего $N$ способов распределения, так как команд меньше чем призовых мест.

Ссылки

e-olymp
ideone

e-olymp 2062. Лилавати

Задача взята с сайта e-olymp

Задача

Крупнейшему индийскому математику XII в. Бхаскаре принадлежит трактат «Сиддханта-широмани» («Венец учения»), переписанный в XIII в. на полосках пальмовых листьев. Этот трактат состоит из четырех частей, из которых «Лилавати» посвящена арифметике, «Биджаганита» — алгебре, остальные две части астрономические. «Лилавати» (что значит «прекрасная») Бхаскара посвятил своей дочери.

Многие свои задачки Бхаскара излагал в поэтической форме, вот одна из них:

Из множества чистейших цветков лотоса
Третья часть была принесена в дар Шиве,
Пятая часть – Вишну, шестая часть – Солнцу;
Четвёртую часть всех цветков получил Бхвани,
А оставшиеся шесть цветков были даны высокочтимому Учителю.

Мы не можем дословно передать всю прелесть и красоту звучания этих стихов Древней Индии, поэтому нашу задачку сформулируем в прозе. Итак, эта же задачка в общем виде: «В дар Шиве принесли A-ую часть цветков лотоса, в дар Вишну – B-ую часть, в дар Солнцу – C-ую часть, для Бхвани досталась D-ая часть и высокочтимый Учитель получил E цветков. Сколько всего цветков лотоса было в распоряжении дарившего?»

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

В первой и единственной строке входных данных заданы через пробел 5 неотрицательных целых чисел: A, B, C, D и E, каждое из которых не превышает 100.

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

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

Тесты

# Входные данные Выходные данные
1 3 5 6 4 6 120
2 8 8 0 4 20 40
3 2 10 20 0 1 -1
4 2 3 20 60 1 -1
5 2 4 8 16 1 16

Код

Решение

Целое это 1, поэтому [latex]1-(\frac{1}{a}+\frac{1}{b}+\frac{1}{c}+\frac{1}{d})=\frac{1}{e}[/latex]

В свою очередь общее количество цветков будет [latex]e\cdot(\frac{a\cdot b\cdot c\cdot d}{a\cdot b\cdot c\cdot d-(b\cdot c\cdot d+a\cdot c\cdot d+a\cdot b\cdot d+a\cdot b\cdot c)})[/latex]

Остается учесть что входные данные могут иметь нули. И в конце проверить чтоб количество цветов принесённых в дар было целым числом для каждого из Богов.

Ссылки

ideone
e-olymp

e-olymp 8522. Делимость

Задача

Заданы два натуральных числа $a$ и $b$. Проверьте, делится ли $a$ на $b$.

Входные данные: Два натуральных числа $a$ и $b$ $(1 \le a, b \le 10^9)$

Выходные данные: Если $a$ не делится на $b$ нацело, вывести в одной строке частное и остаток от деления $a$ на $b$. Иначе вывести "Divisible".

Тесты

$a$ $b$ Вывод программы
15 3 Divisible
12 7 1 5
15 23 0 15
1000000000 889879 1123 665883

Continue reading

e-olymp 1452. Кролики

Задача взята с сайта e-olymp.

Задача

Как-то наконец земляне нашли обитаемую планету, назвали ее ТТВ, и отправили вместе с кораблем туда одного кролика. Кролику понравился климат новой планеты и через месяц он произвел на свет еще одного кролика. Известно, что каждый месяц каждый кролик, присутствующий на планете, производил на свет еще одного кролика. На планете откуда-то взялся монстр, который в начале месяца съедал [latex] k [/latex] кроликов, если только их становилось строго больше [latex] k [/latex]. В задаче необходимо определить количество кроликов, которое будет на планете через [latex] n [/latex]месяцев после прибытия туда космического корабля с первым кроликом.

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

Первая строка содержит количество месяцев [latex] n [/latex] [latex] (0 ≤ n ≤ 100) [/latex], вторая — число кроликов [latex] k [/latex] [latex]  (0 ≤ k ≤ 10000) [/latex], которое съедал монстр.

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

Определить количество кроликов, которое будет находиться на планете ТТВ через [latex] n [/latex] месяцев после поселения туда первого кролика. Известно, что результат для любого теста всегда не больше [latex] 2 \cdot 10^9 [/latex].

Тесты

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

1

0 10

1

2

1 10

2

3

10 7

128

4

7 128

12

5

30 0

1073741824

6

29 29

2

7

20 20

16

8

90 90

64

Cпособ 1 (с циклом)

Код

 

Решение

Известно, что изначально на планете был один кролик. Создадим цикл, который будет высчитывать популяцию кроликов на планете через [latex] n [/latex] месяцев после прибытия. Цикл будет работать до тех пор, пока количество месяцев будет больше нуля. В нем будем высчитывать популяцию кроликов по простой формуле [latex] r = r \cdot 2 [/latex], где [latex] r [/latex] — количество кроликов. Если же количество кроликов, съедаемых монстром в начале месяца строго больше того количества, которое уже есть на планете, то от этой популяции отнимем [latex]  k [/latex]кроликов : [latex] r = r[/latex] $-$ [latex] k [/latex]. Внутри цикла также не забываем от данного количества [latex] n [/latex] месяцев отнимать по одному каждый раз.

Способ 2 (без цикла)

Код

Решение

Сам алгоритм похож на 1 способ, однако здесь мы будем использовать рекурсивную функцию, а не цикл. Функция  int f2();  будет вызывать сама себя до тех пор, пока количество месяцев [latex] n [/latex] не станет равным нулю.

Ссылки

Засчитанное решение на e-olymp.

1 Код в ideone.

2 Код в ideone.

e-olymp 2. Цифры

Задача

Вычислить количество цифр целого неотрицательного числа $n$.

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

Одно целое неотрицательное число $n$ [latex](0 \ge n \ge 2\cdot10^9)[/latex].

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

Количество цифр в числе $n$.

Тесты

Входные данные Выходные данные
12345 5
1 1
353628 6
5454 4
0 1

Код программы (с использованием условных операторов)

 

Код программы (без использования условных операторов)

Решение

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

Ссылки

E-Olymp

Ideone (с условными операторами)

Ideone (без условных операторов)

e-olymp 8531. Делимость на числа

Задача

Задано натуральное число [latex]n.[/latex] Делится ли оно одновременно на [latex] a\ [/latex] и на [latex] b?[/latex]?

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

Три натуральных числа [latex] n, a, b,[/latex] не больших [latex] 10^{9}.[/latex]

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

Выведите «YES» если [latex] n\ [/latex] делится одновременно на [latex] a\ [/latex] и на [latex] b\ [/latex]. Выведите «NO» иначе.

Тесты

Ввод Вывод
1 12 4 6 YES
2 10 5 6 NO
3 1056 22 6 YES
4 98 103 5 NO

Решение

Проверим делимость [latex] n\ [/latex] на [latex] a\ [/latex] и [latex] b.[/latex] Число $n$ делится одновременно на $a$ и $b$ тогда, когда и остаток от деления $n$ на $a$ равен $0$ ( n % a == 0), и остаток от деления $n$ на $b$ равен $0$ ( n % b == 0).

Код с ветвлением

Код без использования ветвления

 

Ссылки

e-olymp 8527. Неравенство ax ≤ b

Задача:

Для заданных целых чисел $a$ и $b$ найти наибольшее и наименьшее целое решение неравенства [latex]ax\leq b [/latex].

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

Два целых числа $a$ и $b$, по модулю не превосходящих $1000$.

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

Если неравенство [latex]a x\leq b [/latex] не имеет решений, то вывести no solution.

Если любое действительное число является решением неравенства [latex]ax\leq b [/latex], то вывести all.

Иначе в одной строке вывести наименьшее и наибольшее целое решение неравенства [latex]ax\leq b [/latex]. Если наименьшего целого решения не существует, вывести -INF. Если наибольшего целого решения не существует, вывести INF.

Тесты:

Входные данные Выходные данные
0 4 all
0 0 all
0 -1 no solution
289 133 -INF 0
-150 -298 2 INF
3  10 -INF 3
956 0 -INF 0
-3  10 -3  INF
-3  0 0 INF
1000 1000 -INF 1
-1000 -1000 1 INF
-1000 1000 -1 INF

Решение: 

Объяснение:

Задача сводится к решению неравенства $ x\leq\frac{a}{b} $ или $ x\geq\frac{a}{b},$ в зависимости от значений параметров $a$ и $b.$ Поэтому необходимо рассмотреть все возможные варианты значений $a$ и $b$ от которых будет зависеть значение неравенства.  Если $a>0$, то выражение  будет равносильно $ x\leq\frac{a}{b} $, так как знак неравенства при делении на положительное число не меняется. Поскольку, нам нужно, чтобы $x$ был меньше данного выражения (либо равен), значение которого может быть и дробным (поэтому тип данных $a$ и $b$ дробный, хоть по условию, нам и нужен целый ответ), округляем в меньшую сторону. В обратном случае  ($a<0$ и, следовательно, исходное выражение эквивалентно $ x\geq\frac{a}{b}$) нам нужно наоборот, большее значение, поэтому и округление производится в большую сторону. Затем остается рассмотреть только частный случай $a=0$ , что и делается в начале кода.

e-olymp

ideone

e-olymp 8520. Условный оператор — 1

Условие

Вычислите значение $ y $ в соответствии со следующим условием:

[latex] y=\begin{cases}x^{2} — 3x +4 , x<5\\x + 7 , x\geq 5\end{cases} [/latex]

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

Одно целое число [latex] x (-1000\leq x\leq 1000) [/latex].

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

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

Тесты

входные данные выходные данные
 1             2             2
 2             10             17
 3             15             22
 4             32             39

Решение

Решение этой задачи довольно простое. Мне потребовалось создать условие, где если $ x $ меньше пяти, то [latex]y=x^{2}-3x+4 [/latex] , а для  $ x $ больше или равняется пяти [latex]y=x+7 .[/latex]

e-olymp
ideone.com

Без условного оператора :

Решение I

Используем логический оператор $ && $ так как он не вычисляет второе условие, если первое ложно.

ideone.com

Решение II

Для вычисления используется тернарный оператор который проверяет условие и выполняет действие [latex]y=x^{2}-3x+4 [/latex] если условие вернет истину (true) или С если условие возвращает ложь (false).

ideone.com

Решение III

В этом решении используется оператор множественного выбора switch, который сравнивает $ x $ со значением заложенным в  case, а после выполняет действие [latex]y=x^{2}-3x+4 [/latex]. Если значения не совпадают, тогда выполняется [latex]y=x^{2}-3x+4 [/latex].

ideone.com

e-olymp 8372. Составить треугольник

Задача взята с сайта e-olymp

Задача

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

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

Три натуральных числа $a, b, c (1 ≤ a, b, c ≤ 1000)$ — длины трех отрезков.

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

Вывести YES если из отрезков можно составить невырожденный треугольник и NO в противном случае.

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 5 6 7 YES
2 3 7 4 NO
3 16 24 32 YES
4 54 1 100 NO
5 1 1 1 YES

Код программы (Ветвление)

Код программы (Линейные вычисления)

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

Пусть $a, b, c$ – длины трех отрезков. Из них можно составить невырожденный треугольник, если длина каждых двух отрезков больше длины третьего (это условие известно как неравенство треугольника): | $b$ | < | $a$ | + | $c$ | \begin{cases} b + c > a\\a + c > b\\a + b > c\end{cases}

Ссылки

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

Код программы на ideone (Линейные вычисления)

Код программы на ideone (Ветвление)

e-olymp 3867. Ленивый Мишка

Задача. Ленивый Мишка

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

  • На мытье посуды уйдет [latex]t_1[/latex] секунд
  • Пропылесосить квартиру можно за [latex]t_2[/latex] секунд
  • Процесс игры с Маринкой займет [latex]t_3[/latex] секунд

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

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

Три целых числа [latex]t_1[/latex], [latex]t_2[/latex], [latex]t_3[/latex] ([latex]1 ≤ t_1, t_2, t_3 ≤ 1000[/latex]).

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

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

Тесты

Ввод Вывод
1 1 7 2 1
2 100 45 1 1
3 66 9 888 9
4 5 800 4 4
5 25 46 25 25
6 13 10 12 10
7 999 995 1000 995

Решение 1

Мишка выбирает мамино поручение, что занимает наименьшее количество времени. Нам дано время за которое Мишка выполнит данные поручения. Найдём из них наименьшее и выведем на экран. Воспользуемся функцией int min (int, int); из библиотеки cmath.

Код 1

Решение 2

Для нахождения минимума трёх чисел заведём переменную min и воспользуемся логическим ветвлением.

Код 2

Ссылки

Первое решение

Второе решение

Условие задачи

Компиляция первого решения

Компиляция второго решения

e-olymp 206. Турист

Задача

Гена собирается на туристический слет учеников своей школы. В своем классе он был назначен ответственным за палатки. У себя дома он нашел 3 палатки: первая их них весит [latex]a_1[/latex] килограмм и вмещает [latex]b_1[/latex] человек, вторая весит [latex]a_2[/latex] килограмм и вмещает [latex]b_2[/latex] человек, третья весит [latex]a_3[/latex] килограмм и вмещает [latex]b_3[/latex] человек.

В классе Гены [latex]k[/latex] человек. Выясните, может ли он выбрать палатки так, чтобы в них все могли поместиться. При этом учитывайте, что выбранные палатки должны суммарно весить не более [latex]w[/latex] килограмм.

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

Первая строка содержит два целых числа [latex]k[/latex] и [latex]w[/latex] ([latex]1 \le k \le 15[/latex], [latex]1 \le w \le 30[/latex]). Вторая строка содержит шесть целых чисел: [latex]a_1,  a_2,  a_3,  b_1,  b_2,  b_3[/latex] ([latex]1 \le a_1,  a_2,  a_3 \le 15[/latex], [latex]1 \le b_1,  b_2,  b_3 \le 30[/latex]).

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

Выведите YES, если палатки указанным образом выбрать можно, и NO в противном случае.

Тесты

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

5 5 6 6 4 5

YES
2 2

2 1 2 1 1 1

NO
15 30

10 3 10 5 11 7

NO
8 8

5 4 4 5 3 6

YES
5 30

6 1 12 2 10 1

NO

Код программы (вариант с тернарной операцией)

Код программы (линейный вариант)

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

Путем полного перебора получим несколько вариантов выбора палаток: взять одну из трёх палаток, две из трёх, или все три. Зададим переменную flag типа bool, принимающую значение, равное значению логического выражения, которое истинно лишь в случае удовлетворения хотя бы одного из вариантов условиям вместимости и веса, и ложно, если ни один из вариантов не удовлетворяет этим условиям. Затем с помощью тернарной операции выведем YES, если значение flag равно true, или NO, в случае противном.

Во втором варианте кода в выводе вместо тернарной операции используются операции математические, ведь условие «если А, то B, а иначе — C» на языке математики можно представить как BA — C(A-1), A = {0,1}, и так как переменная типа  boolсодержит в себе значение либо 0, либо 1, а литералы типа char содержат не сами символы, а их числовой код из таблицы ASCII, то это вполне реализуемо. В данном коде происходит последовательное выведение трёх символов типа  char: «Y», «E» и «S» в случае  flag = 1, и «N», «O» и пробел, если  flag = 0 .  

Ссылки

E-Olymp

Ideone (вариант с тернарной операцией)

Ideone (линейный вариант)

e-olymp 58. Биллиард

Задача


Биллиард представляет собой прямоугольник размерами $M \times N$, где $M$ и $N$ — натуральные числа. Из верхней левой лузы вылетает шар под углом $45^{\circ}$ к соседним сторонам. Лузы размещено только в углах биллиарда. Определите количество столкновений шара с бортами биллиарда, после которых он опять попадет в одну из луз, и номер лузы, в которую упадет шар. Считать, что трение отсутствует, столкновения абсолютно упругие, а шар — материальная точка.

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

Во входной строке два числа $M$ и $N$, $1 ≤ M, N ≤ 2000000000$. Нумерация луз по часовой стрелке, начиная с левой верхней лузы, из которой вылетел шар, согласно рисунка. $M$ — горизонтальная сторона биллиарда, $N$ — вертикальная сторона биллиарда.

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

Два числа: количество отражений шара и номер лузы в которую упадет шар.

Тесты

Входные данные Выходные данные
2 1 1 2
5 6 9 4
12 33 13 2
156 156 0 3
654 236 443 4

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

Решение

Чтобы решить эту задачу, необходимо найти НОД значений $M$ и $N$ из условия. Для этого, сперва нужно подключить библиотеку, содержащую функцию для нахождения НОД двух чисел, что мы и сделали во $2$ строке. Далее, в $8$ строке, введем перемененную g и присвоим ей значение НОД для $M$ и $N$. Теперь же, зная наш НОД, с его помощью можем подобрать эквивалентные числам из входного потока значения, которые будут, возможно, гораздо меньшими, чем изначальные, и работать уже с ними. В последующих строках находим искомые данные, причем количество отражений шара всегда находится по одной и той же формуле, в то время как номер лузы, в которую упадет шар, зависит от выполнения одного из трех условий, что и видно в коде.

Ссылки

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

e-olymp 2371. Черный квадрат

Условие

Вдохновленный шедевром Казимира Малевича «Черный квадрат», Петр Палевич решил создать собственную версию картины. Он приготовил полотно в виде прямоугольной сетки с $m \times n$ белыми квадратами — $m$ строк по $n$ ячеек каждая.

Петр покрасил некоторые клетки в черный цвет так, что черные ячейки сформировали квадрат размером $s \times s$ ячеек. Но на следующий день Петр разочаровался в своем творении и уничтожил его, разрезав полотно горизонтальными полосами размера $1 \times n$, после чего сжег их в камине.

На следующее утро Петр передумал и решил восстановить картину. Он попытался найти ее останки в камине, и, к счастью, одну из полос, а именно $k$-ую сверху, огонь не тронул.

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

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

Первая строка содержит четыре целых числа: $m$, $n$, $s$ и $k$ $ \left( 1 \leqslant m, n \leqslant 5000, 1 \leqslant s \leqslant \min \left( m, n \right), 1 \leqslant k \leqslant m \right) $.

Вторая строка содержит $n$ символов и описывает $k$-ую строку картины, ‘.’ означает белую клетку, ‘*’ означает черную клетку.

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

Если изображение может быть однозначно восстановлено, то следует вывести «Unique». Если существует несколько вариантов восстановления картины, то вывести «Ambiguous». Если ни одной соответствующей картины не существует, вывести «Impossible».

Тесты

Ввод Вывод
$3$ $4$ $2$ $3$
..**
Unique
$4$ $4$ $2$ $3$
*.*.
Impossible
$3$ $5$ $2$ $2$
.**.
Ambiguous
$2$ $8$ $1$ $2$
……*.
Unique

Код

String

C-string

Решение

Основная сложность задачи заключается в аккуратном рассмотрении всех возможных вариантов. После прочтения строки символов, которую представляет собой вытащенная из огня полоска, исследуем ее на количество подряд идущих символов ‘*’. Если последовательностей из звездочек в одной строке несколько, то никакие добавленные полоски не смогут сделать из нее квадрат, и тогда решений нет. Иначе дальнейшее решение делится на два случая:

  1. Спасенная из огня полоска не содержит звездочек. Тогда мы проверяем, может ли поместиться квадрат из звездочек хотя бы в одну из двух частей, на которые эта полоска делит картину. Если да, проверяем, однозначно ли определяем этот квадрат, или же имеется несколько вариантов его возможного расположения в них.
  2. Спасенная из огня полоска содержит звездочки. Тогда, если количество звездочек не совпадает с длиной стороны квадрата, то построить его невозможно, а иначе проверяем, однозначно ли определяем этот квадрат. Здесь необходимо аккуратно рассмотреть все «особенные» случаи, такие как квадрат, состоящий из одной звездочки, а также первая и последняя полоски картины. Очевидно, что в этих случаях расположение квадрата определяется единственным образом.

Если сравнивать, что выгоднее использовать в данной задаче для задания спасённой из огня полоски — строку или массив символов, — то использование строки способствует немного более быстрому решению задачи, чем массив символов; объём используемой памяти при этом не изменяется.

Ссылки

Условие на e-olymp.com
Код с использованием string на ideone.com
Код с использованием c-string на ideone.com

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 219. Центральное отопление

Задача

Кар Карыч с Пином восемнадцать часов подряд распивали холодные молочные коктейли и закусывали их мороженым. После этого Кар Карыч свалился со страшной простудой, а Пин решил провести в домик своему другу центральное отопление. Расчет количества отопительных приборов необходимо производить строго по ГОСТу 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

Алгортм решения

  1. Находим объём комнаты по заданным сторонам по формуле [latex]V=a \cdot b \cdot c[/latex].
  2. Делим полученный объём на объём, обогреваемый одной батареей.
  3. Округляем при необходимости полученный ответ вверх, чтобы найти минимальное количество батарей.

Округление

Если разделить объём [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

e-olimp 197. Отрезок и окружности

Задача

На плоскости задана система концентрических окружностей, центры которых находятся в начале координат, а радиусы равны $1, 2, 3, \ldots$ Также на плоскости задан отрезок, концы которого находятся в точках [latex] (x_{1};y_{1}) [/latex], [latex] (x_{2};y_{2}) [/latex].
Необходимо найти число общих точек этого отрезка и указанной системы окружностей.

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

Первая строка входного файла содержит 4 целых числа [latex]x_{1}[/latex], [latex]y_{1}[/latex], [latex]x_{2}[/latex], [latex]y_{2}[/latex]. Эти числа не превосходят $10^3$ по абсолютной величине. Заданный отрезок имеет ненулевую длину.

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

В выходной файл выведите ответ на задачу.

Тесты

Входные данные Выходные данные
-1 -1 1 1 2
-1 1 1 1 1
1 1 2 1 1
-5 -5 5 -5 5
-10 10 -10 10 28

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

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

Для начала рассмотрим первое условие. Пусть наш отрезок таков, что при движении от одного края к другому, расстояние до начала координат возрастает. Для такого отрезка ответ очевиден — это количество целых чисел между расстояниями от начала координат до обоих концов отрезка. Условие из шестнадцатой строчки кода получилось путем приведения подобных и раскрытия скобок следующих неравенств:
[latex]x_{1}^{2}+y_{1}^{2}-x_{2}^{2}-y_{2}^{2}+(x_{1}-x_{2})^{2}+(y_{1}-y_{2})^{2}<0[/latex] и [latex]-x_{1}^{2}-y_{1}^{2}+x_{2}^{2}+y_{2}^{2}+(x_{1}-x_{2})^{2}+(y_{1}-y_{2})^{2}<0[/latex]

Иначе сведем данную задачу к рассмотренной выше. Для этого необходимо найти на отрезке точку, ближайшую к началу координат. Таким образом исходный отрезок разбивается на два новых, для которых выполнено условие из простой задачи. Также следует рассмотреть крайний случай, а именно, если ближайшая к [latex] (0;0) [/latex] точка находится на целом расстоянии от начала координат. В этом случае мы посчитаем это пересечение дважды, поэтому необходимо уменьшить ответ на единицу.

Стоит заметить, что находить саму ближайшую точку нет необходимости. Достаточно найти лишь расстояние до нее. Также мы добавляем маленькую константу [latex]\varepsilon=10^{-8}[/latex] к большему расстоянию до конца отрезка и отнимаем из меньшего, чтобы избежать случая нахождения какой-либо точки отрезка на окружности. В противном случае решение задачи будет работать не корректно.

Ссылки

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

Код решения

 

e-olymp 76. Новый шкаф

ЗадачаНовый шкаф

Заданы размеры прямоугольной двери [latex]a[/latex], [latex]b[/latex] и размеры шкафа, который имеет форму прямоугольного параллелепипеда [latex]x[/latex], [latex]y[/latex], [latex]z[/latex]. Можно ли пронести шкаф сквозь дверь, если проносить его разрешается так, чтобы каждое ребро шкафа было параллельно или перпендикулярно стороне двери.

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

Пять действительных чисел [latex]a[/latex], [latex]b[/latex], [latex]x[/latex], [latex]y[/latex], [latex]z[/latex] ( [latex] 0\;\lt\;a,\;b,\;x,\;y,\;z\;\lt\;10[/latex] ).

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

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

Тесты

Входные данные Выходные данные
[latex]5\;7\;4\;6\;8[/latex] [latex]1[/latex]
[latex]1\;4\;2\;3\;6[/latex] [latex]0[/latex]
[latex]2.9\;6.7\;5.1\;3.7\;1.0[/latex] [latex]1[/latex]
[latex]4\;6\;6\;4\;3[/latex] [latex]1[/latex]
[latex]1.5\;8\;9.9\;2\;7.5[/latex] [latex]0[/latex]
[latex]2\;2\;2\;2\;2[/latex] [latex]0[/latex]
[latex]2\;3\;7\;8\;8[/latex] [latex]0[/latex]
[latex]5\;6\;2\;4\;3.5[/latex] [latex]1[/latex]

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

Решение

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

Имеем шесть возможных вариантов ширины и высоты грани шкафа — [latex](x,y)[/latex], [latex](y,x)[/latex], [latex](y,z)[/latex], [latex](z,y)[/latex], [latex](x,z)[/latex], [latex](z,x)[/latex]

Сравнивая их с размерами двери определяем, можно ли пронести шкаф сквозь дверь.

Ссылки

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

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

Задача

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

В голові приватного підприємця виникла ідея зробити асорті (змішати два види цукерок — популярні і не популярні). Взявши різну масу кожного виду цукерок Петро отримав асорті вартість [latex]1[/latex] кг якого [latex]A[/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

Код програми

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

За умовою завдання у нас єдине невідоме це кількість популярних цукерок в асорті. 1 кг = 1000 г. Таким чином складаємо рівняння з одним невідомим і отримуємо [latex]1000(A-N) / (P-N)[/latex].

Посилання

Посилання на 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]H[/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]H[/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]H[/latex]

в таком случае нам необходимо найти дугу [latex]NX_1[/latex],для этого умножив радиус на величину центрального угла: [latex]NX_1[/latex] =[latex]X_0 X_1 \times \arcsin \frac {H}{X_0 X_1}[/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_3} {X_0 X_1} [/latex]

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

1.1.2.1.2.1. [latex]X_0 X_1 < \sqrt{X_0 X_2^2 + H^2} [/latex]

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

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

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

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

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

1.2.1.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.1.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 \arcsin \frac{A}{X_0 X_1}[/latex]

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

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

1.2.2.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
Код решения