2010年3月22日 星期一

UVa 587 There's treasure everywhere!

解題策略

給一張藏寶圖,記載著如何找到寶藏的指令,要算出最終寶藏的確切位置跟及離出發點的距離。這題是典型的模擬題,照著題目要求在平面座標上四處移動就行了。

我在兩個地方稍微傷了點腦筋
  1. 這題的input parsing不好做,或者說用c++ std IO有點麻煩。
    operator>>切字串時不能選擇delimeter,用getline 來切也不能設定超過一個delimeter,可是這題偏偏就有兩個-逗點跟句點。我不想自己切,最後就把字串內的逗點跟句點都換成空白,這樣就能用上stringstream了。
  2. 浮點數誤差:這題送去ZJ後,我拿到一個WA結果如下
您的答案為: The treasure is located at (0.000,-0.000).
正確答案為: The treasure is located at (0.000,0.000).
怎麼會有負零呢!?  應該不是負零,是個非常非常小的負數,因為浮點數不夠精確才產生的誤差,加上一個EPS修正就行了。(不過事實上我對EPS的觀念還不是很懂..orz)

解決這兩項大概就沒問題了,AC get。


2010年3月18日 星期四

UVa 371 Ackermann function

解題策略

爛題目,首先光題目就誤導人了,這題不是Ackermann function ,是 3n+1 ,我還特別跑去確認 Ackermann function 的樣子。

然後兩個很爛的陷阱 (題目敘述沒明說)
1. 有可能 L>H。而最後輸出時必須交換成L<=H ,這跟UVa 100 3n+1不一樣。
2. 題目說範圍不會超過long的真正的意思是unsigned long,所以一般 int 會吃WA。

被細節弄得很火。

提供測資
==input==
2000 3000
3000 2000
0 0

==Output==
Between 2000 and 3000, 2919 generates the longest sequence of 216 values.
Between 2000 and 3000, 2919 generates the longest sequence of 216 values.

UVa 10125 Sumsets

解題策略

這題的解法很直接,要找d=a+b+c
用四層迴圈下去跑a,b,c,d就好了 XDDDD

我犯了幾個錯誤
  1. 要找最大符合d (意思是數列中可能出現好幾個符合要求的解),所以迴圈應該由最大元素往下找,第一個找到的解就是答案,我一開始由最小元素往上遞增尋找,拿了WA。
  2. 沒找到解就回傳0,殊不知0也有可能是解: 0 = -5 + 3 + 2,這裡也吃了一個WA,所以我後來改回傳 INT_MAX 作為無解。
這題有負值,所以 -5 = -10 + -2 + 7 ,這樣算一組合法的解。
是比較需要小心的地方。

官網論壇上的(a+b)=(d-c)法,方法複雜很多,卻沒有比較快。


2010年3月1日 星期一

UVa 357 Let Me Count The Ways

147674同樣的題目,順便就吃下來啦
我發現IE會讓我的程式碼排版亂掉,真讓人困擾@_@

UVa 674 Coin Change

典型的DP題,沒有玩什麼花招..
Sagit's C++ 動態規劃
我想我就不需要多解釋了