Background

In the present world you frequently meet a lot of call numbers and they are going to be longer and longer. You need to remember such a kind of numbers. One method to do it in an easy way is to assign letters to digits as shown in the following picture:

	1 ij	2 abc	3 def
4 gh	5 kl	6 mn
7 prs	8 tuv	9 wxy
0 oqz

Problem

Write a program to find the shortest sequence of words (i.e. one having the smallest possible number of words) which corresponds to a given number and a given list of words. The correspondence is described by the picture above.

Input

Input contains a series of tests. The first line of each test contains the call number, the transcription of which you have to find. The number consists of at most 100 digits. The second line contains the total number of the words in the dictionary (maximum is 50000). Each of the remaining lines contains one word, which consists of maximally 50 small letters of the English alphabet. The total size of the input file doesn't exceed 300KB. The last line of input file contains call number -1.

Output

Each line of output contains the shortest sequence of words which has been found by your program. The words are separated by single spaces. If there is no solution to the input data, the line contains text "No solution.". If there are more solutions having the minimum number of words, you can choose any single one of them.

Sample

7325189087
            5
            it
            your
            reality
            real
            our
            4294967296
            5
            it
            your
            reality
            real
            our
            -1
            

reality our
            No solution.
            

在计算机图形运算中，常常要将浮点数转换为整数，例如在图像的光栅化阶段，就要执行大量的类型转换，以便将浮点数表示的坐标转化为整数表示的屏幕坐标。Ok，it's so easy：
----------------------------------------------------------------------------------------
//
// 强制类型转换
// 小数部分将被裁剪掉
//
int_val = (int)float_val;
----------------------------------------------------------------------------------------
嘿嘿，很高兴你居然和我一样单纯！这个操作实在是太TINY了，以至于我从来没想过它是怎么实现的，直到某天某个家伙跟我说，不要使用标准C类型转换，因为那太慢了！我当时的震惊不下于倒霉的冒险者遇上了龙。

标准C类型转换最大的优点是，它是独立于平台的，无论是在X86上跑，还是在PowerPC上跑，你什么都不用担心，编译器会为你搞定一切。而这也恰恰是它最大的缺点——严重依赖于编译器的实现。而实际测试表明，编译器所生成的代码，其速度实在不尽人意。

一个替代的方法是直接对数据位进行操作。如果你对IEEE浮点数的表示法比较熟悉的话（如果你压根什么都不知道，请先查阅文末附录中的资料），这是显而易见的。它提取指数和尾数，然后对尾数执行移位操作。代码如下：
----------------------------------------------------------------------------------------
//
// 将32位浮点数fval转换为32位整数并存储在ival中
// 小数部分将被裁剪掉
//
void TruncToInt32 (int &ival, float fval)
{
ival = *(int *)&fval;

// 提取尾数
// 注意实际的尾数前面还有一个被省略掉的1
int mantissa = (ival & 0x07fffff) | 0x800000;

// 提取指数
// 以23分界，指数大于23则左移，否则右移
// 由于指数用偏移表示，所以23+127=150
int exponent = 150 - ((ival >> 23) & 0xff);

if (exponent < 0)
ival = (mantissa << -exponent);
else
ival = (mantissa >> exponent);

// 如果小于0，则将结果取反
if ((*(int *)&fval) & 0x80000000)
ival = -ival;
}
----------------------------------------------------------------------------------------
该函数有一个BUG，那就是当fval=0时，返回值是2。原因是对于语句mantissa>>exponent，编译器使用了循环移位指令。解决方法是要么对0作特殊处理，要么直接用汇编来实现。

这个函数比标准的C转换要快，而且由于整个过程只使用了整数运算，可以和FPU并行运行。但缺点是，(1)依赖于硬件平台。例如根据小尾和大尾顺序的不同，要相应地修改函数。(2)对于float和double要使用不同的实现，因为二者的数据位不同。(3)对于float，只能保留24位有效值，尽管int有32位。

更快的方法是使用FPU指令FISTP，它将栈中的浮点数弹出并保存为整数：
----------------------------------------------------------------------------------------
//
// 将64位浮点数fval转换为32位整数并存储在ival中
// 小数部分将四舍五入到偶数
//
inline void RoundToIntFPU (int &ival, double fval)
{
_asm
{
fld fval
mov edx, dword ptr [ival]
fistp dword ptr [edx]
}
}
----------------------------------------------------------------------------------------
很好，无论速度还是精度似乎都相当令人满意。但如果换一个角度来看的话，fistp指令需要6个cycle，而浮点数乘法才仅仅需要3个cycle！更糟的是，当fistp运行的时候，它必须占用FPU，也就是说，其他的浮点运算将不能执行。仅仅为了一次类型转换操作就要付出如此大的代价，光想想就觉得心疼。

当然，它也有很多优点：更快的速度，更精确的数值（四舍五入到偶数），更强的适用性（float和double均可)。要注意的是，FPU默认的四舍五入到偶数（round to even）和我们平常所说的四舍五入（round）是不同的。二者的区别在于对中间值的处理上。考虑十进制的3.5和4.5。四舍五入到偶数是使其趋向于邻近的偶数，所以舍入的结果是3.5->4，4.5->4；而传统的四舍五入则是3.5->4，4.5->5。四舍五入到偶数可以产生更精确，更稳定的数值。

除此之外，还有更好，更快的方法吗？有的，那就是华丽的 Magic Number ！

请看下面的函数：
----------------------------------------------------------------------------------------
//
// 将64位浮点数转换为32位整数
// 小数部分将四舍五入到偶数
//
inline void RoundToInt64 (int &val, double dval)
{
static double magic = 6755399441055744.0;
dval += magic;
val = *(int*)&dval;
}
----------------------------------------------------------------------------------------
快，这就是它最伟大的地方！你所需要的仅仅是一次浮点数加法，你还能再奢望些什么呢？

当然，绝对不要使用莫名其妙的代码，现在马上就让我们来看看它是怎么变的戏法。

首先，我们要搞清楚FPU是怎样执行浮点数加法的。考虑一下8.75加2^23。8.75的二进制表示是1000.11，转化为IEEE标准浮点数格式是1.00011*2^3。假设二者均是32位的float，它们在内存中的存储为：
----------------------------------------------------------------------------------------
符号位(31), 指数(30-23), 尾数(22-0)

8.75: 0, 10000010, 0001 1000 0000 0000 0000 000

2^23: 0, 10010110，0000 0000 0000 0000 0000 000
----------------------------------------------------------------------------------------
FPU所执行的操作是：(1)提升指数较小者的指数，使二者指数相同；(2)将二者的尾数相加；(3)将结果规整为标准格式。让我们具体来看看整个过程：
----------------------------------------------------------------------------------------
1，提升8.75的指数，尾数要相应地右移23-3=20位：

8.75 = 1.00011*2^3 = .0000000000000000000100011*2^23

2，将二者相加。必须注意的是，
   由于float只有23位尾数，所以8.75的低位被移除掉了：

8.75: 0, 10010110, 0000 0000 0000 0000 0001 000
 +
2^23: 0, 10010110，0000 0000 0000 0000 0000 000
 =
0, 10010110, 0000 0000 0000 0000 0001 000

3，将规整为标准格式：

别忘了2^23还有个前导1，所以结果是规整的，无需执行任何操作
----------------------------------------------------------------------------------------
你发现什么了吗？不错，将结果的尾数部分提取出来，正是int(8.75)！是的，magic number的奥妙就在这里，通过迫使FPU将尾数移位，从而获得我们需要的结果。

但是别高兴得太早，让我们来看看负数的情况。以-8.75为例，-8.75加2^23相当于2^23减去8.75，过程如下：
----------------------------------------------------------------------------------------
2^23: 0, 10010110，0000 0000 0000 0000 0000 000
 -
8.75: 0, 10010110, 0000 0000 0000 0000 0001 000
 =
0, 10010110, 1111 1111 1111 1111 1110 000
----------------------------------------------------------------------------------------
很好，尾数部分正是int(-8.75)=-8的补码。然而，2^23的前导1在减法过程中被借位了，所以结果的尾数前面并没有1，FPU将执行规整操作，最后我们得到的是：
----------------------------------------------------------------------------------------
0, 10010110, 1111 1111 1111 1111 1100 000
----------------------------------------------------------------------------------------
功亏一篑！等等，如果将2^23的尾数的最高位置1，那么在减法过程中不就可以保全前导1了吗？完全正确，这就是我们需要的。所以最后的magic number是0,10010110,1000 0000 0000 0000 0000 000，也就是1.5*2^23。

然而，我们要清楚这个方法的一些局限性。首先，在将结果的float值保存为整数时，我们需要使用某些mask值将22-31位屏蔽掉。其次，float只能保有最多23位的有效值，在将尾数最高位置1后，有效值更是降到了22位，这意味着我们对大于2^23-1的数值无能为力。

相比之下，如果我们只处理double，那么所有的问题就都迎刃而解了。首先，double的指数位，符号位和尾数的最高位全部都在高32位，无需屏蔽操作。其次，double有多达52位的尾数，对于32位的int来说，实在是太奢侈了！

用于double的magic number是1.5*2^52=6755399441055744.0，推导过程是一样的。

根据同样的原理，我们还可以计算出将float和double转化为定点数的magic number。例如对于16-16的定点数，尾数右移的位数比原先转化为整数时要少16，所以对于double来说，相应的magic number就是1.5*2^36。如果要转化为8-24的定点数，则移位次数要少24，magic number是1.5*2^28。对于其他格式的定点数，以此类推。比起int(float_val*65536)这样的表达式，无论是速度还是精度都要优胜得多。

另外，不得不再次重申的是，对于在最后的结果中被移除掉的数值，FPU会将其四舍五入到偶数。然而，有时我们确实需要像floor和ceil那样的操作，那该怎么办呢？很简单，将原数加上或减去一个修正值就可以了，如下所示：
----------------------------------------------------------------------------------------
// 修正值
static double magic_delta=0.499999999999;

// 截取到整数
inline void Floor64 (int &val, double dval)
{
RoundToInt64(val,dval-delta);
}

// 进位到整数
inline void Ceil64 (int &val, double dval)
{
RoundToInt64(val,dval+delta);
}
----------------------------------------------------------------------------------------
这个世界上没有免费的午餐。我们获得了速度，相对应地，也必须付出一些代价，那就是可移植性。上述方法全都基于以下几个假设：(1)在x86上跑；(2)符合IEEE的浮点数标准；(3)int为32位，float为32位，double为64位。局限性其实是蛮大的，相比之下，int_val=(int)float_val就要省事多了。当然，你也可以使用条件编译。

最后，让我们来看两组实际的测试数值。这份报告来自于Sree Kotay和他的朋友Herf：
----------------------------------------------------------------------------------------
平台：Pentium IV/1.2

64位浮点数到32位整数的转换：

int(f)：        2772.65 ms
fistp：         679.269 ms
magic number：  622.519 ms

64位浮点数到16-16定点数的转换：

int(f*65536)：  2974.57 ms
fistp：         3100.84 ms
magic number：  606.80 ms

floor函数：

ANSI floor：    7719.400 ms
magic number：  687.177 ms
----------------------------------------------------------------------------------------
平台：Pentium D/3.2

64位浮点数到32位整数的转换：

int(f)：        1948.470 ms
fistp：         523.792 ms
magic number：  333.033 ms

64位浮点数到16-16定点数的转换：

int(f*65536)：  2163.56 ms
fistp：         7103.66 ms
magic number：  335.03 ms

floor函数：

ANSI floor：    3771.55 ms
magic number：  380.25 ms
----------------------------------------------------------------------------------------
性能的差距实在令人惊讶，不是吗？我想说的是，写编译器的家伙绝对不是傻瓜（恐怕比你我都要聪明得多），他们当然知道所有这些优秀的算法。但为什么编译器的表现会如此糟糕呢？其中一个理由是，为了使浮点数运算尽可能精确和迅速，IEEE在算法的选择上有很多的限制。而另一方面，IEEE的舍入规则（四舍五入到偶数）尽管从维持浮点数的连贯性上来看非常棒，但却不符合ANSI C在浮点数到整数的类型转换上的说明（截尾）。于是，编译器不得不做一大堆的工作来保证行为的正确性（符合标准）。这在大部分情况下都不是什么问题——除非你在写图形/声音/多媒体之类的代码。

刚刚在我的赛扬1.1G上实际测试了一下。编译器是VC2003，使用PerformenceCounter来计算时间，在DEBUG模式下，C标准转换/FISTP/MagicNumber三种方法所耗费时间的比约为5/3/2。但在优化全开的RELEASE模式下，标准C类型转换的速度却是遥遥领先于所有其他的方法！也不知道是我的测试方法有问题，还是该赞VS厉害。
--------------------------------------------------------------------------------------
参考文献和相关资源可到鄙人的小店下载：http://greatsorcerer.go2.icpcn.com/info/float2int.html

1，What Every Computer Scientist Should Know About Floating-Point Arithmetic by David Goldberg（PDF）：
这篇论文囊括了关于浮点数的所有东西，正如其名字所示，任何想要了解浮点数的人都必读的文献。（其中关于精度的讨论实在令我受益非浅。） 

2，Let's Get to The Floating Point by Chris Hecker（PDF）：
早期的关于浮点数的文章，写得非常棒，值得一看。
 
3，IEEE Standard 754 for Binary Floating Point Arithmetic by Prof.W.Kahan（PDF）：
关于IEEE754标准的说明。 

4，IA64 Floating Point Operations and the IEEE Standard for Binary Floating Point Arithmetic（PDF）：
关于IA64的浮点数实现。 

5，Know Your FPU: Fixing Floating Fast by Sree Kotay 

两人游戏： 给定K堆火柴，每堆火柴数为N1,N2,N3,...Nk,
两人轮流拿，看谁拿到最后一根火柴谁就胜利。
    规则：每次只能从一堆中拿，每次至少拿一根，最多可拿光。
假若我先走，求教我必胜的策略。
    比如：有三堆，1  2  3

---------------------------------------------------------------

求出 N = N1^N2^N3^…^Nk （“^”为C++中的按位异或运算符）。
若 N 等于零，称此状态为必胜状态，否则称为非必胜状态。
从必胜状态中改小一个且只改小一个数字是不可能到达另一个必胜状态的。
从非必胜状态中一定可以找到一个数n，使得n<Ni且N1^N2^…^Ni-1^n^Ni+1^…^Nk=0 (其中1<=i<=k)，也就是说从非必胜状态一定可以只改小一个数字而到达必胜状态。
若某一方保证每次拿火柴后当前状态都是必胜状态，此方将胜出（当然要求相对此方的初始状态为非必胜状态）。

---------------------------------------------------------------

发信人: Nature (成长●快乐●烦恼), 信区: Mathematics
标  题: 关于取火柴问题的解答
发信站: 南京大学小百合站 (Tue May  7 09:22:18 2002), 站内信件

题目1：    今有若干堆火柴，两人依次从中拿取，规定每次只能从一堆中取若干根，
可将一堆全取走，但不可不取，最后取完者为胜，求必胜的方法。

题目2：    今有若干堆火柴，两人依次从中拿取，规定每次只能从一堆中取若干根，
可将一堆全取走，但不可不取，最后取完者为负，求必胜的方法。

解答如下：

先解决第1题

定义1：若所有火柴数异或为0，则该状态被称为利他态，用字母T表示；否则，
为利己态，用S表示。

定理1：对任何S态，存在方法，从其中取一堆中的若干根，使状态变为T态。
引理1.1 ：A(i)为非副整数，i=1..n, 记c=A(1) xor A(2) xor ……  xor A(n),

若c>0,则存在A(t), A(t) xor c <A(t)
证明： 把c表示成二进制，记它的二进制数的最高位为第p位，
  则必然存在一个A(t),它二进制的第p位也是1。（否则，若所有的A(i)的第p位都是0，
c的第p位就也为0，矛盾！）
  x=a(t) xor c 的第p位将为1 xor 1,即0；
  又因为c的最高位为p，所以x高于p位的值不变。所以必有x<a(t).即a(t) xor 
c<a(t)
.
  命题得证。

再来证定理1.
证明：
 设共有n堆火柴，每堆的数目分别为A(i)，i=1..n，A(i)为非副整数.
 记c=A(1) xor A(2) xor ……  xor A(n),
 因为是S态，所以 c>0;
 所以存在A(t), A(t) xor c <A(t)。
 A(t)' = A(t) xor c <A(t)
  c' = A(1) xor A(2) xor …  xor A(t)' xor … xor A(n)
   = A(1) xor A(2) xor …  xor A(t) xor c xor … xor A(n)
   = A(1) xor A(2) xor …  xor A(t) xor … xor A(n) xor c
   = c xor c = 0
所以，用把第t堆由A(t)根取成A(t)' 根（A(t)' = A(t) xor c <A(t) )，状态成
为T态。
故命题成立。    #

定理2：T态，取任何一堆的若干根，都将成为S态。
证明：反证法：
  反设存在一堆，记为第m堆，从中取了若干根，根数由A(m)变为A(m)' .
  A(m)>A(m)' 状态均为T态。
  记c=A(1) xor A(2) xor … xor A(m) xor…  xor A(n),
  记c'=A(1) xor A(2) xor … xor A(m)' xor…  xor A(n),
  c=0;c'=0;
  所以有 0= A(1) xor A(2) xor … xor A(m) xor…  xor A(n)
= A(1) xor A(2) xor … xor A(m-1) xor A(m+1) xor… xor A(n) xor A(m)
= d xor A(m)
     d= A(1) xor A(2) xor … xor A(m-1) xor A(m+1) xor… xor A(n)
故 A(m)=d
        同理， d xor A(m)' =0
   A(m)'= d
  所以，A(m)'=A(m) . 矛盾！
  故反设不成立。原命题成立。 #

定理 3：S态，只要方法正确，必赢。
 最终胜利即由S态转变为T态，任何一个S态，只要把它变为T态，（由定理一，
可以把它变成T态。）对方只能把T态转变为S态(定理2)。这样，所有S态向T态的转变都可以
有己方控制，对方只能被动地实现由T态转变为S态。故S态必赢。 #
定理4：T态，只要对方法正确，必败。
 由定理3易得。


我们再来处理第2题。我们会发现两题会有一些相同之处，控制S->T态的人控制着
主动权
。经过分析，我们有以下结论：
定义2：若一堆中仅有1根火柴，则被称为孤单堆。若大于1根，则称为充裕堆。
定义3：T态中，若充裕堆的堆数大于等于2，则称为完全利他态，用T2表示；若充
裕堆的堆数等于0，则称为部分利他态，用T0表示。
定理4：不存在充裕堆数为1的T态。
证明：
 孤单堆的根数异或只会影响二进制的最后一位，但充裕堆会影响高位（非最后一位）。

 一个充裕堆，高位必有一位不为0，则所有根数异或不为0。故不会是T态。
定义4：S态中，若充裕堆的堆数大于等于2，则称为完全利己态，用S2表示；若充
裕堆的堆数等于1，则称为自主利己态，用S1表示; 若充裕堆的堆数等于0，则称为部分利
己态，用S0表示。

定理4：S0态，即仅有奇数个孤单堆，必败。T0态必胜。
证明：S0态，其实就是每次只能取一根。每次第奇数根都由己取，第偶数根都由对
方取，所以最后一根必己取。败。
  同理, T0态必胜#
定理5：S1态，只要方法正确，必胜。
证明：若此时孤单堆堆数为奇数，把充裕堆取完；否则，取成一根。
   这样，就变成奇数个孤单堆，由对方取。
   由定理4，对方必输。己必胜。 #
定理6：S2态不可转一次变为T0态。
证明：充裕堆数不可能一次由2变为0。得证。 #
定理7：S2态可一次转变为T2态。
证明：由定理1，S态可转变为T态，态可一次转变为T态
   又由定理6，S2态不可转一次变为T0态，
   所以转变的T态为T2态。 #
定理8：T2态，只能转变为S2态或S1态。
证明：. 由定理2，T态必然变为S态。
     由于充裕堆数不可能一次由2变为0，所以此时的S态不可能为S0态。
  命题得证。
定理9：S2态，只要方法正确，必胜.
证明：方法如下：
   1） S2态，就把它变为T2态。（由定理7）
   2） 对方只能T2转变成S2态或S1态(定理8)
  若转变为S2, 转向1）
  若转变为S1, 这己必胜。（定理5）
定理10：T2态必输。
证明：同9。
 综上所述，必输态有： T2,S0
     必胜态：   S2,S1,T0.
两题比较：
第一题的全过程其实如下：
 S2->T2->S2->T2-> …… ->T2->S1->T0->S0->T0->……->S0->T0(全0)
第二题的全过程其实如下：
 S2->T2->S2->T2-> …… ->T2->S1->S0->T0->S0->……->S0->T0(全0)
下划线表示胜利一方的取法。
    是否发现了他们的惊人相似之处。
我们不难发现(见加黑部分)，S1态可以转变为S0态（第二题做法），也可以转变为
T0（第一题做法）。哪一方控制了S1态，他即可以有办法使自己得到最后一根（转变为
T0）,也可以使对方得到最后一根（转变为S0）。
 所以，抢夺S1是制胜的关键！
 为此，始终把T2态让给对方，将使对方处于被动状态，他早晚将把状态变为S1.
(见定理9的证明).