fork download
copy 
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <vector>
  4. #include <string>
  5. #include <sstream>
  6. #include <random>
  7.  
  8. using std::cout;
  9. using std::cin;
  10. using std::vector;
  11. using std::endl;
  12.  
  13. int MinValueOf(int a, int b)
  14. {
  15.     return (a < b) ? a : b;
  16. }
  17. int BuyingApple(vector<int> PriceaTag, int Friends, int KilogramsToBuy)
  18. {
  19.     vector<vector<int>> Table(Friends + 1, vector<int>(KilogramsToBuy + 1, 0));
  20.     for (int i = 1; i <= Friends; i++)
  21.     {
  22.         for (int j = 0; j <= i; j++)
  23.         {
  24.             Table.at(i).at(j) = INT32_MAX;
  25.             if (j == 0)
  26.                 Table[i][0] = 0;
  27.             else if (PriceaTag[j] > 0)
  28.                 Table[i][j] = MinValueOf(Table[i][j], Table.at(i - 1).at(i - j) + PriceaTag.at(j));
  29.         }
  30.     }
  31.     return (Table[Friends][KilogramsToBuy] == 0) ? -1 : Table[Friends][KilogramsToBuy];
  32. }
  33.  
  34. int main()
  35. {
  36.     std::random_device rd;
  37.     std::mt19937 gen(rd());
  38.     std::uniform_int_distribution<> distrib(-1, 1000);
  39.     std::uniform_int_distribution<> distribNK(1, 100);
  40.     std::uniform_int_distribution<> distribPos(1, 1000);
  41.     int Friends;
  42.     int Kilogram;
  43.     vector<int> Price;
  44.     while (true)
  45.     {
  46.         try
  47.         {
  48.             Friends = distribNK(gen);
  49.             Kilogram = distribNK(gen);
  50.             Price = std::vector<int>(Kilogram + 1, 0);
  51.             std::generate(Price.begin() + 1, Price.end(), [&]() { return distrib(gen); });
  52.             std::transform(Price.begin() + 1, Price.end(), Price.begin() + 1, [&](int n)
  53.                 { if (n == 0) return distribPos(gen);  return n; });
  54.             std::cout << BuyingApple(Price, Friends, Price.size() - 1) << std::endl;
  55.         }
  56.     	catch (std::out_of_range& rError)
  57.     	{
  58.     		std::cout << rError.what() << "\n";
  59.     		std::cout << "The following tests cause an issue:\n\n";
  60.             std::cout << "Friends = " << Friends << "\nK = " << Kilogram << "\nPrice data:\n";
  61.             int i = 0;
  62.             for (auto p : Price)
  63.             {
  64.                 std::cout << "[" << i << "]: " << p << "\n";
  65.                 ++i;
  66.             }
  67.             return 0;
  68.     	}
  69.     }
  70. }
  71.  
Success #stdin #stdout 0s 4344KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
-1
-1
vector::_M_range_check: __n (which is 33) >= this->size() (which is 33)
The following tests cause an issue:

Friends = 98
K = 32
Price data:
[0]: 0
[1]: 429
[2]: 119
[3]: 106
[4]: 63
[5]: 545
[6]: 564
[7]: 433
[8]: 442
[9]: 891
[10]: 740
[11]: 711
[12]: 280
[13]: 349
[14]: 954
[15]: 612
[16]: 165
[17]: 126
[18]: 206
[19]: 753
[20]: 889
[21]: 958
[22]: 667
[23]: 171
[24]: 447
[25]: 781
[26]: 644
[27]: 52
[28]: 497
[29]: 350
[30]: 221
[31]: 548
[32]: 650
https://ideone.com/qijxhC
language:
C++14 (gcc 8.3)
created:
4 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!