2019年全國信息學(xué)奧林匹克競賽真題無答案

1、2019年全國信息學(xué)奧林匹克競賽真題（第一試）全國青少年信息學(xué)奧林匹克競賽CCF NO1 2019第一試時間：2019 年 7 月 16 日 08:00 - 13:00題口名稱回竦路線機(jī)器人序列題目類型傳統(tǒng)型傳統(tǒng)型傳統(tǒng)型目錄routerobotsequence可執(zhí)行文件名routerobotsequenca輸入文件名route.inrobot insequeneg.in輸出文件名route.outrobot ou七sequence.out每個測試點(diǎn)時限1.0秒3.0秒1.0穆內(nèi)存限制512 MB512 MB512 MB子任務(wù)數(shù)目202025測試點(diǎn)是否等分是足是提交源程序文件名對于C+涪言rou

2、te c:pprobot.eppsequenew.epp對于C語吉route.crobot.csequence.c對于Pascal語古routep3Srobotpossequence.pms編譯選項對FC十十語言-02 -lm對于c語古-02 -lm對p Pascal語言-02注意事項1. 選于提交的源文件必須存放在己建立好的帶仔下發(fā)樣例的文件夬中（該文件夬 與試題同名幾2. 丈件名（包梏穆序名和輸入輸出文件名）必須使用英文小寫。3結(jié)果比較方式為忽略行木空格、文木回車后的全文比較。I. C/C+中函數(shù)Hiainf）的返冋值類空必須是hit,債為0.5.對于因未連守以上規(guī)則對成績造成的影響，相關(guān)

3、審訴不予受理。回家路線(route)【地目描述】貓國的帙路系統(tǒng)中科”個站點(diǎn).從i”編號.小貓準(zhǔn)備從i號站點(diǎn)出發(fā),乘坐列 車回到盤角所在的n號站點(diǎn)。它育詢了能紗曝坐的列車.這些列車共/W班,從15 編號。小貓將在0時刻到達(dá)1號站點(diǎn)。對于i號列車,它將在時刻p從站點(diǎn)石出發(fā), 在時刻<7, r達(dá)站點(diǎn)兒，小前只能任肘刻乃上八:列乍，也只能任時刻彳卜八；列乍小貓可以通過多次換乘到達(dá)，!號站點(diǎn),一次換乘是指對于兩班列車.假設(shè)分別為« 號與V號列車，仆=”，并且務(wù)s幾，那么小貓可以乘坐完“號列車后在兒號站點(diǎn) 算待p、. - %個時刻井在時刻八乘坐V號列車.小貓只想回對貓廉并H減少途中的麻煩，

4、對此它闇煩跺值來衡就。小貓在站點(diǎn)等待時將増加煩踐似，對r 一次r (/ > 0)個時刻的等待.煩躁値將墩 加川2十冊+ C其屮人乩C是給定的幣數(shù)注範(fàn)小斯迂上第一班列年前，即 從0時刻起停陽在i號站點(diǎn)的那空時刻也那作一次等待若小貓最終在時刻z到達(dá)n號站點(diǎn),則煩鎌值將再增加z.形式化地說,苦小貓共乘坐了上班別軋依次乘坐的列牟編號可用序列耐.仏小 表示.該方案被稱作一條可行的回家路線.當(dāng)且僅當(dāng)它滿足下列兩個條件;1. 心-1 K =刀2對于所有jL<j<約，滿足ySj =壬小I!仙"如對于該回家垢線，小驕得到的煩隸值將為：q” + (人此+ r亠農(nóng))+工他“小-如)

5、9;+川幾小的)+ °)1小貓想讓自己的煩跺值盡屆小請你幫它求出所有可行的回冢路線中,能刃到的M 小的煩鏗也 題目保證至少存在亠條可行的回家略線?！据斎敫袷健繌奈募oute.in中讀入數(shù)據(jù)。第一行五個幣數(shù)兒mA.B.C,變敝盤義見題目描述.接F來”行,第i行四個整分別農(nóng)示八;列車的出發(fā)站、到達(dá)站、 出發(fā)時刻與到達(dá)時刻?！据敵龈袷健枯擧1到文件route.out中。輸出僅一行一個娜數(shù).龍示所求的答案®3 4 1 5 1012 3 412 5 712 6 82 3 9 13【樣例1輸出】94【樣例1解釋】共有三條可行的回壕路線：1.依次乘坐.4號列牟,得到的煩躁值為：10 +

6、 (1 X32 + 5x3+ 10)卜(I X (9 - 1)2 + 5 X! (9 - I) + KF)= 1(142依次乘坐Z 4號列車.得到的煩辣值為：1()十(1 x52 + 5x5+- 10)十(1 X (9 了嚴(yán)十 5 x (9 7)十 10)= 943. 依次乘坐34號列車，得到的煩躁值為：10 + (1 x62 + 5x(i+- 10) -+ (1 X (9 - 3)2 + 5x(9-s)-r 1(>)= 102 第二條路線得到的煩躁值殳小為9仁【樣例2輸入】4 3 12 312 2 32 3 5 73 4 7 9【樣例2輸岀】34【樣例3】見選子 I錄卜的 rxmte/

7、route3.tn - j route/raiiteS.avis* 諺樣例的數(shù)據(jù)類型與瑕終測試點(diǎn)58致。見選 FJ親卜的 raute/Toute4rautc/routed anso該樣例的數(shù)據(jù)類型與域終測試點(diǎn)11 M 致.【樣例5】見選 FII 錄卜的 v'oute/vouteS.in fJ rwite/route5.ana 該樣例的數(shù)據(jù)類型與最終測試點(diǎn)18-20 -致.【數(shù)據(jù)范圍與提示】對F所有測試點(diǎn),2<n< nr 5 1 < /n < 2 X l()f,()W A W 10 0W B.C W IO61 S 民< n w * yi . » &

8、lt; E < (ji < 毎個測試點(diǎn)的具體陳制見下范測試點(diǎn)編號nA.H.C特殊限制其他特殊條件1 2< 1(H)=斤一 1無y< 一 冊 +13-1S KM)X = C =()5-89< 2(X)(!< KMX)A = fi = (Xi v為104 =(>H - 14無15A = H = 0無16 - 17< L05<2x 105A = (»18-20無機(jī)器人(robot.)【題目描述】小R焉炊硏究機(jī)器人.鼓近，小K新研制出了胸種機(jī)器人，分別是卩型機(jī)器人和Q熨機(jī)器人?，F(xiàn)伍他要 測試達(dá)兩粧機(jī)器人的移動能力.側(cè)試托從左到右排成-排的

9、”個桂了上進(jìn)行，柱了用 l-n依次編號'號柱子的島度為一個止整數(shù)人。機(jī)器人只能在相鄰柱子間移動,即: 若機(jī)器人當(dāng)前征r號柱子上，它貝能嘗試移動到j(luò)- 1號和i - 1號柱子上。每抄;測氐小R會選取個起點(diǎn)”，并將兩種機(jī)器人均放琵在八柱了上。隨厲 它們會按自己的規(guī)則移動。F型機(jī)器人蕓一直冋左移動，們它無法移動到比起點(diǎn)$更高的柱子上。更具休地, P型機(jī)器人H號柱子停止移動"當(dāng)且僅當(dāng)下列兩個條件均成立; I = 1或力 > 幾°對干滿足t j Ss的j,有力S /r,»Q型機(jī)器人會亶向右移動，但它只能移動到比起點(diǎn).、更低的柱了上。更只體地, Q型機(jī)器人在r

10、(r>5)號柱子停止移動，當(dāng)且僅當(dāng)下列兩個條件均成立；廠="或 Ar+1 > A,>對滿足 x < J < r 的 j.hj < /js .規(guī)在，小R可以設(shè)世侮根柱子的赧 i號柱子可選擇的高度范【M為A.-.fi, EP A, < h,. <際 小R冷卑無論測試的起點(diǎn)5選在哪里，兩種機(jī)器人移動過的柱子數(shù)駄的 姥的絕對值邵小于等于2。他想知道有多少種柱了倚度的設(shè)邏方案斶足耍求，小R認(rèn) 為兩種方梟不同當(dāng)且仗蘭蟲在一個匕使得兩種方案中點(diǎn)號社子的島度不同。請你告訴 他滿足要求的方案數(shù)模1U« + 7后的結(jié)果?！据斎敫袷健繌奈募obo

11、t.in中讀入數(shù)據(jù)=>第一行一個正榕數(shù)“表示柱子的數(shù)載。接下來«行,第i行兩個圧整數(shù)兒,分別衣示/號柱了的戟小和駁大高度.【揄出格式】輸出到文件robot,.out中。僅一行一個整數(shù)，表示答案109 4-"的殖<=J 33 3a 41 23 3【樣例1榆岀】【樣例1解釋】柱子髙度共兩種悄況：1. 高度為;32 32 3,此時若起點(diǎn)設(shè)置在5, P型機(jī)器人將停在1號柱子，共移動 4個柱子。Q型機(jī)器人停在5號柱子共移動0個柱子，不符合條件。2. 胎度為：32 4 2；h此時無論起點(diǎn)選在哪.都満是條件具體見卜表：起點(diǎn)編號P塑機(jī)器人Q型機(jī)器人1停在1號柱子.移動過（）個停

12、在2號柱子，移動過1個2停任2號柱了，移動過0個停在2號柱子，移動過0個3停在1號柱子.移動過2個停在5號柱子，移動過2個4停在4號柱子.移動過0個停在4號柱子，移動過0個5停在4號柱子移動過1個停在5號柱子，移動過0個【樣例2】見選手FI 錄卜的 robot/r(jbot2.in *j robot/rvbof2au8°【樣例3見選手11 錄卜的 robot/robot3方1 與 robot/wbod【樣例1見選丁|求 F的 robo>t/robot4 *J rot)ot/n)l)ot4-(ms【數(shù)據(jù)茫圍與提示】對于所有測試數(shù)4g： 1</1<300 , 1<

13、 (化每個測試點(diǎn)的具體限制見下麥;測試點(diǎn)編號/? <特殊性質(zhì)1.27A, = B； H； < 7X4BT5,6,750R, < 1009,10300Bi < 100()011J25()兒=B( = W9iritis無16.171501&192002030()序歹ij (sequence)【題目描述】給定兩個長度為n的正整數(shù)序列仞與bA，序列的下標(biāo)為1,2.現(xiàn)在你需 嬰分別對兩個序列各指定恰好K個F標(biāo)，翌求至少有L個下標(biāo)在兩個序列中都被檔定, 便得這2K個下標(biāo)在序列中對應(yīng)的元索的總和最大。形式化地說.你而要確定兩個長度為K的序列CAM.其中1 < <i

14、 < 2 < v “ S .1 < di < d, < - v d忙玉 n并要求H標(biāo)足晟大化以十以/IMb I【輸入格式】從文setienc.in中讀入數(shù)據(jù)。本麺輸入文什包含多組數(shù)據(jù)，第一行一個止整數(shù)7農(nóng)示數(shù)粥組數(shù)-接卜來每三行農(nóng)示一組數(shù)粧。每組數(shù)據(jù)第一行三個整數(shù)n.K.L,變就恿義見題目描述。毎組數(shù)據(jù)第二行n個整數(shù)左示序列|«.b伸組數(shù)嶠第三行”個整數(shù)表示序列血卜【輸岀格式】輸出到文件gywarge.gl中g(shù)對于毎組數(shù)槪輸出一行一個鑒數(shù)義示答案。【樣例1輸入】5111775 214 5584217276 411 583242 693177 541 66 65 9 19 53 914 2【樣例1諭出】274562【樣例1解釋】第一組數(shù)據(jù)選擇的下標(biāo)為：=,綽=仲第二組數(shù)據(jù)選擇的卜標(biāo)為! Ct = II.-31 .（咖二12.31第三組數(shù)據(jù)選擇的下標(biāo)為：問=13,41 同| = 3.5。第四組數(shù)據(jù)選樣的F標(biāo)為:cg = 12,3,4,6）M = N34,6L第丘組數(shù)據(jù)選擇的卜標(biāo)為：仙=憶孑45.® , 如=口2認(rèn)6）°【樣例2】見選 于*11 錄 卜的 sequence /sequence 2. in -j sequence/gequenceZ.ans o【樣例33見選 FLI 余 卜 的 超邑qu的me