fork(3) download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <cctype>
  5.  
  6. using namespace std;
  7.  
  8. #define UNDEF 1000000000
  9.  
  10. int target;
  11. vector<pair<char, int> > ops;
  12.  
  13. // Apply the inverse of ops[j] to the value i.
  14. int invOp(int i, int j) {
  15. 	switch (ops[j - 1].first) {
  16. 	case '+': return i - ops[j - 1].second;
  17. 	case '-': return i + ops[j - 1].second;
  18. 	case '*':
  19. 		if (i % ops[j - 1].second == 0) {
  20. 			return i / ops[j - 1].second;
  21. 		} else {
  22. 			return UNDEF;
  23. 		}
  24. 	case '/': return i * ops[j - 1].second;
  25. 	default: throw "Yikes!";
  26. 	}
  27. }
  28.  
  29. // _m[0][i][j] == 2 => can compute i using some subset of the first j ops
  30. // _m[0][i][j] == 1 => can't compute i using some subset of the first j ops
  31. // _m[0][i][j] == 0 => don't know yet
  32. // _m[1][i][j] == 2 => can compute -i using some subset of the first j ops
  33. // _m[1][i][j] == 1 => can't compute -i using some subset of the first j ops
  34. // _m[1][i][j] == 0 => don't know yet
  35. vector<vector<unsigned char> > _m[2];
  36.  
  37. bool _isKnown(int i, int j) {
  38. 	bool neg = (i < 0);
  39. 	int ai = (1 - 2 * neg) * i;
  40. 	return ai < _m[neg].size() && j < _m[neg][ai].size() && _m[neg][ai][j] != 0;
  41. }
  42.  
  43. // Get the answer as a bool from _m[][][].  Assumes _isKnown(i, j) == true.
  44. bool _gm(int i, int j) {
  45. 	bool neg = (i < 0);
  46. 	int ai = (1 - 2 * neg) * i;
  47. 	return static_cast<bool>(_m[neg][ai][j] - 1);
  48. }
  49.  
  50. // Set the answer in _m[][][], stretching the vector(s) if necessary.
  51. void _sm(int i, int j, bool x) {
  52. 	bool neg = (i < 0);
  53. 	int ai = (1 - 2 * neg) * i;
  54.  
  55. 	// We may need to grow the vector(s)
  56. 	if (ai >= _m[neg].size()) {
  57. 		_m[neg].resize(ai + 1);		// New values init to 0 ("don't know")
  58. 	}
  59. 	if (j >= _m[neg][ai].size()) {
  60. 		_m[neg][ai].resize(j + 1);		// New values init to 0 ("don't know")
  61. 	}
  62.  
  63. 	_m[neg][ai][j] = static_cast<int>(x) + 1;
  64. }
  65.  
  66. // Can we compute i using some subset of the first j ops?
  67. bool canReach(int i, int j) {
  68. 	if (i == 0) {
  69. 		return true;
  70. 	}
  71.  
  72. 	if (j == 0) {
  73. 		return false;
  74. 	}
  75.  
  76. 	if (!_isKnown(i, j)) {
  77. 		// Compute the new value
  78. 		int invResult = invOp(i, j);
  79. 		_sm(i, j, canReach(i, j - 1) || (invResult != UNDEF && canReach(invResult, j - 1)));
  80. 	}
  81.  
  82. 	return _gm(i, j);
  83. }
  84.  
  85. int main(int argc, char **argv) {
  86. 	// target = atoi(argv[1]);
  87. 	// for (int i = 2; i < argc; ++i) {
  88. 	// 	ops.push_back(make_pair(argv[i][0], atoi(argv[i] + 1)));
  89. 	// }
  90. 	cin >> target;
  91. 	string s;
  92. 	while (cin >> s) {
  93. 		ops.push_back(make_pair(s[0], atoi(s.c_str() + 1)));
  94. 	}
  95. 	// Multiply all values that appear as the operand of a division
  96. 	int d = 1;
  97. 	for (int i = 0; i < ops.size(); ++i) {
  98. 		if (ops[i].first == '/') {
  99. 			d *= abs(ops[i].second);
  100. 		}
  101. 	}
  102.  
  103. 	cout << "Target is " << target << ".  " << ops.size() << " operations to try.\n";
  104.  
  105. 	// Adjust all input values accordingly
  106. 	target *= d;
  107. 	for (int i = 0; i < ops.size(); ++i) {
  108. 		if (ops[i].first == '+' || ops[i].first == '-') {
  109. 			ops[i].second *= d;
  110. 		}
  111. 	}
  112.  
  113. 	// Look for the target.  We can stop looking when d == target, since
  114. 	// then applying no operations gives 0.
  115. 	int nearest;
  116. 	for (int i = 0; i < target; ++i) {
  117. 		if (canReach(target + i, ops.size())) {
  118. 			nearest = target + i;
  119. 			break;
  120. 		}
  121. 		if (canReach(target - i, ops.size())) {
  122. 			nearest = target - i;
  123. 			break;
  124. 		}
  125. 	}
  126.  
  127. 	cout << "Nearest value that we can reach is " << (static_cast<double>(nearest) / d) << ".\n";
  128.  
  129. 	return 0;
  130. }
  131.  
Success #stdin #stdout 0.52s 3464KB
comments (?)
stdin
copy 
10 +4000 +5500 /1000
stdout
copy 
Target is 10.  3 operations to try.
Nearest value that we can reach is 9.5.
https://ideone.com/hU1Rpq
language:
C++14 (gcc 8.3)
created:
9 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!