精校word版---2002年第14届国际信息学奥赛试题

2002年第14届国际信息学奥赛试题解析韩 国第一题 成古利青蛙Day 1. a gameIn Korea, the naughtiness of the cheonggaeguri, a small frog, is legendary, This is a well-deserved reputation, because the frogs jump through your rice paddy at night, flattening rice plants. In the morning, after noting which plants have been flattened, you want to identify the path of the frog which did the most dam age. A frog always jumps through the paddy in a straight line, with every hop the same length:Your rice paddy has plants arranged on the intersection points of a grid as shown in Figure-1, and the troublesome frogs hop completely through your paddy, starting outside the paddy on one side and ending outside the paddy on the other side as shown in Figure-2:Many frogs can jump through the paddy, hopping from rice plant to rice plant, Every hop lands on a plant and flattens it, as in Figure-3. Note that some plants may be landed on by more than one frog during the night. Of course, you can not see the lines showing the paths of the frogs or any of their hops outside of your paddy-for the situation in Figure-3. what you can see is shown in Figure-4:From Figure-4, you can reconstruct all the possible paths which the frogs may have followed across your paddy. You are only interested in frogs which have landed on at least 3 of your rice plants in their voyage through the paddy. Such a path is said to be frog path. In this case, that means that the three paths shown in Figure-3 are frog paths（there are also other possible frog paths）. The vertical path down column 1 might have been a frog path with hop length 4 except there are only 2 plants flattened so we are not interested; and the diagonal path including the plants on row 2 col. 3, row 3 col. 4, and row 6 col. 7 has three flat plants but there is no regular hop length which could have spaced the hops in this way while still landing on at least 3 plants, and hence it is not a frog path. Note also that along the line a frog path follows there may be additional flattened plants which do not need to be landed on by that path(see the plant at (2,6) on the horizontal path across row 2 in Figure-4), and in fact some flattened plants may not be explained by any frog path at all.Your task is to write a program to determine the maximum number of landing in any single frog path（where the maximum is taken over all possible frog paths）. In Figure-4 the answer is 7, obtained from the frog path across row 6.INPUTYour program is to read from standard input. The first line contains two integers R and C, respectively the number of rows and columns in your rice paddy, 1R，C5000. The second line contains the single integer N, the number of flat-tenedrice plants, 3N5000. Each of the remaining N lines contains two intergers, the row number （1row numberR） and the column number（1column numberC）of a flattened rice plant, separated by one blank. Each flattened plant is only listed once.OUTPUTYour program is to write to standard output. The output contains one line with a single integer, the number of plants flattened along a frog path which did the most damage if there exists at least on frog path, otherwise, 0.EXAMPLE INPUTS AND OUTPUTSExample 1: input output(the example of Figure -4)6 7142 16 64 22 52 62 73 46 16 22 36 36 46 56 77Example 2: input（the example of Figure -5）6 7181 16 23 51 54 71 21 41 61 72 12 32 64 24 44 55 46 55 6output 4SCORINGIf your program outputs the correct answer for a test case within the time limit, then you get full points for the test case, and otherwise you get 0 points.参考译文：（day 1文件名frog. *内存限制：64MB，时间限制2s）问题描述：在韩国，成古利（一种小青蛙）的顽皮是众所皆知的，且名符其实，因为这种青蛙在晚上一路跳跃过你的稻田，并踩平稻作物。在早上，看过被踩平的稻作物后，你要找出造成最 大伤害的那条青蛙踩过的路径。青蛙永远以直线跳跃过稻田 每个跳跃的长度皆相同如Figure1所示，稻作物种在格子点上。如Figure2所示，麻烦的青蛙由稻田的一侧跳入，一路跳跃至稻田的另一侧离开。青蛙从一株稻作物跳跃到另一株稻作物，如Figure3所示，每一个跳跃踩平所处之稻作物。请注意：有些稻作物可能被一只以上的青蛙踩平过。以Figure3为例，你无法看到稻田外之青蛙跳跃路径。Figure3为你所观察到的现象。从Figure4，你将可以重建青蛙跳跃过的所有可能路径。你有兴趣的路径应该至少有3株稻作物被踩平，这种路径叫做青蛙路径。Figure3标示的三个路径口是青蛙路径（当然也有可能还有其他的青蛙路径）。例如，我们对第一行上的路径没有兴趣，因灾此路径只有2株稻作物被踩平（跳跃长度是4），另外跳跃过（列2行3），（列3行4）及（列6行7）之斜角路径，虽然有二株稻作物被踩平，但因为跳跃长度并不规则，所以不是合法路径。请注意，有些踏平的稻作物无法由任何青蛙路径来解释，如Figure 4内第二列中踏平之踩作物可以为一个青蛙路径掺杂其他原因所踏平之稻作物，如（列2行6）之稻作物。你的任务是写一个程序在所有可能的青蛙路径中，找到具有被踩平最多稻作物之所属的青蛙路径（即引起稻作物最大伤害）。在Figure 4中列6中之青蛙路径，产生答案7。输入：你的程序将由标准输入读入。第一行包括两个整数R和C，分别是你的稻田的列和行数，1<=R,c<=5000。第二行包括单一个整数N，其为被踩平稻作的个数，3< = N < = 5000。剩下的N行，每行包括两个整数，即为被踩平稻作物的列号码（1< = 列号码 < = R）和行号码（1 < = 行号码< = C），用一个空白间隔。每株被踩平的稻作物只列出一次。输出：你的程序将写到标准输出。输出单一个整数在一行。如果存在任何合法之青蛙路径，找出具有最大伤害之青蛙路径，并输出此青蛙路径所属的踩平之稻作物数；否则输出0。输入输出样例：样例1：（图四的例子）frog. in6 7142 16 64 22 5