e-olymp 27. Циклические сдвиги

Задача

Циклический сдвиг

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

Например, если $n = 11$, то в двоичной системе это $1011_2$, его циклические сдвиги: $0111_2$, $1110_2$, $1101_2$, $1011_2$. Максимальное значение $m$ у всех полученных таким образом чисел будет иметь число $1110_2 = 14_{10}$.

Для заданного числа $n$ определить максимальное значение $m$.

Входные данные: одно число $n (1 ≤ n ≤ 2\cdot 10^9)$.

Выходные данные: искомое число $m$.

Тесты

Входные данные Выходные данные
11 14
23 30
256 256
257 384
34132 43664

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

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

  1. Сначала мы находим степень двойки, большую данного числа;
  2. Далее мы циклически сдвигаем влево данное число на один бит и из полученных чисел выбираем наибольшее.

Ссылки

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

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 7337. Скидки

Задача

В супермаркете электроники, если верить телерекламе, существует система скидок: из двух купленных товаров полностью оплачивается только стоимость товара, который дороже, а другой отдается бесплатно. Какой суммы достаточно, что бы оплатить покупку трёх товаров, если известна цена каждого?
Входные данные: три натуральных числа $a, b, c$ — цены трёх товаров $(1\leq a, b, c\leq10000)$.
Выходные данные: стоимость покупки.

Тесты

Входные данные Выходные данные
213   6554   234
6767
320   3670   5555
5875
15   47   13
60
215   30   73
245
370   53   823
876

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

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

Для нахождения самого дорогого и самого дешёвого товаров мы используем встроенные методы  Math.max()  и Math.min()  из класса Math. Находим минимальное число из чисел $a, b$ и $c$: Math.min(Math.min(a, b), c) (например: Math.min(Math.min(1, 2), 3) будет равно $1$). Далее проводим такую же операцию с нахождением максимального числа среди $a, b, c$:  Math.max(Math.min(a, b), c) (пример:  Math.max(Math.min(1, 2), 3) будет равно $3$). Затем суммируем полученные минимальное и максимальное числа и получаем ответ.

Ссылки

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