NOIP 2009 全國青少年信息學奧林匹克聯賽普及組複賽試題

1．多項式輸出

(poly.pas/c/cpp)

【問題描述】

一元 n 次多項式可用如下的表達式表示：

1 0

1

1 f (x) a x a xn … a x a

n

n

n = + − + + +

− ， ≠ 0 n a

其中，

i

i a x 稱為i 次項， i a 稱為i 次項的係數。給出一個一元多項式各項的次數和系

數，請按照如下規定的格式要求輸出該多項式：

1. 多項式中自變量為x，從左到右按照次數遞減順序給出多項式。

2. 多項式中只包含係數不為0 的項。

3. 如果多項式n 次項係數為正，則多項式開頭不出現「+」號，如果多項式n 次項系

數為負，則多項式以「-」號開頭。

4. 對於不是最高次的項，以「+」號或者「-」號連接此項與前一項，分別表示此項

係數為正或者係數為負。緊跟一個正整數，表示此項係數的絕對值（如果一個高於0 次的項，

其係數的絕對值為1，則無需輸出1）。如果x 的指數大於1，則接下來緊跟的指數部分的形

式為「x^b」，其中b 為x 的指數；如果x 的指數為1，則接下來緊跟的指數部分形式為「x」；

如果x 的指數為0，則僅需輸出係數即可。

5. 多項式中，多項式的開頭、結尾不含多餘的空格。

【輸入】

輸入文件名為 poly.in，共有2 行

第一行 1 個整數，n，表示一元多項式的次數。

第二行有 n+1 個整數，其中第i 個整數表示第n-i+1 次項的係數，每兩個整數之間用空格隔開。

【輸出】

輸出文件 poly.out 共1 行，按題目所述格式輸出多項式。

【輸入輸出樣例 1】

poly.in poly.out

5

100 -1 1 -3 0 10

100x^5-x^4+x^3-3x^2+10

【輸入輸出樣例2】

poly.in poly.out

3

-50 0 0 1

-50x^3+1

【數據範圍】

1 ≤ n ≤ 100，多項式各次項係數的絕對值均不超過100。

2．分數線劃定

(score.pas/c/cpp)

【問題描述】

世博會志願者的選拔工作正在 A 市如火如荼的進行。為了選拔最合適的人才，A 市對

所有報名的選手進行了筆試，筆試分數達到面試分數線的選手方可進入面試。面試分數線根

據計劃錄取人數的150%劃定，即如果計劃錄取m名志願者，則面試分數線為排名第m*150%

（向下取整）名的選手的分數，而最終進入面試的選手為筆試成績不低於面試分數線的所有

選手。

現在就請你編寫程序劃定面試分數線，並輸出所有進入面試的選手的報名號和筆試成

績。

【輸入】

輸入文件名為 score.in。

第一行，兩個整數n，m（5 ≤ n ≤ 5000，3 ≤ m ≤ n），中間用一個空格隔開，其

中n 表示報名參加筆試的選手總數，m 表示計劃錄取的志願者人數。輸入數據保證m*150%

向下取整後小於等於n。

第二行到第 n+1 行，每行包括兩個整數，中間用一個空格隔開，分別是選手的報名號k

（1000 ≤ k ≤ 9999）和該選手的筆試成績s（1 ≤ s ≤ 100）。數據保證選手的報名號各

不相同。

【輸出】

輸出文件 score.out。

第一行，有兩個整數，用一個空格隔開，第一個整數表示面試分數線；第二個整數為進入面試的選手的實際人數。

從第二行開始，每行包含兩個整數，中間用一個空格隔開，分別表示進入面試的選手的報名號和筆試成績，按照筆試成績從高到低輸出，如果成績相同，則按報名號由小到大的

順序輸出。

【輸入輸出樣例】

score.in score.out

6 3

1000 90

3239 88

2390 95

7231 84

1005 95

1001 88

88 5

1005 95

2390 95

1000 90

1001 88

3239 88

【樣例說明】

m*150% = 3*150% = 4.5，向下取整後為4。保證4 個人進入面試的分數線為88，但因為88

有重分，所以所有成績大於等於88 的選手都可以進入面試，故最終有5 個人進入面試。

3．細胞分裂

(cell.pas/c/cpp)

【問題描述】

Hanks 博士是BT (Bio-Tech，生物技術) 領域的知名專家。現在，他正在為一個細胞實驗做準備工作：培養細胞樣本。

Hanks 博士手裡現在有N 種細胞，編號從1~N，一個第i 種細胞經過1 秒鐘可以分裂為Si 個同種細胞（Si 為正整數）。現在他需要選取某種細胞的一個放進培養皿，讓其自由分裂，

進行培養。一段時間以後，再把培養皿中的所有細胞平均分入M 個試管，形成M 份樣本，用於實驗。Hanks 博士的試管數M 很大，普通的計算機的基本數據類型無法存儲這樣大的

M 值，但萬幸的是，M 總可以表示為m1 的m2 次方，即2

1

M = m m ，其中m1，m2 均為基本

數據類型可以存儲的正整數。

注意，整個實驗過程中不允許分割單個細胞，比如某個時刻若培養皿中有4 個細胞，

Hanks 博士可以把它們分入2 個試管，每試管內2 個，然後開始實驗。但如果培養皿中有5

個細胞，博士就無法將它們均分入2 個試管。此時，博士就只能等待一段時間，讓細胞們繼

續分裂，使得其個數可以均分，或是乾脆改換另一種細胞培養。

為了能讓實驗儘早開始，Hanks 博士在選定一種細胞開始培養後，總是在得到的細胞「剛好可以平均分入M 個試管」時停止細胞培養並開始實驗。現在博士希望知道，選擇哪種細

胞培養，可以使得實驗的開始時間最早。

【輸入】

輸入文件名為 cell.in，共有三行。

第一行有一個正整數 N，代表細胞種數。

第二行有兩個正整數 m1，m2，以一個空格隔開， 2

1

m m 即表示試管的總數M。

第三行有 N 個正整數，第i 個數Si 表示第i 種細胞經過1 秒鐘可以分裂成同種細胞的個

數。

【輸出】

輸出文件 cell.out 共一行，為一個整數，表示從開始培養細胞到實驗能夠開始所經過的

最少時間（單位為秒）。

如果無論 Hanks 博士選擇哪種細胞都不能滿足要求，則輸出整數-1。

【輸入輸出樣例 1】

cell.in cell.out

1

2 1

3

-1

【輸入輸出樣例1 說明】

經過 1 秒鐘，細胞分裂成3 個，經過2 秒鐘，細胞分裂成9 個，……，可以看出無論怎麼分裂，細胞的個數都是奇數，因此永遠不能分入2 個試管。

2009-11-21 18:58 回覆

59.33.120.* 5樓

【輸入輸出樣例 2】

cell.in cell.out

2

24 1

30 12

2

【輸入輸出樣例2 說明】

第 1 種細胞最早在3 秒後才能均分入24 個試管，而第2 種最早在2 秒後就可以均分（每

試管144/(241)=6 個）。故實驗最早可以在2 秒後開始。

【數據範圍】

對於 50%的數據，有2

1

m m ≤ 30000。

對於所有的數據，有1 ≤N≤ 10000，1 ≤m1 ≤ 30000，1 ≤m2 ≤ 10000，1 ≤ Si ≤ 2,000,000,000。

4．道路遊戲

(game.pas/c/cpp)

【問題描述】

小新正在玩一個簡單的電腦遊戲。

遊戲中有一條環形馬路，馬路上有n 個機器人工廠，兩個相鄰機器人工廠之間由一小段

馬路連接。小新以某個機器人工廠為起點，按順時針順序依次將這n 個機器人工廠編號為

1~n，因為馬路是環形的，所以第n 個機器人工廠和第1 個機器人工廠是由一段馬路連接在一起的。小新將連接機器人工廠的這n 段馬路也編號為1~n，並規定第i 段馬路連接第i 個

機器人工廠和第i+1 個機器人工廠（1 ≤ i ≤ n-1），第n 段馬路連接第n 個機器人工廠和第1個機器人工廠。

遊戲過程中，每個單位時間內，每段馬路上都會出現一些金幣，金幣的數量會隨著時間發生變化，即不同單位時間內同一段馬路上出現的金幣數量可能是不同的。小新需要機器人的幫助才能收集到馬路上的金幣。所需的機器人必須在機器人工廠用一些金幣來購買，機器人一旦被購買，便會沿著環形馬路按順時針方向一直行走，在每個單位時間內行走一次，即從當前所在的機器人工廠到達相鄰的下一個機器人工廠，並將經過的馬路上的所有金幣收集給小新，例如，小新在i（1 ≤ i ≤ n）號機器人工廠購買了一個機器人，這個機器人會從i 號機器人工廠開始，順時針在馬路上行走，第一次行走會經過i 號馬路，到達i+1 號機器人工廠（如果i=n，機器人會到達第1 個機器人工廠），並將i 號馬路上的所有金幣收集給小新。

遊戲中，環形馬路上不能同時存在2 個或者2 個以上的機器人，並且每個機器人最多能夠在環形馬路上行走p 次。小新購買機器人的同時，需要給這個機器人設定行走次數，行走次數可以為1~p 之間的任意整數。當馬路上的機器人行走完規定的次數之後會自動消失，小新必須立刻在任意一個機器人工廠中購買一個新的機器人，並給新的機器人設定新的行走次數。

以下是遊戲的一些補充說明：

1. 遊戲從小新第一次購買機器人開始計時。

2. 購買機器人和設定機器人的行走次數是瞬間完成的，不需要花費時間。

3. 購買機器人和機器人行走是兩個獨立的過程，機器人行走時不能購買機器人，購買完機器人並且設定機器人行走次數之後機器人才能行走。

4. 在同一個機器人工廠購買機器人的花費是相同的，但是在不同機器人工廠購買機器

人的花費不一定相同。

5. 購買機器人花費的金幣，在遊戲結束時再從小新收集的金幣中扣除，所以在遊戲過程中小新不用擔心因金幣不足，無法購買機器人而導致遊戲無法進行。也因為如此，遊戲結束後，收集的金幣數量可能為負。現在已知每段馬路上每個單位時間內出現的金幣數量和在每個機器人工廠購買機器人

需要的花費，請你告訴小新，經過m 個單位時間後，扣除購買機器人的花費，小新最多能收集到多少金幣。

【輸入】

輸入文件名為 game.in。

第一行 3 個正整數，n，m，p，意義如題目所述。

接下來的 n 行，每行有m 個正整數，每兩個整數之間用一個空格隔開，其中第i 行描

述了i 號馬路上每個單位時間內出現的金幣數量（1 ≤ 金幣數量≤ 100），即第i 行的第j

（1 ≤ j ≤m）個數表示第j 個單位時間內i 號馬路上出現的金幣數量。

最後一行，有 n 個整數，每兩個整數之間用一個空格隔開，其中第i 個數表示在i 號機

器人工廠購買機器人需要花費的金幣數量（1 ≤ 金幣數量≤ 100）。

【輸出】

輸出文件 game.out 共一行，包含1 個整數，表示在m 個單位時間內，扣除購買機器人

花費的金幣之後，小新最多能收集到多少金幣。

【輸入輸出樣例】

game.in game.out

2 3 2

1 2 3

2 3 4

1 2

5

【數據範圍】

對於 40%的數據，2 ≤ n ≤ 40，1 ≤m≤ 40。

對於 90%的數據，2 ≤ n ≤ 200，1 ≤m≤ 200。

對於 100%的數據，2 ≤ n ≤ 1000，1 ≤m≤ 1000，1 ≤ p ≤m。