#include <iostream>
#include <fstream>
#include <vector>
#include <map>
using namespace std;
const int MAXLEN = 9;
int DEBUG = 0;
long long MAXVAL;
long long gcd(long long a, long long b) {
if (DEBUG > 0) MAXVAL = max(MAXVAL, max(a,b));
return (b ? gcd(b, a % b) : a);
}
class Fraction {
public:
long long n,d;
Fraction(long long num=0, long long denom=1) : n(num), d(denom) {
long long temp = gcd(n,d); if ((temp < 0) != (denom < 0))
temp = -temp; n /= temp;
d /= temp;
}
bool operator<(const Fraction& other) const {
return (n*other.d < other.n*d);
}
bool operator==(const Fraction& other) const {
return (n == other.n && d == other.d); }
bool operator!=(const Fraction& other) const {
return (n != other.n || d != other.d);
}
Fraction operator+(const Fraction& other) const {
return Fraction(n*other.d + d*other.n, d*other.d);
}
Fraction operator-(const Fraction& other) const {
return Fraction(n*other.d - d*other.n, d*other.d);
}
Fraction operator*(const Fraction& other) const {
return Fraction(n*other.n, d*other.d);
}
Fraction operator/(const Fraction& other) const {
return Fraction(n*other.d, d*other.n);
}
};
ostream& operator<<(ostream& out, Fraction& f) {
out << f.n;
if (f.d > 1)
out << "/" << f.d;
return out;
}
const int MAX_M = 2*MAXLEN + 1;
Fraction coef[MAX_M][1 + MAX_M];
void dumpEquations(map<string,int> &index);
int transition(map<string,int> &index, string newest) {
for (int k=0; k < newest.size(); k++) {
map<string,int>::iterator it = index.find(newest.substr(k));
if (it != index.end())
return it->second; }
return 0; }
Fraction solve(string A, string B) {
MAXVAL = 0;
if (DEBUG > 1) cout << "Solving " << A << " vs " << B << endl;
map<string,int> index; index[""] = 0;
int n = A.size();
string players[] = {A,B};
for (int k=0; k <= n; k++)
for (int j=0; j<2; j++) {
string sub = players[j].substr(0,k);
if (index.find(sub) == index.end()) {
int i = index.size();
index[sub] = i;
}
}
int M = index.size();
for (int j=0; j < M; j++)
for (int k=0; k < M+1; k++)
coef[j][k] = 0;
coef[index[A]][M] = 1; coef[index[B]][M] = 0;
for (map<string,int>::iterator it = index.begin(); it != index.end(); ++it) {
string sub = it->first;
int i = it->second;
if (sub.size() < n) { coef[index[sub]][transition(index, sub+"H")] = Fraction(1,2);
coef[index[sub]][transition(index, sub+"T")] = Fraction(1,2);
}
}
dumpEquations(index);
for (int r=M-1; r >= 0; r--) {
if (coef[r][r] != 0) {
Fraction denom = (Fraction(1) - coef[r][r]);
for (int k=0; k < M+1; k++)
coef[r][k] = coef[r][k] / denom;
coef[r][r] = 0;
}
for (int a=0; a < M; a++) {
Fraction factor = coef[a][r];
if (factor != 0) {
for (int k=0; k<M+1; k++) {
if (coef[r][k] != 0)
coef[a][k] = coef[a][k] + factor * coef[r][k];
}
coef[a][r] = 0;
}
}
if (DEBUG > 1) cout << "After clearing col " << r << endl;
dumpEquations(index); }
return coef[0][M]; }
int main(int argv, char** argc) {
DEBUG = (argv - 1);
ifstream fin;
fin.open((argv > 1) ? argc[1] : "paradox.in"); while (true) {
string playerA,playerB;
fin >> playerA;
if (playerA == "$") break;
fin >> playerB;
if (playerA.size() != playerB.size() || playerA.size() > MAXLEN)
cerr << "INVALID INPUT: " << playerA << " " << playerB << endl;
Fraction answer = solve(playerA, playerB);
cout << answer.n << "/" << answer.d;
if (DEBUG > 0) cout << "\t\t(max value " << MAXVAL << ")";
cout << endl;
}
}
void dumpEquations(map<string,int> &index) {
if (DEBUG > 1) {
int M = index.size();
vector<string> states(M);
for (map<string,int>::iterator it = index.begin(); it != index.end(); ++it) {
if (it->first == "")
states[it->second] = "''";
else
states[it->second] = it->first;
}
for (int j=0; j < M; j++) {
cout << states[j] << " = ";
int terms=0;
for (int k=0; k < M; k++) {
if (coef[j][k] != 0) {
if (++terms > 1)
cout << " + ";
cout << "(" << coef[j][k] << ")*" << states[k];
}
}
if (coef[j][M] != 0) {
if (++terms > 1)
cout << " + ";
cout << coef[j][M];
terms++;
}
if (terms == 0)
cout << 0;
cout << endl;
}
}
}