lonsomehell

Untitled

Feb 2nd, 2018
147
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.99 KB | None | 0 0
  1. #include <iostream>
  2. #include <string>
  3. #include <algorithm>
  4. #include <stdexcept>
  5.  
  6.  
  7. using namespace std;
  8.  
  9. template <typename T> //queue type to store group
  10. class queue
  11. {
  12. private:
  13.  
  14.     struct Node {
  15.         T     value;
  16.         Node *next;
  17.  
  18.         Node(T _value) : value(_value), next(NULL) {}
  19.     };
  20.  
  21.     Node *front;
  22.     Node *back;
  23.  
  24. public:
  25.     queue() : front(NULL), back(NULL) {}
  26.  
  27.     ~queue() {
  28.         while (front != NULL)
  29.             dequeue();
  30.     }
  31.  
  32.     void enqueue(T _value) {
  33.         Node *newNode = new Node(_value);
  34.  
  35.         if (front == NULL)
  36.             front = newNode;
  37.         else
  38.             back->next = newNode;
  39.  
  40.         back = newNode;
  41.     }
  42.  
  43.     T dequeue() {
  44.         if (front == NULL)
  45.             throw std::underflow_error("Nothing to dequeue");
  46.  
  47.         Node *temp = front;
  48.         T     result = front->value;
  49.  
  50.         front = front->next;
  51.         delete temp;
  52.  
  53.         return result;
  54.     }
  55.  
  56.     T Front() {
  57.         return front->value;
  58.     }
  59.  
  60.     T Back() {
  61.         return back->value;
  62.     }
  63. };
  64.  
  65.  
  66. int main()
  67. {
  68.     long long nbPlaces;
  69.     long long nbTours;
  70.     int nbGroupes;
  71.     cin >> nbPlaces >> nbTours >> nbGroupes; cin.ignore();
  72.  
  73.     int groupes [nbGroupes];
  74.     for (int i = 0; i < nbGroupes; i++)
  75.     {
  76.         cin >> groupes[i] ;  cin.ignore();
  77.     }
  78.  
  79.     int gains [nbGroupes];
  80.     int groupeSuivant [nbGroupes];
  81.  
  82.     for (int i = 0; i < nbGroupes; i++)
  83.     {
  84.         int currentIndex = i;
  85.         gains[i] = 0;
  86.         while (true)
  87.         {
  88.             int nextGp = groupes[currentIndex];
  89.             if (gains[i] + nextGp > nbPlaces)
  90.             {
  91.                 break;
  92.             }
  93.             gains[i] += nextGp;
  94.  
  95.             currentIndex++;
  96.             if (currentIndex == nbGroupes)
  97.             {
  98.                 currentIndex = 0;
  99.             }
  100.  
  101.             if (currentIndex == i)
  102.             {
  103.                 break;
  104.             }
  105.         }
  106.         groupeSuivant[i] = currentIndex;
  107.     }
  108.  
  109.     long long total = 0;
  110.     int currentIndex = 0;
  111.  
  112.     for (int i = 0; i < nbTours; i++)
  113.     {
  114.         total += gains[currentIndex];
  115.         currentIndex = groupeSuivant[currentIndex];
  116.     }
  117.  
  118.  
  119.     std::wcout << total << std::endl;
  120. }
Advertisement
Add Comment
Please, Sign In to add comment