fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <cstdint>
  4. #include <map>
  5. #include <chrono>
  6.  
  7. typedef std::vector<std::uint64_t> DType;
  8. typedef std::vector<DType> RType;
  9. typedef std::map <std::uint64_t, bool> SType;
  10.  
  11. DType MakeInit(std::uint64_t N){
  12. 	std::uint64_t i = N;
  13. 	DType D;
  14. 	for (std::size_t i = 1; i <= N; i++)
  15. 	{
  16. 		D.push_back(1);
  17. 	}
  18. 	return D;
  19. }
  20.  
  21. bool AddRadix(DType& D, std::uint64_t R){
  22. 	bool Carry = false;
  23. 	D[0]++;
  24. 	for (std::size_t i = 0; i < D.size(); i++)
  25. 	{
  26. 		if (Carry == true){
  27. 			D[i]++;
  28. 		}
  29. 		Carry = false;
  30.  
  31. 		if (D[i] > R){
  32. 			D[i] = 1;
  33. 			Carry = true;
  34. 		}
  35. 	}
  36. 	return true;
  37. }
  38.  
  39. bool check(DType& D, std::uint64_t Max){
  40. 	SType M;
  41. 	std::uint64_t V = 0;
  42.  
  43. 	for (std::size_t k = 1; k <= D.size(); k++){
  44. 		for (std::size_t i = 0; i < D.size(); i++){
  45. 			for (std::size_t j = 0; j < k; j++){
  46. 				auto Idx = (i + j) % D.size();
  47. 				V += D[Idx];
  48. 			}
  49. 			M[V] = true;
  50. 			V = 0;
  51. 		}
  52. 	}
  53. 	if (M.size() < Max) return false;
  54. 	for (std::uint64_t i = 1; i <= Max; i++){
  55. 		if (M[i] == false) return false;
  56. 	}
  57. 	return true;
  58. }
  59.  
  60. RType MakeHoge(std::uint64_t N = 5, std::uint64_t R = 21 - 5,std::uint64_t M =21){
  61. 	DType D = MakeInit(N);
  62. 	bool F = false;
  63. 	RType Re;
  64.  
  65. 	while (F == false){
  66. 		if (check(D,M) == true){
  67. 			Re.push_back(D);
  68. 		}
  69. 		AddRadix(D, R);
  70.  
  71. 		F = true;
  72. 		for (std::size_t i = 0; i < D.size(); i++){
  73. 			if (D[i] != R){
  74. 				F = false;
  75. 				break;
  76. 			}
  77. 		}
  78. 	}
  79.  
  80.  
  81. 	return Re;
  82.  
  83. }
  84.  
  85. bool Show(RType& R){
  86.  
  87. 	for (auto& oo : R){
  88. 		std::cout << '[';
  89. 		for (auto& o : oo){
  90. 			std::cout << o<<',';
  91. 		}
  92. 		std::cout << ']' << std::endl;
  93. 	}
  94.  
  95. 	return true;
  96. }
  97. int main(){
  98. 	std::uint64_t N = 5;
  99. 	std::uint64_t M = 21;
  100. 	std::uint64_t R = M-N;
  101. 	RType Re;
  102.  
  103. 	auto S = std::chrono::high_resolution_clock::now();
  104. 	Re = MakeHoge(N, R, M);
  105. 	Show(Re);
  106. 	auto E = std::chrono::high_resolution_clock::now();
  107.  
  108. 	auto El = std::chrono::duration_cast<std::chrono::milliseconds >(E - S);
  109.  
  110. 	std::cout << "Time Using:" << El.count() << "ms" << std::endl;
  111.  
  112. 	return 0;
  113.  
  114. }
Success #stdin #stdout 4.11s 3236KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
[5,2,10,3,1,]
[3,10,2,5,1,]
[10,3,1,5,2,]
[5,1,3,10,2,]
[10,2,5,1,3,]
[1,5,2,10,3,]
[2,10,3,1,5,]
[1,3,10,2,5,]
[3,1,5,2,10,]
[2,5,1,3,10,]
Time Using:4113ms
https://ideone.com/IAcA0d
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!