e-olymp 2814. Быстрое возведение в степень.

Задача

Очень часто возникает задача эффективного вычисления xn по данным $x$ и $n$, где $n$ — положительное целое число.

Предположим, например, что необходимо вычислить $x^{16}$. Можно просто начать с $x$ и 15 раз умножить его на $x$. Но тот же ответ можно получить всего за четыре умножения, если несколько раз возвести в квадрат получающийся результат, последовательно вычисляя $x^{2}$, $x^{4}$, $x^{8}$, $x^{16}$.

Эта же идея, в целом, применима к любому значению $n$ следующим образом. Запишем $n$ в виде числа в двоичной системе счисления (убирая нули слева). Затем заменим каждую «1» парой символов SX, а каждый «0» — символом S и вычеркнем крайнюю слева пару символов SX. Результат представляет собой правило вычисления $x^{n}$, в котором «S» трактуется как операция возведения в квадрат, а «X» — как операция умножения на $x$. Например, $n = 23$ имеет двоичное представление $10111$. Таким образом, мы формируем последовательность SXSSXSXSX, из которой удаляем начальную пару SX для получения окончательного правила SSXSXSX. Это правило гласит, что необходимо «возвести в квадрат, возвести в квадрат, умножить на $x$, возвести в квадрат, умножить на $x$, возвести в квадрат и умножить на $x$», т.е. последовательно вычислить значения $x^{2}$, $x^{4}$, $x^{5}$, $x^{10}$, $x^{11}$, $x^{22}$, $x^{23}$.

Вам нужно для заданного n сформулировать соответствующее правило быстрого возведения числа $x$ в степень $x^{n}$

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

Одно натуральное число $n$, не превышающее $2 \cdot 10^{9}$.

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

Выведите строку для правила возведения числа $x$ в степень $n$ для получения $x^{n}$.

Тесты

# Входные данные Выходные данные
1 23 SSXSXSX
2 1
3 16 SSSS
4 1000000 SXSXSXSSXSSSSSXSSSXSSSSSS
5 2018 SXSXSXSXSXSSSSXS

Решение

Создаём две строки $s$ и $s1$ для двоичного представления числа $n$ и для правила нахождения числа $n$ соответственно. Далее мы проверяем $n$ на чётность, добавляя к строке $s$

  • $0$ при чётном $n$
  • $1$ при нечётном $n$

и делим $n$ на $2$. Продолжаем это пока $n \neq 0$. Таким образом мы получили двоичный код, записанный в обратном порядке от двоичного кода числа $n$. После мы присваиваем цифрам «0» и «1» соответственно «S» и «SX» справа налево (в порядке двоичного кода числа $n$). В конце, удаляем первые символы «SX» с помощью метода erase(), таким образом получая ответ

Условие задачи можно найти на e-olymp
Код решения — ideone

e-olymp 2817. Двоичные числа

Задача

Для заданного положительного целого числа $n$, распечатать позиции всех $1$ в двоичном его представлении. Позиция младшего бита имеет номер $0$.
Позиции $1$ в двоичном представлении числа $13$ — это $0$, $2$, $3$.
Напишите программу, которая для каждого набора данных:

  • читает натуральное число $n$,
  • вычисляет позиции $1$ в двоичном представлении $n$,
  • выводит результат.

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

В первой строке входного файла содержится одно натуральное число $d$, указывающее количество наборов входных данных, $1 \leq d \leq 10$. Входные данные заданы ниже.

Каждый набор данных состоит ровно из одной строки, содержащей ровно одно целое число $n$, $0 \leq n \leq 10^6$.

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

Вывод должен состоять ровно из $d$ строк — по одной строке для каждого набора входных данных.

Строка $i$, $1 \leq i \leq d$, должна содержать возрастающую последовательность целых чисел, разделенных одним пробелом — позиции $1$ в двоичном представлении $i$-го числа, полученного во входных данных.

Тесты

 

Входные данные
Выходные данные
$3$
$17$
$7$
$5$
$0$ $4$
$0$ $1$ $2$
$0$ $2$
$4$
$1945$
$1337$
$1000000$
$999999$
$0$ $3$ $4$ $7$ $8$ $9$ $10$
$0$ $3$ $4$ $5$ $8$ $10$
$6$ $9$ $14$ $16$ $17$ $18$ $19$
$0$ $1$ $2$ $3$ $4$ $5$ $9$ $14$ $16$ $17$ $18$ $19$
$10$
$0$
$1$
$2$
$3$
$4$
$5$
$6$
$7$
$8$
$9$
$0$
$1$
$0$ $1$
$2$
$0$ $2$
$1$ $2$
$0$ $1$ $2$
$3$
$0$ $3$

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

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

Для решения этой задачи нужно понять, что остаток от деления $n$ на $2$ это последняя цифра в двоичном коде числа $n$, а деление целочисленной переменной $n$ на $2$ это отбрасывание последней цифры в двоичном коде. Цикл с счетчиком $i$ до момента, как $n$ не станет равняться $0$, очевиден, как и внешний цикл от $0$ до $d$, который реализовывает $d$ итераций ввода числа $n$. Стоит отметить, что тесты на e-olymp (все, кроме первого) чувствительны к пробелам в конце строки, из-за чего появляется необходимость каким-то образом его избежать.

Ссылки

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

e-olymp 622. Единицы

Единицы

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

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

Одно целое число [latex]n[/latex] [latex](0 ≤ n ≤ 2\cdot10^9)[/latex].

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

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

Тесты

Входные данные Выходные данные
20 2
0 0
1 1
5 2
2000000000 13

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

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

Алгоритм заключается в последовательном делении заданного числа [latex]n[/latex] на [latex]2[/latex] и нахождении количества остатков от деления (по условию), равных единице. Полагаем начальное количество единиц [latex]k[/latex] равное нулю. Затем, нужно прибавить остаток от деления к имеющемуся у нас [latex]k[/latex]. Если остаток равен единице то мы получим [latex]k+1[/latex] что нам и требуется.

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

e-olymp 7457. Max-Min в двійковій системі счислення

Умова

Вивчаючи двійкову систему числення, Василько вирішив попрактикуватися і придумав таку вправу. Він із бітів числа створював найбільше і найменше число, переставляючи біти, після чого знаходив їх різницю. Проте хлопець не знає, чи правильно виконує вправу. Допоможіть йому. Напишіть програму, яка за даним числом [latex]N[/latex] знаходить різницю між найбільшим і найменшим числом, які утворюються із бітів заданого числа. У найбільшого числа найбільший біт співпадає з найбільшим бітом заданого числа.

Пояснення

[latex]N = 13_{10}[/latex], в двійковій системі числення — [latex]1101_2[/latex], найбільше число [latex]1110_2[/latex] = [latex]14_{10}[/latex], найменше число [latex]0111_2[/latex] = [latex]7_{10}[/latex]. [latex]14-7=7[/latex].

Вхідні дані

В єдиному рядку записане число N ([latex]N<2^{31}[/latex]).

Вихідні дані

Єдине число — відповідь до вправи Василька.

Тести

Вхідні дані Вихідні дані
$2$ $1$
$15$ $0$
$86$ $105$
$1000$ $945$
$40$ $45$

Код програми

Рішення

Процес вирішення даної задачі поділяється на 4 кроки:

  1. За допомогою циклу рахуємо кількість одиниць та нулів у двійковому вигляді поданого числа [latex]n[/latex].
  2. Створимо функцію [latex]max\_number[/latex], яка за поданою кількістю нулів та одиниць буде повертати найбільше число, яке в двійковій формі складатиметься з цієї кількості одиниць та нулів. Очевидно, що отримати найбільше число в двійковому вигляді можна, якщо записати спочатку всі одиниці, а потім — усі нулі.
  3. Створимо функцію [latex]min\_number[/latex], яка за поданою кількістю нулів та одиниць буде повертати найменше число, яке в двійковій формі складатиметься з цієї кількості одиниць та нулів. Зрозуміло, що найменше число буде виглядати навпаки — спочатку будуть стояти всі нулі, а потім — усі одиниці.
  4. Виведемо на екран різницю підрахованих функціями [latex]max\_number[/latex] та [latex]min\_number[/latex] значень.

Посилання

Код програми на ideone
Умова на сайті E-Olymp