Решение задачи "1, 10, 100, 1000..." с Timus

С пояснением   Просмотров: 35


Представим себе бесконечную последовательность цифр, составленную из записанных друг за другом возрастающих степеней десятки. Вот начало этой последовательности: 110100100010000… Всё, что надо — определить, какая цифра находится в такой последовательности на определённом месте.

Код

#include <bits/stdc++.h>

using namespace std;
int main()
{
    int m, n;
    cin >> n;
    for(int i = 0; i < n; ++i){
        cin >> m;
        if(sqrt(8. * m - 7) == int(sqrt(8. * m - 7)))
            cout << 1 << endl;
        else
            cout << 0 << endl;
    }
    return 0;
}

         

 Администратор Photo Автор: Администратор


Ok, just posting this to help others understand few things here:

The sequence is 1101001000100000... If you see the locations of the digit 1, you can observe that it is at location 1,2,4,7...=> ( 1 + 0 ),( 1 + 1 ),( 1 + ( 1 + 2 )),( 1+(1+2+3 )..So, it is 1+sum_of_n_digits.

What we have now is below:

1 + n*( n+1 )/2 [ note that n*(n+1)/2 is the sum of first n natural numbers ].

Now, this value should be equal to the input value, say P.

1 + n*(n+1)/2 = p [ I/p P=7 => n should be 3, back track ].

2 + n^2 + n = 2p

n^2 + n = 2(p-1)

n^2 + n - 2 (p-1) = 0;

This is a quadratic equation in 'n'. The roots of a quadratic equation are

( -b +- sqrt( b^2 - 4ac ) )/2a

-1 +- sqrt( 8p-7 ) / 2;

But, for our example, if you do some analysis, if the value of 8p-7 is a perfect square, then the value at that position 'p' would be 1. Else the value would be 0.

So, check for 8p-7 to be a perfect square. This is the optimal solution. Got mine accepted.

BTW, if you face any difficulty at test 3, it means you have to upgrade your ints to doubles. Because 8p-7 can falll over the size of int [atleast in Java].

Thanks,
Babaev Minhojkhon.

Отправить решение задачи
Чтобы отправить решение вам нужно войти в систему или зарегистрироваться

Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться