1620D - Exact Change - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;

const int INF=1e9;

int solve(vector<int> a, vector<int> x) {
  int ret = 0;
  for (int ai: a) {
    for (int xi: x) {
      if (ai>=xi and (ai-xi)%3==0) {
        ai -= xi;
      }
    }
    if (ai%3==0) {
      ret = max(ret, ai/3);
    }
    else {
      return INF;
    }
  }
  return ret;
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0);
  
  int tc;  cin >> tc;
  while (tc--) {
    int n;  cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
      cin >> a[i];
    }

    int ans = INF;
    ans = min(ans, solve(a, {}));
    ans = min(ans, solve(a, {1})+1);
    ans = min(ans, solve(a, {2})+1);
    ans = min(ans, solve(a, {3, 2, 1})+2);  // 3=2+1
    ans = min(ans, solve(a, {4, 2, 2})+2);  // 4=2+2

    cout << ans << "\n";
  }

  return 0;
}