fork(1) download 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4.  
  5. long g(int n, int l, int mid, int r, int fromL, int turns){
  6.   long right = 0;
  7.   long left = 0;
  8.  
  9.   if (mid + r <= n)
  10.     right = g(n, mid, mid + r, r, 1, turns + (1^fromL));
  11.  
  12.   if (mid + l <= n)
  13.     left = g(n, l, mid + l, mid, 0, turns + fromL);
  14.  
  15.   // Multiples
  16.   int k = n / mid;
  17.  
  18.   // This subtree is rooted at 2/3
  19.   return 4 * k * turns + left + right;
  20. }
  21.  
  22.  
  23. long f(int n) {  
  24.   // 1/1, 2/2, 3/3 etc.
  25.   long total = n;
  26.  
  27.   // 1/2, 2/4, 3/6 etc.
  28.   if (n > 1)
  29.     total += 3 * (n >> 1);
  30.  
  31.   if (n > 2)
  32.   // Technically 3 turns for 2/3 but
  33.   // we can avoid a subtraction
  34.   // per call by starting with 2. (I
  35.   // guess that means it's probably 
  36.   // another subtree, but I haven't
  37.   // thought it through.)
  38.     total += g(n, 2, 3, 1, 1, 2);
  39.  
  40.   return total;
  41. }
  42.  
  43.  
  44. int main() {
  45.   cout << f(10000);
  46.  
  47.   return 0;
  48. }
Success #stdin #stdout 0.15s 5292KB
comments (?)
stdin 
Standard input is empty
stdout 
782828208
https://ideone.com/KC8FLa
language:
C++ 4.3.2 (gcc-4.3.2)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!