信息學(xué)聯(lián)賽知識：基本程序題集(2)
2009-11-12 23:03:50網(wǎng)絡(luò )
輸入
輸入第一行為N(N<=1000)，第二行有N個(gè)整數，分別描述每個(gè)果子
輸出
輸出一個(gè)數即最小代價(jià)
Problem7射擊競賽
題目描述
射擊的目標是一個(gè)由R*C(2≤R≤C≤1000)個(gè)小方格組成的矩形網(wǎng)格。每一列恰有2個(gè)白色的小方格和R-2個(gè)黑色的小方格。行從頂至底編號為1-R，列從左至右編號為1-C。射擊者可射擊C次。在連續的C次射擊中，若每列恰好有一個(gè)白色的方格被射中，且不存在無(wú)白色方格被射中的行，這樣的射擊才是正確的。如果存在正確的射擊方法，則要求找到它。
輸入
輸入第一行為R，C，后面R行每行C個(gè)數，如果為0則為白格，1則為黑格
輸出
輸出正確方案--每行兩個(gè)數即射擊坐標，否則輸出-1
Problem8任務(wù)安排
題目描述
一家工廠(chǎng)的流水線(xiàn)正在生產(chǎn)一種產(chǎn)品，這需要兩種操作：操作A和操作B。每個(gè)操作只有一些機器能夠完成。A型機器從輸入庫接受工件，對其施加操作A，得到的中間產(chǎn)品存放在緩沖庫。B型機器從緩沖庫接受中間產(chǎn)品，對其施加操作B，得到的最終產(chǎn)品存放在輸出庫。所有的機器平行并且獨立地工作，每個(gè)庫的容量沒(méi)有限制。每臺機器的工作效率可能不同，一臺機器完成一次操作需要一定的時(shí)間。 給出每臺機器完成一次操作的時(shí)間，計算完成A操作的時(shí)間總和的最小值，和完成B操作的時(shí)間總和的最小值。
輸入
輸入第一行 三個(gè)用空格分開(kāi)的整數：
N，工件數量 (1<=N<=1000)
M1，A型機器的數量 (1<=M1<=30)
M2，B型機器的數量 (1<=M2<=30)
第二行……，接下來(lái)M1個(gè)整數（表示A型機器完成一次操作的時(shí)間，1..20），接著(zhù)是M2個(gè)整數（B型機器完成一次操作的時(shí)間，1..20）
輸出
只有一行。輸出兩個(gè)整數：完成所有A操作的時(shí)間總和的最小值，和完成所有B操作的時(shí)間總和的最小值（A操作必須在B操作之前完成）。
Problem9最小差距
題目描述
給定一些不同的一位數字，你可以從這些數字中選擇若干個(gè)，并將它們按一定順序排列，組成一個(gè)整數，把剩下的數字按一定順序排列，組成另一個(gè)整數。組成的整數不能以0開(kāi)頭（除非這個(gè)整數只有1位）。
例如，給定6個(gè)數字，0,1,2,4,6,7，你可以用它們組成一對數10和2467，當然，還可以組成其他的很多對數，比如210和764，204和176。這些對數中兩個(gè)數差的絕對值最小的是204和176，為28。
給定N個(gè)不同的0~9之間的數字，請你求出用這些數字組成的每對數中，差的絕對值最小的一對（或多對）數的絕對值是多少？
輸入
輸入第一行包括一個(gè)數T（T≤1000），為測試數據的組數。
每組數據包括兩行，第一行為一個(gè)數N（2≤N≤10），表示數字的個(gè)數。下面一行為N個(gè)不同的一位數字。
輸出
輸出T行，每行一個(gè)數，表示第i個(gè)數據的答案。即最小的差的絕對值
二、 分治法
Problem1一元三次方程的解
題目描述
有形如：ax3+bx2+cx+d=0這樣的一個(gè)一元三次方程。給出該方程中各項的系數(a，b，c，d均為實(shí)數)，并約定該方程存在三個(gè)不同實(shí)根(根的范圍在-100至100之間)，且根與根之差的絕對值>=1。要求由小到大依次在同一行輸出這三個(gè)實(shí)根(根與根之間留有空格)，并精確到小數點(diǎn)后4位。
輸入
輸入僅一行，有四個(gè)數，依次為a、b、c、d
輸出
輸出也只有一行，即三個(gè)根(從小到大輸出)
Problem2查找第k大元素
題目描述
有N個(gè)數，請找出其中第k大的數(N<=10000)
輸入
輸入第一行為N、K，第二行有N個(gè)數
輸出
輸出第K大的數
Problem3麥森數
題目描述
形如2^P-1的素數稱(chēng)為麥森數，這時(shí)P一定也是個(gè)素數。但反過(guò)來(lái)不一定，即如果P是個(gè)素數，2^P-1不一定也是素數。到1998年底，人們已找到了37個(gè)麥森數。最大的一個(gè)是P=3021377，它有909526位。麥森數有許多重要應用，它與完全數密切相關(guān)。
任務(wù)：從文件中輸入P（1000<P<3100000），計算2^P-1的位數和最后500位數字（用十進(jìn)制高精度數表示）
輸入
輸入只包含一個(gè)整數P（1000<P<3100000）
輸出
輸出第一行是十進(jìn)制高精度數2^P-1的位數。
第2-11行：十進(jìn)制高精度數2^P-1的最后500位數字。（每行輸出50位，共輸出10行，不足500位時(shí)高位補0）
Problem4逆序對個(gè)數
題目描述
給出一個(gè)數列{an}，如果存在i<j，但是a[i]>a[j]那么我們稱(chēng)a[i]與a[j]是一對逆序對，現要求求出數列{an}中逆序對的個(gè)數
輸入
輸入第一行為整數N(N<=10000)，第二行有N個(gè)數，即為數列{an}
輸出
輸出僅一個(gè)數，即逆序對的個(gè)數
Problem5尋找最近點(diǎn)對
題目描述
給出平面內的N(N<=10000)個(gè)點(diǎn)，點(diǎn)兩兩都有一個(gè)距離，現要求出所有點(diǎn)對中距離最小的那一對
輸入
輸入第一行為N，后面有N行，每行兩個(gè)數分別描述每個(gè)點(diǎn)的橫縱坐標
輸出
輸出一個(gè)數，即最近點(diǎn)對的距離
Problem6剔除多余括號
題目描述
鍵盤(pán)輸入一個(gè)含有括號的四則運算表達式，可能含有多余的括號，編程整理該表達式，去掉所有多余的括號，原表達式中所有變量和運算符相對位置保持不變，并保持與原表達式等價(jià)。
輸入
輸入一行，即為表達式，長(cháng)度小于250
輸出
輸出也一行，為剔出多余括號之后的表達式
Problem7賽程安排
題目描述
有n個(gè)編號為1到n 的運動(dòng)員參加某項運動(dòng)的單循環(huán)比賽，即每個(gè)運動(dòng)員要和所有其他運動(dòng)員進(jìn)行一次比賽。試為這n個(gè)運動(dòng)員安排一個(gè)比賽日程，使得每個(gè)運動(dòng)員每天只進(jìn)行一場(chǎng)比賽，且整個(gè)比賽在n-1天內結束。
輸入
輸入一行，即為運動(dòng)員人數n(n<=10000)
輸出
輸出一個(gè)n階方陣A[1..N,0..N-1](表示比賽日程)，當J＞0時(shí)，A[I,J]表示第I名運動(dòng)員在第J天的比賽對手。
三、 搜索算法
Problem1皇后問(wèn)題
題目描述
在一N*N的棋盤(pán)中，擺上N個(gè)皇后，使其互不攻擊，有多少種擺法(皇后攻擊同行同列與同斜行的棋子)
輸入
輸入一行，即整數N(N<=10)
輸出
輸出一個(gè)數，即總方案數
Problem2八數碼問(wèn)題
題目描述
有一個(gè)3*3的方陣，其中有8個(gè)數，一個(gè)方格為空，可以通過(guò)移動(dòng)方格將初始的方陣移動(dòng)成其他的方陣
輸入
輸入兩個(gè)3*3的方陣，即為初始狀態(tài)與目標狀態(tài)，0代表空的方格
輸出
輸出最少的步數使初始方陣轉換為目標方陣，如果無(wú)解則輸出'No Solution'
Problem3拼圖
題目描述
這個(gè)拼圖游戲要求將一些圖形拼成一個(gè)正方形，圖形的個(gè)數從1到5。圖形不能旋轉，拼的時(shí)候不能重疊，拼完后的正方形里面不能有隙。所有給定的圖形都要使用。
輸入
輸入第一行是一個(gè)整數n，表示圖形的個(gè)數，范圍從1到5。接下來(lái)有n個(gè)部分，每個(gè)部分的第一行是2個(gè)整數i和j，表示下面的i行j列用來(lái)描述一個(gè)圖形。圖形用0和1表示，1表示圖形占有這個(gè)置，0表示不占有，中間沒(méi)有空格。圖形的長(cháng)與寬都不超過(guò)5。根據圖形給出的順序給每個(gè)圖形編號，從1開(kāi)始，至多到5。保證數據無(wú)多解情況。
輸出
如果不能拼成一個(gè)正方形，就輸出"No solution possible"；否則，輸出一種拼的方案：一個(gè)正方形的數陣，每個(gè)位置上的數字是占有這個(gè)位置的圖形的編號，中間沒(méi)有空格。
Problem4質(zhì)數方陣
題目描述
求一個(gè)5*5的方陣，滿(mǎn)足如下要求：
(1)每行每列的數字和為s
(2)(1,1)上的數字為t
(3)每個(gè)橫行豎行斜行所形成的五位數都是質(zhì)數
給定s,t求滿(mǎn)足要求的方陣數
輸入
輸入一行兩個(gè)數即s，t
輸出
輸出第一行為方案數，接下來(lái)按序輸出所有方案(每個(gè)方案件都有一空行)
Problem5埃及分數
題目描述
在古埃及，人們使用單位分數的和(形如1/a的, a是自然數)表示一切有理數。
如：2/3=1/2+1/6,但不允許2/3=1/3+1/3,因為加數中有相同的。
對于一個(gè)分數a/b,表示方法有很多種，但是哪種最好呢？
首先，加數少的比加數多的好，其次，加數個(gè)數相同的，最小的分數越大越好。如：
19/45=1/3 + 1/12 + 1/180
19/45=1/3 + 1/15 + 1/45
19/45=1/3 + 1/18 + 1/30,
19/45=1/4 + 1/6 + 1/180
19/45=1/5 + 1/6 + 1/18.
最好的是最后一種，因為1/18比1/180,1/45,1/30,1/180都大。
給出a,b(0〈a〈b〈1000),編程計算最好的表達方式。
輸入
輸入僅一行，即為N，表示有N組測試數據，每組測試數據為一行包含a,b(0〈a〈b〈1000)。
輸出
輸出N行，對應每組測試數據，對于每組測試數據輸出若干個(gè)數，自小到大排列，依次是單位分數的分母。
Problem6字符串變換
題目描述
已知有兩個(gè)字串 A$, B$ 及一組字串變換的規則（至多6個(gè)規則）:
A1$ -> B1$
A2$ -> B2$
規則的含義為：在 A＄中的子串 A1$ 可以變換為 B1$、A2$ 可以變換為 B2$ …。
例如：A$＝'abcd' B$＝'xyz'
變換規則為：
'abc'->'xu' 'ud'->'y' 'y'->'yz'
則此時(shí)，A$ 可以經(jīng)過(guò)一系列的變換變?yōu)?B$，其變換的過(guò)程為：
'abcd'->'xud'->'xy'->'xyz'
共進(jìn)行了三次變換，使得 A$ 變換為B$。
輸入
輸入格式如下：
A$ B$
A1$ B1$ \
A2$ B2$ |-> 變換規則
... ... /
所有字符串長(cháng)度的上限為 20。
輸出
輸出最短步數，若在10步（包含 10步）以?xún)饶軐$變換為B$，則輸出最少的變換步數；否則輸出"NO ANSWER!"
Problem7聰明的打字員
題目描述
阿蘭是某機密部門(mén)的打字員，她現在接到一個(gè)任務(wù)：需要在一天之內輸入幾百個(gè)長(cháng)度固定為6的密碼。當然，她希望輸入的過(guò)程敲擊鍵盤(pán)的總次數越少越好。
不幸的是，出于保密的需要，該部門(mén)用于輸入密碼的鍵盤(pán)是特殊設計的，鍵盤(pán)上沒(méi)有數字鍵，而只有以下六個(gè)鍵:Swap0,Swap1,Up, Down, Left, Right，為了說(shuō)明這6個(gè)鍵的作用，我們先定義錄入區的6個(gè)位置的編號，從左至右依次為1，2，3，4，5，6。下面列出每個(gè)鍵的作用：
Swap0：按Swap0，光標位置不變，將光標所在位置的數字與錄入區的1號位置的數字（左起第一個(gè)數字）交換。如果光標已經(jīng)處在錄入區的1號位置，則按Swap0鍵之后，錄入區的數字不變；
Swap1：按Swap1，光標位置不變，將光標所在位置的數字與錄入區的6號位置的數字（左起第六個(gè)數字）交換。如果光標已經(jīng)處在錄入區的6號位置，則按Swap1鍵之后，錄入區的數字不變；
Up：按Up，光標位置不變，將光標所在位置的數字加1（除非該數字是9）。例如，如果光標所在位置的數字為2，按Up之后，該處的數字變?yōu)?；如果該處數字為9，則按Up之后，數字不變，光標位置也不變；
Down：按Down，光標位置不變，將光標所在位置的數字減1（除非該數字是0），如果該處數字為0，則按Down之后，數字不變，光標位置也不變；
Left：按Left，光標左移一個(gè)位置，如果光標已經(jīng)在錄入區的1號位置（左起第一個(gè)位置）上，則光標不動(dòng)；
Right：按Right，光標右移一個(gè)位置，如果光標已經(jīng)在錄入區的6號位置（左起第六個(gè)位置）上，則光標不動(dòng)。
當然，為了使這樣的鍵盤(pán)發(fā)揮作用，每次錄入密碼之前，錄入區總會(huì )隨機出現一個(gè)長(cháng)度為6的初始密碼，而且光標固定出現在1號位置上。當巧妙地使用上述六個(gè)特殊鍵之后，可以得到目標密碼，這時(shí)光標允許停在任何一個(gè)位置。
現在，阿蘭需要你的幫助，編寫(xiě)一個(gè)程序，求出錄入一個(gè)密碼需要的最少的擊鍵次數。
輸入
輸入一行，含有兩個(gè)長(cháng)度為6的數，前者為初始密碼，后者為目標密碼，兩個(gè)密碼之間用一個(gè)空格隔開(kāi)。
輸出
輸出僅一行，含有一個(gè)正整數，為最少需要的擊鍵次數。
Problem8 01序列
題目描述
求指定長(cháng)度滿(mǎn)足下列要求的序列的個(gè)數：
(1)全由01組成
