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.  
  69. 		if (Min <= Sc) continue;
  70. 		if (C == 2)continue;
  71. 		if (S.size() >= D.size() / 2) {
  72. 			std::int64_t T = M[D];
  73. 			if (T == 0) {
  74. 				M[D] = Sc;
  75. 			}
  76. 			else {
  77. 				if (T+2 <= Sc) continue;//ここいじると厳密解と近似値が変わる。T+X => X>=2（厳密解）、X<2（近似解？）
  78. 				M[D] = Sc;
  79. 			}
  80. 		}
  81.  
  82. 		S.push_back({ D,Sc,C + 1 });
  83. 		if (C == 0) {
  84. 			std::int64_t T = D[Sc%D.size()];
  85. 			if (T == -1) {
  86. 				Sc++;
  87. 			}
  88. 			else {
  89. 				D[Sc%D.size()] = -1;
  90. 				Sc += T;
  91. 			}
  92. 			if (std::find_if_not(D.begin(), D.end(), [](auto& o) {return o == -1; }) == D.end()) {
  93. 				if (Min > Sc) {
  94. 					Min = Sc;
  95. 					//M[D] = Sc;
  96. 				}
  97. 			}
  98. 			else {
  99. 				S.push_back({ D,Sc + CountNext(D,Sc%D.size()),0 });
  100. 			}
  101. 		}
  102. 		else {
  103. 			Sc++;
  104. 			S.push_back({ D,Sc + CountNext(D,Sc%D.size()),0 });
  105. 		}
  106.  
  107. 	}
  108. 	//	MemoOut(M);
  109. 	return Min;
  110. }
  111. /**/
  112. std::int64_t MakeHoge(const std::string& S) {
  113. 	DType D = MakeVector(S);
  114.  
  115. 	return Solvar(D);
  116. }
  117. bool Show(const std::string& S, std::int64_t N) {
  118. 	std::cout << N << ':' << S << std::endl;
  119. 	return true;
  120. }
  121.  
  122. int main() {
  123. 	std::string S;
  124. 	std::int64_t V = 0;
  125.  
  126. 	S = "12_3";
  127. 	V=MakeHoge(S);
  128. 	Show(S, V);
  129. 	S = "14432";
  130. 	V=MakeHoge(S);
  131. 	Show(S, V);
  132. 	S = "887654329";
  133. 	V=MakeHoge(S);
  134. 	Show(S, V);
  135. 	S = "313__";
  136. 	V=MakeHoge(S);
  137. 	Show(S, V);
  138. 	S = "4_35_1264_23_434";
  139. 	V=MakeHoge(S);
  140. 	Show(S, V);	
  141. 	S = "123456789123456789";
  142. 	V=MakeHoge(S);
  143. 	Show(S, V);
  144. 	S = "88967472612377988186";
  145. 	V=MakeHoge(S);
  146. 	Show(S, V);
  147. 	S = "19898693316679441672";
  148. 	V=MakeHoge(S);
  149. 	Show(S, V);
  150. 	S = "93769682716711132249893";
  151. 	V=MakeHoge(S);
  152. 	Show(S, V);
  153.  
  154. 	return 0;
  155. }
  156.  
  157.  
  158.  
Time limit exceeded #stdin #stdout 5s 59584KB
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/B9vl8l
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!