e-olymp 8538. Калькулятор

07/08/2020 by Александр Розин

Условие

Калькулятор Ильи выполняет два действия: умножает текущее число на три и прибавляет к нему единицу. На калькуляторе сейчас число $1$. Помогите Илье определить наименьшее количество действий, после которой он получит число $n$.

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

Одно число $n$ $\left(10\leq n\leq 10^9\right)$.

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

Выведите наименьшее количество операций.

Тесты

№	Входные данные	Выходные данные
1	1447	16
2	18	3
3	111	6

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

#include <iostream>
using namespace std;
 
int main() {
    long long n;
    int k = 0;
    cin >> n;
    while (n > 0) {
        k += n%3 + 1;
        n /= 3;
    } 
    cout << k - 2;
}

#include <iostream>

using namespace std;

int main() {

long long n;

int k = 0;

cin >> n;

while (n > 0) {

k += n%3 + 1;

n /= 3;

}

cout << k - 2;

}

Решение

Решим данную задачу от обратного. Пусть нам дано число $n$ и нам надо из него получить $1$, задействовав как можно меньше операций. Для этого объявим цикл while(), который будет работать до тех пор, пока наше число $n$ будет строго больше $0$. Внутри цикла опишем следующее решение: пусть k будет счётчиком нажатий на кнопки калькулятора и изначально равняется $0$. Тогда, при каждом шаге цикла мы к счётчику будем прибавлять остаток от деления на $3$. n%3 — именно столько раз нам потребуется отнять $1$ от $n$ чтобы можно было нацело разделить на $3$. Далее, делим $n$ на $3$ и это потребует еще одного нажатия (что и происходит в строке $9$). Так как в условии цикла мы написали, что $n > 0$, то мы пройдём лишнюю итерацию и к счётчику прибавятся два лишних шага. Поэтому, при выводе ответа, от $k$ отнимаем $2$.

Related Images:

e-olymp 8373. Перевернутая башня

23/12/2018 by Богдан Павлов

Задача

Вавилонцы решили построить удивительную башню — расширяющуюся к верху и содержащую бесконечное число этажей и комнат. Она устроена следующим образом — на первом этаже одна комната, затем идет два этажа на каждом из которых по две комнаты, затем идёт три этажа, на каждом из которых по три комнаты и так далее.

Эту башню решили оборудовать лифтом — и вот задача: нужно научится по номеру комнаты определять, на каком этаже она находится и какая она по счету слева на этом этаже.

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

Номер комнаты [latex]n (1\leqslant n \leqslant 2\cdot10^{9})[/latex].

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

Выведите два целых числа: номер этажа и номер комнаты на этаже если считать слева.

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	1	1 1
2	5	3 2
3	35	11 5
4	31	11 1
5	2000000000	1650964 845

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

#include <iostream>
#include <cmath>
using namespace std;
int main() {
    int n; // номер комнаты
    int rooms_per_floor = 1; // кол-во комнат на этаже
    int temp = 0;
    int rooms = 0; // общее количество комнат
    int floor = 0; // этаж, на котором будет находиться комната #n
    cin >> n;
    while(n>0){
        if(rooms_per_floor == temp){
            temp = 0;
            rooms_per_floor++;
        }
        else if(n-rooms_per_floor>0){
            rooms+=rooms_per_floor;
            temp++;
            floor++;
            n-=rooms_per_floor;
        }
        else break;
    }
    cout << floor+1 << " " << n;
    return 0; 
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

int n; // номер комнаты

int rooms_per_floor = 1; // кол-во комнат на этаже

int temp = 0;

int rooms = 0; // общее количество комнат

int floor = 0; // этаж, на котором будет находиться комната #n

cin >> n;

while(n>0){

if(rooms_per_floor == temp){

temp = 0;

rooms_per_floor++;

}

else if(n-rooms_per_floor>0){

rooms+=rooms_per_floor;

temp++;

floor++;

n-=rooms_per_floor;

}

else break;

}

cout << floor+1 << " " << n;

return 0;

}

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

Для решения данной задачи я воспользовался циклом while, в котором на каждой итерации, проверял будет ли значение выражения n-rooms_per_floor больше нуля. Если оно было больше нуля, то из n вычиталось количество комнат на текущем этаже, а если меньше нуля, то цикл прерывался. После изменений, выполненных в цикле, переменная n соответствует номеру комнату на этаже, а переменная floor, которая равна количеству вычитаний из n, соответствует этажу, на котором находится комната. К ней в конце необходимо добавить единицу, так как в этой переменной не учитывается «текущий» этаж.

Ссылки

- Засчитанное решение на e-olymp
- Код на ideone

Related Images:

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