fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <string>
  5.  
  6. #define MAX long(26000000)
  7.  
  8. std::vector<std::vector<long>> dp;
  9.  
  10. struct Currency
  11. {
  12. 	Currency(int v, int w) : value(v), weight(w) { };
  13.  
  14. 	int weight;
  15. 	int value;
  16. };
  17.  
  18. class PBank
  19. {
  20. public:
  21.  
  22. 	bool init_pb_prop();
  23. 	bool init_currencies();
  24. 	bool evaluate();
  25.  
  26. private:
  27. 	int empty_pb, full_pb;
  28. 	std::vector<Currency> currencies;
  29. };
  30.  
  31. int main()
  32. {
  33. 	int n_tests;
  34. 	std::vector<PBank> vpb;
  35.  
  36. 	//std::cout << "Number of tests: ";
  37. 	std::cin >> n_tests;
  38. 	vpb.resize(n_tests);
  39.  
  40. 	for (auto &pb : vpb)
  41. 	{
  42. 		if (pb.init_pb_prop() && pb.init_currencies() && pb.evaluate())
  43. 			continue;
  44. 		else
  45. 			std::cout << "This is impossible.\n";
  46. 	}
  47.  
  48. 	return 0;
  49.  
  50. }
  51.  
  52. bool PBank::init_pb_prop()
  53. {
  54. 	//std::cout << "\nEmpty and full pb weight: ";
  55. 	std::cin >> empty_pb >> full_pb;
  56.  
  57. 	if (empty_pb < 1 || empty_pb >= full_pb || full_pb > 10000)
  58. 		return false;
  59. 	else
  60. 		return true;
  61. }
  62.  
  63. bool PBank::init_currencies()
  64. {
  65. 	int curr_container_size, curr_val, curr_weight;
  66. 	//std::cout << "\nCurrencies number: ";
  67. 	std::cin >> curr_container_size;
  68. 	if (curr_container_size < 1 || curr_container_size > 500)
  69. 		return false;
  70.  
  71. 	for (int j = 0; j < curr_container_size; j++)
  72. 	{
  73. 		//std::cout << "\nCurrency nr " << j + 1 << ": ";
  74. 		std::cin >> curr_val >> curr_weight;
  75. 		if (curr_val < 1 || curr_val > 50000 || curr_weight < 1 || curr_weight > 10000)
  76. 			return false;
  77. 		else
  78. 			currencies.push_back(Currency(curr_val, curr_weight));
  79. 	}
  80.  
  81. 	std::sort(currencies.begin(), currencies.end(),
  82. 		[](const Currency &c1, const Currency &c2)
  83. 	{
  84. 		return (static_cast<double>(c1.value) / c1.weight) > (static_cast<double>(c2.value) / c2.weight);
  85. 	});
  86.  
  87. 	return true;
  88. }
  89.  
  90. bool PBank::evaluate()
  91. {
  92. 	dp.resize(currencies.size(), std::vector<long>(full_pb - empty_pb + 1));
  93.  
  94. 	int div;
  95.  
  96. 	for (int wt = 0; wt <= full_pb - empty_pb; wt++)
  97. 	{
  98. 		for (auto i = 0; i < currencies.size(); i++)
  99. 		{
  100. 			if (wt == 0)
  101. 			{
  102. 				dp[i][wt] = 0;
  103. 				continue;
  104. 			}
  105.  
  106. 			div = wt / currencies[i].weight;
  107.  
  108. 			if (i == 0)
  109. 			{
  110. 				if (wt % currencies[i].weight == 0)
  111. 					dp[i][wt] = div * currencies[i].value;
  112. 				else
  113. 					dp[i][wt] = MAX;
  114. 				continue;
  115. 			}
  116.  
  117. 			if (wt - currencies[i].weight < 0)
  118. 				dp[i][wt] = std::min(dp[i - 1][wt], MAX);
  119. 			else
  120. 			{
  121. 				if (div > 1 && wt >= currencies[i].weight * div)
  122. 					dp[i][wt] = std::min(dp[i - 1][wt], dp[i][wt - currencies[i].weight * div] + currencies[i].value * div);
  123. 				else
  124. 					dp[i][wt] = std::min(dp[i - 1][wt], dp[i][wt - currencies[i].weight] + currencies[i].value);
  125.  
  126. 				dp[i][wt] = std::min(dp[i][wt], dp[i - 1][wt - currencies[i].weight] + currencies[i].value);
  127.  
  128. 			}
  129. 		}
  130. 	}
  131. 	/*
  132. 	for (int c = 0; c < dp.size(); c++)
  133. 	{
  134. 		for (int r = 0; r < dp[c].size(); r++)
  135. 			std::cout << dp[c][r] << "\t";
  136. 		std::cout << std::endl;
  137. 	}
  138. 	*/
  139. 	int last = dp[currencies.size() - 1][full_pb - empty_pb];
  140. 	if (last == MAX)
  141. 		return false;
  142. 	else
  143. 		std::cout << "The minimum amount of money in the piggy-bank is " << last << ".\n";
  144.  
  145. 	return true;
  146. }
  147.  
  148.  
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
4
10 110
2
1 1
30 50
10 110
2
1 1
50 30
1 6
2
10 3
20 4
2 10
2
1 3
2 5
stdout
copy 
The minimum amount of money in the piggy-bank is 60.
The minimum amount of money in the piggy-bank is 100.
This is impossible.
The minimum amount of money in the piggy-bank is 3.
https://ideone.com/X4Yf6K
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

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!