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 480. Возведение в степень — 2

Задача

Для заданных $A$, $B$ и $M$ вычислить $A^B \mod M$.

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

Во входном файле даны три натуральных числа $A$, $B$, $M$ $(1 ≤ A, \, B ≤ 10^{18}, \, 2 ≤ M ≤ 2 \cdot 10^9)$, записанные в одной строке через пробел.

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

В выходной файл выведите одно число, равное $A^B \mod M$.

Тесты

Входные данные Выходные данные
$531$ $348$ $1645$ $911$
$1784353$ $453345$ $463973$ $214457$
$39252362$ $345673$ $786536$ $302328$
$68790234$ $679643$ $789057$ $281232$
$324$ $8564$ $45074547$ $32984424$

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

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

По свойствам операций со сравнениями по модулю:
$$C \equiv C \mod K \pmod K$$
$$CD \equiv (C \mod K) \cdot (D \mod K) \pmod K$$
$$C \equiv D \pmod K \Rightarrow C^n \equiv D^n \pmod K$$
Отсюда выводим рекуррентную формулу бинарного возведения в степень по модулю:
$$
A^B \mod M =
\begin{cases}
1 \text{ при } B = 0\\\
\left ( \left (A \mod M \right ) \left ( (A \mod M)^{B-1} \mod M \right )\right )\mod M \\\\ \text{ при } B \equiv 1 \pmod 2\\\
\left ( \left (A \mod M \right)^2 \right)^{\frac{B}{2}} \mod M \text{ при } B \equiv 0 \pmod 2 \wedge B \neq 0
\end{cases}
$$

Ссылки

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

e-olymp 446. Ровные делители

Задача

Натуральное число [latex] m [/latex] называется ровным делителем числа [latex] n [/latex], если частное и остаток от деления [latex] n [/latex] на [latex] m [/latex] равны. По заданному натуральному числу [latex] n [/latex] найти количество его ровных делителей.

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

Натуральное число [latex] n (1 ≤ n ≤ 10^{6}) [/latex].

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

Выведите искомое количество ровных делителей числа [latex] n [/latex].

Тесты

Входные данные Выходные данные
5 1
20 2
200 6
653 1
5982 4

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

Решение

Для решения этой задачи сперва введем переменную [latex]q[/latex], в которой будем хранить количество ровных делителей числа [latex] n [/latex]. Затем запустим цикл, который будет проверять каждое из чисел от [latex] 1 [/latex] до [latex] n [/latex] включительно, является ли оно ровным делителем. Если условие выполняется, то увеличиваем значение, хранящееся в [latex]q[/latex] на единицу. После цикла выведем искомое на экран.

Ссылки

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

e-olymp 2. Цифры

Задача

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

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

Неотрицательное целое число [latex]n[/latex] [latex](0<=n<=2*10^9)[/latex].

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

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

Тесты

n Количество цифр
3 1
327 3
1024 4

Решение

Объявляем переменную x для подсчета цифр в числе и присваиваем ей значение 1, вводим n . Далее используем цикл while , проверяя деление числа n на 10 (так как тип числа int ). Это «отбрасывает» последнюю цифру в числе. Пока результат проверки истинный, инкриментируем x на 1.

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

Монстр

Ссылка на оригинал задачи

Задача:

Монстр гонится за Риком и Морти на другой планете. Они настолько напуганы, что иногда кричат. Точнее, Рик кричит в моменты времени [latex]b,[/latex] [latex]b + a,[/latex] [latex]b + 2a,[/latex] [latex]b + 3a,[/latex]…, а Морти кричит в моменты времени [latex]d,[/latex] [latex]d + c,[/latex] [latex]d + 2c,[/latex] [latex]d + 3c,[/latex]….

Монстр поймает их, если в какой-то момент времени они закричат одновременно. Так что он хочет знать, когда он поймает их (первый момент времени, когда они закричат одновременно) или они никогда не закричат одновременно.

Ввод:

Первая строка входных данных содержит два целых числа [latex]a[/latex] и [latex]b[/latex]  [latex](1\leq a,[/latex]  [latex]b\leq 100).[/latex]

Вторая строка входных данных содержит два целых числа [latex]c[/latex] и [latex]d[/latex] [latex](1\leq c,[/latex]  [latex]d\leq 100).[/latex]

Вывод:

Выведите первый момент времени, когда Рик и Морти закричат одновременно, или  - 1, если они никогда не закричат одновременно.

Тесты:

Ввод
Вывод
20 2
9 19
82
2 1
16 12
-1

Код:

Решение:

В этих моментах времени, заданных прогрессиями, изменяется только коэффициент при [latex]a[/latex] и [latex]c.[/latex] Создадим для них 2 цикла. Так как равных моментов времени может быть много, а нам нужен только первый, создаем вектор и ,когда моменты равны, добавляем в него этот момент. Затем, уже вне цикла, проверяем пустой ли вектор, и в таком случаем выводим -1, так как моменты на данном промежутке не были равны ни разу. Если же вектор непустой, выходим первый элемент вектора. Он и будет искомым первым одновременным криком.

 

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

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

e-olymp 109. Нумерация

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

Для нумерации  $latex m$ страниц книги использовали $latex n$ цифр. По заданному $latex n$ вывести $latex m$ или $latex 0$, если решения не существует. Нумерация начинается с первой страницы.

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

Единственное число n. В книге не более 1001 страницы.

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

Искомое количество страниц.

Тесты

Входные данные Выходные данные
1 27 18

Код

 

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

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

Посмотреть, как работает программа со входными данными 27 можно на сайте  ideone.
Задача решена на основе данного решения.

e-olymp 128. Счастливые билеты

Задача. Подсчитайте количество счастливых билетов, у которых сумма первых трёх цифр равна N(N≤27). Счастливым билетом называется билет с шестизначным номером, у которого сумма первых трёх цифр равна сумме трёх последних.

Тесты

Число N 3 27 26 1 10
Количество билетов 100 1 9 9 3969

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

Код можно увидеть тут.

Алгоритм

Любой шестизначный номер мы можем представить как 2 трехзначных номера.

Рассмотрим все варианты трехзначных номеров. Две первые цифры такого номера могут быть любыми. Переберем все их комбинации с помощью двух вложенных циклов. Для третьей цифры введем специальное условие. Она должна быть результатом вычитания двух первых цифр из [latex]N[/latex], а также быть именно цифрой, то есть меньшей 10.

Когда в цикле встречается подходящая комбинация, мы увеличиваем счетчик [latex]c[/latex] на 1. Поскольку на самом деле номер шестизначный, то каждой удачной комбинации в первой его половине будет соответствовать [latex]c[/latex] комбинаций во второй. Следовательно, искомое число счастливых билетов будет равно [latex]c^2[/latex].

Ссылка на авторское решение задачи.