Какие будут номер строки и столбца для заданного числа n в бесконечной таблице, где строки и столбцы пронумерованы
Какие будут номер строки и столбца для заданного числа n в бесконечной таблице, где строки и столбцы пронумерованы целыми числами сверху вниз и слева направо? В таблице числа заполняются по границам квадратов, бесконечно возрастающих в размере. Входные данные: одно целое число n (1 ≤ n ≤ 1018). Обратите внимание на необходимость использования 64-битных чисел (тип int64) при обработке значений, которые могут превышать 32-битные значения.
Liya 15
Чтобы определить номер строки и столбца для заданного числа n в бесконечной таблице, мы можем использовать следующий подход.Первым шагом необходимо определить квадрат, в котором находится число n. Обратите внимание, что каждый квадрат имеет свои уникальные значения в левом верхнем и правом нижнем углу. Находим наименьший квадрат, в котором число n находится.
Пусть k будет размером этого квадрата. Тогда квадрат будет иметь значения в левом верхнем углу равное (k - 1) ^ 2 + 1 и в правом нижнем углу равное k ^ 2.
Далее определяем позицию числа n внутри квадрата. Для этого найдем "шаг" от левого верхнего угла к числу n. Например, для числа 15 в квадрате 4x4 шаг будет равен 3, так как нам нужно пройти 3 числа вниз и 3 числа вправо, чтобы достичь числа 15.
Зная размер квадрата k и шаг от левого верхнего угла, мы можем вычислить номер строки и столбца числа n в таблице.
Номер строки можно посчитать, добавив к номеру строки левого верхнего угла размер квадрата (k - 1) и шаг. То есть, номер строки будет равен (k - 1) + шаг.
Номер столбца можно посчитать, добавив к номеру столбца левого верхнего угла шаг. То есть, номер столбца будет равен шаг.
Теперь мы знаем, как определить номер строки и столбца для заданного числа n в бесконечной таблице.
Давайте решим задачу на примере:
Пусть n = 30. Мы должны определить номер строки и столбца для этого числа в бесконечной таблице.
Найдем наименьший квадрат, в котором число 30 находится. Для этого мы можем сравнивать значения (k - 1) ^ 2 + 1 и k ^ 2 с числом 30:
1 ^ 2 = 1 < 30
2 ^ 2 = 4 < 30
3 ^ 2 = 9 < 30
4 ^ 2 = 16 < 30
5 ^ 2 = 25 < 30
6 ^ 2 = 36 > 30
Таким образом, наименьший квадрат, в котором число 30 находится, имеет размер k = 6. Значения в левом верхнем и правом нижнем углах этого квадрата равны: (6 - 1) ^ 2 + 1 = 26 и 6 ^ 2 = 36.
Теперь определим позицию числа 30 внутри квадрата. Нам нужно пройти 4 числа вниз и 2 числа вправо от левого верхнего угла, чтобы достичь числа 30.
Номер строки будет равен (k - 1) + шаг = (6 - 1) + 4 = 9.
Номер столбца будет равен шаг = 2.
Таким образом, для числа 30 в бесконечной таблице номер строки равен 9, а номер столбца равен 2.