fork download
copy 
  1. #include <iostream>
  2. #include <sstream>
  3. #include <vector>
  4. #include <tuple>
  5. #include <cstdint>
  6. #include <string>
  7. #include <algorithm>
  8. #include <map>
  9.  
  10. typedef std::tuple<std::uint64_t, std::uint64_t> RData;
  11. typedef std::tuple<char, char> Data;
  12. typedef std::vector<Data> DType;
  13. typedef std::tuple<Data, Data> Pair;
  14. typedef std::vector<Pair> PType;
  15.  
  16. DType GetInput(std::istream& is) {
  17. 	char A = 0;
  18. 	char B = 0;
  19. 	DType D;
  20.  
  21. 	while (is >> A) {
  22. 		if (!(is >> B)) break;
  23. 		D.push_back({A,B});
  24. 	}
  25.  
  26. 	return D;
  27. }
  28.  
  29. template<int N>
  30. bool IsMatch(DType& D) {
  31. 	for (std::size_t i = 0; i < D.size(); i++) {
  32. 		if (std::get<N>(D.front()) != std::get<N>(D[i])) return false;
  33. 	}
  34. 	return true;
  35. }
  36.  
  37. bool Calc_rec(DType A,DType B, RData& R, std::size_t Depth) {
  38.  
  39. 	if (Depth == 0) {
  40. 		if (IsMatch<0>(A))std::get<0>(R)++;
  41. 		if (IsMatch<1>(A))std::get<1>(R)++;
  42. 		return true;
  43. 	}
  44. 	if (!(IsMatch<0>(A) || IsMatch<1>(A))) return false;
  45.  
  46. 	for (std::size_t i = 0; i < B.size(); i++) {
  47. 		A.push_back(B[i]);
  48. 		B.erase(B.begin()+i);
  49. 		Calc_rec(A, B, R, Depth - 1);
  50. 		B.push_back(A.back());
  51. 		A.pop_back();
  52. 		std::sort(B.begin(), B.end());
  53. 	}
  54.  
  55. 	return false;
  56. }
  57.  
  58. template<int N>
  59. std::size_t Count(DType& D) {
  60. 	std::map<char, std::size_t> M;
  61. 	std::size_t C = 0;
  62. 	for (auto& o : D) {
  63. 		M[std::get<N>(o)]++;
  64. 	}
  65.  
  66. 	for (auto& o : M) {
  67. 		C = std::max(o.second, C);
  68. 	}
  69. 	return C;
  70. }
  71.  
  72. bool IsPair(Data& A, Data& B) {
  73. 	return (std::get<0>(A) == std::get<0>(B)) || (std::get<1>(A) == std::get<1>(B));
  74. }
  75.  
  76. bool Calc_rec2(DType A,PType P, PType& R) {
  77. 	for (std::size_t i = 0; i < A.size(); i++) {
  78. 		for (std::size_t j = i + 1; j < A.size(); j++) {
  79. 			if (i == j)continue;
  80. 			if (IsPair(A[i], A[j])) {
  81. 				P.push_back({ A[i],A[j] });
  82. 				A.erase(A.begin() + j);
  83. 				A.erase(A.begin() + i);
  84. 				Calc_rec2(A, P, R);
  85. 				A.push_back(std::get<0>(P.back()));
  86. 				A.push_back(std::get<1>(P.back()));	
  87. 				std::sort(A.begin(), A.end());
  88. 				P.pop_back();
  89. 			}
  90. 		}
  91. 	}
  92. 	if (P.size() > R.size()) R = P;
  93. 	return true;
  94. }
  95. PType Calc2(DType& D) {
  96. 	PType R;
  97. 	std::sort(D.begin(), D.end());
  98. 	Calc_rec2(D, PType(), R);
  99. 	return R;
  100. }
  101.  
  102. RData Calc(DType& D) {
  103. 	RData R{ 0,0 };
  104.  
  105. 	std::sort(D.begin(), D.end());
  106.  
  107. 	std::size_t A = Count<0>(D);
  108. 	std::size_t B = Count<1>(D);
  109. 	std::size_t C = std::max(A, B);
  110.  
  111. 	for (std::size_t i = 2; i<C+1; i++) {
  112. 		Calc_rec(DType(), D, R, i);
  113. 	}
  114.  
  115. 	return R;
  116.  
  117. }
  118.  
  119. bool Show(std::string& S, RData& R) {
  120. 	std::cout << S << ':' << std::get<0>(R) << ',' << std::get<1>(R) << std::endl;
  121. 	return true;
  122. }
  123. bool Show2(std::string& S, PType& R) {
  124. 	std::cout << S << ':'<<R.size()<<'@';
  125.  
  126. 	for (auto& o : R) {
  127. 		std::cout << '[' << std::get<0>(std::get<0>(o)) << std::get<1>(std::get<0>(o)) << ',' << std::get<0>(std::get<1>(o)) << std::get<1>(std::get<1>(o)) << ']';
  128. 	}
  129. 	std::cout << std::endl;
  130.  
  131. 	return true;
  132. }
  133. int main() {
  134.  
  135. 	{
  136. 		std::string S = "DAD2HAH3";
  137. 		std::stringstream ss(S);
  138. 		DType D = GetInput(ss);
  139. 		PType R = Calc2(D);
  140. 		Show2(S, R);
  141. 	}
  142.  
  143. 	{
  144. 		std::string S = "DAD3D8D9DJH5H8HKSASKCAC5C8CK";
  145. 		std::stringstream ss(S);
  146. 		DType D = GetInput(ss);
  147. 		PType R = Calc2(D);
  148. 		Show2(S, R);	
  149. 	}
  150.  
  151. 	{
  152. 		std::string S = "SAS2S3S4S5S6S7S8S9C2C3C4C5C6C7C8C9CT";
  153. 		std::stringstream ss(S);
  154. 		DType D = GetInput(ss);
  155. 		PType R = Calc2(D);
  156. 		Show2(S, R);
  157. 	}
  158. 	/** //**/
  159. 	return 0;
  160. }
  161. /** /
  162. int main() {
  163.  
  164. 	{
  165. 		std::string S = "DAD2HAH3";
  166. 		std::stringstream ss(S);
  167. 		DType D = GetInput(ss);
  168. 		RData R = Calc(D);
  169. 		Show(S, R);
  170. 	}
  171.  
  172. 	{
  173. 		std::string S = "DAD3D8D9DJH5H8HKSASKCAC5C8CK";
  174. 		std::stringstream ss(S);
  175. 		DType D = GetInput(ss);
  176. 		RData R = Calc(D);
  177. 		Show(S, R);
  178. 	}
  179.  
  180. 	{
  181. 		std::string S = "SAS2S3S4S5S6S7S8S9C2C3C4C5C6C7C8C9CT";
  182. 		std::stringstream ss(S);
  183. 		DType D = GetInput(ss);
  184. 		RData R = Calc(D);
  185. 		Show(S, R);
  186. 	}
  187.  
  188. 	return 0;
  189. }
  190. /**/
Time limit exceeded #stdin #stdout 5s 15248KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
DAD2HAH3:2@[D2,DA][H3,HA]
DAD3D8D9DJH5H8HKSASKCAC5C8CK:7@[C5,C8][CA,CK][D3,D8][D9,DJ][DA,SA][H5,H8][HK,SK]
https://ideone.com/QNbwWa
language:
C++14 (gcc 8.3)
created:
7 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!