2014
02-14

Extended Normal Order Sort

When sorted in standard order, strings with digits in them may not sort to where they are expected. For instance, xyz100 precedes xyz2. In some applications such as listing files, normal order sort may be used where any string of digits in a character string is treated as a single digit with numerical value given by the digit string. For example, the following are in normal order:

XYZ001, XYZ2, XYZ003, XYZ08, XYZ23, XYZ100, XYZQ

We wish to extend normal order sort in two ways:

1. Lower case and upper case letters sort the same (with the upper case value).

2. If a plus (+) or minus (-) sign precedes a digit and does not follow a digit, it is considered part of the following number for sorting purposes.

So 123+456+7890 are three numbers separated by plus signs but A+003 is the same as A3.

To do our sort, we will use a library sort routine but we need to furnish a comparison routine. Write a comparison routine which takes as input two strings of printable, non-space ASCII characters (chr(33)-chr(126)) and returns:

-1 if the first string should precede the second in extended normal order
0 it the two strings are the same in extended normal order, or
1 if the first string should follow the second in extended normal order.

The first line of input contains a single integer N, (1 ≤ N ≤ 1000) which is the number of data sets that follow. Each data set consists of a single line of input containing the two strings to be compared separated by a space.

The first line of input contains a single integer N, (1 ≤ N ≤ 1000) which is the number of data sets that follow. Each data set consists of a single line of input containing the two strings to be compared separated by a space.

5
x-3 X0001
123-456-7890 123+456+7890
xYz000123J XyZ+123j
#\$%^&*[]- abcdefgh
Abc47jKL+00123 ABC+47jkL123

1 -1
2 1
3 0
4 -1
5 0

http://acm.hit.edu.cn/hoj/problem/view?id=2761

gn=2^n+(-1)^(n+1)

#include <stdio.h>
#include <math.h>

int main()
{
long long n,gn,dig;

while (scanf("%lld", &n) == 1)
{
if (n == 0)
printf("%d\n", 0);
else
{
/*gn = pow(2, n)+pow(-1, n+1);*/
dig = ceil(n*log10(2));
printf("%lld\n", dig);
}
}

return 0;
}

1. 听说博人传要在中国上映我忍了半年没看，2月18号那天第一时间就去看了，一个人去看的- -！因为找了好几个人都纷纷表示倒贴钱都不看- -!然后看的人的确很少，刚开始我也以为会很多人看，然而就座率不足5成…你可以随意选个好位置坐- -

2. bottes vernies blanches

I appreciate the efforts you men and women place in to share blogs on such sort of matters, it was certainly useful. Keep Posting!

3. 您没有考虑 树的根节点是负数的情况， 若树的根节点是个很大的负数，那么就要考虑过不过另外一边子树了

4. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术，也不懂什么是算法，从而也不要求程序员懂什么算法，做程序从来不考虑性能问题，只要页面能显示出来就是好程序，这是国内的现状，很无奈。

5. 题目需要求解的是最小值，而且没有考虑可能存在环，比如
0 0 0 0 0
1 1 1 1 0
1 0 0 0 0
1 0 1 0 1
1 0 0 0 0
会陷入死循环

6. “再把所有不和该节点相邻的节点着相同的颜色”，程序中没有进行不和该节点相邻的其他节点是否相邻进行判断。再说求出来的也不一样是颜色数最少的