fork download
copy 
  1. #include <iostream>
  2. #include <memory>
  3. #include <vector>
  4. #include <ctime>
  5. #include <algorithm>
  6.  
  7. static const uint64_t SEED = 0xDEADBEEFull;
  8. static const uint32_t COLORS_NUM = 2;
  9. static uint64_t next = SEED;
  10. uint32_t LCGRand()
  11. {
  12.     next = next * 6364136223846793005 + 1442695040888963407;
  13.     return next >> 32;
  14. }
  15.  
  16. void resetLCGRand()
  17. {
  18.     next = SEED;
  19. }
  20.  
  21. float getEmaxAvg(size_t sequenceLen, size_t sequencesCount = 30)
  22. {
  23.     size_t sum = 0;
  24.     for (size_t tries = 0; tries < sequencesCount; tries++) {
  25.         uint32_t lastColor = LCGRand();
  26.         size_t currentSequence = 1;
  27.         size_t maxSequence = 0;
  28.         for (size_t i = 1; i < sequenceLen; i++) {
  29.             uint32_t color = LCGRand() % COLORS_NUM;
  30.             if (color != lastColor) {
  31.                 maxSequence = std::max(maxSequence, currentSequence);
  32.                 currentSequence = 1;
  33.             } else {
  34.                 ++currentSequence;
  35.             }
  36.             lastColor = color;
  37.         }
  38.         sum += maxSequence;
  39.     }
  40.     return (float)sum / sequencesCount;
  41. }
  42.  
  43. int main()
  44. {
  45.     resetLCGRand();
  46.  
  47.     for (auto && seqLen : { 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000 }) {
  48.         std::cout << seqLen << "," << getEmaxAvg(seqLen, 30) << std::endl;
  49.     }
  50.     return 0;
  51. }
  52.  
Time limit exceeded #stdin #stdout 5s 4520KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
10,2.93333
100,6.6
1000,10
10000,14.0667
100000,16.7
1000000,20.3
10000000,23.8667
https://ideone.com/dGYGm7
language:
C++14 (gcc 8.3)
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!