fork download
copy 
  1. #include<vector>
  2. #include<iostream>
  3.  
  4. using namespace std;
  5.  
  6. int c1=0;
  7. int c2=0;
  8.  
  9. int tarai1(int a,int b,int c)
  10. {
  11. 	int x,y,z;
  12. 	c1++;
  13. 	if(a<=b)return b;
  14. 	x=tarai1(a-1,b,c);
  15. 	y=tarai1(b-1,c,a);
  16. 	z=tarai1(c-1,a,b);
  17. 	return tarai1(x,y,z);
  18. }
  19.  
  20. class Stack : public vector<int>
  21. {
  22. public:
  23. 	int pop()
  24. 	{
  25. 		int v=back();
  26. 		pop_back();
  27. 		return v;
  28. 	}
  29. };
  30.  
  31. int tarai2(int a,int b,int c)
  32. {
  33. 	Stack A,B,C;
  34. 	Stack PC;
  35. 	Stack RET;
  36. 	int pc;
  37. 	int ret;
  38. 	pc=0;
  39.  
  40. 	while(true)
  41. 	{
  42. 		switch(pc)
  43. 		{
  44. 		case 0:
  45. 			c2++;
  46. 			if(a<=b)
  47. 			{
  48. 				RET.push_back(b);
  49. 				pc  = 6;
  50. 				continue;
  51. 			}
  52. 			else
  53. 			{
  54. 				pc=1;
  55. 				continue;
  56. 			}
  57. 		case 1:
  58. 			A.push_back(a);
  59. 			B.push_back(b);
  60. 			C.push_back(c);
  61. 			PC.push_back(2);
  62. 			a=A.back()-1;
  63. 			b=B.back();
  64. 			c=C.back();
  65. 			pc=0;
  66. 			continue;
  67. 		case 2:
  68. 			a=B.back()-1;
  69. 			b=C.back();
  70. 			c=A.back();
  71. 			PC.push_back(3);
  72. 			pc=0;
  73. 			continue;
  74. 		case 3:
  75. 			a=C.back()-1;
  76. 			b=A.back();
  77. 			c=B.back();
  78. 			PC.push_back(4);
  79. 			pc=0;
  80. 			continue;
  81. 		case 4:
  82. 			c=RET.pop();
  83. 			b=RET.pop();
  84. 			a=RET.pop();
  85. 			A.pop();
  86. 			B.pop();
  87. 			C.pop();
  88. 			pc=0;
  89. 			continue;
  90. 		case 6:
  91. 			if(PC.empty())
  92. 			{
  93. 				return RET.back();
  94. 			}
  95. 			pc=PC.pop();
  96. 			continue;
  97. 		}
  98. 	}
  99. }
  100.  
  101.  
  102. int main()
  103. {
  104. 	int x,y;
  105. 	bool OK=true;
  106. 	for(int i=0;i<10;++i)
  107. 	{
  108. 		for(int j=0;j<10;++j)
  109. 		{
  110. 			for(int k=0;k<10;++k)
  111. 			{
  112. 				c1=0;
  113. 				c2=0;
  114. 				x=tarai1(i,j,k);
  115. 				y=tarai2(i,j,k);
  116. 				if(!(c1==c2 && x==y))
  117. 				{
  118. 					OK=false;
  119. 					cout<<"NG "<<x<<" "<<y<<" "<<c1<<" "<<c2<<endl;
  120. 				}
  121. 			}
  122. 		}
  123. 	}
  124. 	if(OK)
  125. 	{
  126. 		cout<<"OK"<<endl;
  127. 	}
  128. }
Success #stdin #stdout 0.08s 3464KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
OK
https://ideone.com/rO18tw
language:
C++14 (gcc 8.3)
created:
8 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!