一个ACM试题(200分)

Problem B : Kasperkey
Time Limit: 1000 MS Memory Limit: 65536 K
Description
In computers, a virus is a program or programming code that replicates by being copied or initiating its copying to another program, computer boot sector ordo
cument. Viruses can be transmitted as attachments to an e-mail note or in ado
wnloaded file, or be present on a diskette or CD. The immediate source of the e-mail note,do
wnloaded file, or diskette you've received is usually unaware that it contains a virus. Some viruses wreak their effect as soon as their code is executed;
other viruses liedo
rmant until circumstances cause their code to be executed by the computer. Some viruses are benign or playful in intent and effect ("Happy Birthday, asky007!") and some can be quite harmful, erasing data or causing your hard disk to require reformatting. A virus that replicates itself by resending itself as an e-mail attachment or as part of a network message is known as a worm.
To protect their system from virus, people usually install Anti-Virus softwares.This is a big problem to asky007. He likes Kaspersky Anti-Virus ,but it costs too mush computer resource. Unfortunately, asky007's CPU is PIII 433, and it is impossible to run Kaspersky. So , asky007 wants to develop a Anti-Virus software, he calls it Kasperkey.
When asky007 tests Kasperkey, he finds a new problem. Some viruses use a technical name 'olymorphic code' to let AV can't find them. Viruses can be change their code in different times.For example , a virus'code is 'asky007' now and may be '007asky' an hour later.Thank Godness! Asky007 finds a rule. He captures the virus two times, and marks the shadinesses.For example , it is :


ID Shadiness
The First Time The Second Time
1 1 111
2 10111 10
3 10 0





The rule is if you make a sequence use the ID, the shadiness of two times may be same.Just like '2113'. The first time 's Shadiness become '101111110', sodo
the second time. Now, you can say it is a virus. If can's find a such sequence or the shadiness's length is bigger than 100, you can suppose it can't be a virus.

Input
The first line of the input file contains the number N , the number of IDs, then
followed by 2N lines.The first N lines mean the first time's shadiness, and then
the second.Process to the end of file.
Process to the end of file.

Input
The first line of the input file contains the number N , the number of IDs, then
followed by 2N lines.The first N lines mean the first time's shadiness, and then
the second.Process to the end of file.
Process to the end of file.

Output
If it exists some sequence descripted above, output the shortest ID sequence;
otherwise output “It is not a virus.” In one line.

Sample Input
3
1
10111
10
111
10
0
3
10
10111
1
111
10
0
Sample Output
2113
It is not a virus.

你不会不懂这段英文吧？

典型的ACM题目。。。前面两大段都是废话

直接深度优先搜索应该可以吧。
ID数据类型是
IDType = record
Len1, Len2 : integer;
//1st Time & 2nd Time length
Seq1, Seq2 : string;
//1st Time & 2nd Time sequence
end;
ID : Array [1..1000] of IDType;
结点类型是
NodeType = record
ID:integer;
//当前选取的ID数字
SeqLen1, SeqLen2 : integer;
//当前已生成序列1与序列2的长度
Seq1, Seq2 : string;
//当前已经生成的序列1与序列2
end;
Node : array [0..101] of NodeType;
大致算法就是：
1. Node[0] := (0,0,0,'','');
P:=1;
2. while p>0do

2.1 inc(Node[p].ID);
IDNUM := Node[p].ID;
Node[p].seqlen1 = Node[p-1].seqlen1+ID[IDNUM].len1;
Node[p].seqlen2 = Node[p-1].seqlen2+ID[IDNUM].len2;
Node[p].seq1 = Node[p-1].seq1+ID[IDNUM].seq1;
Node[p].seq2 = Node[p-1].seq2+ID[IDNUM].seq2;
2.2 len = min(Node[p].seqlen1, Node[p].seqlen2);
//min函数应返回两个参数中的最小值； （我忘了delphi中有没有这个函数了。。。。）
2.3 if left(Node[p].seq1, len) = left(Node[p].seq2, len) and (Node[p].seqlen1 <= 100) and (Node[p].seqlen2 <= 100) then

2.3.1 if Node[p].seqlen1 = Node[p].seqlen2 then
算法结束，打印结果;
2.3.2 inc(p);
Node[p].ID := 0;
2.4 else
if IDNUM > N then
dec(p);
3 end;
//goto 2
4 输出无解
==========
随便写的，大致意思应该表达清楚了

哦， 看漏了， 是要求 output the shortest ID sequence. 那么2.3.1那里就不要直接输出，改为比较是否shorter的结果，如果是就记录结果。在4那里输出

谢谢