[USACO] sec_1-4_The Clocks

過年前來一帖~

有夠詭異的題目

乍看之下用BFS暴搜 DEBUG DE了3小時= =(其實好像還是可以 只是沒找到正確的剪枝而已)

後來想一想(查一查..)由於每個方法轉4次以上就會重複 SO 3^7爆破摟
-----------------------------------------------------------------
試過許多方法 一開始原本要試TBFS(雙向廣度優先搜尋) 後來因為不熟悉用法而且題目要求解路徑

想說太麻煩而改回單純BFS 但又遭遇了一開始提到的問題(重複判斷一直出錯 導致錯誤解)

後來試了下DFS 但好像方法錯了 一直試一直試....

最後只好爬文 剛好看到發人深省的一文

"順序不影響結果 & 鎂種發法超過4次等於沒轉"

怎麼一開始會沒想到呢？ 應該是太執著於DEBUG 而沒有從頭到尾重新檢視題目吧 要以此為鑑阿
-----------------------------------------------------------------
USER: Lee Pu [leepupu1]
TASK: clocks
LANG: C++

Compiling...
Compile: OK

Executing...
Test 1: TEST OK [0.000 secs, 3176 KB]
Test 2: TEST OK [0.000 secs, 3176 KB]
Test 3: TEST OK [0.076 secs, 3176 KB]
Test 4: TEST OK [0.022 secs, 3176 KB]
Test 5: TEST OK [0.054 secs, 3176 KB]
Test 6: TEST OK [0.076 secs, 3176 KB]
Test 7: TEST OK [0.086 secs, 3176 KB]
Test 8: TEST OK [0.054 secs, 3176 KB]
Test 9: TEST OK [0.076 secs, 3176 KB]

All tests OK.
Your program ('clocks') produced all correct answers! This is your
submission #14 for this problem. Congratulations!

Here are the test data inputs:

------- test 1 ----
9 9 12
6 6 6
6 3 6
------- test 2 ----
12 9 12
9 9 9
12 9 12
------- test 3 ----
6 9 3
3 3 9
12 12 12
------- test 4 ----
9 3 9
9 9 9
9 9 9
------- test 5 ----
6 12 12
12 12 12
12 12 12
------- test 6 ----
3 12 9
6 6 6
12 12 12
------- test 7 ----
12 3 3
3 6 6
12 3 6
------- test 8 ----
12 3 9
9 12 12
3 6 9
------- test 9 ----
9 12 9
12 3 12
9 12 9
Keep up the good work!
Thanks for your submission!

CODE

Ubuntu PHP 加裝curl

網路爬文爬了兩小時 一直出現相容錯誤

乾脆直接降級吧

sudo aptitude install php5-curl

夜...

深夜 (對我來說.

望著滿桌滿櫃的書 心思卻已跟著一首接著一首的歌漂蕩走了

難得夜深人靜 好好沈澱一下自己..

發呆一夜吧！

同學會~~~

今天是國中畢業以來第一次舉辦同學會.

不知道是否因為某人 我們班畢業後並沒有感情很好的樣子~ 好加在今年終於辦成了 感謝戴XDD

----------------------------------------------------------------

一早約10點左右集合完 一起搭公車去新竹

已經兩年了阿 也該抽個時間讓自己沈浸於國中生活的回憶了~~

一路閒聊~大家都沒怎麼變嘛~~~ 教主仍然是教主 渣還是渣 王不退位...

不過大家高中的生活都過的多彩多姿呢~！

直到今天我才知道原來SOGO頂樓是高級餐廳 我們訂位的鬥牛士就是再那

今天唯一美中不足的就是用餐的位置.. 位啥我要跟"阿貢"坐勒~？！ 害我默了...

燒烤吃到飽 吃到有夠飽 好多肉阿~ 晚上要吃素了..

飯後 橋了許久 最後決定去湯姆熊續攤 好吧 我承認我對電腦比較有興趣.. 只打了一台應應景=口=

------------------------------------------------------------------------

能再一次看到國中的同學還蠻溫馨的說 雖然有快一半的人沒來 但想見的都來了 還有啥怨言呢？

兩年了阿..... 重新見面實在令人五味雜陳 看著你 卻無語... 沉默太久 也許就是對自己的放縱 逃避吧

同樣的錯總是一錯再錯 也許吧 無所謂了 難道還要算出已分叉的道路再度交會的期望值 才懂的鬆開思緒？

------------------------------------------------------------------------

後記... 自從FB活化後 許久沒去看無名了 看看自己一年前的文章 哈~ 真熱血阿~

時至月末 該放下的也該放下了 格式化右腦吧 追夢摟~~~

紀念！AC100！

感動阿 從創帳號到現在差不多一年了 中間經歷了一段空窗期 今天終於100AC了

接下來就繼續面對寒窗苦讀的日子吧！~

要習慣遠離電腦摟 看書看累了再研究一下Algorithm吧！

ACM Q10422

ACM Q10422 Knights in FEN

BFS爆搜 要剪枝 用左下黑子數和所剩步數判斷(吃餛飩麵時想到的XD

這議題deBug de了1.5小... 結果竟然錯再最終狀態的最後一行黑白不分..天阿！

太粗心了...

The Code

ACM Q571

ACM Q571 Jugs

大家應該都有玩過到水遊戲吧？ 就是說有某甲很無聊，拿了兩個空杯子，最大容量分別是Ca,Cb公升

你現在有無限多的水(水資源浩劫..) 題目要求你裝出N公升的水

我一開始以為有啥神奇的解法 結果竟然要用BFS暴搜出解答 BFS竟然還能用在這種地方？！

是說用每一種方法去試 確定沒重複再丟到QUEUE裡 等待下次遍歷 一開始寫了快200行...AC 但看了別人的碼後傻眼

我竟然忘了可以直接開bool陣列去存visit 頭腦不清楚阿~~

貼上第2版的碼 精簡過 也把visit改正了..

The Code