e-olymp 8701. Кузнечик-попрыгунчик

Задача

Кузнечик-попрыгунчик долго сидел на отметке [latex]0[/latex] числовой прямой, так долго, что придумал инновационную методологию своего перемещения. Такую, что за каждую итерацию движения он выполняет ровно два прыжка, перемещаясь сначала на [latex]a[/latex], а затем на [latex]b[/latex] единичных отрезков по числовой прямой, причем, если число положительное, то он движется вправо, а если отрицательное, то влево. Продолжительность прыжка в секундах равна соответствующему количеству единичных отрезков, на которое переместится кузнечик.

Например, если [latex]a = 3[/latex], а [latex]b = — 2[/latex], то через [latex]3[/latex] сек. он будет на отметке [latex]3[/latex], а через [latex]5[/latex] сек. от начала движения попадет на отметку [latex]1[/latex]. Далее, на [latex]8[/latex] секунде переместится на отметку [latex]4[/latex], а на [latex]10[/latex] секунде вернется на [latex]2[/latex].

При заданных [latex]a[/latex] и [latex]b[/latex] найти сколько необходимо времени в секундах, чтобы допрыгать до отметки x числовой прямой или вывести [latex]-1[/latex], если это невозможно.

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

Целочисленные значения [latex]a[/latex], [latex]b[/latex], [latex]x[/latex] — в одной строке через пробел. Значение по модулю не превышают [latex]10^{9}[/latex].

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

Ответ на задачу.

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 3 -2 1 5
2 100 200 0 0
3 -10 -20 -900 900
4 5 1 5 5
5 1 3 10 -1

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

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

Для того, чтобы найти время которое нужно кузнечику чтобы добраться до необходимой точки, запустим цикл, отображающий процесс его передвижения. В переменной cur_pos будем хранить текущую позицию кузнечика, а в переменной cnt — время, которое понадобилось кузнечику чтобы добраться до cur_pos. Перед запуском цикла, с помощью условных операторов, проверим возможность кузнечика добраться до необходимой ему точки. Запустим цикл for, состоящий из [latex]x[/latex] итераций(за [latex]x[/latex] прыжков кузнечик определенно должен добраться до необходимой точки, так как расстояния, которые он преодолевает с помощью прыжков целочисленные, соответственно, расстояние минимального прыжка — 1). На каждой итерации цикла сначала перемещаем кузнечика на [latex]a[/latex] единичных отрезков, и проверяем добрался ли он до необходимой точки, а после перемещаем на [latex]b[/latex] единичных отрезков и проверяем то же условие. После выхода из цикла, в зависимости от значения переменной found выводим [latex]-1[/latex] или cnt, в случае если кузнечик все же добрался до необходимой точки.

Несмотря на то что тематика этой задачи «Массивы», эта задача решается без их помощи. Единственное применение массивам, которое я нашёл в этой задаче, это изобразить в качестве массива числовую прямую, но, к сожалению, из-за ограничений входных данных, минимальный размер такого массива составлял бы около 1 гигабайта.

e-olymp-1456. Барбос и Мухтар

Задача Барбос и Мухтар

Условие

На одной Большой Поляне росли два Больших Дерева – Большой Дуб и Большой Платан. К Большому Дубу были привязаны две собаки Барбос, длина цепи которого была равна $x$ метров, и Мухтар, длина его цепи $y$ метров. Однажды Барбосу надоело сидеть рядом с Мухтаром и он отбежал от Большого Дуба натянув свою цепь, Мухтар следуя примеру Барбоса, тоже решил подальше отбежать от Большого Дуба и тоже натянул свою цепь. Так они и сидели с натянутыми цепями, пока не заметили, что сидят на концах Прямой Тропы, на которой рос Большой Платан. Еще они заметили, что расстояние от Большого Дуба до Большого Платана равно расстоянию от Большого Дуба до Прямой Тропы. Также они не могли не заметить, что Барбосу в $z$ раз дальше бежать до Большого Платана по Прямой Тропе, чем Мухтару.

Каждая собака на Большой Поляне знает, что Большие Деревья – это материальные точки, а Прямая Тропа – отрезок прямой.

Помогите Барбосу и Мухтару узнать расстояние от Большого Дуба до Большого Платана.

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

Три вещественных числа $x$, $y$, $z$ (0 < $x, y, z $<[latex]10^7[/latex]) .

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

Вывести расстояние от Большого Дуба до Большого Платана с 9 десятичными знаками. Если это расстояние найти невозможно, то вывести слово IMPOSSIBLE.

 

Входные данные Выходные данные
1 12 23 3 24.023426067
2 11 10 120 9.999927078
3 1 3 3 3.162277660

 Решение

Решение

Пусть о — расстояние между Дубом и большим Платаном. После введения $x$, $y$ и $z$ проверяем первое условие if: если длины цепей Барбоса и Мухтара совпадают, то, когда обе собаки добежали до прямой тропы, треугольник, образованный их натянутыми цепями и прямой тропой является равнобедренным. Расстояние от Дуба до прямой тропы — высота треугольника, проведенная его основанию. Также основание высоты — Большой Платан (по условию). По свойству высоты, проведенной из вершины равнобедренного треугольника к его основанию, получим, что расстояние от Барбоса до Большого Платана равно расстоянию от Мухтара до Большого Платана, что противоречит условию (Барбосу в $z$ раз больше бежать до Большого Платана по Прямой Тропе, чем Мухтару). Также равенство расстояний до Большого Платана мы проверяем далее в условии: $(z==1)$. Если $z$ равен $1$, то эти отрезки равны, и утверждение, написанное выше, будет неверным. Проходя эту проверку, мы смотрим, удовлетворяют ли введенные данные условию задачи. Если утверждения в if выполняются — выводим IMPOSSIBLE, так как условия задачи не выполняются. В противном случае пропускаем первый if — данные введены корректно. Следующий условный оператор проверяет, равен ли $z$ нулю. Если да, то выводим y, потому что в таком случае расстояние от Дуба до Бльшого Платана равно длине цепи Мухтара. Именно Мухтара, так как, по условию, Барбосу бежать до Большого Платана дольше. Если данное условие не выполняется, вычисляем расстояние между деревьями по формуле: $\frac{(yy-xxzz)}{double(1-zz)}$
Затем выводим расстояние, округлив его до 9 знаков после запятой .

Ссылки

Ссылка на e-olymp

Ссылка на ideone

e-olymp 845. Открытка и конверт

Задача

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

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

В первой строке находятся размеры открытки, во второй — размеры конверта. Размеры открытки и конверта — целые положительные числа, не превосходящие $100.$

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

Если открытку можно вложить в конверт, вывести $Possible,$ если нет — вывести $Impossible$.

Тесты

Входные данные Выходные данные
1 1 10
9 9
Possible
2 20 40
2 4
Possible
3 50 20
40 40
 Impossible
4 10 4
5 5
 Impossible

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

Решение

Объявляем и вводим переменные $H$, $W$, $h$, $w$, где будем хранить длины открыток и конверта.
Потом находим наибольшую сторону конверта и открытки, найдем диагональ конверта.
Пользуясь тем, что мы знаем точно какие варианты «Possible» ставим выводим их, а в противном случае «Impossible».

Ссылки

ideone

e-olymp

e-olymp 3766. Тысячелетие

Задача

Мудрый король решил ввести новый календарь. «Завтра будет первый день календаря, то есть день [latex]1[/latex] месяца [latex]1[/latex] года [latex]1[/latex]. Каждый год состоит из [latex]10[/latex] месяцев, с [latex]1[/latex] по [latex]10[/latex], и начинается с большого месяца. Обычный год начинается с большого месяца, за которым следует малый месяц, затем большой месяц и так далее один за другим. То есть первый месяц большой, второй малый, третий большой, …, десятый, он же последний, малый. Большой месяц состоит из [latex]20[/latex] дней, а малый месяц из [latex]19[/latex] дней. Однако годы, кратные трем, то есть год [latex]3[/latex], год [latex]6[/latex], год [latex]9[/latex] и так далее, состоит из [latex]10[/latex] больших месяцев и ни одного малого.»

Много времени прошло со дня введения календаря, и для празднования дня тысячелетия [latex]([/latex]год [latex]1000[/latex], месяц [latex]1[/latex], день [latex]1[/latex][latex])[/latex] решено было организовать королевскую лотерею, победителями которой станут те, кто прожил столько же дней, какое число выпадет в лотерее. Напишите программу, которая поможет людям вычислить количество дней от их дня рождения до дня тысячелетия.

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

Входные данные имеют следующий формат:

n
Y1 M1 D1
Y2 M2 D2

Yn Mn Dn

Первая строка задает количество тестов [latex]n, \left ( n \leq 100 \right )[/latex]. Далее следуют n тестов, каждый из которых представляет собой одну строку с тремя натуральными числами [latex]Y_{i}\left ( Y_{i}< 1000 \right ), M_{i} \left ( M_{i}< 10 \right )[/latex] и [latex]D_{i} \left ( D_{i}\leq 20 \right )[/latex], задающих соответственно год, месяц и день рождения некоторого человека в нотации королевского календаря.

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

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

Тесты

Ввод Вывод
1 2
1 1 1
344 3 1
196470
128976
2 3
696 5 1
182 9 5
998 8 7
59710
160715
252
3 2
344 2 19
696 4 19
128977
59712
4 1
999 10 20
1

Код

Решение

Запишем большой месяц (20 дней) и малый месяц (19 дней) соответственно в константы bigMonth и smallMonth, а также большой год (200 дней) и малый год (195 дней) соответственно в bigYear и smallYear. Затем проходим по циклу for n раз. Проверяем, если год, в котором родился человек,  кратен 3, считаем количество полных прожитых человеком месяцев (каждый месяц — 30 дней) первого после рождения года, а также дни месяца, в котором он родился. В противном случае ( else) прибавляем дни каждого полного месяца, проверяя, большой он, и малый. Затем добавляем дни первого прожитого человеком месяца, так же учитывая его длительность. После этого проходим по циклу for, начальной итерацией которого является ( Y + 1), потому что дни года рождения мы посчитали ранее. За каждый год, номер которого кратен 3, добавляем 200 дней, а за некратный — 195. В конце выводим количество полученных дней +1, так как должны посчитать их количество включительно с днем рождения.

Решение

Снова проходим по циклу for n раз. Однако, теперь считаем дни без помощи циклов. В переменную lifeYears записываем годы жизни -1 , так как дни года рождения мы посчитаем далее. Затем, в if проверяем, находится ли количество прожитых лет в диапазоне от 1 до 3. Если да, то в переменную multipleThree записываем 1 — количество лет, кратных трем, то есть 999 год. В else multipleThree приравниваем к lifeYears, деленую на 3. В следующем if проверяем, больше ли количество лет трех. Если да, прибавляем 5 дней за больший 999 год. Затем, в переменную notMultipleThree записываем количество лет, не кратных трем. В следующей строке прибавляем ко дням жизни годы, умноженные на соответствующие им количества в каждом. После, в if проверяем, кратен ли год рождения 3. Если да, Находим количество полных прожитых месяцев, и умножаем его на bigMonth. Далее, находим дни, прожитые в месяц рождения. В else проверяем, родился ли человек в нечетном месяце. Если да, добавляем к дням количество дней, вычисляющееся по формуле, записанной в коде, если нет — аналогично. В конце, выводим количество дней +1, так как должны посчитать их количество включительно с днем рождения.

Ссылки

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

Задача

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

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

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

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

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

Выведите значение [latex]y[/latex] в соответствии с заданным условием.

Тесты

Ввод Вывод
1 -8 -3
2 5 10
3 81 531603
3 -76 -71

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

Решение

Используем условные операторы для того, чтобы определить в каком диапазоне находится [latex]x\left ( x< -4,-4\leq x\leq 7,x> 7 \right )[/latex] и в соответствии с условием задачи подставляем [latex]x[/latex] в определенное уравнение.

Ссылки

e-olymp 75. Пираты и монеты

Задача

[latex]n[/latex] пиратам удалось справедливо разделить клад из [latex]m[/latex] золотых монет — каждый получил свою часть согласно своему пиратскому рангу и стажу. Самый молодой пират взял [latex]a[/latex] монет, а каждый следующий пират брал на одну монету больше, чем предыдущий его коллега. Последним был капитан, которому досталось вдвое больше от запланированного, очевидно, что после него монет больше не осталось.

Сколько было пиратов вместе с капитаном, если известны [latex]a[/latex] и [latex]m[/latex]. Так как капитан без команды просто пират, то [latex]n > 1[/latex].

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

Два натуральных числа [latex]a[/latex] и [latex]m[/latex] ([latex]1 \leq a \leq 100, m < 15150[/latex]). Входные данные корректны.

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

Количество пиратов [latex]n[/latex].

Тесты

 #  ВХОДНЫЕ ДАННЫЕ  ВЫХОДНЫЕ ДАННЫЕ
 1  5 25  3
 2  3 24  4
 3  4 38  5
 4  5 55  6
 5  6 75  7

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

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

Для решения задачи воспользуемся формулой арифметической прогрессии, которая в данном случае равна: [latex](2a + n — 1)\frac{n}{2} + a + n — 1[/latex]. Отсюда получаем квадратное уравнение : [latex]\frac{n^{2}}{2} + n(a + \frac{1}{2}) + a — 1 = m[/latex], упростим и получим: [latex]n^{2} + 2an + n + 2a — 2 = 2m[/latex]. В коде задаем чему равно [latex]b[/latex], [latex]c[/latex] и [latex]d[/latex]. Где [latex]b[/latex] и [latex]c[/latex] — коэффициенты квадратного уравнения, а [latex]d[/latex] — дискриминант квадратного уравнения, который вычисляем по формуле: [latex]b^{2} — 4c[/latex]. Они нужны для нахождения корня данного квадратного уравнения. При этом ответом на задачу будет только один корень квадратного уравнения, так как количество пиратов не может принимать отрицательное значение. Поэтому вычисляем корень квадратного уравнения по формуле: [latex]\frac{-b + \sqrt{b}}{2}[/latex], тем самым получаем ответ на нашу задачу.

Код программы (с циклом)

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

В данном способе используем цикл. Как он работает: в условии цикла задаем проверку, когда наступит очередь капитана и будет выполнятся равенство вида [latex]m — 2a = 0[/latex] цикл прекратит свою работу. Пока это равенство не будет выполнятся цикл будет выполнять работу арифметической прогрессии, постоянно увеличивая количество монет [latex]a[/latex] на каждого пирата при этом, вычитая каждый раз из общего клада [latex]m[/latex], также, пока не выполняется данное равенство, считаем количество пиратов [latex]n[/latex], путем прибавления [latex]n + 1[/latex], пока работает цикл. И когда цикл прекращает свою работу, в конце учитываем капитана и к полученному количеству пиратов [latex]n[/latex] прибавляем [latex]n + 1[/latex]. И получаем ответ на нашу задачу.

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

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

В данном способе воспользуемся рекурсивной функцией и условными операторами. Как это работает: внутри рекурсивной функции расписываем условные операторы, которые определяют равенством [latex]m — 2a = 0[/latex] — когда наступила очередь капитана, а пока это условие не выполняется, функция будет вызывать сама себя пока это условие не удовлетворится, функция каждый раз вызывается с новыми параметрами соответственно. Где [latex]a[/latex] — количество монет даваемое пиратам, увеличивается по рангу каждого пирата, [latex]m[/latex] — клад, от него отнимаем текущее [latex]a[/latex], и [latex]n[/latex] — количество пиратов, считаем пиратов. И в конце выводит количество пиратов. Задача решена.

Ссылки

e-olymp 839. Пересечение отрезков

Задача

Два отрезка на плоскости заданы целочисленными координатами своих концов в декартовой системе координат.

Требуется определить, существует ли у них общая точка.

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

В первой строке содержатся координаты первого конца первого отрезка, во второй — второго конца первого отрезка, в третьей и четвёртой — координаты концов второго отрезка. Координаты целые и по модулю не превосходят $10000$.

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

Вывести слово $Yes$, если общая точка есть, или слово $No$ в противном случае.

Тесты

Входные данные Выходные данные
1 0 0
1 0
1 0
1 1
Yes
2 0 0
1 0
2 0
3 0
No
3 7 4
1 1
1 1
3 2
Yes
4 -9725 -8992
9812 9925
-9999 7011
8122 -9248
Yes
5 -9999 -1
10000 1
0 0
0 1
No

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

С ветвлением:

без ветвления:

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

Чтобы проверить пересекаются ли заданные отрезки построим прямые, которым они принадлежат, затем найдём точку их пересечения и проверим принадлежит ли она каждому из отрезков.
Для построения прямых воспользуемся формулой прямой проходящей через две точки и немного её преобразуем:
$\frac{x — x_1}{x_2 — x_1} = \frac{y — y_1}{y_2 — y_1}$ ~ $(x — x_1) \cdot (y_2 — y_1) = (y — y_1) \cdot (x_2 — x_1)$ ~ $x \cdot (y_2 — y_1) — y_2 \cdot x_1 + y_1 \cdot x_1 = y \cdot (x_2 — x_1) — x_2 \cdot y_1 + x_1 \cdot y_1$ ~ $y \cdot (x_2 — x_1) = x \cdot (y_2 — y_1) + x_2 \cdot y_1 — x_1 \cdot y_2$.
Обозначим за $k_x$ множитель при $x$, за $k_y$ множитель при $y$, а всё остальное за $b$. Тогда имеем уравнение вида:
$y \cdot k_y = x \cdot k_x + b$, таких у нас будет 2:

  1. $y \cdot k_{y_1} = x \cdot k_{x_1} + b_1$
  2. $y \cdot k_{y_2} = x \cdot k_{x_2} + b_2$

Теперь рассмотрим несколько случаев:
1. Прямые параллельны, следовательно могут не иметь точки пересечения или совпадать.
Проверим совпадают ли $b_1$ и $b_2$. Так как уравнения не сокращены на НОД, то рассмотрим равенство отношений $b_1$ и $b_2$ на $k_{y_1}$, $k_{x_1}$ и $k_{y_2}$, $k_{x_2}$ соответственно. Если они равны, то прямые совпадают. Иначе не имеют точек пересечения, а следовательно и отрезки тоже не пересекаются.
Когда прямые совпадают, необходимо проверить, что отрезки на этой прямой имеют хоть какую-то общую точку. Каждый из концов каждого отрезка проверим на вхождение в другой. Если такое вхождение есть, то отрезки пересекаются, иначе нет.
2. Прямые не параллельны, а следовательно имеют точку пересечения.
Тогда, решив систему двух линейных уравнений в общем виде получим что:

  • $x = \frac{b_1 \cdot k_{x_2} — b_2 \cdot k_{x_1}}{k_{y_1} \cdot k_{x_2} — k_{x_1} \cdot k_{y_2}}$
  • $y = \frac{b_2 \cdot k_{y_1} — b_1 \cdot k_{y_2}}{k_{x_1} \cdot k_{y_2} — k_{y_1} \cdot k_{x_2}}$

Осталось проверить находится ли точка с координатами $(x, y)$ в каждом из отрезков. Для этого просуммируем расстояния от этой точки до границ каждого отрезка и сравним с длинами отрезков. Если суммы соответственно совпали с длинами, то отрезки пересекаются, иначе — нет.

Ссылки

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

Задача

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

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

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

Одно целое число  [latex] x(-10000 ≤ x ≤ 10000)[/latex].

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

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

Тесты

Ввод Вывод
1 2 4
2 20 8100
3 100 1000500
3 -5 39

Программы с ветвлением

Решение

Используем тернарный оператор для проверки [latex]x\geq 10[/latex].

Ссылки

Линейные вычисления

Решение

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

Ссылки

e-olymp 1623. Чётные и нечётные числа

Задача

Дано три целых числа $a$, $b$, $c$. Определить, есть ли среди них хотя бы одно чётное и хотя бы одно нечётное число.

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

Числа $a$, $b$, $c$, не превышающие по модулю $10000$ (числа могут быть отрицательными).

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

Вывести «YES» или «NO».

Тесты

# Входные данные Выходные данные
1 3 4 5 YES
2 7 7 7 NO
3 2 3 50 YES
4 -1 -3 5 NO
5 10 5 -2 YES

Код решения

Решение

Проверяем, есть ли среди введенных чисел хотя бы одно четное и хотя бы одно нечетное. При выполнении обоих условий, выводим «YES», в другом случае «NO».

e-olymp 8654. Целочисленное умножение

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

Задача

Даны три целых числа $a, b, c.$ Вычислить значение выражения $a \cdot b \text{ mod } c.$

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

Три целых положительных числа $a, b, c \left( a, b, c < 2^{63} \right).$

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

Вывести значение выражения $ a \cdot b \text{ mod } c.$

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 2 3 2 0
2 11 3 2 1
3 123456789
987654321
17
0
4 5000400000023
23000400400500
100000000070707
68238553233174
5 10000018585
10000000000005
101020304050607080
85850050000993845

Решение

Для решения задачи напишем рекурсивную функцию умножения, основанную на том, что [latex]\displaystyle a\cdot b =\displaystyle[/latex][latex] \begin{cases}\left(a+a\right)\cdot\frac{b}{2} &\text{} b\equiv_{2} 0 \\a+a\cdot\left(b-1\right) &  \text{} b \not \equiv_{2} 0\ \end{cases}.[/latex] Поскольку максимальное значение из условия задачи в два раза меньше максимального числа из 64-битных беззнаковых чисел и[latex]\left(a\cdot b\right)\text{ mod } c =\left(a\text{ mod } с \cdot b\text { mod }c\right)\text{ mod }c,[/latex] мы можем на каждом шагу применять к $a$ и $b$  операцию остатка от деления на $c$ , за счет чего произведение никогда не будет превосходить $2^{64}-1$.

  • Засчитанное решение на e-olymp
  • Код на ideone

e-olymp 774. Торт

Задача

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

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

Содержит три натуральных числа: радиус стола [latex]r \left(1\leqslant r\leqslant 1000 \right)[/latex], ширину [latex]w[/latex] и длину [latex]l[/latex] торта [latex] \left(1\leqslant w \leqslant l \leqslant 1000\right)[/latex].

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

Вывести слово [latex]YES[/latex], если торт помещается на стол, и слово [latex]NO[/latex] в противном случае.

Тесты

Входные данные Выходные данные
1 38 40 60 YES
2 35 20 70 NO
3 50 60 80 YES
4 30 60 90 NO

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

с ветвлением:

без ветвления:

 

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

Вписанный в окружность прямоугольник

Вписанный в окружность прямоугольник

Для того, чтобы узнать, помещается торт на столе или нет, необходимо найти диагональ прямоугольного торта. Зная длину и ширину прямоугольника, находим диагональ по теореме Пифагора. Если она равна или меньше диаметра стола $AB^2$ + $AD^2$ <= 4$OD^2$, значит торт помещается, и пишем  "YES". Если диагональ больше диаметра стола, пишем  "NO".

Ссылки

  • Условие задачи на e-olymp
  • Код программы с ветвлением на ideone
  • Код программы без ветвления на ideone

e-olymp 273. Возведение в степень

Задача

По трем натуральным числам [latex]a[/latex], [latex]b[/latex] и [latex]m[/latex] вычислить значение [latex]a^b\mod m[/latex].

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

Три натуральных числа [latex]a[/latex], [latex]b[/latex], [latex]m[/latex] [latex]\left(1 \leqslant a, m \leqslant 10^9, 2 \leqslant b \leqslant 10^7\right)[/latex].

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

Вывести [latex]a^b\mod m[/latex].

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 1 2 100 1
2 100 2 1000000 10000
3 2 3 50 8
4 9 2 1 0
5 9 2 25 6

Код с циклом

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

Решение

Для решения этой задачи я воспользовался функцией бинарного возведения в степень binpow () (рекурсивной для программы с ветвлением и нерекурсивной для программы с циклом). Это приём, позволяющий возводить любое число в [latex]n[/latex]-ую степень за [latex]O(\log n)[/latex] умножений. В этой функции при возведении я дополнительно применял операцию деление с остатком к результату res и возводимому числу a для того, чтобы получить решение.

Запустить код с циклом (ideone) можно здесь
Запустить код с ветвлением (ideone) можно здесь
Задача на E-olymp

e-olymp 8528. Система глобальнейшего позиционирования

Задача

Недавно во Флатландии было решено создать Новейшую Систему Глобальнейшего Позиционирования. Поскольку страна занимает бесконечно большой участок плоскости, то вывод спутников очень затруднителен, поэтому было решено ограничиться наземным методом позиционирования.

Для этого во Флатландии было построено три радиовышки, не находящиеся на одной прямой. Объект, который хочет узнать свое местоположение, посылает вышкам сигнал. По силе сигнала, дошедшего до вышек, определяется расстояние между вышками и объектом.
Напишите программу, которая реализует последний компонент системы, который, получая координаты вышек и расстояния от объекта до каждой из них, находит координаты объекта.

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

В первой строке находятся три пары чисел $x_{1}$, $y_{1}$, $x_{2}$, $y_{2}$, $x_{3}$ и $y_{3}$  — координаты вышек. Во второй строке находятся три неотрицательных числа — расстояния до соответствующих вышек. Все входные числа целые и по модулю не превышают $50$.

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

Если не существует такого местоположения объекта, что расстояния до вышек соответствовали бы данным, то выведите в единственное слово «Impossible». Иначе выведите два числа — координаты объекта с точностью до шести знаков после запятой.

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 0 4 2 6 5 0
2 2 5
2.000000 4.000000
2 2 2 0 1 1 1
2.828427 1 1.4142135
0.000000 0.000000
3 -5 3 -3 3 -2 4
3 1 1
-2.000000 3.000000
4 0 0 2 1 2 -2
0.841722586 2 2
0.677124 -0.500000
5 0 0 10 0 5 6
7 7 1
Impossible

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

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

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

Для решения данной задачи нужно найти точку пересечения трёх окружностей, следовательно получаем систему из трёх уравнений окружностей, а именно:

[latex]\begin{cases}(x_{1} — x)^{2} + (y_{1} — y)^{2} = r_{1}^{2},\\(x_{2} — x)^{2} + (y_{2} — y)^{2} = r_{2}^{2}, \\(x_{3} — x)^{2} + (y_{3} — y)^{2} = r_{3}^{2};\end{cases}[/latex]

где $x_{1}$, $y_{1}$, $x_{2}$, $y_{2}$, $x_{3}$ и $y_{3}$  — координаты вышек, $r_{1}$, $r_{2}$ и $r_{3}$ — расстояния до соответствующих вышек, $x$ и $y$ — координаты объекта.

После применения формул сокращённого умножения многочленов, получим систему вида:

[latex]\begin{cases}x_1^2-2x_{1}x+x^{2}+y_1^2-2y_{1}y+y^{2}=r_1^2, & (1)\\x_2^2-2x_{2}x+x^{2}+y_2^2-2y_{2}y+y^{2}=r_2^2, & (2)\\x_3^2-2x_{3}x+x^{2}+y_3^2-2y_{3}y+y^{2}=r_3^2; & (3)\end{cases}[/latex]

Отнимем от первого уравнения второе и от  второго уравнения третье, получим:

[latex]\begin{cases}x_1^2-x_2^2-2x_{1}x+2x_{2}x+y_1^2-y_2^2-2y_{1}y+2y_{2}y=r_1^2-r_2^2, & (1)-(2)\\x_2^2-x_3^2-2x_{2}x+2x_{3}x+y_2^2-y_3^2-2y_{2}y+2y_{3}y=r_2^2-r_3^2; & (2)-(3)\end{cases}[/latex]

Далее выражаем $x$ и $y$:

[latex]\begin{cases}2y(y_{2}-y_{1})=r_1^2-r_2^2-x_1^2+x_2^2+2x_{1}x-2x_{2}x-y_1^2+y_2^2,\\2y(y_{3}-y_{2})=r_2^2-r_3^2-x_2^2+x_3^2+2x_{2}x-2x_{3}x-y_2^2+y_3^2;\end{cases}[/latex]

[latex]\begin{cases}2x(x_{2}-x_{1})=r_1^2-r_2^2-y_1^2+y_2^2+2y_{1}y-2y_{2}y-x_1^2+x_2^2,\\2x(x_{3}-x_{2})=r_2^2-r_3^2-y_2^2+y_3^2+2y_{2}y-2y_{3}y-x_2^2+x_3^2;\end{cases}[/latex]

[latex]\begin{cases}y=\frac{r_1^2-r_2^2-x_1^2+x_2^2+2x_{1}x-2x_{2}x-y_1^2+y_2^2}{2(y_{2}-y_{1})},\\y=\frac{r_2^2-r_3^2-x_2^2+x_3^2+2x_{2}x-2x_{3}x-y_2^2+y_3^2}{2(y_{3}-y_{2})};\end{cases}[/latex]

[latex]\begin{cases}x=\frac{r_1^2-r_2^2-y_1^2+y_2^2+2y_{1}y-2y_{2}y-x_1^2+x_2^2}{2(x_{2}-x_{1})},\\x=\frac{r_2^2-r_3^2-y_2^2+y_3^2+2y_{2}y-2y_{3}y-x_2^2+x_3^2}{2(x_{3}-x_{2})};\end{cases}[/latex]

Приравняем соответствующие координаты объекта, получим систему вида:

[latex]\begin{cases}\frac{r_1^2-r_2^2-x_1^2+x_2^2+2x_{1}x-2x_{2}x-y_1^2+y_2^2}{2(y_{2}-y_{1})}=\frac{r_2^2-r_3^2-x_2^2+x_3^2+2x_{2}x-2x_{3}x-y_2^2+y_3^2}{2(y_{3}-y_{2})},\\\frac{r_1^2-r_2^2-y_1^2+y_2^2+2y_{1}y-2y_{2}y-x_1^2+x_2^2}{2(x_{2}-x_{1})}=\frac{r_2^2-r_3^2-y_2^2+y_3^2+2y_{2}y-2y_{3}y-x_2^2+x_3^2}{2(x_{3}-x_{2})};\end{cases}[/latex]

Находим координаты объекта:

[latex]\begin{cases} \begin{split} 2(y_{3}-y_{2})(r_1^2-r_2^2-x_1^2+x_2^2+2x_{1}x-2x_{2}x-y_1^2+y_2^2)= \\ =2(y_{2}-y_{1})(r_2^2-r_3^2-x_2^2+x_3^2+2x_{2}x-2x_{3}x-y_2^2+y_3^2),\\2(x_{3}-x_{2})(r_1^2-r_2^2-y_1^2+y_2^2+2y_{1}y-2y_{2}y-x_1^2+x_2^2)= \\ =2(x_{2}-x_{1})(r_2^2-r_3^2-y_2^2+y_3^2+2y_{2}y-2y_{3}y-x_2^2+x_3^2); \end{split} \end{cases}[/latex]

[latex]\begin{cases} \begin{split} 2(y_{3}-y_{2})(2x_{1}x-2x_{2}x)-2(y_{2}-y_{1})(2x_{2}x-2x_{3}x) = \\ =2(y_{2}-y_{1})(r_2^2-r_3^2-x_2^2+x_3^2-y_2^2+y_3^2)-\\-2(y_{3}-y_{2})(r_1^2-r_2^2-x_1^2+x_2^2-y_1^2+y_2^2),\\2(x_{3}-x_{2})(2y_{1}y-2y_{2}y)-2(x_{2}-x_{1})(2y_{2}y-2y_{3}y)= \\ =2(x_{2}-x_{1})(r_2^2-r_3^2-y_2^2+y_3^2-x_2^2+x_3^2)-\\-2(x_{3}-x_{2})(r_1^2-r_2^2-y_1^2+y_2^2-x_1^2+x_2^2);\end{split}\end{cases}[/latex]

[latex]\begin{cases} \begin{split} 4x(y_{3}-y_{2})(x_{1}-x_{2})-4x(y_{2}-y_{1})(x_{2}-x_{3})= \\ =2(y_{2}-y_{1})(r_2^2-r_3^2-x_2^2+x_3^2-y_2^2+y_3^2)-\\-2(y_{3}-y_{2})(r_1^2-r_2^2-x_1^2+x_2^2-y_1^2+y_2^2),\\4y(x_{3}-x_{2})(y_{1}-y_{2})-4y(x_{2}-x_{1})(y_{2}-y_{3})= \\ =2(x_{2}-x_{1})(r_2^2-r_3^2-y_2^2+y_3^2-x_2^2+x_3^2)-\\-2(x_{3}-x_{2})(r_1^2-r_2^2-y_1^2+y_2^2-x_1^2+x_2^2);\end{split}\end{cases}[/latex]

[latex]\begin{cases}x=\frac{2((y_{2}-y_{1})(r_2^2-r_3^2-x_2^2+x_3^2-y_2^2+y_3^2)-(y_{3}-y_{2})(r_1^2-r_2^2-x_1^2+x_2^2-y_1^2+y_2^2))}{4((y_{3}-y_{2})(x_{1}-x_{2})-(y_{2}-y_{1})(x_{2}-x_{3}))},\\y=\frac{2((x_{2}-x_{1})(r_2^2-r_3^2-y_2^2+y_3^2-x_2^2+x_3^2)-(x_{3}-x_{2})(r_1^2-r_2^2-y_1^2+y_2^2-x_1^2+x_2^2))}{4((x_{3}-x_{2})(y_{1}-y_{2})-(x_{2}-x_{1})(y_{2}-y_{3}))};\end{cases}[/latex]

[latex]\begin{cases}x=\frac{(y_{2}-y_{1})(r_2^2-r_3^2-x_2^2+x_3^2-y_2^2+y_3^2)-(y_{3}-y_{2})(r_1^2-r_2^2-x_1^2+x_2^2-y_1^2+y_2^2)}{2((y_{3}-y_{2})(x_{1}-x_{2})-(y_{2}-y_{1})(x_{2}-x_{3}))},\\y=\frac{(x_{2}-x_{1})(r_2^2-r_3^2-y_2^2+y_3^2-x_2^2+x_3^2)-(x_{3}-x_{2})(r_1^2-r_2^2-y_1^2+y_2^2-x_1^2+x_2^2)}{2((x_{3}-x_{2})(y_{1}-y_{2})-(x_{2}-x_{1})(y_{2}-y_{3}))}.\end{cases}[/latex]

Далее проводим проверку на принадлежность  найденных  координат объекта одной из окружностей. Если найденные координаты принадлежат окружности, то выводим два числа — координаты объекта с точностью до шести знаков после запятой. Если найденные координаты не принадлежат окружности, это означает, что не существует такого местоположения объекта, тогда выводим единственное слово «Impossible».

Ссылки

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

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

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

e-olymp 1151. Кладоискатель

Задача

Юный кладоискатель Рома прошел курс обучения по специальности «кладовое дело», и теперь проходит летнюю практику. Летняя практика проходит близ поселка «Каменные Зори» и длится ровно $b$ дней. Каждый день Рома находит $a$ закопанных в окрестности монет. Таким образом, в конце первого дня у него было $a$ монет, в конце второго — $2a,$ а по окончании практики у Ромы должно накопиться $b\cdot a$ монет.

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

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

Первая строка входного файла содержит два целых числа $a$ и $b$ ($1 \le a, b \le 10^9$).

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

В выходной файл выведите число съеденных Ромой пирожков.

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 1 2 1
2 2 2 2
3 10 5 5
4 56000 35 35
5 300 1000000000 100

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

Решение

Нам заданы $a$ и $b$.
Существует 3 случая их отношения между собой:

  1. $a$ кратно $b$. Тогда в последовательности $a, 2a, 3a,\ldots,b \cdot a$ кратным $b$ будет каждый элемент последовательности. То есть количество дней равно $b$. Или НОД от $a$ и $b$, поскольку $a$ кратно $b$.
  2. Существует такое $k, k \in (1; b), k \in N.$ При котором: $k \cdot a$ кратно $b.$ $\frac{ka}{b} = c, c \in N$. Тогда у $b$ и $a$ есть НОД. $(b, a) = p, p > 1, p \in N$. $a = \tilde a \cdot p$, $b = \tilde b \cdot p.$ Тогда в последовательности $a, 2a, 3a,\ldots, b \cdot a$, а кратным $b$ будет каждый $k$-ый элемент данной последовательности. $c = \frac{ka}{b} = \frac{k \cdot \tilde a \cdot p}{\tilde b \cdot p} = \frac{k\tilde a }{\tilde b },$ $k$ обязан равняться $\tilde b $так как $\tilde a $и $\tilde b$ взаимно простые исходя из определения НОД и $c \in N.$ Отсюда $\frac{b}{k} = \frac{\tilde b p}{\tilde b}=p$ — количество кратных элементов последовательности.
  3. Не существует такого $k, k \in (1; b), k \in N$. При котором: $k \cdot a$ кратно $b$. И $a$ не кратно $b.$ Тогда в последовательности $a, 2a, 3a,\dots,b\cdot a$ кратным $b$ будет только последний элемент последовательности. Так как числа взаимно простые, то НОД равен $1.$

Исходя из этих рассуждений решение задачи сводится к нахождению НОД для $a$ и $b.$ Используем рекурсивную реализацию алгоритма Евклида.

Ссылки

e-olymp 8643. Иннолошадь

Задача

В шахматном иннокоролевстве выводят специальные породы инноконей. Порода инноконя задается парой чисел $(x, y), 0 ≤ x ≤ y$. Инноконь перемещается следующим образом: сначала перемещается на $x$ клеток в одну из четырех сторон, затем поворачивает на 90 градусов влево или вправо и перемещается еще на $y$ клеток. Например, обычный шахматный конь — это инноконь породы (1, 2).

Петя и Вася недавно видели инноконя, он прыгнул с поля $A$ на поле $B$. Пете и Васе стало интересно, какой породы был этот инноконь. Помогите им ответить на этот вопрос.

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

Шахматная доска состоит из 8 строк и 8 столбцов. Строки нумеруются числами от 1 до 8, а столбцы буквами от $a$ до $h$. Таким образом, каждое поле задается парой из буквы и цифры. В двух строках ввода содержатся описания полей $A$ и $B$.

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

Выведите два целых числа $x$ и $y$, $(0 ≤ x ≤ y)$, соответствующие породе данного инноконя.

Тесты

Входные данные Выходные данные
a1 b3 1 2
g5 d3 2 3
e1 e1 0 0
d3 d7 0 4
a2 c2 0 2

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

Решение

Найдем разницы пройденных расстояний по строкам и столбцам. Тогда породой данного инноконя будет пара этих чисел, размещенных по возрастанию.

e-olymp

ideone

e-olymp 8534. Хлопці на ім’я Валя

Задача

У літньому таборі $n$ дітей. Серед будь-яких $L$ дітей є хоча б одна дівчинка. Серед будь-яких $v$ дітей є дитина на ім’я Валя (це ім’я можуть мати і хлопчик, і дівчинка). Напишіть програму, що визначає умову наявності в таборі хоча б одного Валентина.

Вхідні дані

$100≤n≤200$, $40≤L≤140$, $20≤v≤70$. Вхідні дані ввести зі стандартного пристрою введення в один рядок, розділяючи значення пропусками.

Вихідні дані

На стандартний пристрій виведення вивести $1$, якщо відповідь на питання умови стверджувальне. Інакше вивести $0$.

Тесты

Входные данные Выходные данные
110 80 27 1
100 70 30 1
70 50 30 0
85 35 20 1
90 50 50

0

Код програми

Решение

Так як серед $v$ дітей точно знайдеться Валя, то нам необхідно, щоб $n — v + 1$ було додатним. Іншими словами, дітей було більше, ніж достатня для Валь їх кількість. Але так як Валею може бути ще й дівчинка, необхідно, щоб ця різниця була більшою, ніж $l$. Таким чином, завжди знайдеться Валя з інших $v$ дітей, хоча б один з яких не увійшов в $l$. Звідси і формула: $n>v+ l-1$ або  $n> = l + v$.

e-olymp

ideone

 

 

e-olymp 1312. Шкаф

Задача

Размеры шкафа [latex] a \times b \times c [/latex]. Возможно ли его пронести через дверной проём с размерами [latex]x \times y[/latex]? Считается, что шкаф проходит в проем, если размеры, которыми его будут вносить сквозь дверь, не больше соответствующих размеров двери.

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

Целые числа [latex] a, b, c, x, y (1 ≤ a, b, c, x, y ≤ 100)[/latex].

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

Вывести строку «YES«, если шкаф пронести возможно, и «NO» если нельзя.

Тесты

Ввод Вывод
1 4 5 6 10 20 YES
2 4 5 6 3 4 NO
3 12 3 4 5 6 YES
4 12 3 6 5 6 YES
5 12 3 7 5 6 NO

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

Либо

Без условных операторов

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

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

Ссылки

Proggy-Buggy 2018: Задача E. Треугольник или не треугольник?

Задача

Баги считает треугольником любые три различные точки плоскости, соединенные отрезками. Даже написал диссертацию: «Треугольник или не треугольник? Вот в чём вопрос!», которая породила множество вопросов. Его очень утомили вопросы из разряда, «а это треугольник?». Если хотите, помогите Баги: напишите программу «Баги-бот», которая вместо Баги отвечала бы на вопрос, образуют ли три заданные точки треугольник.

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

Строка содержащая три пары целых чисел, координаты $x1$, $y1$, $x2$, $y2$, $x3$, $y3$ $(0\leq xi,yi\leq1000)$, разделенных пробелом.

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

Строка «$yes$» или «$no$» (без кавычек) — ответ программы «Баги-бот».

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 0 0 1 0 0 1 $yes$
2 1 1 1 2 1 3 $yes$
3 1 1 1 1 1 2 $no$

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

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

В задаче главное внимательно прочитать условие. Если любые две заданные точки совпадают, то программа «Баги-бот» должна ответить no, иначе yes.

Ссылки

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

e-olymp 1949. Торт

На свой день рождения Петя купил красивый и вкусный торт, который имел идеально круглую форму. Петя не знал, сколько гостей придет на его день рождения, поэтому вынужден был разработать алгоритм, согласно которому он сможет быстро разрезать торт на [latex]N[/latex] равных частей. Следует учесть, что разрезы торта можно производить как по радиусу, так и по диаметру.

Помогите Пете решить эту задачу, определив наименьшее число разрезов торта по заданному числу гостей.

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

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

Входной файл содержит натуральное число [latex]N[/latex] – число гостей, включая самого виновника торжества ([latex]N \leq 1000[/latex]).

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

Выведите минимально возможное число разрезов торта.

Тесты

Число гостей Минимальное количество рaзрезов
1 0
8 4
13 13

Алгоритм

В данной задаче достаточно заметить следующее:

  1. В случае четного количества гостей необходимо сделать [latex]\frac{N}{2}[/latex] разрезов по диаметру торта.
  2. В случае нечетного количества гостей необходимо сделать [latex]N[/latex] разрезов по радиусу торта.
  3. В случае если гостей 1 то выведем 0 т.к. торт резать не нужно.

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

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


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

  1. С ветвлением.
  2. Без ветвления.

e-olymp 8352. Такси

Такси

В час пик на остановку одновременно подъехали три маршрутных такси, следующие по одному маршруту, в которые тут же набились пассажиры. Водители обнаружили, что количество людей в разных маршрутках разное, и решили пересадить часть пассажиров так, чтобы в каждой маршрутке было поровну пассажиров. Требуется определить, какое наименьшее количество пассажиров придется при этом пересадить.

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

Три натуральных числа, не превосходящих $100$ — количество пассажиров в первой, второй и третьей маршрутках соответственно.

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

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

Тесты

Ввод Вывод
1 1 2 3 1
2 100 100 99 IMPOSSIBLE
3 100 100 100 0
4 19 59 6 31
5 30 9 74 IMPOSSIBLE

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

Решение

В начале выводим полную формулу. Для этого находим, сколько пассажиров должно быть в одном автобусе после всех перестановок : $\frac{b1 + b2 + b3}{3}$. Далее, от количества пассажиров в каждом автобусе изначально отнимаем требуемое значение. Так как оно может отличаться как в плюс, так и в минус используем модуль : $|b1-need|+|b2-need|+|b3-need|$. А так как «излишки» перераспределяются между оставшимися двумя автобусами, то чтобы избежать повторения мы делим все на $2$ : $\frac{|b1-need|+|b2-need|+|b3-need|}{2}$.

Далее мы вычисляем, существует ли остаток от деления общего количества пассажиров на $3$; для этого используем логическую переменную. Если остаток существует и  f == true  , то  выводится [latex]IMPOSSIBLE[/latex].  Если же f == false , то вычисляется и выводится количество перестановок пассажиров.

 

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

Решение

Алгоритм решения в данном случае полностью повторяет предыдущий, но с помощью условного оператора мы можем сразу же проверить сумму пассажиров на делимость, вывести [latex]IMPOSSIBLE[/latex] и завершить программу не вычисляя формулы.

Ссылки

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

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

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