UVa 369 Combinations

-

解題策略

組合公式: C(n,r) = n! / (n-r)!r!
直接使用組合公式來計算結果就可以了。

必須注意的就是階乘的成長速度極快，14! 的值就已經超出long的範圍，更別說第一個範例測資 C(100,6)，100!保證爆掉。所以不能分開計算分子分母最後再相除，要在迴圈中邊乘邊除，壓低計算過程中的數字。

注意

要用浮點數，因為除法會產生小數點。ZeroJudge的測資更嚴苛些，想通過最好把變數精確度提高到long double。而long double與printf溝通的代號是%Lf

碎碎念

偷懶寫的遞迴解法，果然製造 Time Limit Exceeded。自己測了一下，C(34,20)要跑個十來秒，數量級成長很恐怖呀。(汗)


留言

  1. 匿名2012年11月15日 晚上10:56

    這題用DP要怎麼寫?
    100取6還可以計算
    但是到了100取7的時候數字就變成負數了..
    請問..
    有辦法解決嗎?

    回覆刪除
  2. Plover2013年5月1日 上午10:37

    第一個想法就是recursive, 不過C(100,50) 100取50就爆炸了。
    DP的想法就是把rescursive重複計算的部分先 "記" 起來，
    所以直些把所有取法先算完..

    C(0,0) C(1,0) C(2,0) ... C(100,0)
    C(1,1) C(2,1) ... C(100,1)
    C(2,2) ... C(100,2)
    ...
    C(n,m) = C(n-1,m-1) + C(n-1,m) (n > m)
    用這個只會花O(n^2)時間跟空間開始建表，之後查詢O(1)

    Source code: https://bitbucket.org/Menggen/uva/src/e9954c9722df5415c3801b3f027eb059744a8217/UVa/acm_369.cc?at=master

    回覆刪除

張貼留言

這個網誌中的熱門文章

讀書心得: 你以為你以為的就是你以為的嗎?

-
圖片
當初想要接觸哲學的時候，挑上的第一本書就是「你以為你以為就是你以為的嗎?」，因為書名太好玩了。讀完後發現內容也一樣好玩，整本書的形式有點像坊間流行的心理測驗小書，每章的開頭都要讀者先做一組題目，後面接著就對你的答案做一番分析。 我自己的讀後感是，恩，這些題目對一個以前從未接觸過哲學的人來說太過犀利，第一次作答的時候，每翻過一頁都好像在呼自己巴掌，臉頰很燙。 「你以為你以為就是你以為的嗎?」書名念起來很拗口，但是很貼切，因為這些題目為的是要檢查我們腦袋內的想法是否一致，在邏輯上有沒有BUG。 我舉個例子，書裡有道題目「只要不傷害他人，任何人都有權自由追求自己的目標」要讀者回答同不同意，我認為這句話聽起來相當合理，所以勾了同意。過了幾題後，出現另一道題目是「為個人吸食而持有毒品的行為應予除罪化」，這次我的直覺是毒品這麼危險，怎麼可以除罪化呢，馬上勾不同意。 但是，我沒有發現這是刻意安排的陷阱，因為這兩句話其實講的是同一回事。 單純個人持有毒品，不散佈也不販賣，就不算傷害他人，那他就應該有自由追求自己的「吸食毒品」目標的權利，畢竟他只有傷害自己呀。這敘述聽起來有點危險，不過我必須承認一開始的確想的不夠清楚，我以為第一句話是真理，但馬上被反例打了自己的臉。 再舉一個例子，首先是「對藝術品的評斷，純粹是個人品味的問題」，接著是「米開朗基羅是史上數一數二的偉大藝術家」，這牽涉到評斷藝術的標準，不過你只能認同兩句話的其中之一。 書中我最有興趣的是「神明DIY工作室」與「信仰殺戮戰場」，這兩章擺明了直衝基督徒而來。當中有些問題圍繞著以下的敘述，如果你同意「神是全知、全能、又全然慈愛」，那該怎麼解釋世界上發生的許多苦難呢? 比如說被南亞海嘯淹沒的小女孩? 如果神沒辦法消除這些苦難，祂就不是全能。如果神沒辦法事先知道創造出來的世界會有這些苦難，祂就不是全知。如果神明知道有苦難，也有能力去掉，但是卻故意不做，那祂就不是全然慈愛。 我思考後的結論是，全然慈愛的神並不等於神希望世上的苦難越少越好，這些苦難都是在祂的允許下發生的。 書裡指出了一個基督徒的通病，被問倒了之後就嚷嚷「你不知道神是超越人所理解的嗎 」，但回頭又馬上賦予神非常明確地人的屬性。後來我也理解到這些尖銳的問題並不是故意要為難我對神的看法，而是逼迫我去反思一些比較深層的宗教議題，就像我...
閱讀完整內容

UVa 10125 Sumsets

-
解題策略 這題的解法很直接，要找d=a+b+c 用四層迴圈下去跑a,b,c,d就好了 XDDDD 我犯了幾個錯誤 要找最大符合d (意思是數列中可能出現好幾個符合要求的解)，所以迴圈應該由最大元素往下找，第一個找到的解就是答案，我一開始由最小元素往上遞增尋找，拿了WA。 沒找到解就回傳0，殊不知0也有可能是解: 0 = -5 + 3 + 2，這裡也吃了一個WA，所以我後來改回傳 INT_MAX 作為無解。 這題有負值，所以 -5 = -10 + -2 + 7 ，這樣算一組合法的解。 是比較需要小心的地方。 官網論壇上的(a+b)=(d-c)法，方法複雜很多，卻沒有比較快。
閱讀完整內容