信息學聯(lián)賽知識：基本程序題集(2)

輸入

　　輸入第一行為N(N<=1000)，第二行有N個整數(shù)，分別描述每個果子

　　輸出

　　輸出一個數(shù)即最小代價

　　Problem7射擊競賽

　　題目描述

　　射擊的目標是一個由R*C(2≤R≤C≤1000)個小方格組成的矩形網(wǎng)格。每一列恰有2個白色的小方格和R-2個黑色的小方格。行從頂至底編號為1-R，列從左至右編號為1-C。射擊者可射擊C次。在連續(xù)的C次射擊中，若每列恰好有一個白色的方格被射中，且不存在無白色方格被射中的行，這樣的射擊才是正確的。如果存在正確的射擊方法，則要求找到它。

　　輸入

　　輸入第一行為R，C，后面R行每行C個數(shù)，如果為0則為白格，1則為黑格

　　輸出

　　輸出正確方案--每行兩個數(shù)即射擊坐標，否則輸出-1

　　Problem8任務(wù)安排

　　題目描述

　　一家工廠的流水線正在生產(chǎn)一種產(chǎn)品，這需要兩種操作：操作A和操作B。每個操作只有一些機器能夠完成。A型機器從輸入庫接受工件，對其施加操作A，得到的中間產(chǎn)品存放在緩沖庫。B型機器從緩沖庫接受中間產(chǎn)品，對其施加操作B，得到的最終產(chǎn)品存放在輸出庫。所有的機器平行并且獨立地工作，每個庫的容量沒有限制。每臺機器的工作效率可能不同，一臺機器完成一次操作需要一定的時間。 給出每臺機器完成一次操作的時間，計算完成A操作的時間總和的最小值，和完成B操作的時間總和的最小值。

　　輸入

　　輸入第一行  三個用空格分開的整數(shù)：

　　N，工件數(shù)量 (1<=N<=1000)

　　M1，A型機器的數(shù)量 (1<=M1<=30)

　　M2，B型機器的數(shù)量 (1<=M2<=30)

　　第二行……，接下來M1個整數(shù)（表示A型機器完成一次操作的時間，1..20），接著是M2個整數(shù)（B型機器完成一次操作的時間，1..20）

　　輸出

　　只有一行。輸出兩個整數(shù)：完成所有A操作的時間總和的最小值，和完成所有B操作的時間總和的最小值（A操作必須在B操作之前完成）。

　　Problem9最小差距

　　題目描述

　　給定一些不同的一位數(shù)字，你可以從這些數(shù)字中選擇若干個，并將它們按一定順序排列，組成一個整數(shù)，把剩下的數(shù)字按一定順序排列，組成另一個整數(shù)。組成的整數(shù)不能以0開頭（除非這個整數(shù)只有1位）。

　　例如，給定6個數(shù)字，0,1,2,4,6,7，你可以用它們組成一對數(shù)10和2467，當然，還可以組成其他的很多對數(shù)，比如210和764，204和176。這些對數(shù)中兩個數(shù)差的絕對值最小的是204和176，為28。

　　給定N個不同的0~9之間的數(shù)字，請你求出用這些數(shù)字組成的每對數(shù)中，差的絕對值最小的一對（或多對）數(shù)的絕對值是多少？

　　輸入

　　輸入第一行包括一個數(shù)T（T≤1000），為測試數(shù)據(jù)的組數(shù)。

　　每組數(shù)據(jù)包括兩行，第一行為一個數(shù)N（2≤N≤10），表示數(shù)字的個數(shù)。下面一行為N個不同的一位數(shù)字。

　　輸出

　　輸出T行，每行一個數(shù)，表示第i個數(shù)據(jù)的答案。即最小的差的絕對值

　　二、 分治法

　　Problem1一元三次方程的解

　　題目描述

　　有形如：ax3+bx2+cx+d=0這樣的一個一元三次方程。給出該方程中各項的系數(shù)(a，b，c，d均為實數(shù))，并約定該方程存在三個不同實根(根的范圍在-100至100之間)，且根與根之差的絕對值>=1。要求由小到大依次在同一行輸出這三個實根(根與根之間留有空格)，并精確到小數(shù)點后4位。

　　輸入

　　輸入僅一行，有四個數(shù)，依次為a、b、c、d

　　輸出

　　輸出也只有一行，即三個根(從小到大輸出)

　　Problem2查找第k大元素

　　題目描述

　　有N個數(shù)，請找出其中第k大的數(shù)(N<=10000)

　　輸入

　　輸入第一行為N、K，第二行有N個數(shù)

　　輸出

　　輸出第K大的數(shù)

　　Problem3麥森數(shù)

　　題目描述

　　形如2^P-1的素數(shù)稱為麥森數(shù)，這時P一定也是個素數(shù)。但反過來不一定，即如果P是個素數(shù)，2^P-1不一定也是素數(shù)。到1998年底，人們已找到了37個麥森數(shù)。最大的一個是P=3021377，它有909526位。麥森數(shù)有許多重要應用，它與完全數(shù)密切相關(guān)。

　　任務(wù)：從文件中輸入P（1000<P<3100000），計算2^P-1的位數(shù)和最后500位數(shù)字（用十進制高精度數(shù)表示）

　　輸入

　　輸入只包含一個整數(shù)P（1000<P<3100000）

　　輸出

　　輸出第一行是十進制高精度數(shù)2^P-1的位數(shù)。

　　第2-11行：十進制高精度數(shù)2^P-1的最后500位數(shù)字。（每行輸出50位，共輸出10行，不足500位時高位補0）

　　Problem4逆序?qū)�個數(shù)

　　題目描述

　　給出一個數(shù)列{an}，如果存在i<j，但是a[i]>a[j]那么我們稱a[i]與a[j]是一對逆序?qū)�，現(xiàn)要求求出數(shù)列{an}中逆序?qū)Φ膫�數(shù)

　　輸入

　　輸入第一行為整數(shù)N(N<=10000)，第二行有N個數(shù)，即為數(shù)列{an}

　　輸出

　　輸出僅一個數(shù)，即逆序?qū)Φ膫�數(shù)

　　Problem5尋找最近點對

　　題目描述

　　給出平面內(nèi)的N(N<=10000)個點，點兩兩都有一個距離，現(xiàn)要求出所有點對中距離最小的那一對

　　輸入

　　輸入第一行為N，后面有N行，每行兩個數(shù)分別描述每個點的橫縱坐標

　　輸出

　　輸出一個數(shù)，即最近點對的距離

　　Problem6剔除多余括號

　　題目描述

　　鍵盤輸入一個含有括號的四則運算表達式，可能含有多余的括號，編程整理該表達式，去掉所有多余的括號，原表達式中所有變量和運算符相對位置保持不變，并保持與原表達式等價。

　　輸入

　　輸入一行，即為表達式，長度小于250

　　輸出

　　輸出也一行，為剔出多余括號之后的表達式

　　Problem7賽程安排

　　題目描述

　　有n個編號為1到n 的運動員參加某項運動的單循環(huán)比賽，即每個運動員要和所有其他運動員進行一次比賽。試為這n個運動員安排一個比賽日程，使得每個運動員每天只進行一場比賽，且整個比賽在n-1天內(nèi)結(jié)束。

　　輸入

　　輸入一行，即為運動員人數(shù)n(n<=10000)

　　輸出

　　輸出一個n階方陣A[1..N,0..N-1](表示比賽日程)，當J＞0時，A[I,J]表示第I名運動員在第J天的比賽對手。

　　三、 搜索算法

　　Problem1皇后問題

　　題目描述

　　在一N*N的棋盤中，擺上N個皇后，使其互不攻擊，有多少種擺法(皇后攻擊同行同列與同斜行的棋子)

　　輸入

　　輸入一行，即整數(shù)N(N<=10)

　　輸出

　　輸出一個數(shù)，即總方案數(shù)

　　Problem2八數(shù)碼問題

　　題目描述

　　有一個3*3的方陣，其中有8個數(shù)，一個方格為空，可以通過移動方格將初始的方陣移動成其他的方陣

　　輸入

　　輸入兩個3*3的方陣，即為初始狀態(tài)與目標狀態(tài)，0代表空的方格

　　輸出

　　輸出最少的步數(shù)使初始方陣轉(zhuǎn)換為目標方陣，如果無解則輸出'No Solution'

　　Problem3拼圖

　　題目描述

　　這個拼圖游戲要求將一些圖形拼成一個正方形，圖形的個數(shù)從1到5。圖形不能旋轉(zhuǎn)，拼的時候不能重疊，拼完后的正方形里面不能有隙。所有給定的圖形都要使用。

　　輸入

　　輸入第一行是一個整數(shù)n，表示圖形的個數(shù)，范圍從1到5。接下來有n個部分，每個部分的第一行是2個整數(shù)i和j，表示下面的i行j列用來描述一個圖形。圖形用0和1表示，1表示圖形占有這個置，0表示不占有，中間沒有空格。圖形的長與寬都不超過5。根據(jù)圖形給出的順序給每個圖形編號，從1開始，至多到5。保證數(shù)據(jù)無多解情況。

　　輸出

　　如果不能拼成一個正方形，就輸出"No solution possible"；否則，輸出一種拼的方案：一個正方形的數(shù)陣，每個位置上的數(shù)字是占有這個位置的圖形的編號，中間沒有空格。

　　Problem4質(zhì)數(shù)方陣

　　題目描述

　　求一個5*5的方陣，滿足如下要求：

　　(1)每行每列的數(shù)字和為s

　　(2)(1,1)上的數(shù)字為t

　　(3)每個橫行豎行斜行所形成的五位數(shù)都是質(zhì)數(shù)

　　給定s,t求滿足要求的方陣數(shù)

　　輸入

　　輸入一行兩個數(shù)即s，t

　　輸出

　　輸出第一行為方案數(shù)，接下來按序輸出所有方案(每個方案件都有一空行)

　　Problem5埃及分數(shù)

　　題目描述

　　在古埃及，人們使用單位分數(shù)的和(形如1/a的, a是自然數(shù))表示一切有理數(shù)。

　　如：2/3=1/2+1/6,但不允許2/3=1/3+1/3,因為加數(shù)中有相同的。

　　對于一個分數(shù)a/b,表示方法有很多種，但是哪種最好呢？

　　首先，加數(shù)少的比加數(shù)多的好，其次，加數(shù)個數(shù)相同的，最小的分數(shù)越大越好。如：

　　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組測試數(shù)據(jù)，每組測試數(shù)據(jù)為一行包含a,b(0〈a〈b〈1000)。

　　輸出

　　輸出N行，對應每組測試數(shù)據(jù)，對于每組測試數(shù)據(jù)輸出若干個數(shù)，自小到大排列，依次是單位分數(shù)的分母。

　　Problem6字符串變換

　　題目描述

　　已知有兩個字串 A$, B$ 及一組字串變換的規(guī)則（至多6個規(guī)則）:

　　A1$ -> B1$

　　A2$ -> B2$

　　規(guī)則的含義為：在 A＄中的子串 A1$ 可以變換為 B1$、A2$ 可以變換為 B2$ …。

　　例如：A$＝'abcd'　B$＝'xyz'

　　變換規(guī)則為：

　　'abc'->'xu'　'ud'->'y'　'y'->'yz'

　　則此時，A$ 可以經(jīng)過一系列的變換變?yōu)?B$，其變換的過程為：

　　'abcd'->'xud'->'xy'->'xyz'

　　共進行了三次變換，使得 A$ 變換為B$。

　　輸入

　　輸入格式如下：

　　A$ B$

　　A1$ B1$ \

　　A2$ B2$  |-> 變換規(guī)則

　　... ... /

　　所有字符串長度的上限為 20。

　　輸出

　　輸出最短步數(shù)，若在10步（包含 10步）以內(nèi)能將A$變換為B$，則輸出最少的變換步數(shù)；否則輸出"NO ANSWER!"

　　Problem7聰明的打字員

　　題目描述

　　阿蘭是某機密部門的打字員，她現(xiàn)在接到一個任務(wù)：需要在一天之內(nèi)輸入幾百個長度固定為6的密碼。當然，她希望輸入的過程敲擊鍵盤的總次數(shù)越少越好。

　　不幸的是，出于保密的需要，該部門用于輸入密碼的鍵盤是特殊設(shè)計的，鍵盤上沒有數(shù)字鍵，而只有以下六個鍵:Swap0,Swap1,Up, Down, Left, Right，為了說明這6個鍵的作用，我們先定義錄入?yún)^(qū)的6個位置的編號，從左至右依次為1，2，3，4，5，6。下面列出每個鍵的作用：

　　Swap0：按Swap0，光標位置不變，將光標所在位置的數(shù)字與錄入?yún)^(qū)的1號位置的數(shù)字（左起第一個數(shù)字）交換。如果光標已經(jīng)處在錄入?yún)^(qū)的1號位置，則按Swap0鍵之后，錄入?yún)^(qū)的數(shù)字不變；

　　Swap1：按Swap1，光標位置不變，將光標所在位置的數(shù)字與錄入?yún)^(qū)的6號位置的數(shù)字（左起第六個數(shù)字）交換。如果光標已經(jīng)處在錄入?yún)^(qū)的6號位置，則按Swap1鍵之后，錄入?yún)^(qū)的數(shù)字不變；

　　Up：按Up，光標位置不變，將光標所在位置的數(shù)字加1（除非該數(shù)字是9）。例如，如果光標所在位置的數(shù)字為2，按Up之后，該處的數(shù)字變?yōu)?；如果該處數(shù)字為9，則按Up之后，數(shù)字不變，光標位置也不變；

　　Down：按Down，光標位置不變，將光標所在位置的數(shù)字減1（除非該數(shù)字是0），如果該處數(shù)字為0，則按Down之后，數(shù)字不變，光標位置也不變；

　　Left：按Left，光標左移一個位置，如果光標已經(jīng)在錄入?yún)^(qū)的1號位置（左起第一個位置）上，則光標不動；

　　Right：按Right，光標右移一個位置，如果光標已經(jīng)在錄入?yún)^(qū)的6號位置（左起第六個位置）上，則光標不動。

　　當然，為了使這樣的鍵盤發(fā)揮作用，每次錄入密碼之前，錄入?yún)^(qū)總會隨機出現(xiàn)一個長度為6的初始密碼，而且光標固定出現(xiàn)在1號位置上。當巧妙地使用上述六個特殊鍵之后，可以得到目標密碼，這時光標允許停在任何一個位置。

　　現(xiàn)在，阿蘭需要你的幫助，編寫一個程序，求出錄入一個密碼需要的最少的擊鍵次數(shù)。

　　輸入

　　輸入一行，含有兩個長度為6的數(shù)，前者為初始密碼，后者為目標密碼，兩個密碼之間用一個空格隔開。

　　輸出

　　輸出僅一行，含有一個正整數(shù)，為最少需要的擊鍵次數(shù)。

　　Problem8 01序列

　　題目描述

　　求指定長度滿足下列要求的序列的個數(shù)：

　　(1)全由01組成