1850:Code
keyword
概要
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; }