fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. int range_1s = 0;
  6. vector<int> ranges;
  7. int possible_count = 0;
  8. int toInt(string s);
  9. void makeRanges(int size, int range);
  10. bool checkHappy(int number, int size, int range);
  11.  
  12. int main() {
  13. 	// your code goes here
  14.  
  15. 	string problem = "---+-++-";
  16. 	int range = 3;
  17.  
  18. 	int size = problem.size();
  19. 	int number = toInt(problem);
  20. 	makeRanges(size, range);
  21.  
  22.  	if (number == 1) {
  23.  		cout << "1";
  24.  	} else if (checkHappy(number, size, range)) {
  25. 		cout << possible_count;
  26. 	} else {
  27. 		cout << "Impossible";
  28. 	}
  29.  
  30. 	cout << endl << number;
  31.  
  32. 	return 0;
  33. }
  34.  
  35. int toInt(string s) {
  36. 	int result = 0;
  37.  
  38. 	for (int i = s.size() - 1; i >= 0; --i) {
  39. 		//cout << s[i];
  40.  
  41. 		if (s[i] == '+')
  42. 			result += 1 << (s.size() - i - 1);
  43.  
  44. 		//cout << ": " << result << endl;
  45. 	}
  46.  
  47. 	return result;
  48. }
  49.  
  50. void makeRanges(int size, int range) {
  51. 	if (size <= 0)
  52. 		return;
  53.  
  54. 	ranges.clear();
  55.  
  56. 	int original = 1;
  57. 	for (int i = 1; i < size; ++i)
  58. 		range_1s = original = (original << 1) + 1;
  59.  
  60. 	cout << "original: " << original << endl;
  61.  
  62. 	for (int i = 0; i <= (range - size); ++i)
  63. 		ranges.push_back(original << i);
  64.  
  65. 	// // to check ranges
  66. 	// for (int n : ranges)
  67. 	// 	cout << n << endl;
  68.  
  69. }
  70.  
  71. bool isPossibleHappy(int part_num, int part_count, int range, int flipper) {
  72. 	if (part_count < range)
  73. 		return false;
  74.  
  75. 	if (part_num < 0 || part_count <= 0)
  76. 		return false;
  77.  
  78. 	if (part_num == 0 || part_num == 1)
  79. 		return true;
  80.  
  81. 	int flipped = part_num ^ flipper;
  82. 	if (flipped)
  83. 		return true;
  84.  
  85. 	for (int i = range; i < part_count; ++i) {
  86. 		flipper = flipper << 1;
  87. 		if (isPossibleHappy(part_num, part_count, range + 1, flipper))
  88. 			return true;
  89. 	}
  90.  
  91. 	return false;
  92. }
  93.  
  94. bool checkHappy(int target, int size, int range) {
  95. 	int part_num = 0;
  96. 	int part_count = 0;
  97.  
  98. 	for (int i = 0; i < size; ++i) {
  99. 		++part_count;
  100.  
  101. 		part_num = part_num << 1;
  102.  
  103. 		// if bit is exist
  104. 		if (target & (1 << (size - i - 1)))
  105. 			part_num += 1;
  106.  
  107. 		cout << "part_count: " << part_count << ", ";	
  108. 		cout << "part_num: " << part_num << endl;
  109.  
  110.  
  111. 		if (isPossibleHappy(part_num, part_count, range, range_1s)) {
  112. 			if (i == (size - 1))
  113. 				return true;
  114.  
  115. 			// initialzation	
  116. 			if (part_num > 1) {
  117. 				part_num = 0;
  118. 				part_count = 0;
  119. 			}
  120. 		}
  121. 	}
  122.  
  123. 	return false;
  124. }
Success #stdin #stdout 0s 16064KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
original: 255
part_count: 1, part_num: 0
part_count: 2, part_num: 0
part_count: 3, part_num: 0
part_count: 4, part_num: 1
part_count: 5, part_num: 2
part_count: 1, part_num: 1
part_count: 2, part_num: 3
part_count: 3, part_num: 6
0
22
https://ideone.com/s86Fs1
language:
C++ (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!