信息学集训队作业tixVIP

1、题目来源： USACO Open 2002者：情况：搜索可以解决一些数据理由： 不知道可不可以用动态规划，即使是 NP，搜索优化也是一个值得。PROBLEM 3: Circus Tickets Gadnell & Backmolstad, 1997Farmer John is taking 16 cows to see the three ring circus.Being cows,they are seatedhe cow section, a 4x4 set of seats near the front ofthe audience.The seats, rows, and colum

2、ns are numbered thusly:col 1col 3| col 2 | col 4| 15913|261014371115481216- row 1- row 2- row 3- row 4The cows are herded helter-skeltero the seats.It is only after theyare seatedt they check their tickets.In a revelationt willsurprise no one, they are not nesarilyhe proper seats.The layoutof the co

3、w seating icht they can rearrange themselves only byroing a row right or left or roing a column up or down.The exlesbelow show all four operations appproper seating shown above:d to therow or column of the4162738259361047118129678111216131415Rot row 1 rightRot row 1 leftRot col 1 upRot col 1 downGiv

4、en the initial seating arrangement of the cows, determine a very goodset of roions to rearrange cows sot their tickets and seat numbersmatch.east one solution always exists.Your score for each test case will depend on how close you get to the bestnumber of roionbmitted by other contestants fort case

5、.Youroutput sequence must be shortercredit for this problem.n 500 operations in order to receiveH: The sequence 1l 1l 1l 4u 1r 4d 1l 1l 4u 1r 4u 4u 4u swaps the upperleft cow with the cow to her right.PROBLEM NAME: tixINPUT FORMAT:Four lines, each with four spaeparatedegers.Line 1 is therow; line 2

6、is the second row; and so on.SLE INPUT (file tix.in):4 1 2 36 7 8 510 11 12 914 15 16 13OUTPUT FORMAT:A series of output linest contahe ordered sequence of roionst will arrange the cows.Each line contains a row or column number(1.4) followed by a space followed by a lower-case lettert indicatesthe o

7、peration to be performed: r for roe a row right, l for roea row left, u for roe a column up, and d for roe a column down.SLE OUTPUT (file tix.out):lrrrOther correct sequenpos.are equally valid though might not garner as many马戏团入场券Gadnell & Backmolstad, 1997Farmer John 要带 16 只母牛去看杂技，母牛们将坐在观众前附近的一个 4x

8、4 座的牛区。所有座位、行、图标上数字。1 列3 列| 159132 列 |4 列|261014371115481216- 1 行- 2 行- 3 行- 4 行母牛们随机坐在位置上，等它们坐下之后才进行检票。很明显，它们没有必要坐在合适的位置上，位置已被设计成可以左右转一行或上下转一列。下面的例子说明了由上面的状态经过4 种转动操作所到达的目标状态。4162738259361047118129678111216下转第 1 列131415右转第 1 行左转第 1 行上转第 1 列给定牛的原始位置，用较少的旋转次数将牛重排，使得他们的入场券与座位号相符。无论原始位置如何，总有至少一种可行方案。你的每个测试点的成绩取决于你的方案与所有选手的最优方案的接近程度。你的输出序列必须少于 500 个操作。提示：序列 1l 1l 1l 4u 1r 4d 1l 1l 4u 1r 4u 4u 4u 交换了左上角的牛与它右边的牛。程序名：tix输入格式：4 行，每行 4 个数一行是坐在第一行的牛，第二行是坐在第二行的牛等等。输入样例(tix.in)：4 1 2 36 7