Day 9: Uping the problem rating

Disclaimer:

I am a beginner in competitive programming, and this is me documenting my learnings. So, anything I say is just what I think at the moment and should not be taken as hard truths.

Problem 1: Taxi

using vi = vector<int>;

#define all(x) begin(x), end(x)
#define forn(i, n) for(int i = 0; i < n; i++)

main() {
  int n;
  cin >> n;
  vi v(5, 0);
  forn(_, n) {
    int g;
    cin >> g;
    v[g]++;
  }
  // every four will require one car
  int four = v[4]; 
  // every three will require one car
  int three = v[3];
  // it can take groups of one too
  v[1] -= min(v[1], v[3]);
  // a car can take two groups of two and change
  int two = v[2]/2 + v[2]%2;
  int rem = v[2]%2;
  v[1] -= min(v[1], rem*2);
  int one = v[1]/4 + (v[1]%4 != 0);

  int ans = one + two + three + four;
  cout << ans;
}

The above solution was the first accepted solution I could come up with.

This one is more cleaner [Greedy Approach]

using vi = vector<int>;

#define forn(i, n) for(int i = 0; i < n; i++)
#define all(v) begin(v), end(v)
#define endl '\n'

main() {
  int n;
  cin >> n;
  vi v(n);
  for(auto& e: v) cin >> e;
  sort(all(v));
  int i = 0, j = n-1;
  int ans = 0;
  while(i <= j) {
    int curr = v[j];
    while(i < j && curr+v[i] <= 4) {
      curr += v[i++];
    }
    j--;
    ans++;
  }
  cout << ans;
}

Problem 2: Interesting Drink

I was initially afraid to solve the problem seeing dp in the tags. But then I hid the tags, and went for the
problem. lol.

Just check the number of places whose booze price is less than or equal to the price the man can pay.
Binary Search.

using vi = vector<int>;

#define forn(i, n) for(int i = 0; i < n; i++)
#define all(v) begin(v), end(v)
#define endl '\n'

main() {
  int n;
  cin >> n;
  vi v(n);
  for(auto& e: v) cin >> e;
  sort(all(v));
  int q;
  cin >> q;
  forn(_, q) {
    int p;
    cin >> p;
    auto it = upper_bound(all(v), p);
    cout << distance(begin(v), it) << endl;
  }
}

Algorithm

We didn't learn any new algorithm today.