Time Limit: 2 Sec Memory Limit: 256 Mb
题目链接http://acm.csu.edu.cn:20080/csuoj/problemset/problem?pid=2280
Description
Mr. Manuel Majorana Minore made a number of files with numbers in their names. He wants to have a list of the files, but the file listing command commonly used lists them in an order different from what he prefers, interpreting digit sequences in them as ASCII code sequences, not as numbers. For example, the files file10, file20 and file3 are listed in this order.
Write a program which decides the orders of file names interpreting digit sequences as numeric values.
Each file name consists of uppercase letters (from ‘A’ to ‘Z’), lowercase letters (from ‘a’ to ‘z’), and digits (from ‘0’ to ‘9’).
A file name is looked upon as a sequence of items, each being either a letter or a number. Each single uppercase or lowercase letter forms a letter item. Each consecutive sequence of digits forms a number item.
Two item are ordered as follows.
Number items come before letter items.
Two letter items are ordered by their ASCII codes.
Two number items are ordered by their values when interpreted as decimal numbers.
Two file names are compared item by item, starting from the top, and the order of the first different corresponding items decides the order of the file names. If one of them, say A, has more items than the other, B, and all the items of B are the same as the corresponding items of A, BB should come before.
For example, three file names in Sample Input 1, file10, file20, and file3 all start with the same sequence of four letter items f, i, l, and e, followed by a number item, 10, 20, and 3, respectively. Comparing numeric values of these number items, they are ordered as file3 < file10 <file20.
Input
The input consists of a single test case of the following format.
n
s0
s1
.
.
sn
The integer n in the first line gives the number of file names s1 through sn to be compared with the file name given in the next line(s0).
Here,n satisfies 1 ≤ n ≤ 1000
The following n + 1 lines are file names,s0 through sn ,one in each line. They have at least one and no more than nine characters. Each of the characters is either an uppercase letter, a lowercase letter, or a digit.
Sequences of digits in the file names never start with a digit zero (0).
Output
For each of the file names, s1 through sn, output one line with a character indicating whether it should come before s0 or not. The character should be “-” if it is to be listed before s0; otherwise, it should be “+”, including cases where two names are identical.
Sample Input
11
X52Y
X
X5
X52
X52Y
X52Y6
32
ABC
XYZ
x51y
X8Y
X222
Sample Output
题目大意：给你一个模板和n个字符串，对于每个字符串输出‘-’如果该字符串应该排在模板串的前面，否则输出‘+’。排序规则：
1.数字总是排在字母的前面。
2.字母按ASCll排序。
3.数字按照其值的大小排序：对于X52Y与X8Y，由于52>8所以X8Y应该排在X52Y前面。。。
题目明白了接下来就是大模拟了，尽量简化：
#include <cstdio>
#include <cstring>
#define debug(n) printf("%d ",n)
using namespace std;
char s[1020][15];
int a[15],b[15];
int nz(char ch) {
if ((ch>='a' && ch<='z') || (ch>='A' && ch<='Z')) return 0;
return 1;
}
int rd(int x)
{
int s=0;
while (x>0){
x/=10;
s++;
}
return s;
}
int main() {
int n;
scanf ("%d",&n);
for (int i=0; i<=n; i++) {
scanf ("%s",s[i]);
}
int len=strlen(s[0]);
for (int i=0; i<len; i++) {
int k=i;
if (nz(s[0][i])) {
while (nz(s[0][i]) && i<len) a[k]=a[k]*10+s[0][i]-'0',i++;
}
}
for (int i=1; i<=n; i++) {
int mark=0;
int len2=strlen(s[i]);
int head=0;
memset(b,0,sizeof(b));
for (int j=0; j<len2; j++) {
int k=j;
if (nz(s[i][j])) {
while (nz(s[i][j]) && j<len2) b[k]=b[k]*10+s[i][j]-'0',j++;
}
}
while (head<len && head<len2) {
int lin=nz(s[0][head]),ai=nz(s[i][head]);
if (lin<ai) {
printf ("-\n");
mark=1;
break;
} else if (lin>ai) {
printf ("+\n");
mark=1;
break;
} else {
if (a[head]&&b[head]){
if (a[head]>b[head]) {
printf ("-\n");
mark=1;
break;
}
else if (a[head]<b[head]) {
printf ("+\n");
mark=1;
break;
}
head+=rd(a[head]);continue;
}
else if (s[0][head]>s[i][head]) {
printf ("-\n");
mark=1;
break;
} else if (s[0][head]<s[i][head]) {
printf ("+\n");
mark=1;
break;
}
}
head++;
}
if (!mark) {
if (len2<len) printf ("-\n");
else printf ("+\n");
}
}
return 0;
}