Срочно!
Сдать решение задачи 7-Таблица
Полный балл: 100
Ограничение времени: 500 мс
Ограничение памяти: 512M
Ограничение размера стека: 64M
Задача 7: Таблица
Бесконечную таблицу, строки и столбцы которой пронумерованы целыми числами начиная с 1 сверху вниз и слева направо, заполняют целыми числами 1, 2, 3 и т.д. Числа выписываются в соседние клетки по границам квадратов увеличивающегося размера (см. рисунок).
Дано число n, определите номер строки и номер столбца, в котором окажется это число.
Входные данные
Программа получает на вход одно целое число n, 1 ≤ n ≤ 1018.
Обратите внимание, что значение n может быть больше, чем возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные числа (тип int64 в языке Pascal, тип long long в C и C++, тип long в Java и C#).
Выходные данные
Программа должна вывести два целых числа: номер строки и номер столбца, в которых находится число n в этой таблице. Запись выводимых чисел должна содержать только цифры, вывод действительных чисел в ответе считается неверным.
Система оценивания
Решение, правильно работающее только для случаев, когда n ≤ 100, будет оцениваться в 20 баллов.
Решение, правильно работающее только для случаев, когда n ≤ 104, будет оцениваться в 40 баллов.
Решение, правильно работающее только для случаев, когда n ≤ 109, будет оцениваться в 60 баллов.
Пример
Ввод
Вывод
15
4 2
Answers & Comments
Ответ:
def integerSqrt(n):
if n < 2:
return n
else:
smallCandidate = integerSqrt(n >> 2) << 1
largeCandidate = smallCandidate + 1
if largeCandidate*largeCandidate > n:
return smallCandidate
else:
return largeCandidate
n = int(input())
m = integerSqrt(n - 1)
k = (m * (m + 1) + 1)
if m % 2 == 1 :
if k < n :
row = m + 1
col = (m + 1) - (n - k)
elif k == n :
row = m + 1
col = m + 1
else :
col = m + 1
row = (m + 1) + (n - k)
else :
if k < n :
col = m + 1
row = (m + 1) - (n - k)
elif k == n :
row = m + 1
col = m + 1
else :
row = m + 1
col = (m+1)+(n-k)
print(row, col)
Объяснение:
Питон есл ч