fork(4) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int const nMax = 20;
  6.  
  7. int n, k[nMax], c[nMax];
  8.  
  9. int answer;
  10.  
  11. void fun (int position, int orc1, int orc2, int orc3, int current) {
  12. 	if (current > answer) {
  13. 		return;//useless branch
  14. 	}
  15. 	if (position == n) {
  16. 		answer = min(answer, current);
  17. 		return;//final state
  18. 	}
  19. 	bool fighted = false;
  20. 	if (orc1 + orc2 + orc3 >= k[position]) {
  21. 		int enemy = k[position];
  22. 		int toFight = min(enemy, orc3);
  23. 		orc3 -= toFight;
  24. 		enemy -= toFight;
  25. 		toFight = min(enemy, orc2);
  26. 		orc2 -= toFight;
  27. 		enemy -= toFight;
  28. 		toFight = min(enemy, orc1);
  29. 		orc1 -= toFight;
  30. 		enemy -= toFight;
  31. 		fun(position + 1, 0, orc1, orc2, current);
  32. 		fighted = true;
  33. 	}
  34. 	//pay
  35. 	fun(position + 1, orc1, orc2, orc3, current + c[position]);
  36. 	//hire
  37. 	fun(position + 1, orc1 + k[position], orc2, orc3, current + c[position] + c[position]);
  38. 	//fight
  39. 	if (!fighted && orc1 + orc2 + orc3 >= k[position]) {
  40. 		int enemy = k[position];
  41. 		int toFight = min(enemy, orc3);
  42. 		orc3 -= toFight;
  43. 		enemy -= toFight;
  44. 		toFight = min(enemy, orc2);
  45. 		orc2 -= toFight;
  46. 		enemy -= toFight;
  47. 		toFight = min(enemy, orc1);
  48. 		orc1 -= toFight;
  49. 		enemy -= toFight;
  50. 		fun(position + 1, 0, orc1, orc2, current);
  51. 	}
  52. }
  53.  
  54. int main () {
  55. 	int tests;
  56. 	cin >> tests;
  57. 	for (int t = 1; t <= tests; t++) {
  58. 		cin >> n;
  59. 		for (int i = 0; i < n; i++) {
  60. 			cin >> k[i] >> c[i];
  61. 		}
  62. 		answer = 100000000;
  63. 		fun(0, 0, 0, 0, 0);
  64. 		cout << "#" << t << " " << answer << endl;
  65. 	}
  66.  
  67. 	return 0;
  68. }
Success #stdin #stdout 0.09s 4528KB
comments (?)
stdin
copy 
5
20 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
20 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
20 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
20 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
20 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5
stdout
copy 
#1 20
#2 40
#3 60
#4 80
#5 100
https://ideone.com/qAsgd6
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!