Тема: TopCoder SRM 449
250 DIV2
Линк задачи :
http://www.topcoder.com/stat?c=problem_ … p;rd=13903
Решение
class MountainRoad{
public :
double findDistance(vector <int> a, vector <int> b){
double s = *max_element(b.begin(),b.end()) - *min_element(a.begin(),a.end());
s *= sqrt(2.0);
return s;
}
};
Проходит систем тест.
Люди, почему? : )
500 DIV 2
Линк :
http://www.topcoder.com/stat?c=problem_ … p;rd=13903
Решение реккурентное
if (x % 2 == 0) k = ((x + 1)/2)^2
else k = (x/2)^2
f(x) = f(x/2) + k
hokage объяснил
A couple of observations:
1. When x is odd, f(x) = x. (Since x times 1 = x)
2. When x is even, the greatest odd divisor of x is the number formed by truncating trailing 0's in the binary representation of x.
For instance, if x = 12(1100), f(x) = 3(11); if x = 20(10100), f(x) = 5(101).
This is because every even number can be written as product of an odd number and a power of 2(2, 4, 8,...)
3. 1 + 3 + 5 + ... + (2n - 1) = n^2
Однако, непонятно как мы находим k, и почему алгоритм правильный..
Помогите плз разобраться : )