fork(4) download
copy 
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <queue>
  4. #include <vector>
  5.  
  6. // naive approach
  7.  
  8. int waitingTimeSim(const std::vector<int> &tickets, int p)
  9. {
  10.   // setup sim. model
  11.   std::queue<std::pair<int, bool> > people;
  12.   for (int i = 0, n = (int)tickets.size(); i < n; ++i) {
  13.     people.push(std::make_pair(tickets[i], i == p));
  14.   }
  15.   // simulation
  16.   int tP = 0;
  17.   for (;;) {
  18.     std::pair<int, bool> person = people.front();
  19.     people.pop();
  20.     --person.first; ++tP; // by ticket
  21.     if (!person.first) { // if person is done
  22.       if (person.second) return tP; // It's Jesse -> terminate
  23.     } else people.push(person);
  24.   }
  25. }
  26.  
  27. // analytical approach
  28.  
  29. int waitingTime(const std::vector<int> &tickets, int p)
  30. {
  31.   int tP = 0, ticketsP = tickets[p];
  32.   for (int i = 0, n = (int)tickets.size(); i < n; ++i) {
  33.     tP += std::min(tickets[i], ticketsP - (i > p));
  34.     // i > p -> people after jesse -> decr. by 1
  35.   }
  36.   return tP;
  37. }
  38.  
  39. int main()
  40. {
  41.   { std::vector<int> tickets{ 2, 6, 3, 4, 5 };
  42.     for (int p = 0, n = tickets.size(); p < n; ++p) {
  43.       std::cout << "tickets{ 2, 6, 3, 4, 5 }, p = " << p << std::endl;
  44.       int tS = waitingTimeSim(tickets, p);
  45.       std::cout << "simulated t: " << tS << std::endl;
  46.       int t = waitingTime(tickets, p);
  47.       std::cout << "computed t:  " << t << std::endl;
  48.     }
  49.   }
  50.   { std::vector<int> tickets{ 5, 5, 2, 3 };
  51.     for (int p = 0, n = tickets.size(); p < n; ++p) {
  52.       std::cout << "tickets{ 5, 5, 2, 3 }, p = " << p << std::endl;
  53.       int tS = waitingTimeSim(tickets, p);
  54.       std::cout << "simulated t: " << tS << std::endl;
  55.       int t = waitingTime(tickets, p);
  56.       std::cout << "computed t:  " << t << std::endl;
  57.     }
  58.   }
  59.   return 0;
  60. }
Success #stdin #stdout 0s 16072KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
tickets{ 2, 6, 3, 4, 5 }, p = 0
simulated t: 6
computed t:  6
tickets{ 2, 6, 3, 4, 5 }, p = 1
simulated t: 20
computed t:  20
tickets{ 2, 6, 3, 4, 5 }, p = 2
simulated t: 12
computed t:  12
tickets{ 2, 6, 3, 4, 5 }, p = 3
simulated t: 16
computed t:  16
tickets{ 2, 6, 3, 4, 5 }, p = 4
simulated t: 19
computed t:  19
tickets{ 5, 5, 2, 3 }, p = 0
simulated t: 14
computed t:  14
tickets{ 5, 5, 2, 3 }, p = 1
simulated t: 15
computed t:  15
tickets{ 5, 5, 2, 3 }, p = 2
simulated t: 7
computed t:  7
tickets{ 5, 5, 2, 3 }, p = 3
simulated t: 11
computed t:  11
https://ideone.com/ug7K9V
language:
C++ (gcc 8.3)
created:
7 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!