//inpu and output
//ABABAC (input)
//0.304398 (Output)
//ABABAC (Output)
#include <bits/stdc++.h>
using namespace std;
double encoding(string &s, map<char, double> &probability)
{
double ans = 0.0;
double low = 0.0;
double high = 1.0;
double culsum = 0.0;
map<char, pair<double, double>> range;
for (auto u : probability)
{
range[u.first] = {culsum, culsum + u.second};
culsum += u.second;
}
for (int i = 0; i < s.size(); i++)
{
low = range[s[i]].first;
high = range[s[i]].second;
double d = high-low;
culsum = low;
for (auto u : probability)
{
range[u.first] = {culsum, culsum + d*probability[u.first]};
culsum =culsum + d*probability[u.first];
}
}
ans=(low+high)/2;
return ans;
}
void decode(double encodeval,map<char,double>&probability,int length)
{
double ans = 0.0;
double low = 0.0;
double high = 1.0;
double culsum = 0.0;
map<char, pair<double, double>> range;
for (auto u : probability)
{
range[u.first] = {culsum, culsum + u.second};
culsum += u.second;
}
char ch;
for(int i=0;i<length;i++)
{
for(auto u:range)
{
if(u.second.first<=encodeval&&u.second.second>=encodeval)
{
ch=u.first;
cout<<u.first;
break;
}
}
low = range[ch].first;
high = range[ch].second;
double d = high-low;
culsum = low;
for (auto u : probability)
{
range[u.first] = {culsum, culsum + d*probability[u.first]};
culsum =culsum + d*probability[u.first];
}
}
}
int main()
{
int i;
string s;
cin >> s;
map<char, double> propability;
for (i = 0; i < s.size(); i++)
{
propability[s[i]]++;
}
for (auto u : propability)
{
propability[u.first] = u.second / s.size();
// cout<<propability[u.first]<<endl;
}
double encodeval = encoding(s, propability);
cout<<encodeval<<endl;
decode(encodeval,propability,s.size());
return 0;
}
0 Comments