TIOJ-1118

#include <bits/stdc++.h>
#ifdef TEST
    #define debug(...) printf(__VA_ARGS__)
#else
    #define debug(...) (void)0
#endif
#define EB emplace_back
#define MP make_pair
#define ST first
#define ND second
using namespace std;
using ll = long long;
using llu = long long unsigned;
using pii = pair<int,int>;
/************************/
#define MX 100
int dp[MX+5][MX+5];
int proccess(char *s1, int l1, char *s2, int l2){
    // init stage
    memset(dp, 0x00, sizeof(dp));
    //init start point state
    for(int i = 0 ; i <= l1 ; ++i)
        dp[i][0] = -3*i;
    for(int i = 0 ; i <= l2 ; ++i)
        dp[0][i] = -3*i;
    // proccess stage
    for(int i = 0 ; i < l1 ; ++i){
        for(int j = 0 ; j < l2 ; ++j){
            if(s1[i] == s2[j]){
                // if char equal => +1
                dp[i+1][j+1] = dp[i][j]+10;
            }
            else{
                /*
                    choice 1 => concat both char to the prev state(eg. (a,b) -> (aa,bb))
                    choice 2 => concat char to only one side, the other one is space (eg. (a,b) -> (a*, bb)/ (aa/b*))
                */
                dp[i+1][j+1] = max(dp[i][j]-5, max(dp[i][j+1]-3, dp[i+1][j]-3));
            }

        }
    }
    return dp[l1][l2];
}
int main(){
    char s1[MX+5], s2[MX+5];
    int len1, len2;
    while(scanf("%s", s1) != EOF){
        scanf("%s", s2);
        len1 = strlen(s1);
        len2 = strlen(s2);
        int ret = proccess(s1, len1, s2, len2); // return 10x score
        /*debug("best score: %d\n", ret);
        for(int i = 0 ; i <= len1 ; ++i){
            for(int j = 0 ; j <= len2 ; ++j){
                debug("%4d ", dp[i][j]);
            }
            debug("\n");
        }*/
        double ans = double(ret) / len1 * double(10);
        printf("%.2lf%%\n", ans);
    }
    return 0;
}