Задача
Вавилонцы решили построить удивительную башню — расширяющуюся к верху и содержащую бесконечное число этажей и комнат. Она устроена следующим образом — на первом этаже одна комната, затем идет два этажа на каждом из которых по две комнаты, затем идёт три этажа, на каждом из которых по три комнаты и так далее.
Эту башню решили оборудовать лифтом — и вот задача: нужно научится по номеру комнаты определять, на каком этаже она находится и какая она по счету слева на этом этаже.
Входные данные
Номер комнаты [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 |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
#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, соответствует этажу, на котором находится комната. К ней в конце необходимо добавить единицу, так как в этой переменной не учитывается «текущий» этаж.
Думаю, стоило бы использовать $\leqslant$ — \leqslant в условии.
Хорошо. Моя версия короче, но дольше работает.
Т.е. формула этажа получилась, но свернуть и разрешить относительно $n$ у меня сходу не вышло.
Значит пока засчитываем на циклы, но продолжаем думать, как обойтись без них.