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. bool MemoOut(const MType& M) {
  42. 	std::cout << "--Memo--" << std::endl;
  43. 	for (auto& oo : M) {
  44. 		std::cout << oo.second << ':';
  45. 		for (auto& o : oo.first) {
  46. 			std::cout << o<<',';
  47. 		}
  48. 		std::cout << std::endl;
  49. 	}
  50. 	std::cout << "--End--" << std::endl;
  51.  
  52. 	return true;
  53. }
  54.  
  55. std::int64_t Solvar(DType D) {
  56. 	SType S;
  57. 	MType M;
  58. 	VType V;
  59. 	std::int64_t C;
  60. 	std::int64_t Sc;
  61. 	std::int64_t Min = std::numeric_limits<std::int64_t>::max();
  62.  
  63.  
  64. 	S.push_back({ D,0,0 });
  65. 	while (S.size() != 0) {
  66. 		std::tie(D, Sc, C) = S.back();
  67. 		S.pop_back();
  68. 		if (Min <= Sc+CountNext(D,Sc%D.size())) continue;
  69. 		//if (Min <= Sc) continue;
  70. 		if (C == 2)continue;
  71. 		std::int64_t X = M[D];
  72. /**/
  73. 		if (S.size() > D.size()/2) {
  74.  
  75. 			std::int64_t T = M[D];
  76. 			if (T == 0) {
  77. 				M[D] = Sc;
  78. 			}
  79. 			else {
  80. 				if (T+2 <= Sc) continue;//ここいじると厳密解と近似値が変わる。T+X => X>=2（厳密解）、X<2（近似解？）　
  81. 				M[D] = Sc;
  82. 			}
  83. 		}
  84. /**/
  85. 		S.push_back({ D,Sc,C+1 });
  86. 		if (C == 0) {
  87. 			std::int64_t T = D[Sc%D.size()];
  88. 			if (T == -1) {
  89. 				Sc++;
  90. 			}
  91. 			else {
  92. 				D[Sc%D.size()] = -1;
  93. 				Sc+=T;					
  94. 			}
  95. 			if (std::find_if_not(D.begin(), D.end(), [](auto& o) {return o == -1; }) == D.end()) {
  96. 				if (Min > Sc) {
  97. 					Min = Sc;
  98. 					M[D] = Sc;
  99. 				}
  100. 			}
  101. 			else {
  102. 				S.push_back({ D,Sc + CountNext(D,Sc%D.size()),0 });
  103. 			}
  104. 		}
  105. 		else {
  106. 			Sc++;
  107. 			S.push_back({ D,Sc+ CountNext(D,Sc%D.size()),0 });
  108. 		}
  109.  
  110. 	}
  111. //	MemoOut(M);
  112. 	return Min;
  113. }
  114. std::int64_t MakeHoge(const std::string& S) {
  115. 	DType D = MakeVector(S);
  116.  
  117. 	return Solvar(D);
  118. }
  119. bool Show(const std::string& S, std::int64_t N) {
  120. 	std::cout << N << ':' << S << std::endl;
  121. 	return true;
  122. }
  123.  
  124. int main() {
  125. 	std::string S;
  126. 	std::int64_t V = 0;
  127.  
  128. 	S = "12_3";
  129. 	V=MakeHoge(S);
  130. 	Show(S, V);
  131. /**/
  132. 	S = "14432";
  133. 	V=MakeHoge(S);
  134. 	Show(S, V);
  135. /**/
  136. 	S = "887654329";
  137. 	V=MakeHoge(S);
  138. 	Show(S, V);
  139. /**/
  140. /**/
  141. 	S = "313__";
  142. 	V=MakeHoge(S);
  143. 	Show(S, V);
  144. 	S = "4_35_1264_23_434";
  145. 	V=MakeHoge(S);
  146. 	Show(S, V);	
  147. 	S = "123456789123456789";
  148. 	V=MakeHoge(S);
  149. 	Show(S, V);
  150. 	S = "88967472612377988186";
  151. 	V=MakeHoge(S);
  152. 	Show(S, V);
  153. 	S = "19898693316679441672";
  154. 	V=MakeHoge(S);
  155. 	Show(S, V);
  156. 	S = "93769682716711132249893";
  157. 	V=MakeHoge(S);
  158. 	Show(S, V);
  159.  
  160. 	return 0;
  161. }
  162.  
  163.  
  164.  
Time limit exceeded #stdin #stdout 5s 60104KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
6:12_3
20:14432
80:887654329
8:313__
60:4_35_1264_23_434
98:123456789123456789
https://ideone.com/cBzPSj
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!