ACM 10393 - The One-Handed Typist

#include <stdio.h>
#include <string.h>

struct finger
{
    char word;
    int fId;
    int isUse;   
};

struct string
{
    char str[51];    
};

struct string s, sArray[1000];
struct finger f[32];
int index, maxLen;

void creat()
{
    f[0].word = 'a', f[0].fId = 1, f[1].word = 'b', f[1].fId = 4;
    f[2].word = 'c', f[2].fId = 3, f[3].word = 'd', f[3].fId = 3;
    f[4].word = 'e', f[4].fId = 3, f[5].word = 'f', f[5].fId = 4;
    f[6].word = 'g', f[6].fId = 4, f[7].word = 'h', f[7].fId = 7;
    f[8].word = 'i', f[8].fId = 8, f[9].word = 'j', f[9].fId = 7;
    f[10].word = 'k', f[10].fId = 8, f[11].word = 'l', f[11].fId = 9;
    f[12].word = 'm', f[12].fId = 7, f[13].word = 'n', f[13].fId = 7;
    f[14].word = 'o', f[14].fId = 9, f[15].word = 'p', f[15].fId = 10;
    f[16].word = 'q', f[16].fId = 1, f[17].word = 'r', f[17].fId = 4;
    f[18].word = 's', f[18].fId = 2, f[19].word = 't', f[19].fId = 4;
    f[20].word = 'u', f[20].fId = 7, f[21].word = 'v', f[21].fId = 4;
    f[22].word = 'w', f[22].fId = 2, f[23].word = 'x', f[23].fId = 2;
    f[24].word = 'y', f[24].fId = 7, f[25].word = 'z', f[25].fId = 1;
    f[26].word = ' ', f[26].fId = 5, f[27].word = ' ', f[27].fId = 6;
    f[28].word = ',', f[28].fId = 8, f[29].word = '.', f[29].fId = 9;
    f[30].word = ';', f[30].fId = 10, f[31].word = '/', f[31].fId = 10;
}

void allUseFinger()
{
    int i;
    for (i = 0; i < 32; i ++)
        f[i].isUse = 1;
}

void notUseFinger(int n)
{
    if (n == 1) { f[0].isUse = 0, f[16].isUse = 0, f[25].isUse = 0; return; }
    if (n == 2) { f[18].isUse = 0, f[22].isUse = 0, f[23].isUse = 0; return; }
    if (n == 3) { f[2].isUse = 0, f[3].isUse = 0, f[4].isUse = 0; return; }
    if (n == 4) 
    { f[1].isUse = 0, f[5].isUse = 0, f[6].isUse = 0, f[17].isUse = 0, f[19].isUse = 0, f[21].isUse = 0; return; }
    if (n == 5) { f[26].isUse = 0; return; }
    if (n == 6) { f[27].isUse = 0; return; }
    if (n == 7) 
    { f[7].isUse = 0, f[9].isUse = 0, f[12].isUse = 0, f[13].isUse = 0, f[20].isUse = 0, f[24].isUse = 0; return; }
    if (n == 8) { f[8].isUse = 0, f[10].isUse = 0, f[28].isUse = 0; return; }
    if (n == 9) { f[11].isUse = 0, f[14].isUse = 0, f[29].isUse = 0; return; }
    if (n == 10) { f[15].isUse = 0, f[30].isUse = 0, f[31].isUse = 0; return; }
}

int isUseWord(char ch)
{
    if (ch == ' ') return (f[25].isUse || f[26].isUse); 
    if (ch == ',') return f[28].isUse;
    if (ch == '.') return f[29].isUse;
    if (ch == ';') return f[30].isUse;
    if (ch == '/') return f[31].isUse;
    int n = ch - 'a';
    return f[n].isUse;
}
void insert()
{
    int repeatIndex = 0, i;
    for (i = 0; i < index ; i ++)
    {
        if (strcmp(s.str, sArray[i].str) == 0)
           return;
    }       
    struct string repeatS;
    strcpy(sArray[index ++].str, s.str); 
    for (i = index - 1; i >= 1; i ++)
    {
        if (strcmp(sArray[i].str, sArray[i - 1].str) == -1)
        {
            strcpy(repeatS.str, sArray[i].str);
            strcpy(sArray[i].str, sArray[i - 1].str);
            strcpy(sArray[i - 1].str, repeatS.str);
        }
        else return;
    }
    
    return;
}

int main()
{
    creat();
    int F, N, nUF, i, isKey, len;
    while (scanf("%d %d", &F, &N) == 2)
    {
        index = 0, maxLen = 0;  
        allUseFinger();  
        while (F --)
            scanf("%d", &nUF), notUseFinger(nUF);
        while (N --)
        {
            scanf("%s", s.str);
            isKey = 1;
            len = strlen(s.str);
            for (i = 0; s.str[i]; i ++)
            {
                if (!isUseWord(s.str[i]))
                {
                    isKey = 0;
                    break;
                }
            }
            if (isKey && maxLen < len) maxLen = len, index = 0;
            if (isKey && maxLen == len) insert();     
        }
        printf("%d\n", index);
        for (i = 0; i < index; i ++)
            printf("%s\n", sArray[i].str);
    }
    return 0;
}

回目錄
回首頁