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

03/07/2018 by Никита Пушкин

Задача

Быстрое возведение в степень

Очень часто возникает задача эффективного вычисления $x^{n}$ по данным $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

#include <iostream>

using namespace std;

int main() {
    long long n, k = 0;
    cin >> n;
    int c = 0;
    while (n > 1) {
        long long bit = n & 1;
        n >>= 1;
        k <<= 1;
        k |= bit;
        c += 1;
    }
    while (c--) {
        long long bit = k & 1;
        k >>= 1;
        cout << (bit == 0 ? "S" : "SX");
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

long long n, k = 0;

cin >> n;

int c = 0;

while (n > 1) {

long long bit = n & 1;

n >>= 1;

k <<= 1;

k |= bit;

c += 1;

}

while (c--) {

long long bit = k & 1;

k >>= 1;

cout << (bit == 0 ? "S" : "SX");

}

return 0;

}

Решение

С помощью первого цикла while в переменную $k$ записываем перевернутый двоичный код числа $n$. Переменную $c$ используем как счётчик кол-ва бит в $n$. Во втором цикле while выводим S или SX если правый бит $0$ или $1$ соответственно, теряя при это последнюю $1$ как и сказано по условию задачи.

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

Related Images:

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

28/06/2018 by Павел Жуков

Задача

Для заданного положительного целого числа $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$

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

#include <iostream>
using namespace std;

int main() {
    int d;
    cin >> d;
    for (int j = 0; j < d; ++j){ 
        int n; 
        bool w = false;
        cin >> n;
        for (int i = 0; n>0; ++i){
            if (n % 2 == 1){
                if(w) cout << " ";
                w = true;
                cout << i;
                        }
            n /= 2;
        }
        cout << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int d;

cin >> d;

for (int j = 0; j < d; ++j){

int n;

bool w = false;

cin >> n;

for (int i = 0; n>0; ++i){

if (n % 2 == 1){

if(w) cout << " ";

w = true;

cout << i;

}

n /= 2;

}

cout << endl;

}

return 0;

}

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

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

Ссылки

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

Related Images:

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

21/01/2018 by Бондаренко Кирилл

Единицы

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

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

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

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

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

Тесты

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

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

#include <iostream>
using namespace std;

int main() {
    int k=0, n;
    cin >> n;
    while (n > 0){   
        k += (n % 2);
        n = n / 2;
    }
    cout << k;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int k=0, n;

cin >> n;

while (n > 0){

k += (n % 2);

n = n / 2;

}

cout << k;

return 0;

}

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

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

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

Related Images:

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

20/12/2017 by Александра Рябова

Умова

Вивчаючи двійкову систему числення, Василько вирішив попрактикуватися і придумав таку вправу. Він із бітів числа створював найбільше і найменше число, переставляючи біти, після чого знаходив їх різницю. Проте хлопець не знає, чи правильно виконує вправу. Допоможіть йому. Напишіть програму, яка за даним числом [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$

Код програми

#include <iostream>
#include <iomanip>
#include <cmath>

long long max_number(long long n1, long long n0)
{
    long long  number;
    for (int i=n0+n1-1; i>=n0; i--)
    {
        number+=pow(2, i);  
    }
    return(number);
}

long long min_number(long long n1, long long n0)
{
    long long  number;
    for (int i=n1-1; i>=0; i--)
    {
        number+=pow(2, i);  
    }
    return(number);
}

int main() 
{
    long long n;
    cin >> n;
    long long n1=0;
    long long n0=0;
    while (n>0)
    {
        if (n%2==1) n1++;
        else n0++;
        n/=2;
    }
    
    cout << max_number (n1, n0) - min_number (n1, n0);
    return 0;
}

#include <iostream>

#include <iomanip>

#include <cmath>

long long max_number(long long n1, long long n0)

{

long long number;

for (int i=n0+n1-1; i>=n0; i--)

{

number+=pow(2, i);

}

return(number);

}

long long min_number(long long n1, long long n0)

{

long long number;

for (int i=n1-1; i>=0; i--)

{

number+=pow(2, i);

}

return(number);

}

int main()

{

long long n;

cin >> n;

long long n1=0;

long long n0=0;

while (n>0)

{

if (n%2==1) n1++;

else n0++;

n/=2;

}

cout << max_number (n1, n0) - min_number (n1, n0);

return 0;

}

Рішення

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

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