#include <bits/stdc++.h>
using namespace std;
int c = 0;
vector<int> arr[15];
int lol[15][15][100001];
int pref[100001],suf[100001];
long double dp[(1<<15)];
int sz;
long double ge(long double x){
if(x<=1)return 0;
return (x*(x-1))/4.0;
}
int main(){
string s;cin>>s;
int n = s.size();
map<char,int> x;
int ind = -1;
sz = s.size();
for(auto i:s){
ind++;
if(x[i]==0){
x[i] = ++c;
arr[c-1].push_back(ind);
}else{
arr[x[i]-1].push_back(ind);
}
}
for(int i = 0;i<c;i++){
for(int j = 0;j<c;j++){
int add = 2-(i==j) , cnt = 0;
for(int e = 0;e<n;e++){
pref[e] = (e?pref[e-1]:0)+((x[s[e]]-1)==i?cnt:0);
cnt+=(x[s[e]]-1==j?add:0);
}
cnt = 0;
for(int e = n-1;e>=0;e--){
suf[e] = (e<n-1?suf[e+1]:0)+((x[s[e]]-1)==i?cnt:0);
cnt+=(x[s[e]]-1==j?add:0);
}
for(auto d:arr[i]){
lol[i][j][d] = pref[d]+suf[d+1];
//cout<<lol[i][j][d]<<" "<<i<<" "<<j<<" "<<d<<endl;
}
}
}
for(int mask = (1<<c)-1;mask>=0;mask--){
if(mask==(1<<c)-1){
dp[mask] = 0;
continue;
}
dp[mask] = 1000000000.0;
for(int j = 0;j<c;j++){
if(!(mask&(1<<j))){
int l=0,r=arr[j].size()-1;
while(l<r){
int mid = (l+r)/2;
int an = 0;
for(int i=0;i<c;i++)if(!(mask&(1<<i)))an+=lol[j][i][arr[j][mid+1]]-lol[j][i][arr[j][mid]];
if(an>=0)r = mid;
else l = mid+1;
}
int an = 0;
for(int i=0;i<c;i++)if(!((mask&(1<<i))))an+=lol[j][i][arr[j][l]];
dp[mask] = min(dp[mask],dp[mask^(1<<j)]+an);
}
}
}
cout<<setprecision(4)<<fixed<<dp[0]/2.l<<endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
found '100800.5000000000', expected '100800.5000000000', error '0.0000000000' |
| 2 |
Correct |
1 ms |
2392 KB |
found '0.0000000000', expected '0.0000000000', error '-0.0000000000' |
| 3 |
Correct |
1 ms |
2396 KB |
found '0.0000000000', expected '0.0000000000', error '-0.0000000000' |
| 4 |
Correct |
1 ms |
2392 KB |
found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
| 5 |
Correct |
1 ms |
2596 KB |
found '124002.0000000000', expected '124002.0000000000', error '0.0000000000' |
| 6 |
Incorrect |
3 ms |
3280 KB |
1st numbers differ - expected: '772893586.0000000000', found: '500000000.0000000000', error = '0.3530804123' |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4440 KB |
found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
| 2 |
Correct |
1 ms |
2392 KB |
found '1225.0000000000', expected '1225.0000000000', error '0.0000000000' |
| 3 |
Correct |
4 ms |
31068 KB |
found '1023.0000000000', expected '1023.0000000000', error '0.0000000000' |
| 4 |
Correct |
4 ms |
31068 KB |
found '294.0000000000', expected '294.0000000000', error '0.0000000000' |
| 5 |
Correct |
4 ms |
31064 KB |
found '1087.0000000000', expected '1087.0000000000', error '0.0000000000' |
| 6 |
Correct |
5 ms |
31068 KB |
found '1.5000000000', expected '1.5000000000', error '0.0000000000' |
| 7 |
Correct |
4 ms |
31064 KB |
found '703.0000000000', expected '703.0000000000', error '0.0000000000' |
| 8 |
Incorrect |
3 ms |
24924 KB |
1st numbers differ - expected: '55.5000000000', found: '59.0000000000', error = '0.0630630631' |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4440 KB |
found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
| 2 |
Correct |
1 ms |
2392 KB |
found '1225.0000000000', expected '1225.0000000000', error '0.0000000000' |
| 3 |
Correct |
4 ms |
31068 KB |
found '1023.0000000000', expected '1023.0000000000', error '0.0000000000' |
| 4 |
Correct |
4 ms |
31068 KB |
found '294.0000000000', expected '294.0000000000', error '0.0000000000' |
| 5 |
Correct |
4 ms |
31064 KB |
found '1087.0000000000', expected '1087.0000000000', error '0.0000000000' |
| 6 |
Correct |
5 ms |
31068 KB |
found '1.5000000000', expected '1.5000000000', error '0.0000000000' |
| 7 |
Correct |
4 ms |
31064 KB |
found '703.0000000000', expected '703.0000000000', error '0.0000000000' |
| 8 |
Incorrect |
3 ms |
24924 KB |
1st numbers differ - expected: '55.5000000000', found: '59.0000000000', error = '0.0630630631' |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
found '100800.5000000000', expected '100800.5000000000', error '0.0000000000' |
| 2 |
Correct |
1 ms |
2392 KB |
found '0.0000000000', expected '0.0000000000', error '-0.0000000000' |
| 3 |
Correct |
1 ms |
2396 KB |
found '0.0000000000', expected '0.0000000000', error '-0.0000000000' |
| 4 |
Correct |
1 ms |
2392 KB |
found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
| 5 |
Correct |
1 ms |
2596 KB |
found '124002.0000000000', expected '124002.0000000000', error '0.0000000000' |
| 6 |
Incorrect |
3 ms |
3280 KB |
1st numbers differ - expected: '772893586.0000000000', found: '500000000.0000000000', error = '0.3530804123' |
| 7 |
Halted |
0 ms |
0 KB |
- |
