Search for a command to run...
Progressive hints first, then the full explanation and implementation when you're ready to cash out.
Review status
AI-generated and still unreviewed. Double-check the details before internalizing them.
Hints
Open only as much as you need to keep the solve alive.
The positions of the takeouts are bait. Since you may remove any subsequence, only the counts of values , , and matter.
Every can be removed alone because its sum is already divisible by . Putting a together with other elements never helps maximize the number of operations.
For nonzero values, the useful smallest groups are , , and . Larger groups are usually just several smaller valid groups glued together.
Match as many 's with 's as possible. After that, all remaining numbers are equal, so only triples of them can form operations.
If are the counts, the answer is exactly
Because Marisa can choose an arbitrary subsequence, the order of the array does not matter at all. We only care about the counts:
An operation is just choosing some multiset of these values whose sum is divisible by .
A single already has sum , so each zero can be removed in its own operation.
Also, putting a zero into a larger operation is never useful. If an operation removes some zeros plus other elements, split those zeros off into separate operations. That only increases the count. So zeros contribute exactly
operations.
Now ignore zeros.
A and a together sum to , so every pair gives one operation.
If one type is left over, say only 's remain, then the only way to make a sum divisible by is to take triples:
Similarly,
So the greedy construction is:
This gives
Adding zeros:
Assume . We prove no strategy can beat
Give each a potential of , and each a potential of . Total potential is
Consider any valid non-empty operation using ones and twos. Its sum is divisible by . Such a group must have potential
Indeed, the valid smallest groups are and under this weighting, both costing potential; triples of ones cost even more.
Therefore every operation consumes at least potential, so the number of nonzero operations is at most
Our greedy construction reaches exactly that, so it is optimal. The case is symmetric.
For each test case, we just count values and apply the formula.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
int main() {
setIO();
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
int cnt[3] = {};
for (int i = 0; i < n; i++) {
int x;
cin >> x;
cnt[x]++;
}
int ans = cnt[0] + min(cnt[1], cnt[2]) + abs(cnt[1] - cnt[2]) / 3;
cout << ans << '\n';
}
return 0;
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
int main() {
setIO();
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
int cnt[3] = {};
for (int i = 0; i < n; i++) {
int x;
cin >> x;
cnt[x]++;
}
int ans = cnt[0] + min(cnt[1], cnt[2]) + abs(cnt[1] - cnt[2]) / 3;
cout << ans << '\n';
}
return 0;
}