1850:Code

keyword

C++

概要

a,b,...,z,ab,...,az,bc,...,yz,abc,...とアルファベットが並んでいる。文字列(10文字以下)が与えられるのでそれが何番目のものか求める問題。
シミュレーションだと間に合わないので適当に2項係数などをつかってスキップする。

int comb[30][30];

int combination(int n, int m){
    if(comb[n][m]) return comb[n][m];
    if(n==m || !m) return comb[n][m] = 1;
    return comb[n][m] = combination(n-1,m) + combination(n-1,m-1);
}

int solve(string s){
    int n = s.size(), ret = 0;
    if(n==1){
        return s[0] - 'a' + 1;
    }
    for(int i=1; i<n; i++)
        ret += combination(26,i);
    for(char c='a';c<s[0];c++) ret+=combination(26-(c-'a'+1),n-1);
    for(int i=1; i<n-1; i++){
        for(char c=s[i-1]+1; c<s[i]; c++){
            ret += combination(26-(c-'a'+1), n-i-1);
        }
    }
    ret += s[n-1] - s[n-2];
    return ret;
}

int main(){
    char str[12];
    for(int i=0; i<30; i++)
        for(int j=0; j<30; j++)
            comb[i][j] = 0;
    scanf("%s",str);
    int n = strlen(str);
    for(int i=1; i<n; i++){
        if(str[i] <= str[i-1]){
            puts("0");
            return 0;
        }
    }
    printf("%d\n",solve(string(str)));
    return 0;
}