南京市小學(xué)生信息學(xué)競賽初賽復(fù)習(xí) 知識要點(diǎn)

1、2015南京市小學(xué)生信息學(xué)競賽初賽復(fù)習(xí)知識要點(diǎn)、典型題（版本）一、知識要點(diǎn)1. 二分查找；2. 循環(huán)數(shù)組；3. 排序、新型排序；4. 字符串：分離單詞從文件中讀入；5. 進(jìn)制窮舉；窮舉的優(yōu)化（丑數(shù)）；6. 生成法求全排列；7. 組合取數(shù)；8. 遞推迭代深入題目；9. 圖形打??；10. 高精度計(jì)算；11. 數(shù)學(xué)類問題；數(shù)論問題；C（M，N）；12. 回溯；13. 貪心；14. 表達(dá)式計(jì)算；15. 文件操作；二、一些典型題目、經(jīng)典算法（及源程序）1. 排序、查找、二分（1）冒泡排序（已做，需練習(xí)）【程序清單】DIM AS INTEGER NINPUT NDIM AS INTEGER A(N), I

2、, FFOR I = 1 TO NINPUT A(I)NEXT IJ = 1DO F = 0 FOR I = 1 TO N - J IF A(I) > A(I+1) THEN SWAP A(I), A(I+1) F = 1 END IF NEXT I J = J + 1LOOP UNTIL F = 0FOR I = 1 TO N PRINT A(I);NEXT ISLEEP : END（2）二分查找（已做）【程序清單】dim as integer ninput ndim as integer a(n), i, j, x, mfor i = 1 to n input a(i)next if

3、or i = 1 to n-1 for j = i+1 to n if a(i) > a(j) then swap a(i), a(j) next jnext ifor i = 1 to n print a(i); " "next iprintL = 1 : r = ninput "x= ", xdo while L <= Rm = (L+R) 2 if x = a(m) then print "found" sleep : end end ifif x < a(m) thenR = m - 1elseL = m +

4、 1end ifloopprint "Not found!"sleep : end（3）帶二分查找的插入排序（已做，需練習(xí)）【程序清單】DIM AS INTEGER ninput nDIM AS INTEGER a(n), tail, L, R, minput a(1)for i = 2 to n input xL = 1 : R = i-1 : m = (L+R) 2Do while x <> a( m ) and (L <= R) if x > a(m) then L = m + 1elseR = m 1 end ifm = (L+R) 2 lo

5、opif x <> a(m) then for j = i-1 to L step -1 a(j+1) = a(j) next j a(L) = xelsefor j = i-1 to m step -1 a(j+1) = a(j) next j a(m) = xend ifnext iFOR i = 1 TO n PRINT a(i);NEXT iPRINTSLEEP : END2. 報數(shù)問題、循環(huán)數(shù)組（1）夏令營旗手（JS2010，第一題）（已做）【問題描述】2010年江蘇省“信息與未來”小學(xué)生夏令營將在常州市局前街小學(xué)進(jìn)行，該校的何老師得知本校營員小明同學(xué)被營委會選為夏令營的

6、小旗手，就準(zhǔn)備到他家去通知他。由于他不是本班的學(xué)生，所以何老師不知道小明家住在什么地方，只從其他同學(xué)那里得知，小明住在未來小區(qū)一幢不超過100層的高樓中，但在哪一層不清楚。其他同學(xué)提供了三條有用的信息：1）小明家的樓層號是一個素?cái)?shù)；2）該樓層號化為二進(jìn)制數(shù)后，其中1的個數(shù)是偶數(shù)；3）滿足以上兩個條件中，樓層號最大的一個。請你寫一個程序，計(jì)算并輸出滿足條件（1、2）的樓層個數(shù)總數(shù)及小明家的樓層號。【輸入】本題無輸入?！据敵觥績蓚€整數(shù)，即樓層個數(shù)總數(shù)和小明家的樓層號。（2）狐貍找兔子(hide.bas)（已做）【問題描述】圍繞著山頂有10個洞，一只兔子和一只狐貍各住一個洞，狐貍總想吃掉兔子。一天，

7、兔子對狐貍說：你想吃我有一個條件，就是第一次隔一個洞找我，第二次隔兩個洞找我，以后依此類推，次數(shù)不限。若能找到我，你就可以飽餐一頓，在沒有找到我之前不能停止。狐貍一想只有10個洞，尋找的次數(shù)又不限，哪有找不到的道理，就答應(yīng)了條件。結(jié)果就是沒找著?，F(xiàn)請你編寫一個程序，假定狐貍找了1000次，兔子躲在哪個洞里才安全。（3）循環(huán)報數(shù)()（已做，需練習(xí)）【問題描述】 現(xiàn)有N個人圍成一圈（N為輸入的數(shù)據(jù)），按1M的間隔報數(shù)（M也是一個輸入的數(shù)據(jù)）。根據(jù)報數(shù)的結(jié)果發(fā)現(xiàn)，第一個出列的人是1號，第二個出列的人是2號，第三個出列的人是3號，最后一個出列的人是N號。問原來這N個人的排列位置是怎樣的？【輸入】 兩個

8、整數(shù)N和M，表示人數(shù)和報數(shù)的間隔?！据敵觥恳恍泄睳個數(shù)，即這N個人原來的排列順序。（4）環(huán)繞數(shù)(round.bas)（已做，需練習(xí)）【問題描述】一個環(huán)繞數(shù)有如下三個特點(diǎn)：a) 每個數(shù)字指示了它下一個數(shù)字的位置（自左向右數(shù)，數(shù)到末尾后，再繞到最左位往右數(shù)）；b) 組成這個環(huán)繞數(shù)的數(shù)字只輪到一次；c) 當(dāng)所有數(shù)字都輪過一次后，正好回到第一次開始所取到的那個數(shù)字。例如，3162就是一個環(huán)繞數(shù)：l 取該數(shù)任一數(shù)字作為開始，如取1；l 由此數(shù)字開始向右數(shù)1位，輪到了數(shù)字6；l 由6向右數(shù)，數(shù)到2時繞回到3，再向左數(shù)共數(shù)6位，就輪到了數(shù)字3；l 由3向右數(shù)3位，便輪到了數(shù)字2；l 由2繞回到3再向右數(shù)，共

9、數(shù)2位，于是回到1。【任務(wù)】求以3開頭的四位數(shù)中，共有幾個環(huán)繞數(shù)，分別為多少？（5）2N個好人與壞人問題（已做，需練習(xí)）【問題描述】有N個好人與N個壞人首尾相接地站成一圈（N為輸入的一個整數(shù)，且前N個人為好人，后N個人為壞人），按照報數(shù)間隔M進(jìn)行1到M地循環(huán)報數(shù)（即每報到M的人就出列），但M未知。你的任務(wù)是求出一個最小的報數(shù)間隔M，使得最先報出的N個人都是壞人。【輸出】 一個整數(shù)，表示N?！据敵觥?一個整數(shù)，即所求出的報數(shù)間隔M。【輸入樣例】 3【輸出樣例】 53. 排序、新型排序、復(fù)雜排序（已做，需練習(xí)）（1）命名那個數(shù)字（ namenum.bas ）【問題描述】在威斯康辛州牛大農(nóng)場經(jīng)營者之

10、中，都習(xí)慣于請會計(jì)部門用連續(xù)數(shù)字給母牛打上烙印。但是，母牛用手機(jī)時并沒感到這個系統(tǒng)的便利,它們更喜歡用它們喜歡的名字來呼叫它們的同伴，而不是用像這個的語句“C'mon, #4734, get along”。請寫一個程序來幫助可憐的牧牛工將一只母牛的烙印編號翻譯成一個可能的名字。因?yàn)槟概儸F(xiàn)在都有手機(jī)了，使用那標(biāo)準(zhǔn)的按鍵的排布來把收到從數(shù)目翻譯到文字（除了“Q”和“Z”而外）：2: A,B,C 5: J,K,L 8: T,U,V 3: D,E,F 6: M,N,O 9: W,X,Y 4: G,H,I 7: P,R,S可接受的名字都被放在這樣一個叫作"dict.txt"

11、的文件中，它包含一連串的少于 5000個可接受的牛名字（所有的名字都是大寫的）。收到母牛的編號返回那些能從編號翻譯出來并且在字典中的名字。舉例來說，編號 4734 能產(chǎn)生的下列各項(xiàng)名字：GPDG GPDH GPDI GPEG GPEH GPEI GPFG GPFH GPFI GRDG GRDH GRDIGREG GREH GREI GRFG GRFH GRFI GSDG GSDH GSDI GSEG GSEH GSEIGSFG GSFH GSFI HPDG HPDH HPDI HPEG HPEH HPEI HPFG HPFH HPFIHRDG HRDH HRDI HREG HREH HREI

12、HRFG HRFH HRFI HSDG HSDH HSDIHSEG HSEH HSEI HSFG HSFH HSFI IPDG IPDH IPDI IPEG IPEH IPEIIPFG IPFH IPFI IRDG IRDH IRDI IREG IREH IREI IRFG IRFH IRFIISDG ISDH ISDI ISEG ISEH ISEI ISFG ISFH ISFI碰巧，81個中只有一個“GREG”是有效的（在字典中）?，F(xiàn)在，請你寫一個程序來對給出的編號打印出所有的有效名字，如果沒有則輸出“NONE”。編號可能有12位數(shù)字?！据斎搿浚?)單獨(dú)的一行包含一個編號（長度可能從1到12

13、）?！据敵觥浚?）以字典順序輸出一個有效名字的不負(fù)列表，一行一個名字?！緲永斎搿?734【樣例輸出】GREG（2）分?jǐn)?shù)線劃定(score.bas)（已做，需練習(xí)）【問題描述】世博會志愿者的選拔工作正在 A 市如火如荼地進(jìn)行。為了選拔最合適的人才，A 市對所有報名的選手進(jìn)行了筆試，筆試分?jǐn)?shù)達(dá)到面試分?jǐn)?shù)線的選手方可進(jìn)入面試。面試分?jǐn)?shù)線根據(jù)計(jì)劃錄取人數(shù)的150%劃定，即如果計(jì)劃錄取m名志愿者，則面試分?jǐn)?shù)線為排名第m*150%（向下取整）名的選手的分?jǐn)?shù)，而最終進(jìn)入面試的選手為筆試成績不低于面試分?jǐn)?shù)線的所有選手。現(xiàn)在就請你編寫程序劃定面試分?jǐn)?shù)線，并輸出所有進(jìn)入面試的選手的報名號和筆試成績?！据斎搿枯斎?/p>

14、文件名為 score.in。第一行，兩個整數(shù)n，m（5 n5000，3 mn），中間用一個空格隔開，其中n 表示報名參加筆試的選手總數(shù)，m 表示計(jì)劃錄取的志愿者人數(shù)。輸入數(shù)據(jù)保證m*150%向下取整后小于等于n。第二行到第 n+1 行，每行包括兩個整數(shù)，中間用一個空格隔開，分別是選手的報名號k（1000k9999）和該選手的筆試成績s（1s100）。數(shù)據(jù)保證選手的報名號各不相同?！据敵觥枯敵鑫募?score.out。第一行，有兩個整數(shù)，用一個空格隔開，第一個整數(shù)表示面試分?jǐn)?shù)線；第二個整數(shù)為進(jìn)入面試的選手的實(shí)際人數(shù)。從第二行開始，每行包含兩個整數(shù)，中間用一個空格隔開，分別表示進(jìn)入面試的選手的報名

15、號和筆試成績，按照筆試成績從高到低輸出，如果成績相同，則按報名號由小到大的順序輸出。【輸入輸出樣例】6 31000 903239 882390 957231 841005 951001 8888 51005 952390 951000 901001 883239 88【樣例說明】m*150% = 3*150% = 4.5，向下取整后為4。保證4 個人進(jìn)入面試的分?jǐn)?shù)線為88，但因?yàn)?8有重分，所以所有成績大于等于88 的選手都可以進(jìn)入面試，故最終有5 個人進(jìn)入面試。（3）三值排序（）（已做，需練習(xí)）【問題描述】同學(xué)們已經(jīng)學(xué)過若干種排序方法，也解過不少有關(guān)排序的問題?，F(xiàn)在，我們來看一種三值排序問題

16、，即給你一個數(shù)字序列，該序列中只有三種不同的值。這種序列在我們?nèi)粘Ｉ钪幸材芤姷?，例如，?dāng)我們給某項(xiàng)競賽的優(yōu)勝者按金銀銅牌排序的時候，就會出現(xiàn)這樣的序列。在我們這個任務(wù)中，可能的值只有三種：1，2和3。我們用交換的方法，把它們排成升序序列。現(xiàn)在，請你寫一個程序，計(jì)算出當(dāng)給定一個長度為N的、由1、2、3組成的數(shù)字序列后，將該序列排成升序所需要的最少交換次數(shù)?！据斎搿挎I盤輸入：第一行是一個整數(shù)，表示N（1<=N<=1000）；接下來的第二行到N+1行，每行輸入一個1到3之間的整數(shù)?！据敵觥科聊惠敵鲆粋€數(shù)字，表示排成升序所需要的最少交換次數(shù)。【樣例輸入】9221333231【樣例輸出】4

17、4. 字符串（已做，需練習(xí)）（1）分離單詞要求從文件中讀入英文句子或段落，再分離單詞。5. 數(shù)位分離、進(jìn)制轉(zhuǎn)換（已做，需練習(xí)）（1）將二進(jìn)制數(shù)化為十進(jìn)制數(shù)，包含小數(shù)。（2）將十進(jìn)制數(shù)化為二進(jìn)制數(shù)，包含小數(shù)。（3）如果一個十進(jìn)制數(shù)是回文數(shù)，把它轉(zhuǎn)換成二進(jìn)制數(shù)后仍為回文數(shù)，這個數(shù)稱為絕對回文數(shù)。找出11，500以內(nèi)的絕對回文數(shù)。（4）求最大公約數(shù)與最小公倍數(shù)（已做）【問題描述】輸入二個二進(jìn)制整數(shù)（長度不超過20位），求出其最大公約數(shù)與最小公倍數(shù)，并用二進(jìn)制數(shù)輸出。例如：輸入：11，100輸出：1 1100【輸入】兩個二進(jìn)制數(shù)?！据敵觥坑枚M(jìn)制數(shù)表示的最大公約數(shù)與最小公倍數(shù)（4）進(jìn)制數(shù)（已做）【問題

18、描述】給出一個正整數(shù)N（1=N=1023），將其化為10位二進(jìn)制數(shù)，然后計(jì)算出二進(jìn)制數(shù)中的“1”的個數(shù)，若1的個數(shù)為奇數(shù)，則在最高位前加一個1，否則加一個0，最后將在此基礎(chǔ)上形成一個11位二進(jìn)制數(shù)，用3個十六進(jìn)制數(shù)輸出。例如：輸入23，化為二進(jìn)制數(shù)為：0000010111，因?yàn)?的個數(shù)為4，在最高位前加0，得到00000010111。輸出：0H，1H，7H【輸入格式】鍵盤輸入。一個正整數(shù)N?！据敵龈袷健扛鶕?jù)形成的11位二進(jìn)制數(shù)，用3個十六進(jìn)制數(shù)輸出。【樣例】輸入：453輸出：5H，CH，5H（5）數(shù)列（）（已做）【問題描述】給定一個正整數(shù)k(3k15),把所有k的方冪及所有有限個互不相等的k的

19、方冪之和構(gòu)成一個遞增的序列，例如，當(dāng)k=3時，這個序列是：1，3，4，9，10，12，13，（該序列實(shí)際上就是：30，31，30+31，32，30+32，31+32，30+31+32，）請你求出這個序列的第N項(xiàng)的值（用10進(jìn)制數(shù)表示）。例如，對于k=3，N=100，正確答案應(yīng)該是981?！据斎胛募枯斎胛募equence.in 只有1行，為兩個正整數(shù)k和N（k、N的含義與上述的問題描述一致，且3k15，10N1000）?！据敵鑫募枯敵鑫募equence.out 為計(jì)算結(jié)果，是一個正整數(shù)（在所有的測試數(shù)據(jù)中，結(jié)果均不超過2.1*109）。（整數(shù)前不要有空格和其他符號）。【輸入樣例】 3,1

20、00【輸出樣例】981（6）海明碼（hamming.bas）【問題描述】給出 N，B 和 D：找出 N 個編碼（1 <= N <= 64），每個編碼有 B 位（1 <= B <= 8），使得兩兩編碼之間至少有 D 個單位的“海明距離”（1 <= D <= 7）?！昂Ｃ骶嚯x”是指對于兩個編碼，他們的二進(jìn)制表示法中的不同二進(jìn)制位的數(shù)目。看下面的兩個編碼 0x554 和 0x234 之間的區(qū)別（0x554 表示一個十六進(jìn)制數(shù)，每個位上分別是 5，5，4）： 0x554 = 0101 0101 0100 0x234 = 0010 0011 0100 不同的二進(jìn)制位:

21、 xxx xx因?yàn)橛形鍌€位不同，所以“海明距離”是 5。【輸入】輸入文件名為，文件中只有一行，包括 N, B, D。【輸出】輸出文件名為，其中共有N 個編碼（用十進(jìn)制表示），要排序，十個一行。如果有多解，你的程序要輸出這樣的解：假如把它化為 2B 進(jìn)制的數(shù)，它的值要最小?！緲永斎搿?6,7,3【樣例輸出】0 7 25 30 42 45 51 52 75 7682 85 97 102 120 1276. 進(jìn)制窮舉、復(fù)雜窮舉、窮舉的優(yōu)化（1）丑數(shù)(humble.bas)（已做，需練習(xí)）（）【問題描述】對于一個給定的素?cái)?shù)集合 S = p1, p2, ., pK（也就是說，p1、p2、pk都是給定的

22、素?cái)?shù)），考慮那些質(zhì)因數(shù)全部屬于S 的數(shù)的集合這個集合中的數(shù)包括：p1, p1*p2, p1*p1, p1*p2*p3,。稱由這些數(shù)構(gòu)成的集合為相應(yīng)S的丑數(shù)集合。注意：規(guī)定 1 不是丑數(shù)。你的任務(wù)是對于輸入的集合S，去尋找丑數(shù)集合中第N個丑數(shù)?！据斎搿?humble.in)第1行：兩個由空格隔開的整數(shù)K 和 N，此處1<= K<=100，1<=N<=100,000；第 2 行：K個由空格隔開的整數(shù)，它們都是集合S的元素?！据敵觥?humble.out)一行，輸出第N個丑數(shù)?！据斎霕永? 192 3 5 7【輸出樣例】277. 生成法求全排列（已做，需練習(xí)）【程序清單】D

23、IM AS INTEGER N, I, SINPUT NDIM AS INTEGER A(n)FOR I=1 TO N A(i)=INEXT IDO S=S+1 FOR I=1 TO NPRINT A(i); NEXT I PRINT FOR I=N TO 2 STEP -1 IF A(i-1)<A(i) THEN M=I-1:EXIT FOR NEXT I IF I=1 THEN EXIT DOI=N DO IF A(i)>A(m) THEN SWAP A(i),A(m):EXIT DO I=I-1LOOPI=M+1J=N DO SWAP A(i),A(j)I=I+1 J=J-1

24、 LOOP UNTIL I>=JLOOPPRINT SSLEEP : END8. 組合取數(shù)（已做，需練習(xí)）【程序清單】DIM AS INTEGER N, R, S, I, JINPUT N，RDim AS INTEGER b(r)S = 0FOR I = 0 TO R 產(chǎn)生初始的、也是第一種排列 B（I）=INEXT IDO WHILE B(0)=0S=S+1FOR I = 1 TO R 打印當(dāng)前這一組組合的排列情況PRINT B（I）；“ ”；NEXT IPRINTJ=RDO WHILE B(J)=NR+ J 若允許R=N，則要改一下條件，否則會出現(xiàn)問題J=J-1LOOPB（J）=B（

25、J）+1FOR I = J+1 TO R B（I）=B（I-1）+1NEXT ILOOPPRINT “S=”；SSLEEP : END9. 遞推迭代深入（1）求數(shù)組元素（已做）已知給出任意一個自然數(shù)(N<=100)，輸出滿足下列條件的數(shù)組元素及不同方案數(shù)，條件是：1) 數(shù)組元素由各不相同的自然數(shù)組成；2) 最后一個元素必為N；3) 每一個元素都不小于它前面一個元素的平方（第一個元素除外）；4) 數(shù)組中包含的元素個數(shù)可以不相同，但至少要有一個元素；例如：輸入：N=1輸出：數(shù)組: (1)K=1 用K記錄不同的方案數(shù)又如： N=5數(shù)組： (5)，(1，2，5)，(1，5)， (2,5) K=4

26、（2）回文數(shù)列（已做，需練習(xí)）【問題描述】對一個正整數(shù)K，求出K的所有拆分，并統(tǒng)計(jì)輸出其中回文數(shù)列的個數(shù)。所謂回文數(shù)列是指該數(shù)列中的所有數(shù)字，從左向右或從右向左看都相同。例如，K=4時，有如下的拆分： 4 = 1 + 1 + 1 + 1 回文數(shù)列1 = 1 + 1 + 2= 1 + 2 + 1 回文數(shù)列2= 2 + 1 + 1= 2 + 2 回文數(shù)列3= 1 + 3= 3 + 1因此，回文數(shù)列共有3個。【輸入】一個正整數(shù)K（1<K26）。【輸出】滿足條件的回文數(shù)列的個數(shù)。【輸入樣例】4【輸出樣例】3（3）排序集合（）（已做，需練習(xí)）【問題描述】對于集合N=1,2,N的子集，定義一個稱為“

27、小于”的關(guān)系：設(shè)S1=X1,X2,Xi，(X1<X2<<Xi)，S2=Y1,Y2,Yj，(Y1<Y2<<Yj)，如果存在一個k，（0<=k<=mini,j），使得X1=Y1，Xk=Yk，且k=i或X(k+1)<Y(k+1)，則稱S1“小于”S2。你的任務(wù)是：對于任意的n（n<=31）及k（k<2n），求出第k小的子集。【輸入】(sort.in) 輸入文件僅一行，包含兩個用空格隔開的自然數(shù)，n和k?！据敵觥?sort.out) 輸出文件僅一行，是該子集的元素，由小到大排列。空集輸出0?！据斎胼敵鰳永浚?3 4： 1 2 310.

28、 圖形打?。?）螺旋方陣（JS2010，T5，10分）（已做）【問題描述】輸入一個正整數(shù)N（1<=N<=20）后，可以得到一個N*N的數(shù)字螺旋方陣，分別求該方陣中的主對角線與副對角線上的數(shù)字之和S、P，輸出S、P的差。例如：N=5，得到的數(shù)字螺旋方陣如下：12345161718196152425207142322218131211109其中，主對角線從左上角到右下角，得到的數(shù)字之和為：S=1+17+25+21+9=73；副對角線從右上到左下，得到的數(shù)字之和：P=5+19+25+23+13=85，S-P=-12?！据斎搿恳粋€整數(shù)N?！据敵觥恐鲗蔷€與副對角線上數(shù)字和的差。【樣例】 見

29、問題中的舉例。11. 高精度計(jì)算（1）印度國王的棋盤（JS2010，T3，10分）（已做，需練習(xí)）【問題描述】印度國王使用的棋盤有N*N個格子（N無限大），現(xiàn)在從第一個格子開始放麥粒，第一個格子放1粒，第二個格子放2粒，第三個格子放4粒，第N個格子放2(N-1)粒麥粒。請你編程計(jì)算從第K格至第M格共有多少粒麥粒?！据斎搿恳恍校瑑蓚€整數(shù)K，M（4<=K<M<=100）?！据敵觥抗灿卸嗌倭｛溋＃ńY(jié)果不超過6位時，直接輸出結(jié)果；結(jié)果超過6位時，只輸出結(jié)果的最高3位和最低3位，以逗號分隔）。12. 數(shù)學(xué)類問題（數(shù)論問題）(1)數(shù)學(xué)作業(yè)(math.bas)（已做）【問題描述】小明的數(shù)學(xué)

30、老師布置了一堆數(shù)學(xué)題作為作業(yè)，這些數(shù)學(xué)題有一個共同的特點(diǎn)，就是都是要求計(jì)算出C(N,M)中不同質(zhì)因子的個數(shù)。Steven請你幫他寫一個程序，來幫助他盡快地完成這些作業(yè)。C(N,M)即求在N個數(shù)中選M個數(shù)的組合數(shù)。【輸入格式】(math.in)輸入文件中只有一行，其中有兩個整數(shù)，表示N和M(1<=N, M<=50000)?！据敵龈袷健?math.out) 輸出一個整數(shù)，表示C(N,M)中質(zhì)因子的個數(shù)?！据斎霕永? 3【輸出樣例】 2（2）細(xì)胞分裂(cell.bas)【問題描述】Hanks 博士是BT (Bio-Tech，生物技術(shù)) 領(lǐng)域的知名專家?，F(xiàn)在，他正在為一個細(xì)胞實(shí)驗(yàn)做準(zhǔn)備工

31、作：培養(yǎng)細(xì)胞樣本。Hanks 博士手里現(xiàn)在有N 種細(xì)胞，編號從1N，一個第i 種細(xì)胞經(jīng)過1 秒鐘可以分裂為Si 個同種細(xì)胞（Si 為正整數(shù)）?，F(xiàn)在他需要選取某種細(xì)胞的一個放進(jìn)培養(yǎng)皿，讓其自由分裂，進(jìn)行培養(yǎng)。一段時間以后，再把培養(yǎng)皿中的所有細(xì)胞平均分入M 個試管，形成M 份樣本，用于實(shí)驗(yàn)。Hanks 博士的試管數(shù)M 很大，普通的計(jì)算機(jī)的基本數(shù)據(jù)類型無法存儲這樣大的M 值，但萬幸的是，M 總可以表示為m1的m2次方，即 ，其中m1、m2均為基本數(shù)據(jù)類型可以存儲的正整數(shù)。注意，整個實(shí)驗(yàn)過程中不允許分割單個細(xì)胞，比如某個時刻若培養(yǎng)皿中有4 個細(xì)胞，Hanks 博士可以把它們分入2 個試管，每試管內(nèi)2

32、個，然后開始實(shí)驗(yàn)。但如果培養(yǎng)皿中有5個細(xì)胞，博士就無法將它們均分入2 個試管。此時，博士就只能等待一段時間，讓細(xì)胞們繼續(xù)分裂，使得其個數(shù)可以均分，或是干脆改換另一種細(xì)胞培養(yǎng)。為了能讓實(shí)驗(yàn)盡早開始，Hanks 博士在選定一種細(xì)胞開始培養(yǎng)后，總是在得到的細(xì)胞“剛好可以平均分入M 個試管”時停止細(xì)胞培養(yǎng)并開始實(shí)驗(yàn)?，F(xiàn)在博士希望知道，選擇哪種細(xì)胞培養(yǎng)，可以使得實(shí)驗(yàn)的開始時間最早。【輸入】輸入文件名為 cell.in，共有三行。第一行有一個正整數(shù) N，代表細(xì)胞種數(shù)。第二行有兩個正整數(shù)m1、m2，以一個空格隔開，即表示試管的總數(shù)M。第三行有 N 個正整數(shù)，第i 個數(shù)Si 表示第i 種細(xì)胞經(jīng)過1 秒鐘可以分

33、裂成同種細(xì)胞的個數(shù)。【輸出】輸出文件 cell.out 共一行，為一個整數(shù)，表示從開始培養(yǎng)細(xì)胞到實(shí)驗(yàn)?zāi)軌蜷_始所經(jīng)過的最少時間（單位為秒）。如果無論 Hanks 博士選擇哪種細(xì)胞都不能滿足要求，則輸出整數(shù)-1?！据斎胼敵鰳永?1】12 13-1【輸入輸出樣例1 說明】經(jīng)過 1 秒鐘，細(xì)胞分裂成3 個；經(jīng)過2 秒鐘，細(xì)胞分裂成9 個；?？梢钥闯?，無論怎么分裂，細(xì)胞的個數(shù)都是奇數(shù)，因此永遠(yuǎn)不能分入2 個試管。【輸入輸出樣例 2】224 130 122【輸入輸出樣例2 說明】第 1 種細(xì)胞最早在3 秒后才能均分入24 個試管，而第2 種最早在2 秒后就可以均分（每試管144/(241)=6 個）。故實(shí)驗(yàn)最早可以在2 秒后開始。【數(shù)據(jù)范圍】對于 50%的數(shù)