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

輸入

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

　　輸出

　　輸出一個(gè)數(shù)即最小代價(jià)

　　Problem7射擊競(jìng)賽

　　題目描述

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

　　輸入

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

　　輸出

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

　　Problem8任務(wù)安排

　　題目描述

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

　　輸入

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

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

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

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

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

　　輸出

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

　　Problem9最小差距

　　題目描述

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

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

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

　　輸入

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

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

　　輸出

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

　　二、 分治法

　　Problem1一元三次方程的解

　　題目描述

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

　　輸入

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

　　輸出

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

　　Problem2查找第k大元素

　　題目描述

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

　　輸入

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

　　輸出

　　輸出第K大的數(shù)

　　Problem3麥森數(shù)

　　題目描述

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

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

　　輸入

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

　　輸出

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

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

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

　　題目描述

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

　　輸入

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

　　輸出

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

　　Problem5尋找最近點(diǎn)對(duì)

　　題目描述

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

　　輸入

　　輸入第一行為N，后面有N行，每行兩個(gè)數(shù)分別描述每個(gè)點(diǎn)的橫縱坐標(biāo)

　　輸出

　　輸出一個(gè)數(shù)，即最近點(diǎn)對(duì)的距離

　　Problem6剔除多余括號(hào)

　　題目描述

　　鍵盤輸入一個(gè)含有括號(hào)的四則運(yùn)算表達(dá)式，可能含有多余的括號(hào)，編程整理該表達(dá)式，去掉所有多余的括號(hào)，原表達(dá)式中所有變量和運(yùn)算符相對(duì)位置保持不變，并保持與原表達(dá)式等價(jià)。

　　輸入

　　輸入一行，即為表達(dá)式，長(zhǎng)度小于250

　　輸出

　　輸出也一行，為剔出多余括號(hào)之后的表達(dá)式

　　Problem7賽程安排

　　題目描述

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

　　輸入

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

　　輸出

　　輸出一個(gè)n階方陣A[1..N,0..N-1](表示比賽日程)，當(dāng)J＞0時(shí)，A[I,J]表示第I名運(yùn)動(dòng)員在第J天的比賽對(duì)手。

　　三、 搜索算法

　　Problem1皇后問題

　　題目描述

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

　　輸入

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

　　輸出

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

　　Problem2八數(shù)碼問題

　　題目描述

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

　　輸入

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

　　輸出

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

　　Problem3拼圖

　　題目描述

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

　　輸入

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

　　輸出

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

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

　　題目描述

　　求一個(gè)5*5的方陣，滿足如下要求：

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

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

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

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

　　輸入

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

　　輸出

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

　　Problem5埃及分?jǐn)?shù)

　　題目描述

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

　　如：2/3=1/2+1/6,但不允許2/3=1/3+1/3,因?yàn)榧訑?shù)中有相同的。

　　對(duì)于一個(gè)分?jǐn)?shù)a/b,表示方法有很多種，但是哪種最好呢？

　　首先，加數(shù)少的比加數(shù)多的好，其次，加數(shù)個(gè)數(shù)相同的，最小的分?jǐn)?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.

　　最好的是最后一種，因?yàn)?/18比1/180,1/45,1/30,1/180都大。

　　給出a,b(0〈a〈b〈1000),編程計(jì)算最好的表達(dá)方式。

　　輸入

　　輸入僅一行，即為N，表示有N組測(cè)試數(shù)據(jù)，每組測(cè)試數(shù)據(jù)為一行包含a,b(0〈a〈b〈1000)。

　　輸出

　　輸出N行，對(duì)應(yīng)每組測(cè)試數(shù)據(jù)，對(duì)于每組測(cè)試數(shù)據(jù)輸出若干個(gè)數(shù)，自小到大排列，依次是單位分?jǐn)?shù)的分母。

　　Problem6字符串變換

　　題目描述

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

　　A1$ -> B1$

　　A2$ -> B2$

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

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

　　變換規(guī)則為：

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

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

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

　　共進(jìn)行了三次變換，使得 A$ 變換為B$。

　　輸入

　　輸入格式如下：

　　A$ B$

　　A1$ B1$ \

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

　　... ... /

　　所有字符串長(zhǎng)度的上限為 20。

　　輸出

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

　　Problem7聰明的打字員

　　題目描述

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

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

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

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

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

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

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

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

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

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

　　輸入

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

　　輸出

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

　　Problem8 01序列

　　題目描述

　　求指定長(zhǎng)度滿足下列要求的序列的個(gè)數(shù)：

　　(1)全由01組成