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

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

Задача

На плоскости задана система концентрических окружностей, центры которых находятся в начале координат, а радиусы равны $1,2,3\dots.$ Также на плоскости задан отрезок, концы которого находятся в точках $(X_{1}, Y_{1})$ и $(X_{2}, Y_{2}).$ Необходимо найти число общих точек этого отрезка и указанной системы окружностей.

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

Первая строка входного файла содержит 4 целых числа $X_{1}, Y_{1}, X_{2}, Y_{2}.$ Эти числа не превосходят $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

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

Решение

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

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

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

Ссылки

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

e-olymp 43. Количество участников олимпиады

Задача

Как известно, на вопрос о том, сколько у него учеников, древнегреческий учёный Пифагор отвечал так: «Половина моих учеников изучает математику, четвертая часть изучает природу, седьмая часть проводит время в молчаливом размышлении, остальную часть составляют три девы».

Секретарь олимпиады на вопрос: «Сколько зарегистрировано участников олимпиады по информатике?», отвечал подобно Пифагору: «$k$-тая часть участников начала решать первую задачу, $m$-тая часть – вторую, а $n$-ая – третью.

В то же время $d$ участников решают проблему: «С чего начать?». Ваша задача определить количество участников олимпиады $s$ или вывести $-1$, если секретарь ошибся.

Входные данные: в одной строке заданы числа $k, n, m, d (1 ≤ k, n, m, d ≤ 1000)$.

Выходные данные: вывести количество участников олимпиады $s$, или $-1$, если секретарь ошибся в своём сообщении.

Тесты

$k$ $n$ $m$ $d$ Выходные данные
2 4 7 3 28
4 5 2 1 20
3 7 5 4 -1
6 6 6 1 -1
2 3 6 4 -1
3 2 5 8 -1

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

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

Пусть $x$ — количество учеников Пифагора. Тогда $\displaystyle\frac{x}{2}$ — половина его учеников, тех, которые изучают математику. Следовательно, $\displaystyle\frac{x}{4}$ — ученики, которые изучают природу, а $\displaystyle\frac{x}{7}$ — ученики, которые проводят время в молчаливом размышлении. И, по условию задачи, есть так же три девы.

Получили уравнение вида $\displaystyle\frac{x}{2} + \frac{x}{4} + \frac{x}{7} + 3 = x$, в общем виде $\displaystyle\frac{x}{k} + \frac{x}{m} + \frac{x}{n} + d = x$.
Отсюда выходит, что $\displaystyle\frac{1}{k} + \frac{1}{m} + \frac{1}{n} + dx = 1;$

$\displaystyle\frac{mnx + knx + kmx + kmnd} {kmnx} = 1;$

$\displaystyle(mn + kn + km)x + kmnd = kmnx;$

Отсюда получаем формулу $\displaystyle x = \frac{kmnd} {kmn — mn — kn — km}$.

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

Для того, чтобы проверить, является ли переменная x целым числом или нет, используем метод floor()  из класса Math.

Помимо этого делаем проверку для суммы чисел $\displaystyle\frac{1}{k}$, $\displaystyle\frac{1}{n}$ и $\displaystyle\frac{1}{m}$, так как если оно больше $1$, то количество учеников становится отрицательным, что невозможно. В случае, если $\displaystyle\frac{1} {k} + \frac{1} {n} + \frac{1} {m} = 1$, а $d > 0$, то, это тоже невозможно, а значит, секретарь ошибся.

Так же делаем проверку, которая определяет, не являются ли числа $\displaystyle\frac{q}{k}$, $\displaystyle\frac{q}{n}$ и $\displaystyle\frac{q}{m}$ дробными, так как это бы тоже было ошибкой секретаря (напрмер, если $k = 6$, $m = 6$, $n = 6$, $d = 1$, то при подстановке в формулу мы получаем, что количество участников равно $2$, но тогда получается, что один участник решал сразу три задачи, что, по условию задачи, невозможно).

Если условие не проходит проверки, то выводится «$-1$».

Ссылки

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

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

Задача

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

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

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

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

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

Тесты

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

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

Решение

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

Ссылки

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

Mif 2. Максимум из трех

Задача

Даны действительные числа [latex]x[/latex], [latex]y[/latex], [latex]z[/latex]. Получить [latex]max (x, y, z)[/latex].

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

Действительные числа $latex x,y,z$.

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

[latex]max (x, y, z)[/latex]

Тесты

x y z max
8 3 5 8
9 16 7 16
5 125 150 150

Решение

Пусть даны действительные числа [latex]x[/latex], [latex]y[/latex], [latex]z[/latex]. Нужно получить [latex]max(x,y,z)[/latex]. Для этого вводим [latex]x[/latex], [latex]y[/latex], [latex]z[/latex]. Предполагаем, что $latex z$ хранит максимальное значение. Затем, используя оператор if, сравниваем $latex y, x$. Выводим максимальное значение.

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

A60г

Задача:
Пусть [latex]D[/latex] — заштрихованная часть плоскости и пусть [latex]u[/latex] определяется по [latex]x[/latex] и [latex]y[/latex] yследующим образом: [latex] u=\begin{cases}x^(2)-1;\text{if}(x,y)\in D \\\sqrt{\left| x-1\right|};\text{ another case }\end{cases}[/latex] (запись[latex](x,y)\in D[/latex] означает, что точка с координатами [latex]x,y[/latex] принадлежит [latex]D[/latex]).

Даны действительные числа [latex]x[/latex] и [latex]y[/latex]. Определить [latex]u.[/latex]

a60%d0%b3
Тесты:

ВХОД ВЫХОД
[latex]x[/latex] [latex]y[/latex] [latex]u[/latex]
1 0.3 0.3 0.836660
2 1 1 0.000000
3 2 2 1.000000
4 0 0 -1.000000

Код:

Решение:
Для решения задачи проверим не принадлежит ли выбранная точка полуплоскости [latex]y<0.[/latex] Затем следует проверить не лежит ли выбранная точка вне полукруга, радиус которого равен 1 . Следующим действием нужно проверить не находиться ли точка в вырезанной четвертине маленького круга, радиус которого равен 0.3.

Версия программы на Ideone.com

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

e-olymp 923. Время года

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

Определить название времени года по заданному номеру месяца, используя составные условия.

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

Одно число — номер месяца.

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

Для весенних месяцев вывести Spring, для летних — Summer, для осенних — Autumn и для зимних — Winter.

Тесты

Входные данные Выходные данные
1 5 Spring

Код

 

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

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

 

Посмотреть, как работает программа со входными данными $latex 12$ можно на сайте  ideone.

КМ259(б). Квартеты из клеток

Задача

Назовем квартетом четверку клеток на клетчатой бумаге, центры которых лежат в вершинах прямоугольника со сторонами, параллельными линиям сетки. Какое наибольшее число квартетов, не имеющих общих клеток, можно разместить на прямоугольнике [latex]mn[/latex] клеток?

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

[latex]m, n[/latex]

Вывод

[latex]x[/latex] -кол-во квартетов.

Тесты

m n x
8 6 12
16 7 24
17 8 29.75
15 11 37

Код

 

Решение

Если [latex]m[/latex] и [latex]n[/latex] четные то на прямоугольнике [latex]mn[/latex] можно разместить [latex]\frac{mn}{4}[/latex] квартетов. Если [latex]m[/latex] четное, а [latex]n[/latex] нечетное (и наоборот), то можно разместить [latex]m(n-1)[/latex]. И наконец если [latex]m[/latex] и [latex]n[/latex] — нечетные, то нужно рассматривать два случая:

  1.  [latex]n = 4k + 1[/latex], в этом случае у нас формула такая: [latex]\frac{m(n-1)}{4}[/latex]
  2. Иначе, у нас другая формула: [latex]\frac{ \left(m(n-1)-2\right)}{4}[/latex]

Ссылка на решение в ideone.

e-olymp 63. Анфиса и цветы

Задача. Анфиса и цветы

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

Мурзик одну из цветочных клумб сделал в виде шахматной доски размерами [latex]m[/latex] на [latex]n,[/latex] в каждой клеточке которой растет какой-то цветок. Иногда на эту клумбу он выводит на прогулку Анфису (да, не удивляйтесь, они действительно друзья). Анфиса, начиная всегда с верхнего левого угла передвигается по клумбе к правому нижнему и собирает цветы, причем таким образом, чтобы каждый раз проходить новым маршрутом, а Мурзик на выходе вручает ей кусочек сыра.
Посчитать, какое наибольшее количество кусочков сыра получит Анфиса, если она все время старается сохранить как можно больше цветов. При каждом очередном своем проходе Анфиса обязательно должна собрать как минимум один цветок.

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

В одной строке через пробел заданы два числа [latex]m[/latex] на [latex]n.[/latex]

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

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

<р2>Реализация

Проверить код можно тут.

Тестирование

Входные данные (m, n) Выходные данные
1 2, 3 3
2 3, 3 5
3 3, 4 7
4 4, 3 7
6 5, 7 25

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

Задана цветочная клумба в виде шахматной доски размерами [latex]m[/latex] на [latex]n[/latex]. Очевидно, что количество цветов на данной клумбе равно [latex]m\cdot n[/latex]. Пусть Анфиса, совершая свое очередное передвижение, начиная с левого верхнего угла клумбы и направляясь к правому нижнему, съедает [latex](m-1)\cdot (n-1)[/latex]  цветов, так как, согласно условию задачи, Анфиса обязательно должна собрать как минимум один цветок при каждом проходе. После каждого такого прохода на выходе она получает один кусочек сыра.

Следовательно, имеет место следующая формула: [latex]p=(m-1)\cdot (n-1)+1[/latex], где [latex]p[/latex] — наибольшее количество кусочков сыра, которое может получить Анфиса. Действительно, если [latex]m=2[/latex], [latex]n=3[/latex], то получаем [latex]p=3[/latex].

Mif 1

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

Даны действительные числа [latex]x, y[/latex]. Получить [latex]max(x,y)[/latex].

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

Два действительных числа — [latex]x[/latex] и [latex]y[/latex].

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

Число, являющееся максимумом из двух чисел — [latex]maxOfTwo[/latex]

Тесты

Входные данные Выходные данные
1 3 4 4
2 -3 -5 -3
3 0 12 12

 

Решение:

Альтернативное решение:

 

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

Объявляем три переменные типа  int  —  x, y, maxOfTwo . Вводим с клавиатуры значения для  x и  y . После чего с помощью условного оператора  if-else  проверяем  x>y . Если истинно, присваиваем переменной  maxOfTwo  значение переменной  x , а иначе  MaxOfTwo = y . Выводим значение  MaxOfTwo  с помощью функции  System.out.println() .

Описание альтернативного решения:

Объявляем три переменные типа  int  —  x, y, maxOfTwo . Вводим с клавиатуры значения для  x и  y . Используя тернарный оператор  ?: проверяем истинность выражения  x>y и присваиваем результат операции переменной  maxOfTwo . Выводим значение  MaxOfTwo  с помощью функции  System.out.println() .