網(wǎng)上找的一些算法數(shù)論江蘇2002task

1、JSOI2002江蘇省代表隊(duì)組隊(duì)選拔賽本次競賽共分兩試，本試卷為第二試第二試試題競賽時(shí)間：2002 年 5 月 4 日 8:1511:45試題說明分?jǐn)?shù)分布第一試共三道題，滿分為 160 分。文件命名選手提交的可執(zhí)行程序應(yīng)以”.exe”為后綴，名字附于每題標(biāo)題后，并最終拷貝到指定硬盤的相應(yīng)目錄下。源文件的名字應(yīng)與編譯后的可執(zhí)行程序同名。選手程序應(yīng)從 .IN 中讀入輸入數(shù)據(jù)，不需要進(jìn)行判錯(cuò)處理。執(zhí)行結(jié)果存放到 .OUT 中。輸入輸出文件均不需指定目錄。程序運(yùn)行要求評測時(shí)采用黑盒測試，對每個(gè)測試點(diǎn)有一定的時(shí)間限制和分?jǐn)?shù)。選手程序必須在此時(shí)限內(nèi)運(yùn)行結(jié)束并輸出正確的結(jié)果才能得到這個(gè)點(diǎn)的分?jǐn)?shù)。程序運(yùn)行時(shí)僅

2、對指定的文件讀寫，不應(yīng)在屏幕上顯示任何信息或者等待鍵盤輸入。試題名稱分值可執(zhí)行文件輸入文件輸出文件限時(shí)圓錐 體積計(jì)算46JSOI06.EXEJSOI06.INJSOI06.OUT5s凸多邊形分割54JSOI07.EXEJSOI07.INJSOI07.OUT5s基本粒子60JSOI08.EXEJSOI08.INJSOI08.OUT5s輸出結(jié)果應(yīng)按題面要求，不應(yīng)有多余的字符。題六圓錐體積計(jì)算JSOI06.IN.OUT.PAS/.CPP/.EXE問題描述設(shè)有一個(gè)高為 H，底半徑為 R 的正圓錐，其體積的計(jì)算方法如下： 將此圓錐按高分成 n 個(gè)等份，如下圖中的（b）。對分成的每個(gè)部分都可以近似地看成一

3、個(gè)圓柱體，如圖（c）中的ABCD。HACBDRH圖(a)圖（b）圖（c）圓柱體的體積計(jì)算公式為底面積乘高。對圖（c）陰影部分而言，此時(shí)有 2 種計(jì)算方法：（1）用 AC 為底計(jì)算，計(jì)算出來的體積要比實(shí)際體積小，稱之為小體積；（2）用 BD 為底計(jì)算，計(jì)算出來的體積要比實(shí)際體積大，稱之為大體積。然后，將每種分割方案中的所有小體積相加，作為圓錐的小近似值，記為 V1；再將每種分割方案中的所有大體積相加，作為圓錐的大近似值，記為 V2?？梢钥闯?，當(dāng) n 增加時(shí)，其差 V2 - V1 就必然減少。現(xiàn)規(guī)定，當(dāng) V2-V10.0001 時(shí),就將(V1+V2)/2 作為圓錐的體積。問題：給出 H 與 R，假

4、設(shè)使用的是一臺理想計(jì)算機(jī)，無舍入誤差，求得一個(gè)最小的 n，使V2-V10.0001。 （取 3） 輸 入 輸入文件名：JSOI0.IN其中：第一行有一個(gè)整數(shù)，表示有組輸入數(shù)據(jù)；每組均為一行，有二個(gè)實(shí)數(shù)，表示該組圓錐的高與底半徑（用一個(gè)空格分開）。輸出輸出文件名：JSOI06.OUT .共有行，每行輸出一個(gè)整數(shù)，表示求得的最小的n。題七凸多邊形分割jsoi07/. in /. Out /.pas/.cpp/.exe 問題描述 設(shè)有一個(gè)凸多邊形，其頂點(diǎn)個(gè)數(shù)為 n（3 n 2）。知道可以用 n-3 條不相交的對角線將凸多邊形分為 n-2 個(gè)三角形。如下圖是 n=5 的五種分法：要求給出一種分法，使對

5、角線長度之和為最小。輸入輸入文件名：JSOI07.IN . 其中：第一行有一個(gè)整數(shù)，表示有組輸入數(shù)據(jù)；每組的第一行有一個(gè)整數(shù) n，表示該組測試數(shù)據(jù)的凸多邊形數(shù)；接下來的n 行，每行均有二個(gè)整數(shù)，表示頂點(diǎn)坐標(biāo)（用一個(gè)空格分開）。輸出輸出文件名：JSOI07.OUT .共有行，每行輸出一個(gè)實(shí)數(shù)，為最小對角線長度之和，結(jié)果保留二位小數(shù)。樣例輸入 文 件：1441012234 4輸 出 文 件：200題八基本粒子的超作用jsoi08/. in /. Out /.pas/.cpp/.exe 問題描述 T 博士在一種叫做 Ft 的基本粒子。他發(fā)現(xiàn)把 n 個(gè) Ft 粒子在一起的時(shí)候，會發(fā)生一種可以觀測到的特

6、殊效應(yīng)，被稱之為 Ft 效應(yīng)。奇怪的是，每次選取 n 個(gè)粒子進(jìn)行試驗(yàn)得到 Ft 效應(yīng)的結(jié)果都不盡相同。有人認(rèn)為，這說明 Ft 粒子并不是基本粒子，而是在精細(xì)結(jié)構(gòu)上分化為幾種不同的粒子。然而，T 博士卻不同意這種觀點(diǎn)。他猜想，在兩個(gè) Ft 粒子之間存在著一種超作用。但并不是每兩個(gè)粒子之間都有這種作用，有的粒子根本不和其他粒子發(fā)生作用，而有的則和多個(gè)粒子分別發(fā)生作用。如果用點(diǎn)來表示粒子，用邊來表示超作用，那么 n 個(gè)粒子之間的超作用關(guān)系就是一個(gè)無自環(huán)無重邊的無向圖。T 博士認(rèn)為正是圖的結(jié)構(gòu)決定了 Ft 效應(yīng)的結(jié)果。T 博士打算這樣驗(yàn)證他的想法。他先把試驗(yàn)結(jié)果分類，發(fā)現(xiàn) n 個(gè)粒子產(chǎn)生 Ft 效應(yīng)的

7、結(jié)果最多只有 X 種。如果表示 n 個(gè)粒子超作用關(guān)系的無向圖的數(shù)量也恰好是 X，T 博士的猜想將得到很好的支持。你的任務(wù)就是統(tǒng)計(jì)表示 n 個(gè) Ft 粒子超作用關(guān)系的無向圖的數(shù)量。請注意：T 博士認(rèn)為 Ft 粒子之間是沒有差別的。所以兩個(gè)結(jié)構(gòu)相同的無向圖（同構(gòu)）是同一個(gè)無向圖。 輸 入 輸入文件名：JSOI08.IN。 第一行包含一個(gè)正整數(shù) N，表示有 N 組數(shù)據(jù)。接下來的 N 行，每行一個(gè)整數(shù)（20）。 輸 出 輸出文件名：JSOI08.OUT。共 N 行。每行包含一個(gè)正整數(shù)，即粒子的所有可能的超作用關(guān)系的數(shù)量?！据斎胼敵鰳永浚狠斎胛募敵鑫募?34Jsoi8.outJsoi7.out16.

8、7235.8816.2556.8823.04Jsoi6.out314177854001879649659336011642177152Jsoi6. in51 210 107 421 20108 44Jsoi5.out71391522Jsoi4.out 71820181Jsoi2.out 202102. 5302102. 53331-12707011. 510010104. 5Jsoi3.out 341804551700JSOI1 . OUT12Caban321imix03pk91imix15 9cimi2801JSOI1.IN 51 pop 230 pop 014 no 710 mac 10

9、10 zac 1995JSOI2002表江蘇省代表隊(duì)組隊(duì)選拔賽測試第一試選手簽名輔導(dǎo)教師簽名題輸入文件名輸 出分 值得 分瑪雅日歷Jsoi01.in44444點(diǎn)的劃分Jsoi02.in44444運(yùn)輸問題Jsoi03.in66666最多珠子鏈Jsoi04.in66666單詞連接Jsoi05.in88888評委簽名分得JSOI2002 江蘇省組隊(duì)選拔賽參考第一試題輸入文件名輸 出分值得分瑪雅日歷Jsoi01.in12Caban3241imix043ok941imix1549cimi28014點(diǎn)的劃分Jsoi02.in220102.5( 205)(0 1 3.5)4320102.543331-124

10、770011.5(410100104.54運(yùn)輸問題Jsoi03.in346180645561700606最多珠子鏈Jsoi04.in76單詞連Jsoi05.in6813898188接218JSOI2002表江蘇省代表隊(duì)組隊(duì)選拔賽測試第二試選手簽名輔導(dǎo)教師簽名評委簽名得分題輸入文件名輸 出分 值得 分圓錐體積計(jì)算Jsoi06.in8881012凸多邊形分割Jsoi07.in1010101212基本粒子Jsoi08.in612121416JSOI2002 江蘇省組隊(duì)選拔賽參考第二試題輸入文件名輸 出分 值得 分圓錐體積計(jì)算Jsoi06.in12566583141600183518593826389

11、440110656870860912凸多邊形分割Jsoi07.in167210358810162510568812230412基本粒子Jsoi08.in2611123412123461464549012279579984185616463849074274944016完美 Hamilton 道路【 問題描述 】：一個(gè)圖 G 上的 Hamilton 道路指的是經(jīng)過圖的每個(gè)頂點(diǎn)一次且僅一次的道路。對一個(gè)無向完全圖來說，Hamilton 道路顯然是存在的。然而，另一個(gè)不那么明顯的結(jié)論是：在任意一個(gè)有向完全圖上總是存在著 Hamilton 道路。之為完美 Hamilton 道路。請你找出一個(gè)給定的有向完全圖上的完美 Hamilton 道路（任意一條即可）。【輸入】：輸入文件的一行為一個(gè)正整數(shù)，表示有向圖的頂點(diǎn)數(shù)V。2V10000接下來的 V-1 行為有向圖的邊的信息。第 i 行（2iV）一共有 i-1 個(gè)整數(shù)（取值為