Sort Me |
Time Limit: 2000ms, Special Time Limit:5000ms, Memory Limit:65536KB |
Total submit users: 69, Accepted users: 65 |
Problem 12946 : No special judgement |
Problem description |
We know the normal alphabetical order of the English alphabet, and we can then sort words or other letter sequences. For instance these words are sorted:
ANTLER
ANY COW HILL HOW HOWEVER WHATEVER ZONE The standard rules for sorting letter sequences are used:
The Gorellians, at the far end of our galaxy, have discovered various samples of English text from our electronic transmissions, but they did not find the order of our alphabet. Being a very organized and orderly species, they want to have a way of ordering For instance, if they agree on the alphabetical order UVWXYZNOPQRSTHIJKLMABCDEFG
then the words above would be sorted as
WHATEVER
ZONE HOW HOWEVER HILL ANY ANTLER COW
The first letters of the words are in Dealing with the different alphabetical orders each year by hand (or tentacle) is tedious. Your job is to implement sorting with the English letters in a specified sequence. |
Input |
Input: The input will contain one or more datasets. Each dataset will start with a line containing an integer |
Output |
Output: The first line of output of each dataset will contain "year " followed by the number of the dataset, starting from 1. The remaining n lines are the |
Sample Input |
8 UVWXYZNOPQRSTHIJKLMABCDEFG ANTLER ANY COW HILL HOW HOWEVER WHATEVER ZONE 5 ZYXWVUTSRQPONMLKJIHGFEDCBA GO ALL ACM TEAMS GO 10 ZOTFISENWABCDGHJKLMPQRUVXY THREE ONE NINE FIVE SEVEN ZERO TWO FOUR EIGHT SIX 0 |
Sample Output |
year 1 WHATEVER ZONE HOW HOWEVER HILL ANY ANTLER COW year 2 TEAMS GO GO ALL ACM year 3 ZERO ONE TWO THREE FOUR FIVE SIX SEVEN EIGHT NINE |
Problem Source |
ACM Mid-Central Programming Competition 2013
#include<stdio.h> typedef struct nn { int flag; struct nn *next[26]; }node; node *root; node *builde() { node *p=new node; for(int i=0;i<26;i++) p->next[i]=NULL; p->flag=0; return p; } char str[50],s[50]; int Oder[50]; void set() { node *p=root; for(int i=0;str[i]!='\0';i++) { int j=Oder[str[i]-'A']; if(p->next[j]==NULL) p->next[j]=builde(); p=p->next[j]; } p->flag++; } void print(node *p,int len) { if(p->flag) { for(int i=1;i<=(p->flag);i++) printf("%s\n",str); } for(int i=0;i<26;i++) if(p->next[i]!=NULL) { str[len]=s[i]; str[len+1]='\0'; print(p->next[i],len+1); } } int main() { int t=0,n; while(scanf("%d",&n)>0&&n) { scanf("%s",s); for(int i=0;i<26;i++) Oder[s[i]-'A']=i; root=builde(); while(n--) { scanf("%s",str); set(); } printf("year %d\n",++t); print(root,0); } } |