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, и почему алгоритм правильный..

Помогите плз разобраться : )