Решение задачи "1, 10, 100, 1000..." с Timus
С пояснением   Просмотров: 35
Пояснение к задаче
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].