信息學集訓隊作業(yè)tix

1、題目來源： USACO Open 2002者：情況：搜索可以解決一些數(shù)據(jù)理由： 不知道可不可以用動態(tài)規(guī)劃，即使是 NP，搜索優(yōu)化也是一個值得。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 座的牛區(qū)。所有座位、行、圖標上數(shù)字。1 列3 列| 159132 列 |4 列|261014371115481216- 1 行- 2 行- 3 行- 4 行母牛們隨機坐在位置上，等它們坐下之后才進行檢票。很明顯，它們沒有必要坐在合適的位置上，位置已被設計成可以左右轉(zhuǎn)一行或上下轉(zhuǎn)一列。下面的例子說明了由上面的狀態(tài)經(jīng)過4 種轉(zhuǎn)動操作所到達的目標狀態(tài)。4162738259361047118129678111216下轉(zhuǎn)第 1 列131415右轉(zhuǎn)第 1 行左轉(zhuǎn)第 1 行上轉(zhuǎn)第 1 列給定牛的原始位置，用較少的旋轉(zhuǎn)次數(shù)將牛重排，使得他們的入場券與座位號相符。無論原始位置如何，總有至少一種可行方案。你的每個測試點的成績?nèi)Q于你的方案與所有選手的最優(yōu)方案的接近程度。你的輸出序列必須少于 500 個操作。提示：序列 1l 1l 1l 4u 1r 4d 1l 1l 4u 1r 4u 4u 4u 交換了左上角的牛與它右邊的牛。程序名：tix輸入格式：4 行，每行 4 個數(shù)一行是坐在第一行的牛，第二行是坐在第二行的牛等等。輸入樣例(tix.in)：4 1 2 36 7