調和的靈感

http://zerojudge.tw 為了練習GIT 我把我寫的所有ZeroJudge解答都放上GitHub啦 請參考這個連結 http://github.com/yrchen/ZeroJudge/tree/chchwy 上面同時還有禹任跟俊諺的解答 NetLab ZeroJudge團 在這裡誠摯的歡迎您的加入 一同切磋程式技巧

非常適合作為ACM入門第一題。

質數題大屠殺的時候解的

似乎有不需要任何if判斷的寫法? 還沒參透

有關空間分割的小題目，雖然規則容易找。 至於為什麼是這樣，有興趣的人可以當作歸納法證明的小菜。

無所不在的費波納西數列。

解題策略 這題要做質因數分解，只要先用篩法建好質數表，接下來就簡單了。 要注意的是這題的數字非常大，很接近 int 的上限，一個不小心就會溢位，要小心。

這題破梗就太不好玩了

解題策略 這題是考質因數分解，先把質因數分解表示法轉成數字，數字減一後，再轉回質因數分解表示法。 關鍵測資 Input: 18 1 17 1 15 1 17 1 11 1 11 1 29 1 9 1 2 1 4 1 5 1 7 1 11 1 18 1 23 1 29 1 31 1 29 1 2 3 11 2 25 1 41 2 51 1 5 1 17 1 19 1 23 1 0 Output: 353 1 13 1 31 1 3 1 2 1 41 1 7 1 5 1 2 1 3079 1 7 4 5 1 449 1 2 1 3457 1 7 1 7 1 5 1 3 1 2 4 127 1 2 1 619 1 3 1 2 2 閒聊 最近狂殺質數題。

寫得時候頭腦不是很清楚 有點亂，不夠漂亮，只能算剛好AC而已

很偷懶...這題用counting sort說不定比較快

我一直以來使用的簡單質數檢驗法栽在這題，TLE 上網找了一下，發現2倍數可以先去掉不除 雖然只是簡單的小技巧，但效果很明顯 檢驗過程時間降了一半 就靠著這樣AC了

最近都在研究質數問題 本題因為IO量極大 原本只建了質數表,發現不夠快(TLE) 索性連DigitPrime累計表也建起來 dpCum[n]: 從0~n 累計總共有幾個Digit Prime 這樣每筆測資的時間就降到O(1) 這陣子學了不少質數的技巧 像是這題用的高速篩法 像這種百萬等級的問題，建表都很快 另一題大到十億左右，建表就太慢了

zz...輕鬆簡單的小題

Project's Build Option -> Compiler選項 Produce debugging symbols(-g) (打勾) Strip all symbols from binary(-s) (不要勾) 插入Break point 左邊 "Watches" Tag -> right click "Add watches" -> 輸入 variable name re-build press "F8" into debug mode press "step into" to see the variable content step by step

花了點時間推導才發現原來是個送分題 因為GCD,LCM的GCD,LCM就是自己呀...

解題策略 模擬機器手臂推方塊，典型的模擬題，乖乖照著命令的意思操作方塊，然後細心一點吧。 這題雖然有四個命令 [move/pile] a [onto/over] b，但是仔細觀察，就發現命令只分成兩種，一種是搬動方塊之前，要把目標上面的方塊都歸位(move/onto)，另一種是整疊方塊直接跟著搬動(pile/over)。 以下的程式，move()是搬動方塊，clear_above()是歸位的動作。整個處理的主迴圈就長這樣: // 指令格式 [move/pile] a [onto/over] b while( scanf("%s %d %s %d", cmd1, &a, cmd2, &b)==4 ) { // 排除不合理的命令 if(a==b) continue; if( in_the_same_stack(a,b) ) continue; // [move a] 把a上頭的方塊都歸位，[pile a] 則什麼都不做。 if( strcmp("move", cmd1)==0 ) clear_above(a); // [onto b] 把b上頭的方塊都歸位，[over b] 則什麼都不做。 if( strcmp("onto", cmd2)==0 ) clear_above(b); // 搬動方塊 move(a,b); } 閒聊 把年以前寫的爛code重新整理了一番，把linked list換成vector，速度也小進: 0.030s -> 0.008s。 以下完整code。

用bitset實做，快又有效。

寫這支程式比較像在做苦工，因為規則實在很繁瑣，當初我差點要寫不下去，後來轉念一想，就當作給自己一個挑戰，把繁雜的事情寫得有條有理。 這是我第一次嘗試將Unit Test應用在UVa題目上(拿來對付這種煩人題目剛好)。成果很不錯，只要有強大完整的Test Case在，根本就不用怕改爛程式碼，或者是改東邊炸西邊這種事情發生。所以我在後期也大膽的修正了兩次架構，目前看起來算滿意，整個程式架構相當清楚，而且一次就AC了。 附上我的TestCase ps.我用的是GTest (Google C++ Testing Framework) 題外話，最近跟0.008秒有緣，我已經連三題0.008秒AC了 XDDDDD

一次AC!

一次AC!

Back to High School Physics .... 真的很像高中物理題目...在紙上推導了一下

解題策略 看似簡單，的確也不難，只是有很基本的東西要注意。XDDD 附上測資 0 4294967296 2 4294967296 0 4294967295 2 4294967295 這題測資剛好會超過int(long)的有效範圍，所以必須用 long long 或者 double。 閒聊 ACM真是有趣....而且殘酷....在最基本的地方栽跟頭，毫不留情。

一次AC !!! 太爽啦~ 做法就不講了，我是用Algorithmist的作法，如下 http://www.algorithmist.com/index.php/UVa_10038 Set應用題，非常簡潔俐落的作法...虧我之前還在想一堆有的沒的。 bitset的速度也讓我驚豔， 0.008s ，相當的快!!

「經典就是大家都希望曾經讀過卻又沒人想讀的作品」— 馬克吐溫 我有一堆與程式設計相關的書籍，一冊冊完好如初地擺在我的書架上，這些書曾經影響我程式設計的方式和風格，它們是程式設計師塑造個人哲學的聖經。 不過我也有其他書籍，有的置於書桌上，有些則散落在床邊及客廳沙發上。 這些書多半已破舊、變形且沾滿咖啡漬。那是我賦予它們的最高榮耀，因為它們本來就是實用性的書籍，我參考這些書籍並解決每天碰到的問題。 這本書的目的也是如此。 寫作動機也是期望它能幫你解決每天碰到的程式設計問題。 你所賦予它的最大榮耀就是使用它—想辦法讓它對你有用處，即使~你偶爾拿內頁擦拭濺到的咖啡也無妨！ 相當迷人的書序，讓我也不禁想要找這本書來看看了

簡化版旅行推銷員問題，用DP解 這題我的醒悟就是，用演算法不要太死腦筋 因為這題有一個機歪點，就是如果有多條權重相同的最短路徑，要輸出字典順序最小的那一條。 如果從起點往後DP，那麼字典順序很難解 如果從終點DP回來起點，那麼字典順序自然而然解決了。 瞭解演算法以後，果然還是要靈活使用才行。 附上測資 應該足夠應付各種狀況了

趕進度XDDD 沒什麼好提的小題....

這大概是我最近寫最快的一題:不到半天

解題策略 這題的關鍵其實就是找N (廢話...)，每隻貓都可以從帽子中變出N隻小貓，小貓的高度是 1/(N+1) ，所以有N一切的謎底就都解開了。我的做法也很簡單，就是用個for迴圈去代 n ，然後比對最後工作的小貓數量，直到符合為止。 一個可能蠻有用的測資 483736625 481890304 0 0 答案是 615441 1931252289，找出來的N應該是784。 注意 官網論壇上面很多亂七八糟的測資，像是(3 1), (5 1), (7 1) 等等除不盡的測資，請 完 全 不 要 管 這些東西。所有合法測資都是剛剛好整除的整數，貓的初始高度也一定是某數的完全次方。 閒聊 開心，終於達成100~113連號答題，整排都是綠色的AC看起來就很爽。雖然不是用很數學的方式，但是這個解法是我自己想出來的，相當有成就感。

有趣，但是很繁瑣的題目。 我還花了很長的時間想要怎麼把check的程式簡化縮短，後來發現沒什麼好辦法，就直接爆破了。 1. 用12*12的棋盤可以省掉很多邊界檢查。 2. 從king出發去找敵棋，比較快；用其他棋子去找king，比較慢。 0.000秒AC \(＞﹏＜)/

好有趣的題目。 不過因為參考網路上某份code，實做錯誤的BFS，導致好幾次TE＝　＝a。 話說這好像是我第一次親手實做BFS ? 自己寫了一個Queue，看起來速度很快。 最後AC 0.020秒 Ranking 51 有兩點注意 1. V的y1,y2，測資有可能y1>y2。H也一樣。 2. fillRegion若目標顏色跟原色相同，那就不用做了。

弄了我三天的題目，深深覺得自己還未夠班。 Ranking 136， 但是Run Time相當不理想: 0.760。不知道要怎麼壓到0.2秒以下。 提供下面這份測資，非常關鍵，我通過這份測資後就一次AC了。 來源:http://online-judge.uva.es/board/viewtopic.php?p=49650#49650 7 2 i am jalal he is Hasan 1 2 2 1 3 L P M 1 2 3 1 3 2 2 3 1 2 1 3 1 3 2 2 3 1 6 A B C D E F 2 1 6 5 3 4 6 3 2 5 4 1 5 2 6 1 3 4 3 6 1 5 2 4 1 2 4 6 3 5 3 2 5 6 1 4 5 6 2 4 3 1 5 3 1 4 2 6 2 4 5 6 3 1 2 5 3 4 6 1 4 jalal hasan bijon saiket 1 2 3 4 3 1 2 4 1 2 3 4 2 1 3 4 3 1 2 4 4 3 1 3 3 John Doe Jane Smith Sirhan Sirhan 1 2 3 2 1 3 2 3 1 1 2 3 3 1 2 3 John Doe Jane Smith Sirhan Sirhan 1 2 3 2 1 3 2 3 1 1 2 3 3 1 2 4 jalal hasan bijon saiket 1 2 3 4 2 1 3 4 1 2 3 4 2 1 3 4 3 1 2 4 4 2 1 3 正解 i am jalal he is Hasan L P B jalal bijon John Doe John Doe jalal hasan

引用某個解題者的話：This problem IS a trip. 乍看很簡單，但是很容易在浮點數精確度上吃悶虧。 最後我全部轉成int來運算，確保一切在掌握之內。 兩點提醒 1. 平均開銷算出來以後要四捨五入到小數第二位(1 cent) 2. 因為平均開銷不精確，所以exchange amount 要統計兩個，輸出小的那一個。

蠻有趣的一題，還好距離組語記憶還不算太久。 朝每天至少一題邁進吧。 目前是第二天^+++++^ ps. 雖然我很想以德國人般的嚴謹來面對UVa Online Judge的格式要求。 但常常跟空白、換行對抗感覺不太好...orz ps2. 距離一次AC的目標又進了一步。這題兩次AC。

簡單的問題，但是有些機歪的狀況 摘自UVa forum by kckckc 1. Space or NewLine that have mentioned in previous Post. 2. Maybe the code will meet some problem in some input sets such as input is X 0 3. I didn't handle the leading 0 situation, that means if input is 00007, my out put is 7. 所以下面這是關鍵測資 10 99999999 3 00007 5 0 0 0

小題目。 寫完很久了，不知為何忘了放上來。 最近被848 FMT弄得心煩意亂，唉。

Debug用 #ifndef ONLINE_JUDGE freopen("848_input.txt", "r",stdin); freopen("848_output.txt","w",stdout); #endif 進階版getch(), ungetch() (from K&R) // ungetch(): push a char to stack // getch(): if stack is not empty, pop a char // or get a char from stdin. int buffer[1024]; int top = -1; //stack pointer void ungetch(int c){ buffer[++top] = c; } int getch(){ if(top > -1) return buffer[top--]; else return getchar(); }

不管結果如何，再一天，這樣的日子都要成為過去了。 有一點苦澀，又有一點懷念。

之前看到p值的範圍(10 101 )，以為要做大數，實際上只要用double就行了，難度相當低的一題。