資源簡介

全國青少年信息學奧林匹克競賽
CCF
NOI
2018
第二試
時間:2018年7月20日08:00~13:00
題目名稱
屠龍勇士
情報中心
多邊形
題日類型
傳統(tǒng)型
傳統(tǒng)型
傳統(tǒng)型
目錄
dragon
center
polygon
可執(zhí)行文件名
dragon
center
polygon
輸入文件名
dragon.
in
center.
in
polygon.
In
輸出文件名
dragon
out
center.
out
polygon.
out
每個測試點時限20秒
8.0秒
10.0秒
內(nèi)存限制
512MB
512MB
512MB
測試點/包數(shù)目
20
20
20
測試點是否等分是
是
是
提交源程序文件名
對于C++語言
dragon.cp
center.
cpp
polygon.
cpp
對于C語言
dragon.
c
center.
c
polygon.
C
對于
Pascal語言
dragon.
pas
center.
pas
polygon.
pas
編譯選項
對于C++語言
02-1m
對于C語言
02-1m
對于
Pascal語言
-02
注意事項:
1、提交的源文件必須存放在已建立好的下發(fā)樣例的文件夾中(該文件夾與試題同名)。
2、文件名(包括程序名和輸入輸出文件名)必須使用英文小寫。
3、結果比較方式為忽略行末空格、文末回車后的全文比較。
4、C/C++中函數(shù)main(的返回值類型必須是int,值為0。
全國青少年信息學奧林匹克競賽
第二試屠龍勇士(
dragon)
屠龍勇士(
dragon)
【題目描述】
小D最近在網(wǎng)上發(fā)現(xiàn)了一款小游戲。游戲的規(guī)則如下:
游戲的目標是按照編號1-n順序殺掉n條巨龍,每條巨龍擁有一個初始的生命
值a;。同時每條巨龍擁有恢復能力,當其使用恢復能力時,它的生命值就會每
次增加p;,直至生命值非負。只有在攻擊結束后且當生命值恰好為0時它才會
死去。
游戲開始時玩家擁有m把攻擊力已知的劍,每次面對巨龍時,玩家只能選擇
把劍,當殺死巨龍后這把劍就會消失,但作為獎勵,玩家會獲得全新的一把劍。
小D覺得這款游戲十分無聊,但最快通關的玩家可以獲得ION2018的參賽資格,
于是小D決定寫一個笨笨的機器人幫她通關這款游戲,她寫的機器人遵循以下規(guī)則
每次面對巨龍時,機器人會選擇當前擁有的,攻擊力不高于巨龍初始生命值中攻
擊力最大的一把劍作為武器。如果沒有這樣的劍,則選擇攻擊力最低的一把劍作
為武器。
●機器人面對每條巨龍,它都會使用上一步中選擇的劍攻擊巨龍固定的x次,使
巨龍的生命值減少x×ATK。
之后,巨龍會不斷使用恢復能力,每次恢復p;生命值。若在使用恢復能力前或
某一次恢復后其生命值為0,則巨龍死亡,玩家通過本關。
那么顯然機器人的攻擊次數(shù)是決定能否最快通關這款游戲的關鍵。小D現(xiàn)在得知
了每條巨龍的所有屬性,她想考考你,你知道應該將機器人的攻擊次數(shù)x設置為多少,
才能用最少的攻擊次數(shù)通關游戲嗎?
當然如果無論設置成多少都無法通關游戲,輸出-1即可。
【輸入格式】
從文件
dragon.,in中讀入數(shù)據(jù)。
第一行一個整數(shù)T,代表數(shù)據(jù)組數(shù)。
接下來T組數(shù)據(jù),每組數(shù)據(jù)包含5行。
每組數(shù)據(jù)的第一行包含兩個整數(shù),n和m,代表巨龍的數(shù)量和初始劍的數(shù)量
接下來一行包含n個正整數(shù),第i個數(shù)表示第i條巨龍的初始生命值
接下來一行包含n個正整數(shù),第i個數(shù)表示第i條巨龍的恢復能力p;
●接下來一行包含n個正整數(shù),第i個數(shù)表示殺死第i條巨龍后獎勵的劍的攻擊
力
接下來一行包含m個正整數(shù),表示初始擁有的m把劍的攻擊力。

展開更多......

收起↑