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

Задача

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

prb8373.gif

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

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

Номер комнаты [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

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

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

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

Ссылки

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