【文章內(nèi)容簡介】 、 1 2 3 4 1 2 3。 你任務(wù)是求出一個(gè)序列用上面的方法排序至少需要多少步。 【 要求 】 【 數(shù)據(jù)輸入 】 輸入文件有兩行：第一行是一個(gè)整數(shù) n，表示數(shù)列的長度。第二行有 n個(gè)整數(shù)，表示待排序的數(shù)列，每個(gè)整數(shù)的絕對值不大于 32767。 【 數(shù)據(jù)輸出 】 輸出文件有一行是一個(gè)整數(shù) s，表示完成排序所需的最少步數(shù)。 【 樣例輸入 】 4 3 2 1 4 【 樣例輸出 】 1 提 示： 只需要一步就可以完成排序： 3 2 1 4 1 2 3 4。 選址 Time limit: 10s Memory limit: 32768K Total Submit : 100 Accepted Submit : 13 【問題描述】 很久以前，在世界的某處有一個(gè)形狀為凸多邊形的小島，島上的居民們決定建一個(gè)祭壇，居民們認(rèn)為祭壇的位置離島的頂點(diǎn)處越遠(yuǎn)越好。你的任務(wù)是求凸多邊形內(nèi)一點(diǎn)，使其與各頂點(diǎn)的距離中最短的距離最遠(yuǎn)，點(diǎn)在邊上也可以。這樣的點(diǎn)可能有多個(gè)，你只需輸出這些點(diǎn)與各頂 點(diǎn)的最短距離。 【 要求 】 【 數(shù)據(jù)輸入 】 第一行是一個(gè)整數(shù) N(3≤ N≤ 100)。 接下來 N 行按逆時(shí)針順序給出每個(gè)頂點(diǎn)的坐標(biāo)，每行包含 2 個(gè)實(shí)數(shù)，表示頂點(diǎn)的橫坐標(biāo)和縱坐標(biāo) (坐標(biāo)絕對值小于 10000)。 【 數(shù)據(jù)輸出 】 輸出一個(gè)實(shí)數(shù)，表示凸多邊形內(nèi)一點(diǎn)與各頂點(diǎn)的距離中最短的距離的最大值。 【 樣例輸入 】 3 0 2 9 0 7 7 【 樣例輸出 】 過河 Time limit: 1s Memory limit: 32768K Total Submit : 518 Accepted Submit : 65 【問題描述】 在河上有一座獨(dú)木橋，一只青蛙想沿著獨(dú)木橋從河的一側(cè)跳到另一側(cè)。在橋上有一些石子，青蛙很討厭踩在這些石子上。由于橋的長度和青蛙一次跳過的距離都是正整數(shù)，我們可以把獨(dú)木橋上青蛙可能到達(dá)的點(diǎn)看成數(shù)軸上的一串整點(diǎn)： 0， 1，??， L（其中 L是橋的長度）。坐標(biāo)為 0 的點(diǎn)表示橋的起點(diǎn)，坐標(biāo)為 L 的點(diǎn)表示橋的終點(diǎn)。青蛙從橋的起點(diǎn)開始，不停的向終點(diǎn)方向跳躍。一次跳躍的距離是 S 到 T 之間的任意正整數(shù)（包括 S,T）。當(dāng)青蛙跳到或跳過坐標(biāo)為 L的點(diǎn)時(shí)，就算青蛙已經(jīng)跳出了獨(dú)木橋。題目給出獨(dú)木橋的長度 L，青蛙跳躍的距離范圍 S,T，橋上石子的位置。你的任務(wù)是確定青蛙要想過河，最少需要踩到的石子數(shù)。 【 要求 】 【 數(shù)據(jù)輸入 】 輸入的第一行有一個(gè)正整數(shù) L（ 1 = L = 109），表示獨(dú)木橋的長度。第二行有三個(gè)正整數(shù) S， T， M，分別表示青蛙一次跳躍的最小距離，最大距離，及橋上石子的個(gè)數(shù)，其中 1 = S = T = 10， 1 = M = 100。第三行有 M 個(gè)不同的正整數(shù)分別表示這 M 個(gè)石子在數(shù)軸上的位置（數(shù)據(jù)保證橋的起點(diǎn)和終點(diǎn)處沒有石子）。所有相鄰的整數(shù)之間用一個(gè)空格隔開。 【 數(shù)據(jù)輸出 】 輸出只包括一 個(gè)整數(shù)，表示青蛙過河最少需要踩到的石子數(shù)。 【 樣例輸入 】 10 2 3 5 2 3 5 6 7 【 樣例輸出 】 2 數(shù)字游戲 Time limit: 1s Memory limit: 32768K Total Submit : 323 Accepted Submit : 89 【問題描述】 小 W 發(fā)明了一個(gè)游戲，他在黑板上寫出了一行數(shù)字 a1,a2,? .an，然后給你 m 個(gè)回合的機(jī)會(huì)，每回合你可以從中選擇一個(gè)數(shù)擦去它，接著剩下來的每個(gè)數(shù)字 ai 都要遞減一個(gè)值 bi。如此重復(fù) m 個(gè)回合，所有 你擦去的數(shù)字之和就是你所得到的分?jǐn)?shù)。 小 W 和他的好朋友小 Y 玩了這個(gè)游戲，可是他發(fā)現(xiàn)，對于每個(gè)給出的 an 和 bn 序列，小 Y 的得分總是比他高，所以他就很不服氣。于是他想讓你幫他算算，對于每個(gè) an 和 bn 序列，可以得到的最大得分是多少。這樣他就知道有沒有可能超過小 Y 的得分。 【 要求 】 【 數(shù)據(jù)輸入 】 第一行，一個(gè)整數(shù) n（ 1=n=200），表示數(shù)字的個(gè)數(shù)。 第二行，一個(gè)整數(shù) m（ 1=m=n），表示回合數(shù)。 接下來一行有 n 個(gè)不超過 10000 的正整數(shù)， a1,a2? an，表示原始數(shù)字 ， 最后一行有 n 個(gè)不超過 500 的正整 數(shù)， b1,b2? .bn，表示每回合每個(gè)數(shù)字遞減的值 【 數(shù)據(jù)輸出 】 一個(gè)整數(shù)，表示最大可能的得分 【 樣例輸入 】 3 3 10 20 30 4 5 6 【 樣例輸出 】 47 速配游戲 Time limit: 5s Memory limit: 32768K Total Submit : 295 Accepted Submit : 209 【問題描述】 有這么一個(gè)速配電視節(jié)目。 N 位男士和 N 位女士要在攝像機(jī)前選出他們合適的伴侶。每位女士按照其對每位男士作為配偶的偏愛程度給每位男士排 名次，每位男士也按照其對每位女士作為配偶的偏愛程度給每位女士排名次。這些名次不允許并列。然后每位男士將向心儀的對象求婚，經(jīng)過 殘酷 的競爭之后各自找到適合的伴侶。 最開始的時(shí)候每位男士都還沒有被任何一位女士拒絕。求婚環(huán)節(jié)會(huì)經(jīng)過很多輪進(jìn)行，每一輪： (1) 每位男士向還沒有拒絕過自己的女士中選出自己認(rèn)為最理想的一個(gè)，并向她求婚 (2) 每位女士在所有這一輪中向她求婚的男士中選出自己認(rèn)為最理想的一個(gè)，并不答應(yīng)，也不拒絕。她把其余向她求婚的男士都婉言拒絕掉。經(jīng)過了若干輪求婚之后，在某一輪，幸運(yùn)的事情發(fā)生了：所有的 女士都恰好有一個(gè)求婚者，所有的男士都找到一個(gè)心儀的對象。主持人將繼續(xù)指出這個(gè)配對方式的神奇之處：沒有任意的兩個(gè)配對，比方說男士 A 和女士 a 配對 ,男士 B 和女士 b 配對，使得在 A心目中 b 較 a 更理想，而且在 b心目中 A較 B 更理想（這樣 A和 b 就會(huì) 私奔 ）。因此，主持人總結(jié)說，這個(gè)配對是非常合理的。（他知道，這種情況是一定會(huì)發(fā)生的。） 主持人在節(jié)目之前已經(jīng)知道男士和女士之間的偏愛情況，他想預(yù)先知道最后的匹配結(jié)果是怎么樣的，你能幫幫他嗎？ 【 要求 】 【 數(shù)據(jù)輸入 】 第一行包括一個(gè)數(shù)字 N（ 1=N=1000）以下 N*2 行，每 行有 N個(gè)數(shù)字。第 i+1行（ 1=i=N）表示編號(hào)為 i的男士對女士們的排序（從最喜歡的到最不喜歡的）。第 N+j+1行（ 1=j=N）表示編號(hào)為 j 的女士對男士們的排序（同樣從最喜歡的到最不喜歡的）。 【 數(shù)據(jù)輸出 】 N 行，每行包括一個(gè)數(shù)字。第 i行的數(shù)字表示與編號(hào)為 i的男士匹配的女士的編號(hào)。 【 樣例輸入 】 3 1 2 3 2 3 1 2 1 3 3 2 1 2 3 1 2 3 1 【 樣例輸出 】 3 2 1 3n+1 數(shù)鏈問題 Time limit: 1s Memory limit: 32768K Total Submit : 471 Accepted Submit : 325 【問題描述】 在計(jì)算機(jī)科學(xué)上，有很多類問題是無法解決的，我們稱之為不可解決問題。然而，在很多情況我們并不知道哪一類問題可以解決，那一類問題不可解決?，F(xiàn)在我們就有這樣一個(gè)問題，問題如下： 1. 輸入一個(gè)正整數(shù) n； 2. 把 n 顯示出來； 3. 如果 n=1 則結(jié)束； 4. 如果 n 是奇數(shù)則 n 變?yōu)? ，否則 n 變?yōu)?n/2； 5. 轉(zhuǎn)入第 2 步。 例如對于輸入的正整數(shù) 22， 應(yīng)該有如下數(shù)列被顯示出來： 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 我們推測：對于任意一個(gè)正整數(shù)，經(jīng)過以上算法最終會(huì)推到 1。盡管這個(gè)算法很簡單，但我們?nèi)匀粺o法確定我們的推斷是否正確。不過好在我們有計(jì)算機(jī)，我們驗(yàn)證了對于小于1,000,000 的正整數(shù)都滿足以上推斷。對于給定的正整數(shù) n，我們把顯示出來的數(shù)的個(gè)數(shù)定義為 n 的鏈長，例如 22 的鏈長為 16。 你的任務(wù)是編寫一個(gè)程序，對于任意一對正整數(shù) i和 j，給出 i、 j之間的最長鏈長，當(dāng)然這個(gè) 最長鏈長是由 i、 j 之間的其中一個(gè)正整數(shù)產(chǎn)生的。我們這里的 i、 j 之間即包括 i也包括 j。 【 要求 】 【 數(shù)據(jù)輸入 】 輸入文件只有一行，即為正整數(shù) i和 j， i和 j 之間以一個(gè)空格隔開。 0 i ≤ j 10,000。 【 數(shù)據(jù)輸出 】 文件只能有一行，即為 i、 j 之間的最長鏈長。 【 樣例輸入 】 1 10 【 樣例輸出 】 20 數(shù)制轉(zhuǎn)換 Time limit: 1s Memory limit: 32768K Total Submit : 479 Accepted Submit : 190 【問題描述】 有一種數(shù)制的基數(shù)是 3，權(quán)值可以取 1,0,1，并分別用符號(hào) ,0,1 表示，如這種數(shù)制的 101 表示十進(jìn)制數(shù)的 10，即 1*(3^2)+0*(3^1)+1*(3^0)=10，又如這種數(shù)制的 0 表示十進(jìn)制數(shù)的 3，即 1*(3^1)+0*(3^0)=3。編程要求把給定的有符號(hào)整數(shù)轉(zhuǎn)換為新數(shù)制的數(shù)，該數(shù)的前面不能有多余的 0，如 10 的新數(shù)制表示是 101，則不要輸出成 0101。 【 要求 】 【 數(shù)據(jù)輸入 】 文件有一行或多行，每行有一個(gè)整數(shù) N (2,147,483,647≤ N≤ 2,147,483,647)，整數(shù)內(nèi)不會(huì)有其他分隔符。 【 數(shù)據(jù)輸出 】 對輸入文件的每一行輸出一行，該行是輸入行的整數(shù)的新數(shù)制表示，不能有多余空行，每行之前不能有前導(dǎo)空格。 【 樣例輸入 】 10 3 【 樣例輸出 】 101 0 數(shù)列 Time limit: 1s Memory limit: 32768K Total Submit : 415 Accepted Submit : 226 【問題描述】 給定一個(gè)正整數(shù) k(3≤ k≤ 15),把所有 k 的方冪及所有有限個(gè)互不相等的 k的方冪之和構(gòu)成一個(gè)遞增的序列，例如， 當(dāng) k=3 時(shí)，這個(gè)序列是： 1， 3， 4， 9， 10， 12， 13，? （該序列實(shí)際上就是： 30， 31， 30+31， 32， 30+32， 31+32， 30+31+32，?） 請你求出這個(gè)序列的第 N 項(xiàng)的值（用 10 進(jìn)制數(shù)表示）。 例如，對于 k=3， N=100，正確答案應(yīng)該是 981。 【 要求 】 【 數(shù)據(jù)輸入 】 輸入包含多個(gè)測試數(shù)據(jù)。 每個(gè)測試數(shù)據(jù)只有 1 行，為 2 個(gè)正整數(shù)，用一個(gè)空格隔開： k N （ k、 N 的含義與上述的問題描述一致，且 3≤ k≤ 15， 10≤ N≤ 1000） 【 數(shù)據(jù)輸出 】 對于每個(gè)測試數(shù)據(jù)輸出一個(gè)正整數(shù)（在所有的測 試數(shù)據(jù)中，結(jié)果均不超過*109）。 【 樣例輸入 】 3 100 3 100 【 樣例輸出 】 981 981 2^k 進(jìn)制數(shù) Time limit: 1s Memory limit: 32768K Total Submit : 110 Accepted Submit : 28 【問題描述】 設(shè) r 是個(gè) 2k 進(jìn)制數(shù)，并滿足以下條件： （ 1） r 至少是個(gè) 2 位的 2k 進(jìn)制數(shù)。 （ 2）作為 2k 進(jìn)制數(shù)，除最后一位外， r 的每一位嚴(yán)格小于它右邊相鄰的那一位。 （ 3）將 r 轉(zhuǎn)換為 2 進(jìn)制數(shù) q 后 ，則 q 的總位數(shù)不超過 w。 在這里，正整數(shù) k（ 1≤ k≤ 9）和 w（ kw≤ 30000）是事先給定的。 問：滿足上述條件的不同的 r 共有多少個(gè)？ 我們再從另一角度作些解釋：設(shè) S是長度為 w 的 01 字符串（即字符串 S 由 w 個(gè)“ 0”或“ 1”組成）， S 對應(yīng)于上述條件（ 3）中的 q。將 S從右起劃分為若干個(gè)長度為 k 的段，每段對應(yīng)一位 2k 進(jìn)制的數(shù)，如果 S 至少可分成 2 段，則 S所對應(yīng)的二進(jìn)制數(shù)又可以轉(zhuǎn)換為上述的 2k 進(jìn)制數(shù) r。 例：設(shè) k=3， w=7。則 r 是個(gè)八進(jìn)制數(shù)（ 23=8）。由于 w=7，長度為 7 的 01 字符串按 3位一段分，可 分為 3 段（即 1， 3， 3，左邊第一段只有一個(gè)二進(jìn)制位），則滿足條件的八進(jìn)制數(shù)有： 2 位數(shù)：高位為 1： 6個(gè)（即 12， 13， 14， 15， 16， 17），高位為 2： 5個(gè)，?，高位為6： 1 個(gè)（即 67）。共 6+5+? +1=21個(gè)。 3位數(shù)：高位只能是 1，第 2 位為 2： 5 個(gè)（即 123，124， 125， 126， 127），第 2 位為 3： 4