fork download 
  1. #include <cassert>
  2.  
  3. #include <deque>
  4. #include <iostream>
  5. #include <vector>
  6.  
  7. // Write a program that outputs all possibilities to put + or - or nothing 
  8. // between the numbers 1, 2, ..., 9 (in this order) such that the result is 
  9. // always 100. For example: 1 + 2 + 34 – 5 + 67 – 8 + 9 = 100.
  10.  
  11. enum class Operation {
  12. 	Nothing,
  13. 	Add,
  14. 	Substract
  15. };
  16.  
  17. // Display the list of "+- " and its result
  18. void display(std::vector<int> const& suite,
  19. 		     std::vector<Operation> const& operations,
  20. 		     int const target)
  21. {
  22. 	std::cout << suite[0];
  23. 	for (size_t i = 0, max = operations.size(); i < max; ++i) {
  24. 		switch (operations[i]) {
  25. 		case Operation::Nothing: break;
  26. 		case Operation::Add: std::cout << " + "; break;
  27. 		case Operation::Substract: std::cout << " - "; break;
  28. 		}
  29. 		std::cout << suite[i + 1];
  30. 	}
  31. 	std::cout << " = " << target << "\n";
  32. } // display
  33.  
  34. // Produce the next vector of Operations
  35. // \returns "true" if a vector was produced, "false" otherwise
  36. bool next(std::vector<Operation>& operations) {
  37. 	for (Operation& o: operations) {
  38. 		switch (o) {
  39. 		case Operation::Nothing: 	o = Operation::Add; 		return true;
  40. 		case Operation::Add:     	o = Operation::Substract; 	return true;
  41. 		case Operation::Substract: 	o = Operation::Nothing; 	break; // loop to increment next
  42. 		}
  43. 	}
  44. 	return false; // if we reach here, the vector is not long enough
  45. } // next
  46.  
  47. // Given a list of integers and operations, return the total
  48. int compute(std::vector<int> const& suite,
  49. 		    std::vector<Operation> const& operations)
  50. {
  51. 	assert(suite.size() == operations.size() + 1);
  52.  
  53. 	// 1. First pass, group by "Nothing"
  54. 	std::deque<int> catenated; catenated.push_back(suite[0]);
  55.  
  56. 	for (size_t i = 0, max = operations.size(); i < max; ++i) {
  57. 		if (operations[i] != Operation::Nothing) {
  58. 			catenated.push_back(suite[i+1]);
  59. 			continue;
  60. 		}
  61.  
  62. 		int& last = catenated.back();
  63. 		last *= 10;
  64. 		last += suite[i+1];
  65. 	}
  66.  
  67. 	// 2. Second pass, evaluate
  68. 	int total = catenated[0]; catenated.pop_front();
  69.  
  70. 	for (Operation const& o: operations) {
  71. 		switch (o) {
  72. 		case Operation::Nothing: break;
  73.  
  74. 		case Operation::Add:
  75. 			total += catenated[0]; catenated.pop_front();
  76. 			break;
  77.  
  78. 		case Operation::Substract:
  79. 			total -= catenated[0]; catenated.pop_front();
  80. 			break;
  81. 		}
  82. 	}
  83.  
  84. 	assert(catenated.empty());
  85.  
  86. 	return total;
  87. } // compute
  88.  
  89. // Output the lists of "+- " which achieve the goal for the given vector and the
  90. // given target number.
  91. void compute(std::vector<int> const& suite, int const target) {
  92. 	if (suite.empty()) { return; }
  93.  
  94. 	Operation const N = Operation::Nothing;
  95. 	std::vector<Operation> operations{suite.size() - 1, N};
  96.  
  97. 	do {
  98. 		if (compute(suite, operations) == target) {
  99. 			display(suite, operations, target);
  100. 		}
  101. 	} while (next(operations));
  102. }
  103.  
  104. int main() {
  105. 	std::vector<int> vec{1, 2, 3, 4, 5, 6, 7, 8, 9};
  106. 	compute(vec, 100);
  107. 	return 0;
  108. }
Success #stdin #stdout 0s 3276KB
comments (?)
stdin 
Standard input is empty
stdout 
123 - 45 - 67 + 89 = 100
12 - 3 - 4 + 5 - 6 + 7 + 89 = 100
12 + 3 + 4 + 5 - 6 - 7 + 89 = 100
123 + 4 - 5 + 67 - 89 = 100
1 + 2 + 3 - 4 + 5 + 6 + 78 + 9 = 100
12 + 3 - 4 + 5 + 67 + 8 + 9 = 100
1 + 23 - 4 + 56 + 7 + 8 + 9 = 100
1 + 2 + 34 - 5 + 67 - 8 + 9 = 100
1 + 23 - 4 + 5 + 6 + 78 - 9 = 100
123 + 45 - 67 + 8 - 9 = 100
123 - 4 - 5 - 6 - 7 + 8 - 9 = 100
https://ideone.com/cPT5Pc
language:
C++14 (gcc 8.3)
created:
10 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!