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.
A number being divisible by is absurdly local: for length at least , only the last two digits matter. So don't try to reason about whole subsequences like it's a mystery novel.
Since you may select any subsequence, a single digit 4 already kills beauty. Also, any ordered pair of digits forming a two-digit multiple of kills it.
Among digits , the bad two-digit pairs are exactly Since 4 cannot remain anyway, the real constraints become: avoid subsequences 12 and 32.
Avoiding both 12 and 32 means no 2 may appear after a 1 or 3. Therefore every beautiful remaining string has the form
So keep the longest subsequence of the form Try every split point: keep all 2s before it and all 1/3s after it. If the best kept length is , the answer is .
A selected subsequence forms some number. For divisibility by :
4;So a string is not beautiful iff it contains either digit 4, or one of the bad ordered pairs as a subsequence.
For digits from to , the two-digit multiples of are:
Since a remaining 4 is already illegal, all 4s must be deleted. After that, only digits remain, and the only forbidden subsequences are:
Avoiding 12 means no 1 can appear before a later 2.
Avoiding 32 means no 3 can appear before a later 2.
Together, this says: once we keep a 1 or 3, we can never keep another 2 after it. So every beautiful subsequence must look like:
That is: some number of 2s, followed by any mix of 1s and 3s. Nice. The monster is now a kitten.
We want minimum deletions, so equivalently maximize the length of a beautiful subsequence.
Choose a split point. Keep:
2 before or at the split;1 or 3 after the split;4s.For a split , the kept length is:
Take the maximum over all split points. If this maximum is , then the answer is:
We can compute this in one scan: start with all 1/3s in the suffix, then move the split left-to-right while maintaining prefix 2s and suffix 1/3s.
For each test case, we do work and extra memory.
Across all test cases:
which easily fits the limits.
#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--) {
string s;
cin >> s;
int suffix13 = 0;
for (char c : s) {
if (c == '1' || c == '3') suffix13++;
}
int prefix2 = 0;
int best = suffix13; // split before the first character
for (char c : s) {
if (c == '1' || c == '3') {
suffix13--;
} else if (c == '2') {
prefix2++;
}
// split after this character
best = max(best, prefix2 + suffix13);
}
cout << (int)s.size() - best << '\n';
}
}#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--) {
string s;
cin >> s;
int suffix13 = 0;
for (char c : s) {
if (c == '1' || c == '3') suffix13++;
}
int prefix2 = 0;
int best = suffix13; // split before the first character
for (char c : s) {
if (c == '1' || c == '3') {
suffix13--;
} else if (c == '2') {
prefix2++;
}
// split after this character
best = max(best, prefix2 + suffix13);
}
cout << (int)s.size() - best << '\n';
}
}