#include <bits/stdc++.h>
#define fr(i, a, b) for (int i = (a); i <= (b); ++i)
#define rf(i, a, b) for (int i = (a); i >= (b); --i)
#define fe(x, y) for (auto& x : y)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define all(x) (x).begin(), (x).end()
#define pw(x) (1LL << (x))
#define sz(x) (int)(x).size()
using namespace std;
mt19937_64 rng(228);
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define fbo find_by_order
#define ook order_of_key
template <typename T>
bool umn(T& a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T>
bool umx(T& a, T b) { return a < b ? a = b, 1 : 0; }
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template <typename T>
using ve = vector<T>;
const int N = 1e5 + 5;
string s;
ve<int> v[26];
ld dp[pw(16)];
int pref[N][16];
int suff[N][16];
ve<int> p;
ld calc(int mask, int i) {
ld sum = 0;
int l = 0;
// cout << "WTF " << i << "\n";
fe (x, v[i]) {
ld val1 = 0;
ld val2 = 0;
fr (i, 0, 15) {
if (mask & pw(i)) {
val1 += pref[x][p[i]];
val2 += suff[x][p[i]];
}
}
val1 += 0.5 * l;
val2 += 0.5 * (sz(v[i]) - 1 - l);
// cout << val1 << " " << val2 << "\n";
sum += min(val1, val2);
l++;
}
return sum;
}
int main() {
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#else
ios::sync_with_stdio(0);
cin.tie(0);
#endif
cin >> s;
// fr (i, 1, 899) s.pb('A');
fr (i, 0, sz(s) - 1) {
v[s[i] - 'A'].pb(i);
}
fr (i, 0, sz(s) - 1) {
pref[i][s[i] - 'A'] = 1;
if (i > 0) {
fr (j, 0, 15) {
pref[i][j] += pref[i - 1][j];
}
}
}
rf (i, sz(s) - 1, 0) {
suff[i][s[i] - 'A'] = 1;
if (i + 1 < sz(s)) {
fr (j, 0, 15) {
suff[i][j] += suff[i + 1][j];
}
}
}
fr (i, 0, 25) {
if (sz(v[i])) {
p.pb(i);
}
}
// fe (x, p) {
// cout << char(x + 'A') << "\n";
// }
//
// cout << calc(1, 1) << "\n";
// return 0;
fr (mask, 0, pw(sz(p)) - 1) {
dp[mask] = 1e18;
}
dp[0] = 0;
fr (mask, 0, pw(sz(p)) - 1) {
fr (i, 0, sz(p) - 1) {
if (!(mask & pw(i))) {
umn(dp[mask | pw(i)], dp[mask] + calc(mask, p[i]));
}
}
}
cout << dp[pw(sz(p)) - 1] << "\n";
// ld res = 1e18;
// ve<bool> act(sz(s));
// ve<int> P(sz(s));
// ve<int> S(sz(s));
// ve<int> SS(sz(s));
// ve<int> PP(sz(s));
//
// do {
// fill(all(act), 0);
// fill(all(P), 0);
// fill(all(PP), 0);
// fill(all(S), 0);
// fill(all(SS), 0);
// ld ans = 0;
//
// fe (x, p) {
//
// fr (i, 0, sz(v[x]) - 1) {
// PP[i] = P[v[x][i]];
// if (i > 0) PP[i] += PP[i - 1];
// }
// rf (i, sz(v[x]) - 1, 0) {
// SS[i] = S[v[x][i]];
// if (i + 1 < sz(v[x])) SS[i] += SS[i + 1];
// }
//
// ld best = 1e18;
////
//// {
//// ld now = 0;
//// fr (i, 0, sz(v[x]) - 1) {
//// ld val1 = P[v[x][i]] + i * 0.5;
//// ld val2 = S[v[x][i]] + (sz(v[x]) - 1 - i) * 0.5;
//// now += min(val1, val2);
//// }
//// umn(best, now);
//// }
//
// fr (pref, 0, sz(v[x])) {
// ld now = 0;
// if (pref - 1 >= 0) now += PP[pref - 1];
// if (pref < sz(v[x])) now += SS[pref];
//// fr (i, 0, pref - 1) {
//// now += P[v[x][i]];
//// }
//// fr (i, pref, sz(v[x]) - 1) {
//// now += S[v[x][i]];
//// }
//
// now += ld(0.5) * pref * (pref - 1) / 2;
// int suff = sz(v[x]) - pref;
// now += ld(0.5) * suff * (suff - 1) / 2;
//
//// if (abs(now - 2) <= 1e-7) {
//// cout << pref << " " << suff << "\n";
//// }
//
// umn(best, now);
// }
// fe (cur, v[x]) act[cur] = 1;
//
// fr (i, 0, sz(s) - 1) {
// P[i] = act[i];
// if (i > 0) P[i] += P[i - 1];
// }
// rf (i, sz(s) - 1, 0) {
// S[i] = act[i];
// if (i + 1 < sz(s)) {
// S[i] += S[i + 1];
// }
// }
//// cout << "Add " << best << " " << char(x + 'A') << "\n";
// ans += best;
// }
//// cout << "\n";
// umn(res, ans);
// } while (next_permutation(all(p)));
//
// cout << fixed << setprecision(10) << res << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
388 KB |
1st numbers differ - expected: '100800.5000000000', found: '100800.0000000000', error = '0.0000049603' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
| 2 |
Correct |
0 ms |
340 KB |
found '1225.0000000000', expected '1225.0000000000', error '0.0000000000' |
| 3 |
Correct |
1 ms |
340 KB |
found '1023.0000000000', expected '1023.0000000000', error '0.0000000000' |
| 4 |
Correct |
1 ms |
340 KB |
found '294.0000000000', expected '294.0000000000', error '0.0000000000' |
| 5 |
Correct |
1 ms |
340 KB |
found '1087.0000000000', expected '1087.0000000000', error '0.0000000000' |
| 6 |
Correct |
1 ms |
340 KB |
found '1.5000000000', expected '1.5000000000', error '0.0000000000' |
| 7 |
Correct |
1 ms |
340 KB |
found '703.0000000000', expected '703.0000000000', error '0.0000000000' |
| 8 |
Correct |
1 ms |
340 KB |
found '55.5000000000', expected '55.5000000000', error '0.0000000000' |
| 9 |
Correct |
1 ms |
340 KB |
found '56.0000000000', expected '56.0000000000', error '0.0000000000' |
| 10 |
Correct |
0 ms |
340 KB |
found '45.0000000000', expected '45.0000000000', error '0.0000000000' |
| 11 |
Correct |
1 ms |
352 KB |
found '66.5000000000', expected '66.5000000000', error '0.0000000000' |
| 12 |
Correct |
1 ms |
340 KB |
found '67.0000000000', expected '67.0000000000', error '0.0000000000' |
| 13 |
Correct |
1 ms |
340 KB |
found '66.0000000000', expected '66.0000000000', error '0.0000000000' |
| 14 |
Correct |
0 ms |
340 KB |
found '47.0000000000', expected '47.0000000000', error '0.0000000000' |
| 15 |
Correct |
0 ms |
340 KB |
found '50.0000000000', expected '50.0000000000', error '0.0000000000' |
| 16 |
Correct |
0 ms |
340 KB |
found '49.0000000000', expected '49.0000000000', error '0.0000000000' |
| 17 |
Correct |
0 ms |
340 KB |
found '57.0000000000', expected '57.0000000000', error '0.0000000000' |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
| 2 |
Correct |
0 ms |
340 KB |
found '1225.0000000000', expected '1225.0000000000', error '0.0000000000' |
| 3 |
Correct |
1 ms |
340 KB |
found '1023.0000000000', expected '1023.0000000000', error '0.0000000000' |
| 4 |
Correct |
1 ms |
340 KB |
found '294.0000000000', expected '294.0000000000', error '0.0000000000' |
| 5 |
Correct |
1 ms |
340 KB |
found '1087.0000000000', expected '1087.0000000000', error '0.0000000000' |
| 6 |
Correct |
1 ms |
340 KB |
found '1.5000000000', expected '1.5000000000', error '0.0000000000' |
| 7 |
Correct |
1 ms |
340 KB |
found '703.0000000000', expected '703.0000000000', error '0.0000000000' |
| 8 |
Correct |
1 ms |
340 KB |
found '55.5000000000', expected '55.5000000000', error '0.0000000000' |
| 9 |
Correct |
1 ms |
340 KB |
found '56.0000000000', expected '56.0000000000', error '0.0000000000' |
| 10 |
Correct |
0 ms |
340 KB |
found '45.0000000000', expected '45.0000000000', error '0.0000000000' |
| 11 |
Correct |
1 ms |
352 KB |
found '66.5000000000', expected '66.5000000000', error '0.0000000000' |
| 12 |
Correct |
1 ms |
340 KB |
found '67.0000000000', expected '67.0000000000', error '0.0000000000' |
| 13 |
Correct |
1 ms |
340 KB |
found '66.0000000000', expected '66.0000000000', error '0.0000000000' |
| 14 |
Correct |
0 ms |
340 KB |
found '47.0000000000', expected '47.0000000000', error '0.0000000000' |
| 15 |
Correct |
0 ms |
340 KB |
found '50.0000000000', expected '50.0000000000', error '0.0000000000' |
| 16 |
Correct |
0 ms |
340 KB |
found '49.0000000000', expected '49.0000000000', error '0.0000000000' |
| 17 |
Correct |
0 ms |
340 KB |
found '57.0000000000', expected '57.0000000000', error '0.0000000000' |
| 18 |
Correct |
0 ms |
340 KB |
found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
| 19 |
Correct |
1 ms |
340 KB |
found '1225.0000000000', expected '1225.0000000000', error '0.0000000000' |
| 20 |
Correct |
1 ms |
340 KB |
found '1023.0000000000', expected '1023.0000000000', error '0.0000000000' |
| 21 |
Correct |
1 ms |
340 KB |
found '294.0000000000', expected '294.0000000000', error '0.0000000000' |
| 22 |
Correct |
1 ms |
340 KB |
found '1087.0000000000', expected '1087.0000000000', error '0.0000000000' |
| 23 |
Correct |
0 ms |
340 KB |
found '1.5000000000', expected '1.5000000000', error '0.0000000000' |
| 24 |
Correct |
1 ms |
340 KB |
found '703.0000000000', expected '703.0000000000', error '0.0000000000' |
| 25 |
Correct |
1 ms |
340 KB |
found '55.5000000000', expected '55.5000000000', error '0.0000000000' |
| 26 |
Correct |
1 ms |
340 KB |
found '56.0000000000', expected '56.0000000000', error '0.0000000000' |
| 27 |
Correct |
1 ms |
340 KB |
found '45.0000000000', expected '45.0000000000', error '0.0000000000' |
| 28 |
Correct |
1 ms |
340 KB |
found '66.5000000000', expected '66.5000000000', error '0.0000000000' |
| 29 |
Correct |
1 ms |
340 KB |
found '67.0000000000', expected '67.0000000000', error '0.0000000000' |
| 30 |
Correct |
1 ms |
340 KB |
found '66.0000000000', expected '66.0000000000', error '0.0000000000' |
| 31 |
Correct |
1 ms |
340 KB |
found '47.0000000000', expected '47.0000000000', error '0.0000000000' |
| 32 |
Correct |
1 ms |
340 KB |
found '50.0000000000', expected '50.0000000000', error '0.0000000000' |
| 33 |
Correct |
0 ms |
340 KB |
found '49.0000000000', expected '49.0000000000', error '0.0000000000' |
| 34 |
Correct |
1 ms |
340 KB |
found '57.0000000000', expected '57.0000000000', error '0.0000000000' |
| 35 |
Correct |
1 ms |
1620 KB |
found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000' |
| 36 |
Incorrect |
2 ms |
1620 KB |
1st numbers differ - expected: '12495000.5000000000', found: '12495000.0000000000', error = '0.0000000400' |
| 37 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
388 KB |
1st numbers differ - expected: '100800.5000000000', found: '100800.0000000000', error = '0.0000049603' |
| 2 |
Halted |
0 ms |
0 KB |
- |
