fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <cstdint>
  5. #include <map>
  6. #include <limits>
  7. #include <algorithm>
  8. typedef std::vector<std::int64_t> DType;
  9. typedef std::tuple < DType, std::int64_t,std::int64_t> VType;
  10. typedef std::vector<VType> SType;
  11. typedef std::map<DType, std::int64_t> MType;
  12.  
  13. DType MakeVector(const std::string& S) {
  14. 	DType D;
  15. 	for (auto& o : S) {
  16. 		if (o != '_') {
  17. 			char S[]{ o,'\0' };
  18. 			D.push_back(std::atoi(S));
  19. 		}
  20. 		else {
  21. 			D.push_back(-1);
  22. 		}
  23. 	}
  24.  
  25. 	return D;
  26. }
  27.  
  28. std::int64_t CountNext(const DType& D, std::size_t P) {
  29. 	std::int64_t C = 0;
  30. 	for (std::size_t i = 0; i < D.size(); i++) {
  31. 		if (D[(P + i) % D.size()] == -1) {
  32. 			C++;
  33. 		}
  34. 		else {
  35. 			break;
  36. 		}
  37. 	}
  38. 	return C;
  39. }
  40.  
  41. std::int64_t Solvar(DType D) {
  42. 	SType S;
  43. 	MType M;
  44. 	VType V;
  45. 	std::int64_t C;
  46. 	std::int64_t Sc;
  47. 	std::int64_t Min = std::numeric_limits<std::int64_t>::max();
  48. 	S.push_back({ D,0,0 });
  49. 	while (S.size() != 0) {
  50. 		std::tie(D, Sc, C) = S.back();
  51. 		S.pop_back();
  52. 		if (Min <= Sc+CountNext(D,Sc%D.size())) continue;
  53. 		if (C == 2)continue;
  54. /**/
  55. 		if (S.size() > D.size()/2+1) {
  56. 			std::int64_t T = M[D];
  57. 			if (T == 0) {
  58. 				M[D] = Sc;
  59. 			}
  60. 			else {
  61. 				if (T!=0&&T+1 <= Sc) continue;
  62. 				M[D] = Sc;
  63. 			}
  64. 		}
  65. /**/
  66. 		if(C<2)S.push_back({ D,Sc,C+1 });
  67. 		if (C == 0) {
  68. 			std::int64_t T = D[Sc%D.size()];
  69. 			if (T == -1) {
  70. 				Sc++;
  71. 			}
  72. 			else {
  73. 				D[Sc%D.size()] = -1;
  74. 				Sc += T;
  75. 			}
  76. 			if (std::find_if_not(D.begin(), D.end(), [](auto& o) {return o == -1; }) == D.end()) {
  77. 				if (Min > Sc) {
  78. 					Min = Sc;
  79. 					M[D] = Sc;
  80. 				}
  81. 			}
  82. 			else {
  83. 				S.push_back({ D,Sc + CountNext(D,Sc%D.size()),0 });
  84. 			}
  85. 		}
  86. 		else {
  87. 			Sc++;
  88. 			S.push_back({ D,Sc+ CountNext(D,Sc%D.size()),0 });
  89. 		}
  90.  
  91. 	}
  92.  
  93. 	return Min;
  94. }
  95. std::int64_t MakeHoge(const std::string& S) {
  96. 	DType D = MakeVector(S);
  97.  
  98. 	return Solvar(D);
  99. }
  100. bool Show(const std::string& S, std::int64_t N) {
  101. 	std::cout << N << ':' << S << std::endl;
  102. 	return true;
  103. }
  104.  
  105. int main() {
  106. 	std::string S;
  107. 	std::int64_t V = 0;
  108.  
  109. 	S = "12_3";
  110. 	V=MakeHoge(S);
  111. 	Show(S, V);
  112.  
  113. 	S = "313__";
  114. 	V=MakeHoge(S);
  115. 	Show(S, V);
  116. 	S = "4_35_1264_23_434";
  117. 	V=MakeHoge(S);
  118. 	Show(S, V);	
  119. 	S = "123456789123456789";
  120. 	V=MakeHoge(S);
  121. 	Show(S, V);
  122. 	S = "88967472612377988186";
  123. 	V=MakeHoge(S);
  124. 	Show(S, V);
  125. 	S = "19898693316679441672";
  126. 	V=MakeHoge(S);
  127. 	Show(S, V);
  128. 	S = "93769682716711132249893";
  129. 	V=MakeHoge(S);
  130. 	Show(S, V);
  131. 	return 0;
  132. }
Success #stdin #stdout 0.22s 23240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
6:12_3
8:313__
60:4_35_1264_23_434
98:123456789123456789
149:88967472612377988186
170:19898693316679441672
170:93769682716711132249893
https://ideone.com/VzYVY9
language:
C++14 (gcc 8.3)
created:
6 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!