Задача
Жители планеты Олимпия любят летать в гости на другие планеты. Ученые планеты разработали часы, которые могут налаживаться для отсчета времени на любой планете. Эти часы состоят из шариков, лотка (очереди) и трех чаш: секундной, минутной и часовой. В каждый момент времени количество шариков в чашах показывает время (секунды, минуты и часы соответственно). Каждую секунду первый шарик из очереди попадает в секундную чашу. Если секундная чаша наполнилась (количество шариков равно количеству секунд в минуте на этой планете), то этот шарик переходит в минутную чашу, а остальные шарики переходят из секундной чаши в конец очереди в порядке, обратном к их попаданию в секундную чашу. Аналогично, при наполнении минутной чаши последний шарик переходит в часовую чашу, а остальные шарики из минутной чаши переходят в конец очереди в порядке, обратном к их попаданию в минутную чашу. Если заполняется часовая чаша, то все шарики из нее переходят в конец очереди в порядке, обратном к их попаданию в часовую чашу. Все шарики пронумерованы и в начальный момент времени находятся в очереди.
Написать программ, вычисляющую минимальное количество суток, необходимых для того, чтобы начальное положение шариков в очереди повторилось.
Входные данные
Входной файл содержит в единственной строке натуральные числа $S, M, H, K$ (количество секунд в минуте, минут в часе, часов в сутках и общее количество шариков соответственно), причем:
- $S, M, H ≤ 60$;
- $S+M+H-2≤K≤1000$
Выходные данные
Выходной файл должен содержать в единственной строке вычисленное Вашей программой количество суток.
Тесты
| Входные данные | Выходные данные |
| $5$ $12$ $12$ $30$ | $380$ |
| $7$ $10$ $40$ $70$ | $5610$ |
| $60$ $60$ $60$ $500$ | $4560840$ |
| $60$ $30$ $5$ $1000$ | $4970$ |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 |
import java.util.*; import java.lang.*; import java.io.*; class Main { public static double gcd(double a, double b){ double temp; while(b > 0){ a = a - b*Math.floor(a/b); temp = a; a = b; b = temp; } return a; } public static double lcm(double a, double b){ return a*(b/gcd(a,b)); } public static void main (String[] args) throws java.lang.Exception { int S, M, H, K; Scanner in = new Scanner(System.in); S = in.nextInt(); M = in.nextInt(); H = in.nextInt(); K = in.nextInt(); Deque clock = new ArrayDeque(); for(int i = 1; i <= K; i++) clock.addLast(i); Stack s = new Stack(); Stack m = new Stack(); Stack h = new Stack(); while(h.size() != H){ s.push(clock.getFirst()); //первый шарик очереди падает clock.removeFirst(); //на секундную чашу if(s.size() == S){ //при переполнении чаши m.push(s.peek()); //последний упавший шарик s.pop(); //переходит на минутную чашу while(!s.empty()){ //остальные шарики clock.addLast((Integer)s.peek()); //переходят в конец очереди s.pop(); //в обратном порядке } if(m.size() == M){ //аналогично при переполнении h.push(m.peek()); //минутной чаши m.pop(); while(!m.empty()){ clock.addLast((Integer)m.peek()); m.pop(); } } } } while(!h.empty()){ clock.addLast((Integer)h.peek()); 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.getFirst(); clock.removeFirst(); } //разложение перестановки в композицию непересекающихся циклов boolean[] used = new boolean[K+1]; double permutationOrder = 1; //метки на посещенных элементах for(int i = 1; i <= K; i++){ //порядок перестановки if(!used[i]){ //если элемент не принадлежит ни одному из обследованных циклов double cycleLength = 1; //найти длину его цикла for(int x = i; permutation[x] != i; x = permutation[x]){ used[x] = true; cycleLength++; } /*и воспользоваться тем, что порядок перестановки - произведение длин циклов из его разложения*/ permutationOrder = lcm(permutationOrder, cycleLength); } } System.out.print(Math.round(permutationOrder)); } } |
Алгоритм решения
- Интуитивно понятно, что положение шариков в очереди ежесуточно изменяется по одному и тому же закону, в силу однообразия процесса. Отыскать конкретный вид перестановки можно прямым моделированием часов, используя дек для описания лотка и стеки — каждой из чаш (у очереди задействованы оба конца, у чаш — только один).
-
Определить порядок суточной перестановки можно и возведением её в степень, но это нерациональный способ. Используя теорему о разложении перестановки в композицию циклов (к слову, непересекающихся), можно заметить, что порядок каждого из циклов равен его длине. Если мысленно представить перестановку в виде ориентированного графа, то процесс поиска циклов сведётся к поиску в глубину: обойти каждую компоненту связности, зафиксировать число входящих в неё вершин (на илл.)
$\begin{pmatrix}
1& 2& 3& 4& 5& 6& 7& 8& 9& 10\\
1& 5& 8& 2& 4& 3& 7& 7& 6& 10
\end{pmatrix}$
- Зная длины всех циклов, нетрудно заметить, что задача сводится к поиску НОК полученной последовательности длин. Обосновать такой переход можно индуктивно: порядок перестановки, представимой в виде композиции двух циклов, равен НОК их длин, а случай большего количества циклов в разложении сводится к рассмотренному последовательным рассмотрением пар циклов (результат не зависит от порядка рассмотрения в силу ассоциативности композиции).
Примечание
Операция взятия остатка для чисел с плавающей точкой не определена аппаратно, так что алгоритм Евклида вычисления НОД реализован в соответствии с его математическим описанием.