ACM程序設(shè)計(jì)大賽

1、第9屆南京大學(xué)ACM程序設(shè)計(jì)大賽9thNanjingUniversityACMLocalProgrammingContest試題冊(cè)2011-05-07第9屆南京大學(xué)ACM程序設(shè)計(jì)大賽 A打飯問(wèn)題描述一天中午，星星來(lái)到了食堂吃午飯，如往常一樣，食堂里己經(jīng)排起了長(zhǎng)長(zhǎng)的隊(duì)伍。然而今天有一個(gè)很奇特的現(xiàn)象，隊(duì)伍中的同學(xué)全都是星星的好朋友。眾所周知，食堂的飯菜是很折磨人的，以至于星星只對(duì)某幾種菜感興趣。為了能打到自己感興趣的菜，星星只好采取一種邪惡的方案一插隊(duì)。雖然星星的朋友都很樂(lè)意讓星星插隊(duì)到他們前面以便和星星一起探討“學(xué)術(shù)”問(wèn)題，但是星星還是不想影響到太多的同學(xué)。星星通過(guò)某種神奇的方式得知了隊(duì)伍中每個(gè)

2、同學(xué)對(duì)每種菜的需求量，以及食堂中每種菜剩余的量。星星告訴你他對(duì)每種飯菜的需求量，由于星星數(shù)學(xué)不好，希望你能編寫(xiě)一個(gè)程序告訴他在第幾個(gè)同學(xué)前插隊(duì)剛好能打到所需飯菜。輸入格式A/mVoM表示今日食堂提供的飯菜的種類數(shù)，N表示隊(duì)第一行，兩個(gè)整數(shù)：伍中一共有多少同學(xué)。其中第j個(gè)數(shù)兒表示星星到達(dá)食堂時(shí)第j種菜的剩余量。第二行，A/個(gè)整數(shù)，第三行，M個(gè)整數(shù)，其中第j個(gè)數(shù)巧表示星星對(duì)第j種菜的需求量，坊=()表示星星對(duì)第j種菜不感興趣。接下來(lái)N行，每行M個(gè)整數(shù)，第i(l?：第J(lSjSM)個(gè)數(shù)Gj，表示隊(duì)伍中第?:個(gè)同學(xué)對(duì)第J種菜的需求量。其中1N100,1M10,0Aj,BjyCij100o輸出格式一個(gè)

3、整數(shù)?:，表示星星插隊(duì)在第:個(gè)同學(xué)之前恰好能打到所需的菜。若星星無(wú)論如何都無(wú)法打到所需的菜，輸出若無(wú)需插隊(duì)就能打到所需的菜，輸出N+1。樣例輸入101055237822樣例輸出2提示每位同學(xué)打菜時(shí)，即使第j種菜剩余量不足他所需時(shí)，也會(huì)打走剩余的所有第J種菜，然而星星是希望輪到他的時(shí)候，他感興趣的菜都剩余足夠的份量。B.X問(wèn)題描述“說(shuō)感覺(jué)不只嗅覺(jué)還有味覺(jué)有觸覺(jué)聽(tīng)覺(jué)到體會(huì)都是誤會(huì)偶而約會(huì)卻沒(méi)有感覺(jué)有一天，星星正在聽(tīng)林俊杰的“X”，突然靈光一現(xiàn)，發(fā)現(xiàn)X是一個(gè)十分有意思的字母。星星在X的左上，右上，左下，右下四個(gè)方向上畫(huà)上X,得到了如下的圖形：XXXXX它仍然是X形的，星星狂熱地迷戀一切X形和星形的東

4、西。于是星星又干了如下的事情：星星繼續(xù)在上圖的左上，右上，左下，右下四個(gè)方向上重復(fù)同樣的圖形，得到如下的圖形：XXXXXXXXX星星將剛才得到的圖形編號(hào)為2,并將之前得到的圖形編號(hào)為將一個(gè)“X”編號(hào)為0。星星繼續(xù)在圖形2的左上，右上，左下，右下四個(gè)方向上重復(fù)圖形2,得到了圖形3；緊接著星星又依次得到了圖形4,圖形5?？墒钱?dāng)畫(huà)到圖形5的時(shí)候，星星的紙已經(jīng)被畫(huà)得滿滿的了。被逼無(wú)奈，星星只好求助于你，你能寫(xiě)一個(gè)程序來(lái)幫助星星得到他想要的圖形么？輸入格式若干行，每行一個(gè)整數(shù)i(i7),以-1結(jié)束。輸出格式對(duì)于每一個(gè)輸入譏輸出編號(hào)為2的圖形，每個(gè)圖形后面輸出一空行。每行后面多余的空格不要輸出。樣例輸入0

5、1-1樣例輸出XXXXXX提示每行后面多余的空格不要輸出。第9屆南京大學(xué)ACM程序設(shè)計(jì)大賽 C星形面積問(wèn)題描述上題說(shuō)到，星星狂熱地迷戀一切x形和星形的東西。星星希望得到自己所喜歡的星形的一切數(shù)據(jù)，包括面積。請(qǐng)你編寫(xiě)一個(gè)程序幫星星計(jì)算N角星的面積。輸入格式第一行：一個(gè)整數(shù)N(5N20)o第2N+1行：每行兩個(gè)實(shí)藪表示N角星的第2：個(gè)角頂點(diǎn)的坐標(biāo)。N個(gè)頂點(diǎn)按順時(shí)針?lè)较蚪o出。輸出格式一個(gè)實(shí)數(shù)，所給出N角星的面積，結(jié)果保留2位小數(shù)。樣例輸入0.000002.000001.732051.000001.73205-1.000000.00000-2.00000-1.73205-1.00000-1.73205

6、1.00000樣例輸出6.93提示所謂N角星，是題中所給N個(gè)頂點(diǎn)，第2個(gè)頂點(diǎn)與第(z+2)%Ar個(gè)頂點(diǎn)相連接圍成的圖形，例如樣例中給出的是一個(gè)六角星：D瓶子問(wèn)題描述星星去火星旅行，但是準(zhǔn)備回地球的時(shí)候，他發(fā)現(xiàn)飛船的燃料不夠了。于是星星去向火星人借燃料，火星人答應(yīng)了，要求星星用飛船上的瓶子來(lái)交換。星星的飛船上共有N個(gè)瓶子(1N1.000),經(jīng)過(guò)協(xié)商，火星人只要其中的K個(gè)(1KN)O星星將K個(gè)瓶手交給火星人之后，火星人用他們裝一些燃料給星星。厲有南瓶子都沒(méi)有刻度，只是在瓶口標(biāo)注了容量，第，個(gè)瓶子的容量為(S為整數(shù)，并滿足13L000.000,000)o火星人比較吝嗇，他佛并不會(huì)把所有的瓶子都裝滿燃

7、料。他們拿到瓶子后,會(huì)跑到燃料庫(kù)里鼓搗一通，弄出一小點(diǎn)燃料來(lái)交差。星星當(dāng)然知道他們會(huì)來(lái)這一手，于是事先了解了火星人鼓搗的具體內(nèi)容?；鹦侨嗽谌剂蠋?kù)里只會(huì)做如下的3種操作：將某個(gè)瓶子裝滿燃料；將某個(gè)瓶子中的燃料全部倒回燃料庫(kù)；將燃料從瓶子m倒向瓶子b,直到瓶子b滿或者瓶子a空(燃料傾倒過(guò)程中的損耗可以忽略)。火星人拿出的燃料，當(dāng)然是這些操作所能得到的最小正體積。星星知道，對(duì)于不同的瓶子組合，火星人可能會(huì)被迫給出不同體積的燃料。星星希望找到最優(yōu)的瓶子組合，使得火星人給出盡量多的燃料。輸入格式第一行：2個(gè)整數(shù)N、K。第2N+1行:每看1個(gè)整數(shù)，第2+1行的整數(shù)為3。輸出格式僅一行，一個(gè)整數(shù)，表示火星人

8、給出燃料的最大值。樣例輸入32344樣例輸出4E燃料購(gòu)買問(wèn)題描述在火星上因?yàn)槿剂系膯?wèn)題耽擱了很長(zhǎng)時(shí)間，星星回到地球后決定對(duì)燃料好好研究一番，防止在以后的星際旅行中遇到同樣尷尬的局面。星星發(fā)現(xiàn)，為了方便星際旅行，人類在星際中建立了若干中轉(zhuǎn)站，每個(gè)中轉(zhuǎn)站均有燃料出售，不同中轉(zhuǎn)站燃料的售價(jià)不同。星星意識(shí)到，如果采取合適的策略來(lái)購(gòu)買燃料，他可能在一次星際旅行中省下一大筆錢。星際之中充滿了未知的危險(xiǎn)，星際旅行必須遵行一定的航線。星星希望你能編寫(xiě)一個(gè)程序幫助他計(jì)算能否從一個(gè)中轉(zhuǎn)站到達(dá)另一個(gè)中轉(zhuǎn)站，并且計(jì)算出最小的消費(fèi)。假設(shè)飛船每行駛1單位距離消耗1單位體積的燃料，最初飛船的燃料箱中沒(méi)有燃料。輸入格式第一行

9、，兩個(gè)整數(shù)n,m.(ln1,000,0m10,000),分別表示中轉(zhuǎn)站的數(shù)目和航線的條數(shù)。第二行，個(gè)整數(shù)，其中刃表示第2：個(gè)中轉(zhuǎn)站的燃料單價(jià)。接下來(lái)m行,每行3個(gè)整數(shù)d(0u,v碼1d100),表示編號(hào)為艸的中轉(zhuǎn)站之間存在一條長(zhǎng)度為白勺航線。第m+3行，一個(gè)整數(shù)g(lq100)表示詢問(wèn)次數(shù)。接下來(lái)g行,每行3個(gè)整數(shù)s,e5c(0s.en.lc貞中點(diǎn)示蕓音馥的氮句歌詞。2第二類情況，對(duì)于一首不完整的歌，它的數(shù)據(jù)有可能是這樣表示的：1101120菱就直說(shuō):每當(dāng)星星唱這首歌的時(shí)候，都只會(huì)依次唱出第1句，第10句,第11句和第20句，其他的歌詞都會(huì)被星星跳過(guò)，并且星星自己不會(huì)感覺(jué)到任何異常。3.然而，

10、第二類情況并不是最嚴(yán)重的，有可能還會(huì)出現(xiàn)這樣的數(shù)據(jù)：?2?5?7?,?這類歌是星星不常唱的歌，其中有些數(shù)據(jù)已經(jīng)模糊不清了，我們用問(wèn)號(hào)（？）表示看不清的數(shù)據(jù)，每一個(gè)問(wèn)號(hào)（？）所在的位置原本可能是一個(gè)數(shù)字（0-9）,也有可能是一個(gè)逗號(hào)（J。每當(dāng)星星唱這種歌遇到問(wèn)號(hào)之后，星星的大腦不知道如何處理，歌聲就會(huì)戛然而止，也就是出現(xiàn)了所謂忘詞的情況?，F(xiàn)在S.W.A.T要做的事就是將這類數(shù)據(jù)恢復(fù)，即用數(shù)字或者逗號(hào)來(lái)替換掉每一個(gè)問(wèn)號(hào)，使數(shù)據(jù)變成如衛(wèi)2衛(wèi)3廠，如的格式。其中為正整數(shù)，并且滿足a2a3如。另外，已經(jīng)能夠看清的數(shù)據(jù)是不能更改的，否則可能對(duì)星星的記憶造成嚴(yán)重的損傷。為了能盡快恢復(fù)所有數(shù)據(jù)，S.W.A.T

11、希望你能幫他編寫(xiě)一個(gè)程序來(lái)解決這個(gè)問(wèn)題。輸入格式輸入有若干行，第行是第2首歌的數(shù)據(jù)。每行不超過(guò)50（）個(gè)字符。輸出格式輸出若干行，第?:行是第i首歌的數(shù)據(jù)恢復(fù)后的結(jié)果，若數(shù)據(jù)無(wú)法恢復(fù)成為指定格式，輸出impossible若存在多種恢復(fù)結(jié)果，選取第一個(gè)數(shù)最小的結(jié)果輸出，如果仍然存在多種結(jié)果，選取第二個(gè)數(shù)最小的結(jié)果輸出，以此類推。樣例輸入?,10,?,16,?2?5?7?,?樣例輸出impossible12,50,70,711,2,3,4,5,6,7,8,9,10,11,100,101,102提示1.每個(gè)數(shù)字或逗號(hào)只能替換掉一個(gè)問(wèn)號(hào)，也就是說(shuō)，恢復(fù)后的數(shù)據(jù)和原始數(shù)據(jù)的長(zhǎng)度是相同的。2每首歌的歌詞數(shù)

12、沒(méi)有上限。第9屆南京大學(xué)ACM程序設(shè)計(jì)大賽 G和諧區(qū)間問(wèn)題描述在一個(gè)奇異世界里，存在著一個(gè)星星王國(guó)，所有的星星都在一條直線上。在這個(gè)星星王國(guó)中生活著兩種星星：左星星和右星星，左星星總是凝望著它的右邊，右星星總是凝望著它的左邊，和互望見(jiàn)的左星星和右星星之間可能會(huì)相互吸引，然后配對(duì)。對(duì)于一串尚未配對(duì)的星星來(lái)說(shuō)，總是從最右邊的左星星(從右往左)開(kāi)始配對(duì)，并且每個(gè)左星星會(huì)選擇它右邊離它最近的一個(gè)尚未配對(duì)的右星星與之配對(duì)。當(dāng)配對(duì)結(jié)束后，有可能剩下尚未匹配的左星星和右星星，這種星星會(huì)煩躁、不安、具有暴力傾向，一大堆這樣的星星聚集在一起的話，其至可能引發(fā)暴動(dòng)，總之就是不和諧了。當(dāng)然，在英明神武的星星國(guó)王領(lǐng)導(dǎo)

13、下，整個(gè)王國(guó)之中還是比較和諧的。不過(guò)有一次，國(guó)王希望到它的王國(guó)中去視察，大臣們出于國(guó)王的安全考慮，準(zhǔn)備將國(guó)土視察的區(qū)域用高高的用墻圍起來(lái)。但是這樣子的話，圍墻內(nèi)外的星星和互之間就看不見(jiàn)了，圍墻內(nèi)的星星需要重新配對(duì)。當(dāng)然，大臣們是不希望這個(gè)區(qū)域內(nèi)出現(xiàn)不和諧因素的，也就是說(shuō)他們希望這個(gè)區(qū)域內(nèi)的所有星星都能全部配對(duì)成功。國(guó)土希望視察很多區(qū)域，但是由于國(guó)土的時(shí)間有限只能視察一個(gè)區(qū)域，所以他給出很多候選區(qū)域并讓大臣們最終確定一個(gè)區(qū)域作為視察的目的地。但星星土國(guó)的居民實(shí)在是太多了，大臣們很難判斷出這些區(qū)域會(huì)不會(huì)存在不和諧的因素,希望你能編寫(xiě)一個(gè)程序來(lái)判斷國(guó)王給出的每個(gè)候選區(qū)間會(huì)不會(huì)不和諧。輸入格式第一行，

14、一個(gè)字符串，其長(zhǎng)度小于等于100,000,表示星星王國(guó)中星星居民的居住情況。我們用左方括號(hào)“”表示一個(gè)左星星，右方括號(hào)“”表示一個(gè)右星星，星星們從左往右從1開(kāi)始編號(hào)。例如“”，編號(hào)為1,2,3,4的星星分別為：右星星，左星星，右星星，左星星。第二行，一個(gè)整數(shù)N(1N100.000),表示國(guó)王所給的候選區(qū)域數(shù)目。接下來(lái)N行，每行兩個(gè)藪數(shù)表示每個(gè)候選區(qū)間的起始點(diǎn)和終點(diǎn)。輸出格式N行,若第，個(gè)候選區(qū)間是和諧的，輸出“HeXie”，若該區(qū)間是不和諧的,輸出“BuHeXie”。樣例輸入樣例輸出BuHeXie4BuHeXie22HeXie12BuHeXie2314H小行星問(wèn)題描述為了維護(hù)宇宙的和平，星星創(chuàng)建了一個(gè)“碰撞管理協(xié)會(huì)”(AssociationofCollisionManagement,下面簡(jiǎn)稱ACM)來(lái)研究星體之間的碰撞。目前ACM正在進(jìn)行一項(xiàng)實(shí)驗(yàn)，他們希望牽引兩顆小行星緩慢靠近，最終組成一個(gè)穩(wěn)定的星體。兩顆小行星都是凸多面體形的，為了提高實(shí)驗(yàn)成功的幾率，ACM希望兩顆小行星靠近時(shí)他們的重心盡可能靠近。為了達(dá)到這個(gè)目標(biāo)，ACM的操作員可以在兩顆小行星靠近之前任意旋轉(zhuǎn)這兩顆小行星。請(qǐng)幫助ACM計(jì)算出兩顆小行星碰撞時(shí)，它們重心之間可能的最短距離。兩顆小行星都可以被認(rèn)為是均勻密度的。輸入格式輸入文件包