fork download
copy 
  1. import java.util.*;
  2. import java.lang.*;
  3. import java.io.*;
  4.  
  5. class Main
  6. {
  7. 	public static double gcd(double a, double b){
  8. 		double temp;
  9.     	while(b > 0){
  10.         	a = a - b*Math.floor(a/b);
  11.         	temp = a;
  12. 			a = b;
  13. 	    	b = temp;
  14.     	}
  15.     	return a;
  16.     }
  17.     public static double lcm(double a, double b){
  18.     	return a*(b/gcd(a,b));
  19.     }
  20. 	public static void main (String[] args) throws java.lang.Exception
  21. 	{
  22.     	int S, M, H, K;
  23. 		Scanner in = new Scanner(System.in);
  24. 		S = in.nextInt();
  25. 		M = in.nextInt();
  26. 		H = in.nextInt();
  27. 		K = in.nextInt();
  28. 		Deque<Integer> clock = new ArrayDeque<>(); 
  29. 		for(int i = 1; i <= K; i++)
  30.     		clock.addLast(i);
  31.     	Stack s = new Stack();
  32.     	Stack m = new Stack();
  33.     	Stack h = new Stack();
  34.     	while(h.size() != H){
  35.     		s.push(clock.getFirst());  //первый шарик очереди падает
  36.     		clock.removeFirst();       //на секундную чашу
  37.     		if(s.size() == S){         //при переполнении чаши  
  38. 				m.push(s.peek());      //последний упавший шарик
  39.     			s.pop();               //переходит на минутную чашу
  40.     			while(!s.empty()){     //остальные шарики  
  41. 					clock.addLast((Integer)s.peek());   //переходят в конец очереди
  42. 					s.pop();           //в обратном порядке     
  43. 				}
  44. 				if(m.size() == M){     //аналогично при переполнении          
  45. 					h.push(m.peek());  //минутной чаши      
  46. 					m.pop();
  47. 					while(!m.empty()){
  48. 						clock.addLast((Integer)m.peek());
  49. 						m.pop();
  50. 					}
  51. 				}
  52. 			}
  53. 		}
  54. 		while(!h.empty()){
  55. 			clock.addLast((Integer)h.peek());
  56. 			h.pop();
  57. 		}
  58. 		/*суточная перестановка
  59. 		1  2  3  4  5  6  ... K
  60. 		a1 a2 a3 a4 a5 a6 ... ak*/
  61. 		int[] permutation = new int[K + 1];
  62. 		for(int i = 1; i <= K; i++){
  63. 			permutation[i] = clock.getFirst();
  64. 			clock.removeFirst();
  65. 		}
  66. 		//разложение перестановки в композицию непересекающихся циклов
  67. 		boolean[] used = new boolean[K+1]; 
  68. 		double permutationOrder = 1;    //метки на посещенных элементах
  69. 		for(int i = 1; i <= K; i++){    //порядок перестановки
  70. 		if(!used[i]){    //если элемент не принадлежит ни одному из обследованных циклов
  71. 				double cycleLength = 1;  //найти длину его цикла
  72. 				for(int x = i; permutation[x] != i; x = permutation[x]){
  73. 					used[x] = true;
  74. 					cycleLength++;
  75. 				}
  76. 				/*и воспользоваться тем, что порядок перестановки -
  77. 				произведение длин циклов из его разложения*/
  78. 				permutationOrder = lcm(permutationOrder, cycleLength);
  79. 			}
  80.     	}
  81.     	System.out.print(Math.round(permutationOrder));
  82. 	}
  83. }
Success #stdin #stdout 0.08s 2184192KB
comments (?)
stdin
copy 
60 30 5 1000
stdout
copy 
4970
https://ideone.com/2Ldpoo
language:
Java (HotSpot 12)
created:
5 years ago
visibility:
secret

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!