[ACM] poj 1496 Word Index（組合計數）

Word Index Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 4541 Accepted: 2567

Description

Encoding schemes are often used in situations requiring encryption or information storage/transmission economy. Here, we develop a simple encoding scheme that encodes particular types of words with five or fewer (lower case) letters as integers.

Consider the English alphabet {a,b,c,...,z}. Using this alphabet, a set of valid words are to be formed that are in a strict lexicographic order. In this set of valid words, the successive letters of a word are in a strictly ascending order; that is, later letters in a valid word are always after previous letters with respect to their positions in the alphabet list {a,b,c,...,z}. For example,

abc aep gwz

are all valid three-letter words, whereas

aab are cat

are not.

For each valid word associate an integer which gives the position of the word in the alphabetized list of words. That is:

    a -> 1

    b -> 2

    .

    .

    z -> 26

    ab -> 27

    ac -> 28

    .

    .

    az -> 51

    bc -> 52

    .

    .

    vwxyz -> 83681

Your program is to read a series of input lines. Each input line will have a single word on it, that will be from one to five letters long. For each word read, if the word is invalid give the number 0. If the word read is valid, give the word's position index in the above alphabetical list.

Input

The input consists of a series of single words, one per line. The words are at least one letter long and no more that five letters. Only the lower case alphabetic {a,b,...,z} characters will be used as input. The first letter of a word will appear as the first character on an input line.

The input will be terminated by end-of-file.

Output

The output is a single integer, greater than or equal to zero (0) and less than or equal 83681. The first digit of an output value should be the first character on a line. There is one line of output for each input line.

Sample Input

z
a
cat
vwxyz

Sample Output

26
1
0
83681

Source

East Central North America 1995

解題思路：

題目中所輸入的串必須嚴格上升是很關鍵的一點，在26個字母中隨便選5個字母，則這5個字母只有一個排列（滿足嚴格上升），所以根據此來計數。

比如要求 c e h 這個字典序是多少。該串長3 ，所以先把串長1和2的情況加上，即sum+=c (26,1) + c(26,2) , 該串為3了，注意到第一個字母最初應該從'a'開始,a->b 剩下兩位隨便在25->24個數裡選 ,即 sum+=c (2 5,2) + c( 24 ,2) ，注意第一個字母不能到達 c，否則獲得的串可能會比c e h大。給出的串第二個字母最初不能從a開始，因為要嚴格上升，要從原串上一個字母的下一個字母開始，第一個字母為c，所以第二個字母要從d開始計數, sum+=c( 24 , 1) ,最後一個字母也一樣。這樣最後所得的sum為 ceg的字典序，再加上1就是ceh的字典序了。 對於ceh 有 s+=c[26][1]+c[26][2]+c[25][2]+c[24][2]+c[22][1]+2+1;

代碼：

#include 
#include 
using namespace std;

int c[30][30];

void C()//求組合數
{
    for(int i=0;i<=26;i++)
    {
        c[i][0]=c[i][i]=1;
        for(int j=1;j>s)
    {
        int len=s.length();
        int i;
        for(i=1;i