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

輸入

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

　　輸出

　　輸出一個數即最小代價

　　Problem7射擊競賽

　　題目描述

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

　　輸入

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

　　輸出

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

　　Problem8任務安排

　　題目描述

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

　　輸入

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

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

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

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

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

　　輸出

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

　　Problem9最小差距

　　題目描述

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

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

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

　　輸入

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

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

　　輸出

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

　　二、 分治法

　　Problem1一元三次方程的解

　　題目描述

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

　　輸入

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

　　輸出

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

　　Problem2查找第k大元素

　　題目描述

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

　　輸入

　　輸入第一行為N、K，第二行有N個數

　　輸出

　　輸出第K大的數

　　Problem3麥森數

　　題目描述

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

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

　　輸入

　　輸入只包含一個整數P（1000<P<3100000）

　　輸出

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

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

　　Problem4逆序對個數

　　題目描述

　　給出一個數列{an}，如果存在i<j，但是a[i]>a[j]那么我們稱a[i]與a[j]是一對逆序對，現要求求出數列{an}中逆序對的個數

　　輸入

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

　　輸出

　　輸出僅一個數，即逆序對的個數

　　Problem5尋找最近點對

　　題目描述

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

　　輸入

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

　　輸出

　　輸出一個數，即最近點對的距離

　　Problem6剔除多余括號

　　題目描述

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

　　輸入

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

　　輸出

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

　　Problem7賽程安排

　　題目描述

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

　　輸入

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

　　輸出

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

　　三、 搜索算法

　　Problem1皇后問題

　　題目描述

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

　　輸入

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

　　輸出

　　輸出一個數，即總方案數

　　Problem2八數碼問題

　　題目描述

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

　　輸入

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

　　輸出

　　輸出最少的步數使初始方陣轉換為目標方陣，如果無解則輸出'No Solution'

　　Problem3拼圖

　　題目描述

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

　　輸入

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

　　輸出

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

　　Problem4質數方陣

　　題目描述

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

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

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

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

　　給定s,t求滿足要求的方陣數

　　輸入

　　輸入一行兩個數即s，t

　　輸出

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

　　Problem5埃及分數

　　題目描述

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

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

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

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

　　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行，對應每組測試數據，對于每組測試數據輸出若干個數，自小到大排列，依次是單位分數的分母。

　　Problem6字符串變換

　　題目描述

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

　　A1$ -> B1$

　　A2$ -> B2$

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

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

　　變換規則為：

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

　　則此時，A$ 可以經過一系列的變換變為 B$，其變換的過程為：

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

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

　　輸入

　　輸入格式如下：

　　A$ B$

　　A1$ B1$ \

　　A2$ B2$  |-> 變換規則

　　... ... /

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

　　輸出

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

　　Problem7聰明的打字員

　　題目描述

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

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

　　Swap0：按Swap0，光標位置不變，將光標所在位置的數字與錄入區的1號位置的數字（左起第一個數字）交換。如果光標已經處在錄入區的1號位置，則按Swap0鍵之后，錄入區的數字不變；

　　Swap1：按Swap1，光標位置不變，將光標所在位置的數字與錄入區的6號位置的數字（左起第六個數字）交換。如果光標已經處在錄入區的6號位置，則按Swap1鍵之后，錄入區的數字不變；

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

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

　　Left：按Left，光標左移一個位置，如果光標已經在錄入區的1號位置（左起第一個位置）上，則光標不動；

　　Right：按Right，光標右移一個位置，如果光標已經在錄入區的6號位置（左起第六個位置）上，則光標不動。

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

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

　　輸入

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

　　輸出

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

　　Problem8 01序列

　　題目描述

　　求指定長度滿足下列要求的序列的個數：

　　(1)全由01組成