Advertisement
tepyotin2

Sleepy Cow Herding

Oct 10th, 2023
89
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.94 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. string info(vector<int> &herd, int &curr_cow, int &farthest_cow){
  4.     string info = ", curr_cow: "  + to_string(curr_cow)  +"#H:"+to_string(herd[curr_cow])
  5.          + ", farthest_cow: "+to_string(farthest_cow)+"#H: "+to_string(herd[farthest_cow]);
  6.     return info;
  7. }
  8. int main() {
  9.     freopen("herding.in", "r", stdin);
  10.    
  11.     int n;
  12.     cin >> n;
  13.     vector<int> herd(n);
  14.     for (int i = 0; i < n; ++i) {
  15.         cin >> herd[i];
  16.     }
  17.     sort(herd.begin(), herd.end());
  18.     int min_moves = INT32_MAX;
  19.     if (herd[n - 2] - herd[0] == n - 2 && herd[n - 1] - herd[n - 2] > 2) {
  20.         min_moves = 2;
  21.         cout << "min_moves#1" << endl;
  22.     } else if (herd[n - 1] - herd[1] == n - 2 && herd[1] - herd[0] > 2) {
  23.         min_moves = 2;
  24.         cout << "min_moves#2" << endl;
  25.     } else {
  26.         // min is the patch of length n that has the least # of gaps
  27.         int farthest_cow = 0;
  28.         for (int curr_cow = 0; curr_cow < n; ++curr_cow) {
  29.             cout << "[for] " +info(herd, curr_cow, farthest_cow)  << endl;
  30.             while (
  31.                 farthest_cow + 1 < n
  32.                 && herd[farthest_cow + 1] - herd[curr_cow] < n
  33.             ) {
  34.                 farthest_cow++;
  35.                 cout << "[while] " +info(herd, curr_cow, farthest_cow)  << endl;
  36.             }
  37.             min_moves = min(min_moves, n - (farthest_cow - curr_cow + 1));
  38.             cout << "min_moves: "+to_string(min_moves) << endl;
  39.         }
  40.     }
  41.     // calculate the number of empty cells
  42.     int gap_num = 0;
  43.     for (int i = 1; i < n; i++) {
  44.         gap_num += herd[i] - herd[i - 1] - 1;
  45.     }
  46.     // max is the maximum of the total gap minus either the first or last gap
  47.     int max_moves = max(
  48.         gap_num - (herd[1] - herd[0] - 1),
  49.         gap_num - (herd[n - 1] - herd[n - 2] - 1)
  50.     );
  51.     freopen("herding.out", "w", stdout);
  52.     cout << min_moves << '\n' << max_moves << endl;
  53. }
  54.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement