Advertisement
Guest User

Untitled

a guest
Oct 21st, 2017
76
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.81 KB | None | 0 0
  1. #include <iostream>
  2. #include <iomanip>
  3. #include <fstream>
  4. #include <vector>
  5. #include <cmath>
  6.  
  7. using namespace std;
  8.  
  9. bool check(vector<pair<double, int>> vec, int l, double current_time) {
  10.     vector<pair<double, int>> first_vec = vec;
  11.     vector<pair<double, int>> second_vec = vec;
  12.     bool started = false;
  13.     double first_s = 0;
  14.     double second_s = 0;
  15.  
  16.     while (first_vec.size() && second_vec.size()) {
  17.         if (started) {
  18.             if (first_vec[0].first < second_vec[0].first) {
  19.                 first_s += first_vec[0].first * first_vec[0].second;
  20.                 second_s += first_vec[0].first * second_vec[0].second;
  21.                 second_vec[0].first -= first_vec[0].first;
  22.                 first_vec.erase(first_vec.begin());
  23.  
  24.                 if (first_s - second_s < l) {
  25.                     return false;
  26.                 }
  27.             } else {
  28.                 first_s += second_vec[0].first * first_vec[0].second;
  29.                 second_s += second_vec[0].first * second_vec[0].second;
  30.                 first_vec[0].first -= second_vec[0].first;
  31.                 second_vec.erase(second_vec.begin());
  32.  
  33.                 if (first_s - second_s < l) {
  34.                     return false;
  35.                 }
  36.             }
  37.         } else {
  38.             if (first_vec[0].first < current_time) {
  39.                 first_s += first_vec[0].first * first_vec[0].second;
  40.                 current_time -= first_vec[0].first;
  41.                 first_vec.erase(first_vec.begin());
  42.             } else {
  43.                 first_s += current_time * first_vec[0].second;
  44.                 first_vec[0].first -= current_time;
  45.                 started = true;
  46.                 current_time = 0;
  47.  
  48.                 if (first_s - second_s < l) {
  49.                     return false;
  50.                 }
  51.             }
  52.         }
  53.     }
  54.  
  55.     return first_s - second_s >= l;
  56. }
  57.  
  58. inline double round(double number) {
  59.     return floor(number * 1000 + 0.5) / 1000;
  60. }
  61.  
  62. int main(int argc, char **argv) {
  63.     ifstream fin("trains.in");
  64.  
  65.     int l, n;
  66.     double max_time = 0;
  67.  
  68.     fin >> l >> n;
  69.     vector<pair<double, int>> vec(n);
  70.  
  71.     for (int i = 0; i < n; i++) {
  72.         fin >> vec[i].first >> vec[i].second;
  73.         max_time += vec[i].first;
  74.     }
  75.  
  76.     fin.close();
  77.  
  78.     double lower_bound = 0;
  79.     double upper_bound = max_time;
  80.     double current_time;
  81.     double previous = current_time;
  82.  
  83.     while (round(upper_bound - lower_bound) != 0) {
  84.         current_time = lower_bound + (upper_bound - lower_bound) / 2;
  85.  
  86.         if (check(vec, l, current_time)) {
  87.             upper_bound = current_time;
  88.         } else {
  89.             lower_bound = current_time;
  90.         }
  91.  
  92.         previous = current_time;
  93.     }
  94.  
  95.     ofstream fout("trains.out");
  96.     fout << round(current_time);
  97.     fout.close();
  98.  
  99.     return 0;
  100. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement