fork download 
  1. // http://m...content-available-to-author-only...e.com/q/1258615/35416
  2.  
  3. #include <iostream>
  4. #include <iomanip>
  5. #include <vector>
  6. #include <cstdlib>
  7.  
  8. std::vector<unsigned> bitsums { 0U, 0U, 0U };
  9. std::vector<unsigned> countdown { 0U, 8U, 16U };
  10. unsigned nextToFinish = 1;
  11.  
  12. void recurse(int xOffset, int yOffset, unsigned bitcount, unsigned maxExp) {
  13.   int xPow = 1, yPow = 0;
  14.   for (unsigned e = 0; e != maxExp; ++e) {
  15.     // invariant: xPow + i*yPow = (i - 1)^e
  16.     int x = xPow + xOffset, y = yPow + yOffset;
  17.     unsigned dist = std::max(std::abs(x), std::abs(y));
  18. #if 0
  19.     static unsigned cnt = 0;
  20.     std::cout << ++cnt << ": (" << x << " = " << xPow << "+" << xOffset << ", "
  21.               << y << " = " << yPow << "+" << yOffset << ") @ "
  22.               << dist << " / " << bitcount << "\n";
  23. #endif
  24.     while (countdown.size() <= dist) {
  25.       bitsums.push_back(0);
  26.       countdown.push_back(8 * countdown.size());
  27.     }
  28.     bitsums[dist] += bitcount;
  29.     if (--countdown[dist] == 0 && nextToFinish == dist) {
  30.       do {
  31.         bitsums[nextToFinish] += bitsums[nextToFinish - 1];
  32.         std::cout << std::setw(5) << nextToFinish << " "
  33.                   << std::setw(8) << bitsums[nextToFinish] << "\n";
  34.         if (nextToFinish == 250)
  35.           std::exit(0);
  36.         ++nextToFinish;
  37.       } while (countdown[nextToFinish] == 0);
  38.     }
  39.     if (e)
  40.       recurse(x, y, bitcount + 1, e);
  41.     x = -(xPow + yPow);
  42.     yPow = xPow - yPow;
  43.     xPow = x;
  44.   }
  45. }
  46.  
  47. int main(int argc, char** argv) {
  48.   recurse(0, 0, 1, -1);
  49. }
  50.  
Success #stdin #stdout 0.06s 3232KB
comments (?)
stdin 
Standard input is empty
stdout 
    1       20
    2       75
    3      175
    4      310
    5      515
    6      750
    7     1065
    8     1380
    9     1795
   10     2265
   11     2815
   12     3355
   13     4045
   14     4755
   15     5560
   16     6285
   17     7170
   18     8110
   19     9175
   20    10235
   21    11465
   22    12695
   23    14030
   24    15255
   25    16710
   26    18250
   27    19910
   28    21500
   29    23305
   30    25095
   31    26940
   32    28585
   33    30510
   34    32490
   35    34655
   36    36755
   37    39145
   38    41505
   39    44045
   40    46405
   41    49085
   42    51800
   43    54685
   44    57410
   45    60440
   46    63385
   47    66435
   48    69175
   49    72325
   50    75540
   51    79030
   52    82425
   53    86140
   54    89785
   55    93585
   56    97105
   57   101045
   58   105005
   59   109175
   60   113115
   61   117350
   62   121410
   63   125525
   64   129200
   65   133395
   66   137645
   67   142200
   68   146570
   69   151430
   70   156180
   71   161190
   72   165820
   73   171010
   74   176235
   75   181720
   76   186895
   77   192600
   78   198145
   79   203885
   80   209085
   81   214945
   82   220800
   83   227040
   84   232975
   85   239400
   86   245685
   87   252155
   88   258135
   89   264785
   90   271385
   91   278285
   92   284725
   93   291630
   94   298290
   95   305015
   96   311070
   97   317895
   98   324785
   99   332110
  100   339140
  101   346910
  102   354500
  103   362480
  104   369890
  105   378010
  106   386075
  107   394480
  108   402415
  109   411005
  110   419260
  111   427750
  112   435460
  113   444070
  114   452635
  115   461720
  116   470335
  117   479600
  118   488645
  119   497925
  120   506525
  121   515945
  122   525145
  123   534715
  124   543575
  125   552970
  126   561950
  127   570985
  128   579100
  129   588215
  130   597385
  131   607100
  132   616390
  133   626570
  134   636480
  135   646810
  136   656360
  137   666910
  138   677455
  139   688420
  140   698755
  141   709980
  142   720845
  143   731985
  144   742105
  145   753365
  146   764620
  147   776500
  148   787835
  149   800000
  150   811865
  151   824015
  152   835275
  153   847665
  154   860000
  155   872795
  156   884820
  157   897640
  158   910065
  159   922565
  160   933925
  161   946545
  162   959240
  163   972540
  164   985235
  165   999040
  166  1012515
  167  1026430
  168  1039305
  169  1053300
  170  1067170
  171  1081550
  172  1095150
  173  1109695
  174  1123675
  175  1137940
  176  1150955
  177  1165360
  178  1179730
  179  1194790
  180  1209070
  181  1224330
  182  1239220
  183  1254355
  184  1268340
  185  1283555
  186  1298480
  187  1313945
  188  1328390
  189  1343620
  190  1358205
  191  1372855
  192  1386115
  193  1400865
  194  1415680
  195  1431290
  196  1446245
  197  1462500
  198  1478335
  199  1494760
  200  1510015
  201  1526760
  202  1543510
  203  1560850
  204  1577250
  205  1594950
  206  1612140
  207  1629695
  208  1645760
  209  1663455
  210  1680955
  211  1699330
  212  1716730
  213  1735270
  214  1753360
  215  1771805
  216  1788970
  217  1807735
  218  1826220
  219  1845335
  220  1863160
  221  1882060
  222  1900365
  223  1918745
  224  1935505
  225  1954005
  226  1972580
  227  1991960
  228  2010455
  229  2030500
  230  2050045
  231  2070175
  232  2088795
  233  2108925
  234  2128860
  235  2149455
  236  2168960
  237  2189760
  238  2209745
  239  2230125
  240  2248765
  241  2269265
  242  2289560
  243  2310695
  244  2330560
  245  2351715
  246  2372330
  247  2393180
  248  2412390
  249  2433220
  250  2453510
https://ideone.com/5XOKh2
language:
C++14 (gcc 8.3)
created:
10 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!