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$; для этого используем логическую переменную. Если остаток существует и [latex]f == 1[/latex] , то  выводится [latex]IMPOSSIBLE[/latex].  Если же [latex]f == 0[/latex], то вычисляется и выводится количество перестановок пассажиров.

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

Решение

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

Ссылки

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

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

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

 

e-olymp 8594. Между A и B

Задача

Заданы целые неотрицательные числа $a$ и $b$ [latex](a \le b)[/latex] и натуральное число $x$. Сколько существует чисел между $a$ и $b$ включительно, делящихся на $x$?

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

Три числа $a$, $b$ и $x$ [latex](0 \le a \le b \le 10^{18}, 1 \le x \le 10^{18}[/latex]).

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

Выведите ответ на задачу.

Тесты

Вход Выход
2 6 5 1
1 200 3000 0
83 180 10 10
775 12004 312 36
13 42 7 5

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

 

Решение

Для решения данной задачи, мы должны найти длину отрезка [latex][a;b][/latex], получаем промежуток, а после, если поделим на $x$, обнаружим целую и дробную часть, как раз целая часть числа и будет являться нашим ответом. Формула оказывается таковой: [latex][\frac{b-a}{x} ][/latex]. На сию формулу я буду в основном опираться. Но эта формула не учитывает некоторые случаи.

Если $a$ или $b$ будут без остатка делится на $х$, например, [latex]a=5[/latex], [latex]b=15[/latex], [latex]x=5[/latex]. По старой формуле ответ будет $2$. Но само по себе $a$(или $b$) тоже кратно $x$.  Ещё один случай формула не видит, поэтому нужно прописать дополнительную формулу для подобных ситуаций: [latex][\frac{b-a}{x} + 1][/latex]

Первая формула также не учитывает случай, когда остаток от меньшего числа, больше остатка от большего, например, [latex]a=3[/latex], [latex]b=6[/latex], [latex]x=5[/latex]. Между $a$ и $b$ есть решение, но по старой формуле ответ равен $0$, но мы видим, что ответ есть и он $1$. Опять же, мы должны предусмотреть подобные случаи и сделать для них «исключение» от изначальной формулы, добавив забытую единицу:  [latex][\frac{b-a}{x} + 1][/latex]

Ссылки

e-olymp

ideone

 

e-olymp 8362. Множители

Задача

Найти число от $1$ до $n$ включительно такое, что в разложении его на простые множители количество множителей максимально. Если таких чисел несколько, выбрать максимальное из них.

Например, если $n = 7$, то ответом будет число $6$, как наибольшее число, имеющее в своем разложении $2$ простых множителя $2$ и $3$.

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

Одно целое число $n$ $(1 ≤ n ≤ 2$³¹$- 1)$.

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

Вывести одно искомое число.

Тесты

Ввод Вывод
1 1 1
2 10 8
3 100 96
4 363 256
5 2147483647 1610612736

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

Решение

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

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

Из полученных двух чисел выберем наибольшее, как этого требует условие задачи.

Заметим, что если заданное число будет единицей, двойкой или тройкой, то его и надо вывести на экран.

Ссылки

Задача множители на e-olymp

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

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