4475. Часы

Постановка задачи

Ученые разработали часы, которые могут налаживаться для отсчета времени на любой планете. Они состоят из шариков, лотка (очереди) и трех чаш: секундной, минутной и часовой. В каждый момент времени количество шариков в чашах показывает время (секунды, минуты и часы соответственно). Каждую секунду первый шарик из очереди попадает в секундную чашу. Если секундная чаша наполнилась (количество шариков равно количеству секунд в минуте на этой планете), то этот шарик переходит в минутную чашу, а остальные шарики переходят из секундной чаши в конец очереди в порядке, обратном к их попаданию в секундную чашу. Аналогично, при наполнении минутной чаши последний шарик переходит в часовую чашу, а остальные шарики из минутной чаши переходят в конец очереди в порядке, обратном к их попаданию в минутную чашу. Если заполняется часовая чаша, то все шарики из нее переходят в конец очереди в порядке, обратном к их попаданию в часовую чашу. Все шарики пронумерованы и в начальный момент времени находятся в очереди.

Написать программу, вычисляющую минимальное количество суток, необходимых для того, чтобы начальное положение шариков в очереди повторилось.

Во входном потоке содержится количество секунд в минуте [latex]S[/latex], минут в часе [latex]M[/latex], часов в сутках [latex]H[/latex] и число шариков [latex]K[/latex].

Алгоритм решения

Интуитивно понятно, что положение шариков в очереди ежесуточно изменяется по одному и тому же закону, в силу однообразия процесса. Отыскать конкретный вид перестановки можно прямым моделированием часов, используя дек для описания лотка и стеки — каждой из чаш (у очереди задействованы оба конца, у чаш — только один).
Определить порядок суточной перестановки можно и возведением её в степень, но это нерациональный способ. Используя теорему о разложении перестановки в композицию циклов (к слову, непересекающихся), можно заметить, что порядок каждого из циклов равен его длине. Если мысленно представить перестановку в виде ориентированного графа, то процесс поиска циклов сведётся к поиску в глубину: обойти каждую компоненту связности, зафиксировать число входящих в неё вершин (на илл.)
[latex]\scriptsize \begin{pmatrix} 1 & 2 & 3 & 4 & 5 &6 & 7 & 8 & 9 & 10\\ 1 & 5 & 8 & 2 & 4 & 3 &7 & 9 & 6 & 10 \end{pmatrix}[/latex]
Зная длины всех циклов, нетрудно заметить, что задача сводится к поиску НОК полученной последовательности длин. Обосновать такой переход можно индуктивно: порядок перестановки, представимой в виде композиции двух циклов, равен НОК их длин, а случай большего количества циклов в разложении сводится к рассмотренному последовательным рассмотрением пар циклов (результат не зависит от порядка рассмотрения в силу ассоциативности композиции).

Реализация:

ideone: http://ideone.com/nz2JlG
Засчитанное решение: http://www.e-olimp.com/solutions/1937971

#include <iostream>
    #include <iomanip>  //cout.setprecision(), cout.fixed
    #include <deque>
    #include <stack>
    #include <cmath>    //floor()
    #include <map>
    using namespace std;

    //НОД
    long double gcd(long double a, long double b){
       while(b){
           a = a - b*floor(a/b);
           swap(a, b);
       }
       return a;
    }

    //НОК
    long double lcm(long double a, long double b){
       return a*(b/gcd(a,b));
    }

    int main()
    {
        int S, M, H, K;
        cin >> S >> M >> H >> K;

        //инициализация очереди
        deque<int> clock;
        for(int i = 1; i <= K; i++)
           clock.push_back(i);

        //моделирование суточного цикла
        stack<int> s, m, h;
        while(h.size() != H){
           s.push(clock.front());  //первый шарик очереди падает
           clock.pop_front();           //на секундную чашу
           if(s.size() == S){           //при переполнении чаши
               m.push(s.top());   //последний упавший шарик
               s.pop();            //переходит на минутную чашу
               while(!s.empty()){       //остальные шарики
                   clock.push_back(s.top());   //переходят в конец очереди
                   s.pop();                //в обратном порядке
               }
               if(m.size() == M){               //аналогично при переполнении
                   h.push(m.top());       //минутной чаши
                   m.pop();
                   while(!m.empty()){
                       clock.push_back(m.top());
                       m.pop();
                   }
               }
           }
        }

        while(!h.empty()){
           clock.push_back(h.top());
           h.pop();
        }

        //суточная перестановка
        //1  2  3  4  5  6  ... K
        //a1 a2 a3 a4 a5 a6 ... ak
        int* permutation = new int[K+1];
        for(int i = 1; i <= K; i++){
           permutation[i] = clock.front();
           clock.pop_front();
        }

        //разложение перестановки в композицию непересекающихся циклов
        bool *used = new bool[K+1]; //метки на посещенных элементах
        long double permutation_order = 1; //порядок перестановки
        for(int i = 1; i <= K; i++){
           if(!used[i]){ //если элемент не принадлежит ни одному из обследованных циклов
               long double cycle_length = 1;  //найти длину его цикла
               for(size_t x = i; permutation[x] != i; x = permutation[x]){
                   used[x] = true;
                   cycle_length++;
               }
               //и воспользоваться тем, что порядок перестановки -
               //произведение длин циклов из его разложения
               permutation_order = lcm(permutation_order, cycle_length);
           }
        }
        cout << setprecision(0) << fixed << permutation_order << endl;
        return 0;
    }

#include <iostream>

#include <iomanip> //cout.setprecision(), cout.fixed

#include <deque>

#include <stack>

#include <cmath> //floor()

#include <map>

using namespace std;

//НОД

long double gcd(long double a, long double b){

while(b){

a = a - b*floor(a/b);

swap(a, b);

}

return a;

}

//НОК

long double lcm(long double a, long double b){

return a*(b/gcd(a,b));

}

int main()

{

int S, M, H, K;

cin >> S >> M >> H >> K;

//инициализация очереди

deque<int> clock;

for(int i = 1; i <= K; i++)

clock.push_back(i);

//моделирование суточного цикла

stack<int> s, m, h;

while(h.size() != H){

s.push(clock.front()); //первый шарик очереди падает

clock.pop_front(); //на секундную чашу

if(s.size() == S){ //при переполнении чаши

m.push(s.top()); //последний упавший шарик

s.pop(); //переходит на минутную чашу

while(!s.empty()){ //остальные шарики

clock.push_back(s.top()); //переходят в конец очереди

s.pop(); //в обратном порядке

}

if(m.size() == M){ //аналогично при переполнении

h.push(m.top()); //минутной чаши

m.pop();

while(!m.empty()){

clock.push_back(m.top());

m.pop();

}

while(!h.empty()){

clock.push_back(h.top());

h.pop();

}

//суточная перестановка

//1 2 3 4 5 6 ... K

//a1 a2 a3 a4 a5 a6 ... ak

int* permutation = new int[K+1];

for(int i = 1; i <= K; i++){

permutation[i] = clock.front();

clock.pop_front();

}

//разложение перестановки в композицию непересекающихся циклов

bool *used = new bool[K+1]; //метки на посещенных элементах

long double permutation_order = 1; //порядок перестановки

for(int i = 1; i <= K; i++){

if(!used[i]){ //если элемент не принадлежит ни одному из обследованных циклов

long double cycle_length = 1; //найти длину его цикла

for(size_t x = i; permutation[x] != i; x = permutation[x]){

used[x] = true;

cycle_length++;

}

//и воспользоваться тем, что порядок перестановки -

//произведение длин циклов из его разложения

permutation_order = lcm(permutation_order, cycle_length);

}

cout << setprecision(0) << fixed << permutation_order << endl;

return 0;

}

Примечания

Экспериментально выяснено, что только тип long double является достаточно вместительным для избежания переполнения.
Операция взятия остатка для чисел с плавающей точкой не определена аппаратно, так что алгоритм Евклида вычисления НОД реализован в соответствии с его математическим описанием.
Модификатор fixed используется для предотвращения вывода чисел в научном формате (с использованием степеней десятки).

Related Images:

Похожее

2 thoughts on “e-olimp 4475. Часы”

Мазурок Игорь Евгеньевич says: 13/04/2015 at 18:53

Молодец, хороший анализ задачи.

Опишите (если нельзя исправить) причины зависимости результата от версии компилятора. На G++ два теста дают неверный ответ, а на MSVC9.0 все хорошо. Судя по статистике e-olimp, у Вас есть решение, которое зашло на G++4.7.1, правильно?

Войдите, чтобы ответить
- Іванов Вячеслав Володимирович says: 06/05/2015 at 22:24
  
  К сожалению, нет, ни одна из версий решения на G++ не прошла. Возможно, играет роль специфическая особенность e-olimp-а, мы иногда становились жертвами проблемных чекеров и неожиданного поведения компиляторов. Интереса ради, я нашел оригинальное решение задачи, алгоритм аналогичен.