2010年9月17日 星期五

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;
}


回目錄
回首頁

沒有留言 :

張貼留言

Related Posts Plugin for WordPress, Blogger...