【正文】 題二 乘積最大 （22 分） 問題描述 今年是國際數(shù)學(xué)聯(lián)盟確定的“2022——世界數(shù)學(xué)年” ，又恰逢我國著名數(shù)學(xué)家華羅庚先生誕辰 90 周年。例如對１６進(jìn)制數(shù)來說，用Ａ表示１０，用Ｂ表示１１，用Ｃ表示１２，用Ｄ表示１３，用Ｅ表示１４，用Ｆ表示１５。一般說來，任何一個正整數(shù)Ｒ或一個負(fù)整數(shù)－Ｒ都可以被選來作為一個數(shù)制系統(tǒng)的基數(shù)?？梢则炞C當(dāng) N=3，K=2 時，7 分就是可以得到的連續(xù)的郵資最大值，所以 MAX=7，面值分別為 1 分、3 分。計算結(jié)果四舍五入至小數(shù)點后兩位。 又如：對于 10 進(jìn)制數(shù) 87： STEP1：87+78 = 165 STEP2：165+561 = 726 STEP3：726+627 = 1353 STEP4：1353+3531 = 4884 在這里的一步是指進(jìn)行了一次 N 進(jìn)制的加法，上例最少用了 4 步得到回文數(shù) 4884。由于該系統(tǒng)還在試用階段，所以只有一套系統(tǒng)，因此有可能不能攔截所有的導(dǎo)彈。 （字串僅有一個為‘+’號，其它都由大寫字母組成）程序輸出：① 各個字母表示什么數(shù)，格式如：L=0 ，K=1，……② 加法運(yùn)算是幾進(jìn)制的。 {20%}2．設(shè)有 n 個正整數(shù)（n≤20） ，將它們聯(lián)接成一排，組成一個最大的多位整數(shù)。 例如：（n=10,m=10） ， （1，5） （起點） ， （3，5） （終點） 輸 出：2（即由（1，5）到（3，5）共有 2 條路徑）馬(4,4)(1,1)109876543211 2 3 4 5 6 7 8 9 10 7 / 56 輸入格式：n,m,x1,y1,x2,y2 (分別表示 n,m,起點坐標(biāo)，終點坐標(biāo)) 輸出格式：路徑數(shù)目（若不存在從起點到終點的路徑，輸出 0）第四屆全國青少年信息學(xué)（計算機(jī)）奧林匹克分區(qū)聯(lián)賽復(fù)賽試題 （高中組 競賽用時：3 小時）1．火車從始發(fā)站（稱為第 1 站）開出，在始發(fā)站上車的人數(shù)為 a，然后到達(dá)第 2 站，在第2 站有人上、下車，但上、下車的人數(shù)相同，因此在第 2 站開出時（即在到達(dá)第 3 站之前）車上的人數(shù)保持為 a 人。 輸出：ERROR 23．騎士游歷： 設(shè)有一個 n*m 的棋盤（ 2≤n≤50，2≤m ≤50） ，如下圖，在棋盤上左下角有一個中國象棋馬。 程序要求： 輸入：輸入一個字符串，以“；”結(jié)束， “；”本身不是代數(shù)表達(dá)式中字符，僅作為結(jié)束） ； 輸出：若表達(dá)式正確，則輸出“OK” ；若表達(dá)式不正確，則輸出 “ERROR”，及錯誤類型。 程序要求： 輸入：N； 輸出：如有多種解，則輸出第一行、第一列之和為最小的排列方案；若無解，則輸出“NO！” 。設(shè)計一個挖地雷的方案，使某人能挖到最多的地雷。 例如：A$=’48108’ 其意義為：將 10 進(jìn)制數(shù) 48，轉(zhuǎn)換成 8 進(jìn)制數(shù)輸出。② 計算時可允許出現(xiàn)以下情況： A=B （即可理解為運(yùn)算符的個數(shù)為零） A=B B+B （即全部由 B 產(chǎn)生）?第二屆全國青少年信息學(xué)（計算機(jī)）奧林匹克分區(qū)聯(lián)賽復(fù)賽試題 （高中組 競賽用時：3 小時）1．比賽安排（20 分） 設(shè)有有 2 n（n=6）個球隊進(jìn)行單循環(huán)比賽，計劃在 2 n – 1 天內(nèi)完成，每個隊每天進(jìn)行一場比賽。3 設(shè)有一個四層的積木塊，1～4 層積木塊的數(shù)量依次為： 5，6，7，8 如下圖所示放置：8 15 8 5 16 9 142 3 4 1 4 3 2 6 其中，給出第三層與第四層所標(biāo)示的數(shù)字，并已知第三層的數(shù)據(jù)是由第四層的數(shù)據(jù)計算出來的。2 燈的排列問題： 設(shè)在一排上有 N 個格子（ N≤20） ，若在格子中放置有不同顏色的燈，每種燈的個數(shù)記為 N1，N 2，……N k（k 表示不同顏色燈的個數(shù)） 。 1 / 56NOI’95 “同創(chuàng)杯”全國青少年信息學(xué)（計算機(jī)）奧林匹克競賽分區(qū)聯(lián)賽復(fù)賽試題（高中組） （上機(jī)編程，完成時間：210 分鐘）1 編碼問題： 設(shè)有一個數(shù)組 A:ARRAY[0..N1] OF INTEGER； 數(shù)組中存放的元素為 0～N1 之間的整數(shù)，且 A[i]≠ A[j]（當(dāng) i≠j 時） 。 放燈時要遵守下列規(guī)則：①同一種顏色的燈不能分開；②不同顏色的燈之間至少要有一個空位置。 計算的方法是：第三層的某個數(shù)據(jù) A 是由第四層相鄰的兩個數(shù)據(jù) B，C 經(jīng)過某種計算后產(chǎn)生的：AB C 計算所用到的計算符為：+， ， ，且無優(yōu)先級之分（自左向右計算） ，運(yùn)算符最多為?2 個。設(shè)計一個比賽的安排，使在 2 n – 1 天內(nèi)每個隊都與不同的對手比賽。 輸出結(jié)果為：4810=6084．挖地雷（30 分） 在一個地圖上有 N 個地窖（ N=20） ，每個地窖中埋有一定數(shù)量的地雷。V1 V 2 V3 V4 V5 4 / 56 輸入格式： N： （表示地窖的個數(shù)） 　　　Ｗ 1，W 2，W 3，……W N （表示每個地窖中埋藏的地雷數(shù)量） A12…………… . A1N A23…………..A2N …….. AN1 N 輸出格式： K1K2……….KV （挖地雷的順序 ） MAX （挖地雷的數(shù)量）例如：　　　 ?、猗? ④ ⑦ ⑥其輸入格式為： 輸出： 5 1 –3 4 510，8，4，7，6 max=27 1 1 1 0 0 0 0 1 1 14．砝碼稱重（30 分）設(shè)有 1g、2g、3g、5g、10g、20g 的砝碼各若干枚（其總重=1000） ，要求： 輸入方式：a1 a2 a3 a4 a5 a6 （表示 1g 砝碼有 a1 個，2g 砝碼有 a2 個，…，20g 砝碼有 a6 個） 輸出方式：Total=N （N 表示用這些砝碼能稱出的不同重量的個數(shù)，但不包括一個砝碼也不用的情況）如輸入：1_1_0_0_0_0 （注：下劃線表示空格） 輸出：TOTAL=3 表示可以稱出 1g，2g，3g 三種不同的重量。2．代數(shù)表達(dá)式的定義如下： 例如，下面的式子是合法的代數(shù)表達(dá)式： a； a+b*(a+c)。錯誤類型約定：1．式了中出現(xiàn)不允許的字符；2．括號不配對；acb字母 6 / 563．其它錯誤。 （n,m） (1,1)馬走的規(guī)則為：（1） 馬走日字；（2） 馬只能向右走即如下圖如示： 任務(wù) 1：當(dāng) n,m 輸入之后，找出一條從左下角到右上角的路徑。從第 3 站起（包括第 3 站）上、下車的人數(shù)有一定規(guī)律：上車的人數(shù)都是前兩站上車人數(shù)之和，而下車人數(shù)等于上一站上車人數(shù)，一直到終點站的前一站（第 n1 站） ，都滿足此規(guī)律。例如：n=3 時，3 個整數(shù) 13，312，343 聯(lián)接成的最大整數(shù)為：34331213又如：n=4 時，4 個整數(shù) 7，13，4，246 聯(lián)接成的最大整數(shù)為：7424613程序輸入：n n 個數(shù)程序輸出：聯(lián)接成的多位數(shù) {40%}3．著名科學(xué)家盧斯為了檢查學(xué)生對進(jìn)位制的理解，他給出了如下的一張加法表，表中的字母代表數(shù)字。③ 若不可能組成加法表，則應(yīng)輸出“ERROR！”第五屆全國青少年信息學(xué)（計算機(jī)）奧林匹克分區(qū)聯(lián)賽復(fù)賽試題 （提 高 組 競賽用時：3 小時）第一題 攔截導(dǎo)彈(28 分) 某國為了防御敵國的導(dǎo)彈襲擊，發(fā)展出一種導(dǎo)彈攔截系統(tǒng)。 輸入導(dǎo)彈依次飛來的高度（雷達(dá)給出的高度數(shù)據(jù)是不大于 30000 的正整數(shù)） ，計算這套系統(tǒng)最多能攔截多少導(dǎo)彈，如果要攔截所有導(dǎo)彈最少要配備多少套這種導(dǎo)彈攔截系統(tǒng)。 寫一個程序，給定一個 N（2=N=10 或 N=16）進(jìn)制數(shù) M，求最少經(jīng)過幾步可以得到回 9 / 56文數(shù)。如果無法到達(dá)目的地，則輸出“No Solution” 。 樣例： INPUT OUTPUT N=3 K=2 1 3 MAX=7 10 / 562022 年 題一 進(jìn)制轉(zhuǎn)換 （18 分） 問題描述 我們可以用這樣的方式來表示一個十進(jìn)制數(shù)： 將每個阿拉伯?dāng)?shù)字乘以一個以該數(shù)字所處位置的（值減１）為指數(shù)，以１０為底數(shù)的冪之和的形式。如果是以Ｒ或－Ｒ為基數(shù)，則需要用到的數(shù)碼為 ０，１， ． ． ． ．Ｒ－１。在負(fù)進(jìn)制數(shù)中是用－Ｒ 作為基數(shù)，例如－１５（十進(jìn)制）相當(dāng)于１１０００１（－２進(jìn)制），并且它可以被表示為２的冪級數(shù)的和數(shù)： １１０００１＝１＊（－２） ５ ＋１＊（－２） ４ ＋０＊（－２） ３ ＋０＊（－２） ２ ＋ ０＊（－２） １ ＋１＊（－２） ０ 問題求解 設(shè)計一個程序，讀入一個十進(jìn)制數(shù)和一個負(fù)進(jìn)制數(shù)的基數(shù), 并將此十進(jìn)制數(shù)轉(zhuǎn)換為此負(fù)進(jìn)制下的數(shù)： －Ｒ∈｛－２，－３，－４， ． ． ． ，－２０｝　 輸 入 輸入的每行有兩個輸入數(shù)據(jù)。在華羅庚先生的家鄉(xiāng)江蘇金壇，組織了一場別開生面的數(shù)學(xué)智力競賽的活動，你的一個好朋友 XZ 也有幸得以參加。 輸 出 結(jié)果顯示在屏幕上，相對于輸入，應(yīng)輸出所求得的最大乘積（一個自然數(shù)） 。如下圖所示（見樣例）： 某人從圖的左上角的 A 點出發(fā)，可以向下行走，也可以向右走，直到到達(dá)右下角的B 點。一行單獨的 0 表示輸入結(jié)束。要求由小到大依次在同一行輸出這三個實根 (根與根之間留有空格)，并精確到小數(shù)點后 2 位。1，1，5。輸入：n，k (6n=200，2=k=6)輸出：一個整數(shù)，即不同的分法。2 ，2， 3。當(dāng)選用一個單詞之后，其第一個字母不能 16 / 56再用。輸入格式去部輸入數(shù)據(jù)放在文本文件 中，其格式如下：第一行為一個正整數(shù)(0n=5)表示有 n 組測試數(shù)據(jù)每組的第一行有二個正整數(shù)(p，k)p 表示字串的行數(shù)。(1=s=6)接下來的 s 行，每行均有一個單詞。圖例 17 / 56機(jī)場 高速鐵路飛機(jī)航線　 注意：圖中并沒有標(biāo)出所有的鐵路與航線。)輸入格式第一行為一個正整數(shù) n(0=n=10)，表示有 n 組測試數(shù)據(jù)。輸出格式共有 n 行，每行一個數(shù)據(jù)對應(yīng)測試數(shù)據(jù)?！　∫婆埔?guī)則為：在編號為 1 堆上取的紙牌，只能移到編號為 2 的堆上；在編號為 N 的堆上取的紙牌，只能移到編號為 N1 的堆上；其他堆上取的紙牌，可以移到相鄰左邊或右邊的堆上。文件格式：　　N（N 堆紙牌，1 = N = 100）　　A1 A2 … An （N 堆紙牌，每堆紙牌初始數(shù)，l= Ai =10000）[輸 出]：　　輸出至屏幕。abcd39。[輸入]:　　鍵盤輸人文件名。在地面上 20 / 56有一個小車（長為 L，高為 K，距原點距離為 S1）?！　≌埬阌嬎愠鲂≤嚹芙邮艿蕉嗌賯€小球。 21 / 56　　這些點可以用 k 個矩形（1=k=4）全部覆蓋，矩形的邊平行于坐標(biāo)軸。各個矩形必須完全分開（邊線與頂點也都不能重合）。 [輸入輸出樣例] :　4 2　1 1　2 2　3 6　0 7屏幕顯示：42022 年 22 / 56第九屆全國青少年信息學(xué)奧林匹克聯(lián)賽（N0IP2022）2022 年 11 月 29 日 提高組試題 三小時完成試題輸入：蘇州