poj 1850 Code

Code Time Limit: 1000MS Memory Limit: 30000KTotal Submissions: 9322 Accepted: 4455

Description

Transmitting and memorizing information is a task that requires different coding systems for the best use of the available space. A well known system is that one where a number is associated to a character sequence. It is considered that the words are made only of small characters of the English alphabet a,b,c, ..., z (26 characters). From all these words we consider only those whose letters are in lexigraphical order (each character is smaller than the next character).  The coding system works like this:  • The words are arranged in the increasing order of their length.  • The words with the same length are arranged in lexicographical order (the order from the dictionary).  • We codify these words by their numbering, starting with a, as follows:  a - 1  b - 2  ...  z - 26  ab - 27  ...  az - 51  bc - 52  ...  vwxyz - 83681  ...  Specify for a given word if it can be codified according to this coding system. For the affirmative case specify its code. 

Input

The only line contains a word. There are some constraints:  • The word is maximum 10 letters length  • The English alphabet has 26 characters. 

Output

The output will contain the code of the given word, or 0 if the word can not be codified.

Sample Input

bf

Sample Output

55

Source

Romania OI 2002

提示

题意：

按照a-1,b-2,c-3......的方式编码，给出字符串输出它的编码，如果输入不合法则输出0。

思路：

把问题转化为有几个题目所给字符串形式小于等于它，例如：abc

长度为1：c[26][1]（a,b,c...）=c[26][1]

长度为2：c[25][1]（ab,ac,ad...）+c[24][1]（bc,bd,be...）...=c[26][2]

长度为3：c[1][1](abc)

我们发现

长度为n：c[26][n]

我们先计算长度小于等于它本身的个数，之后减去之前求和中比它大的个数。

还是拿abc来看，

第一步：sum=c[26][1]+c[26][2]+c[26][3]

第二步：

比它大的第一位b~z，sum=sum-c[25][3]

比它大的第二位c~z，sum=sum-c[24][2]

比它大的第三位d~z，sum=sum-c[23][1]

示例程序

Source Code Problem: 1850 Code Length: 708B Memory: 392K Time: 16MS Language: GCC Result: Accepted #include <stdio.h> #include <string.h> int c[27][27]; int main() { int i,i1,len,num=0; char ch[11]; memset(c,0,sizeof(c)); for(i=0;26>=i;i++) { c[i][0]=1; for(i1=1;i>=i1;i1++) { c[i][i1]=c[i-1][i1-1]+c[i-1][i1]; } } scanf("%s",ch); len=strlen(ch); for(i=1;len>i;i++) { if(ch[i-1]>=ch[i]) //是否合法 { break; } } if(i==len) { for(i=1;len>=i;i++) //计算长度为len的所有情况 { num=num+c[26][i]; } for(i=0;ch[i]!='\0';i++) { num=num-c['z'-ch[i]][len-i]; //这里是计算出长度为len比输入字符串大的 } printf("%d",num); } else { printf("0"); } return 0; }