fork(3) download 
  1. #include <iostream>
  2. #include <iomanip>  //cout.setprecision(), cout.fixed
  3. #include <deque>
  4. #include <stack>
  5. #include <cmath>    //floor()
  6. #include <map>
  7. using namespace std;
  8.  
  9. //НОД
  10. long double gcd(long double a, long double b){
  11.    while(b){
  12.        a = a - b*floor(a/b);
  13.        swap(a, b);
  14.    }
  15.    return a;
  16. }
  17.  
  18. //НОК
  19. long double lcm(long double a, long double b){
  20.    return a*(b/gcd(a,b));
  21. }
  22.  
  23. int main()
  24. {
  25.     int S, M, H, K;
  26.     cin >> S >> M >> H >> K;
  27.  
  28.     //инициализация очереди
  29.     deque<int> clock;
  30.     for(int i = 1; i <= K; i++)
  31.        clock.push_back(i);
  32.  
  33.     //моделирование суточного цикла
  34.     stack<int> s, m, h;
  35.     while(h.size() != H){
  36.        s.push(clock.front());  //первый шарик очереди падает
  37.        clock.pop_front();           //на секундную чашу
  38.        if(s.size() == S){           //при переполнении чаши
  39.            m.push(s.top());   //последний упавший шарик
  40.            s.pop();            //переходит на минутную чашу
  41.            while(!s.empty()){       //остальные шарики
  42.                clock.push_back(s.top());   //переходят в конец очереди
  43.                s.pop();                //в обратном порядке
  44.            }
  45.            if(m.size() == M){               //аналогично при переполнении
  46.                h.push(m.top());       //минутной чаши
  47.                m.pop();
  48.                while(!m.empty()){
  49.                    clock.push_back(m.top());
  50.                    m.pop();
  51.                }
  52.            }
  53.        }
  54.     }
  55.  
  56.     while(!h.empty()){
  57.        clock.push_back(h.top());
  58.        h.pop();
  59.     }
  60.  
  61.     //суточная перестановка
  62.     //1  2  3  4  5  6  ... K
  63.     //a1 a2 a3 a4 a5 a6 ... ak
  64.     int* permutation = new int[K+1];
  65.     for(int i = 1; i <= K; i++){
  66.        permutation[i] = clock.front();
  67.        clock.pop_front();
  68.     }
  69.  
  70.     //разложение перестановки в композицию непересекающихся циклов
  71.     bool *used = new bool[K+1]; //метки на посещенных элементах
  72.     long double permutation_period = 1; //период перестановки
  73.     for(int i = 1; i <= K; i++){
  74.        if(!used[i]){ //если элемент не принадлежит ни одному из обследованных циклов
  75.            long double cycle_length = 1;  //найти длину его цикла
  76.            for(size_t x = i; permutation[x] != i; x = permutation[x]){
  77.                used[x] = true;
  78.                cycle_length++;
  79.            }
  80.            //и воспользоваться тем, что порядок перестановки -
  81.            //произведение длин циклов из его разложения
  82.            permutation_period = lcm(permutation_period, cycle_length);
  83.        }
  84.     }
  85.     cout << setprecision(0) << fixed << permutation_period << endl;
  86.     return 0;
  87. }
  88.  
Runtime error #stdin #stdout 0s 3276KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/nz2JlG
language:
C++14 (gcc 8.3)
created:
9 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!