Разбор задачи F
Условия задачи шестого тураУ данной задачи возможно несколько решений.
Первое решение: непосредственно создаем текстовую строку, последовательно записывая в нее значения точных квадратов, пока не получится строка необходимой длины. Далее выводим соответствующий символ в этой строке. Такое решение должно набирать 20 баллов. Оно крайне неэффективно, так как требует большого числа операций с памятью.
Второе решение: строку не конструируем, а просто подсчитываем ее длину, суммируя длины десятичных записей всех точных квадратов. В результате мы узнаем, какую цифру в каком числе нам необходимо определить. Такое решение имеет сложность O(N), но работает быстрее, так как не производятся сложные операции над строками. Такое решение должно набирать 60 баллов.
Третье, наиболее эффективное решение. Вместо перебора всех чисел подряд определяем, сколько существует чисел, чьи квадраты имеют длину 1, затем – сколько чисел, чьи квадраты имеют длину два и т.д. В результате получится алгоритм сложности O(log n). Он будет набирать 100 баллов.
Хотя входные данные и ограничены значением 109, при вычислении значения «длина точного квадрата» * «количество чисел такой длины» может произойти переполнение типа int, поэтому будем использовать тип long long.
Для удобства будем индексировать позицию не с 1, а с 0.