Разбор задачи F
Условия задачи шестого тураУ данной задачи возможно несколько решений.
Первое решение: непосредственно создаем текстовую строку, последовательно записывая в нее значения точных квадратов, пока не получится строка необходимой длины. Далее выводим соответствующий символ в этой строке. Такое решение должно набирать 20 баллов. Оно крайне неэффективно, так как требует большого числа операций с памятью.
Второе решение: строку не конструируем, а просто подсчитываем ее длину, суммируя длины десятичных записей всех точных квадратов. В результате мы узнаем, какую цифру в каком числе нам необходимо определить. Такое решение имеет сложность O(N), но работает быстрее, так как не производятся сложные операции над строками. Такое решение должно набирать 60 баллов.
Третье, наиболее эффективное решение. Вместо перебора всех чисел подряд определяем, сколько существует чисел, чьи квадраты имеют длину 1, затем – сколько чисел, чьи квадраты имеют длину два и т.д. В результате получится алгоритм сложности O(log n). Он будет набирать 100 баллов.
Хотя входные данные и ограничены значением 109, при вычислении значения «длина точного квадрата» * «количество чисел такой длины» может произойти переполнение типа int, поэтому будем использовать тип long long.
Для удобства будем индексировать позицию не с 1, а с 0.
#include<iostream>
#include<cmath>
using namespace std;
/* Возвращает длину числа – количество десятичных цифр в нем */
int length(long long n)
{
int result=0;
while(n)
{
++result;
n/=10;
}
return result;
}
/* Возвращает k-ю цифру числа n * k=0..length(n)-1 */
int kthdigit(long long n, int k)
{
k=length(n)-1-k;
while(k)
{
n/=10;
--k;
}
return n%10;
}
/* Вычисляет 10^n */
long long power10(int n)
{
if(n==0)
return 1;
else
return 10*power10(n-1);
}
/* Функция count возвращает количество чисел,
* чьи квадраты имеют длину k */
long long count(int k)
{
/* Min – минимальное число, чей квадрат имеет длину k символов */
/* Для вычисления используется функция ceil, округляющая значение вверх */
long long Min=(long long)ceil(sqrt(power10(k-1)));
/* Max – максимальное число число, чей квадрат имеет длину k символов */
/* Для вычисления используется функция floor, округляющая значение вниз */
long long Max=(long long)floor(sqrt(power10(k)-1));
return Max-Min+1;
}
int main()
{
long long n; /* Для какого числа ищем ответ */
cin>>n;
--n; /* Для удобства индексируем с 0, поэтому вычтем 1 */
int len; /* Текущая длина квадрата */
long long skipped=0; /* Сколько чисел уже пропущено */
for(len=1;;++len) /* Цикл, сколько чисел нужно пропустить */
{
long long currlencount=count(len); /* Столько чисел имеют квадраты длины len */
if(n>=currlencount*len)
{
/* Пропускаем все currlencount чисел, чьи квадраты имеют длину len */
skipped+=currlencount;
n-=currlencount*len;
}
else
{
/* Нельзя пропустить все числа,
* нужно искать ответ среди чисел,
* чьи квадраты имеют длину len */
skipped+=n/len; /* Сколько чисел нужно пропустить из тех,
* чьи квадраты имеют длину len */
n=n%len; /* Позиция в числе, которую нужно вернуть */
/* Выводим в квадрате числа skipped+1 цифру номер n */
cout<<kthdigit((skipped+1)*(skipped+1),n)<<endl;
return 0;
}
}
}