The Tagtraum House

Have Yourself A Merry Little Christmas

2011-12-15T15:13:00.001+08:00

One of my favorite Christmas song. Accuradio has a channel “Have Yourself A Merry Little Christmas” that plays various versions of this song. That is so nice.

Have Yourself A Merry Little Christmas – Lyrics

Music composed by Hugh Martin, lyrics by Ralph Blane

Have yourself a merry little Christmas,
Let your heart be light
From now on,
our troubles will be out of sight

Have yourself a merry little Christmas,
Make the Yule-tide gay,
From now on,
our troubles will be miles away.

Here we are as in olden days,
Happy golden days of yore.
Faithful friends who are dear to us
Gather near to us once more.

Through the years
We all will be together,
If the Fates allow
Hang a shining star upon the highest bough.
And have yourself A merry little Christmas now.

洪卓立 - 愛別等

2011-12-07T11:22:00.001+08:00

好聽好聽~~

作曲：Johnny Yim
填詞：陳姿喬@Zoo Music
編曲：Johnny Yim

無聊隨意獨行從來無意搜尋
情感空洞内心怕自問愛得深但剩得天真

悠然和你共行平凡輪廓怎相襯
偷望著加點留神沿途漫步確認真摯聲音

＊日落逐漸近像蜜運在附近
相戀不必一定地震天
腳步開始走近眉目再對望即將發生
夜半一吻突然動心抱緊早已認識的人
難得跟情人思想同行每段説話深得我心
明日又能為誰認真若這刻輕率轉身
遺失這情人怎可再等
喜歡你聽懂我心快著緊（愛別等）＊

仍然隨意漫遊閒談微笑交流
談占星命運心理學問你的聲音另有質感

Repeat （＊）

世事總變化難設想最差
同預測天氣越早休假
投入地種二人的花

夜半一吻突然動心帶走苦澀内心傷痕
能公開成爲知己情人每日每夜傾身貼心

明日又能為誰認真若這刻輕率轉身
遺失這情人怎可再等
喜歡你聽懂我心愛別等
喜歡你必須發生吻入心

Python utf-8 decoding problem

2011-11-29T16:33:00.001+08:00

今天用Python/Google App Engine寫網站時遇到的error message:

File "C:\Python27\lib\encodings\utf_8.py", line 16, in decode
    return codecs.utf_8_decode(input, errors, True)
UnicodeDecodeError: 'utf8' codec can't decode byte 0xa4 in position 57: invalid start byte

中文無法正常顯示，後來查到的解決方式是：把檔案編碼方式改成utf-8即可正常顯示。
reference: http://bbs.chinaunix.net/archiver/tid-2332880.html

Melody–Realize (龍櫻op)

2011-06-19T00:31:00.001+08:00

作詞：melody. /MIZUE
作曲：Koutaro Odaka
編曲：Kei "Spicy" Kawano

(日文)

I can 迷わずに進もう
願いに近ずけるよ
I see the light
Wake up, stand up
もう一度明日へ try

Look at my 小さいの手で
Hold on tight つかまえた my precious
なくしそうな visions is me
見失いたくない自分のway

Do you know that I want it all
心の奥で輝きつずける
その夢を忘れないで

I can 迷わずに進もう
願いに近ずけるよ

いつの日にか溢れる光の花を咲かせよう
I see the light
Wake up, stand up
もう一度明日へ try

Here I am 瞳閉じたら
独りじゃないことに気ずいた
乾いていた心が嬉しい涙に染まる Once again

I promise 今から
この胸の中で動き始めた
この鼓動感じながら

I will 思い切りつらぬく
このまま走りたいから
いつの日にか夢見た場所で
A-ha-ha と笑っているでしょ
Wake up, stand up
何度でも Get up and try

Carry on…..
I realize
I realize
That we can get there

I can 迷わずに進もう
願いに近ずけるよ

いつの日にか溢れる光の花を咲かせよう

I will 思い切りつらぬく
このまま走りたいから
いつの日にか夢見た場所で
A-ha-ha と笑っているでしょ
Wake up, stand up
何度でも Get up and try

(中譯)

對著不再迷惘的未來前進吧
向願望接近吧
I see the light
wake up, stand up
再一次對著明天去嘗試

看我用小小的這雙手
緊緊抓住獲得的珍貴東西
這種稍縱即逝的想法卻是我
不想丟失的，自己的道路

Do you know that I want it all
在心的深處持續閃耀的
這個夢想是絕對不會忘記的

對著不再迷惘的未來前進吧
向願望接近
也許某一天吧
滿溢著光輝的花朵就會綻放
I see the light
wake up, stand up
再一次向明天嘗試

Here I am 閉上雙眼的話
就會意識到其實並不孤獨
乾涸的心
再一次被高興的淚水所溼潤

I promise 從今天開始
在胸中開始澎湃的
這個鼓動我感覺到了

★我會下定決心貫徹到底
想要就這樣子一路奔跑下去
所以，也許某一天能在夢中所盼望的地方
a-ha-ha 開懷地笑著吧
wake up, stand up
不管是幾次 get up and try ★

carry on...
I realize
I realize
that we can get there

對著不再迷惘的未來前進吧
向願望接近吧

也許某一天
滿溢著光耀的花朵就會綻放

Plants vs Zombies soundtrack

2011-02-27T15:47:00.001+08:00

Plants vs Zombies is my favorite game recently. What fascinates me most is its graphic design and music. The music is from Laura Shigihara, from Wiki I learned that she wants to mix in melodic tunes and funky beats! One of my favorite song in this game is its main menu background music. It is:

I like it especially from 0:35!

This is one is also good. 好鬼得意！

Scaling for IE/Chrome/Firefox/Safari

2011-02-10T21:17:00.000+08:00

I want a scaling that works for all above browsers. I end up with two separate style sheets, one for IE, and one for the rest browsers. And I did something like this:

This is sample text before scale

This is sample text after scale

<div class="myclass">This is sample text</div>
<style type="text/css">
.myclass {
    width: 100%;
    background: #ECECEC;
    font: bold 24px Arial;
}
</style>

<!--[if IE]>
<style type="text/css">
.myclass {
    zoom: 0.6;
}
</style>
<![endif]-->

<!--[if !IE]>-->
<style type="text/css">
.myclass {
    -moz-transform: scale(0.6);
    -webkit-transform: scale(0.6);
}
</style>
<!--<![endif]-->

The css 'zoom' would work for IE and Safari. 'zoom' scales element to the top left of element, and '-moz-transform' and '-webkit-transform' scales to the center. The 'position' property could be further adjusted in browser specific styles so that all browsers display the element at exactly same position after scale!

Conditional comments

2011-02-10T20:59:00.001+08:00

Conditional comments only work for IE, but it can be used for deciding whether the browser is IE or not, and include browser specific style sheets.

<!--[if IE]>
do something for IE
<![endif]-->
<!--[if !IE]>-->
do something for other browsers
<!--<![endif]-->

Reference: http://www.quirksmode.org/css/condcom.html

Chrome minimum font size

2011-02-10T20:25:00.000+08:00

I find my chrome failed to display my css font size settings. I learned that chrome has a default minimum font size setting, and the solution is to add below syntax:

-webkit-text-size-adjust:none;

天梯 - 釗峰

2011-01-14T20:47:00.001+08:00

《天梯》

主唱：釗峰@C AllStar
作曲：賴映彤@groovision
填詞：鍾晴
編曲：Adrian Chan@Sense &賴映彤@groovision
監製：簡@groovision

如可找個荒島
向未來避開生活中那些苦惱
如冬天欠電爐雙手擁抱可跟天對賭

無論有幾高就如絕路
隔絕塵俗只想要跟你可終老
來跨出那地圖不需好報都只想你好

能共你沿途來爬天梯不用忌諱
中傷流言全悍衛
留住你旁人如何話過不可一世
問我亦無愧有你可失去我一切

幾多對持續愛到幾多歲
當生命仍能為你豁出去
千夫所指裡誰理登不登對
仍挽手歷盡在世間興衰

幾多對能悟到幾多精髓能撐下去
竭力也要為愛盡瘁抱緊一生未覺累
前方仍然大霧
到懸崖或海邊也許永不知道
能相擁到白頭一起偕老不跟天鬥高

前面有幾高一片荒土
每步隨著攀登叫雙手都粗糙
從崎嶇這路途開墾給你可走得更好

能共你沿途來爬天梯黑夜亦亮麗
於山頭同盟洪海中發誓
留住你旁人如何話過不可一世
問我亦無愧有你可以拆破這天際

幾多對持續愛到幾多歲
當生命仍能為你豁出去
千夫所指裡誰理登不登對
仍挽手歷盡在世間興衰

幾多對能悟到幾多精髓能撐下去
竭力也要為愛盡瘁抱緊一生未覺累

握著手而幸福包圍泥牆簡陋
牽著走懷著勇氣至愛得永久

幾多對持續愛到幾多歲
不轟烈如何做世界之最
千夫所指裡誰理登不登對
仍挽手歷盡在世間興衰
幾多對能悟到幾多精髓能撐下去
竭力也要為愛盡瘁抱緊一生未覺累

幾多對持續愛到幾多歲
當生命仍能為你豁出去

林俊傑 - 熟能生巧

2010-12-24T23:05:00.001+08:00

作詞：林秋離作曲：林俊傑
醒著像睡著躺著像思考神魂顛倒
感情太單調竟然是煩惱如何是好
也許來陣風雨花謝滿地
黯然神傷的困擾
可以刺激那顆渾渾噩噩
失去了烈火激情的大腦
吹風就感冒淋雨就發燒有愛就好
＃我不再逃空虛日子這一路都在熬
也許愛情就是熟能生巧
你絕對想不到我多渴望
讓生活染上一些顏料
是紅橙黃或藍靛紫都好
一圈一圈的圍繞
終於能自在的坦誠說愛你
火一點就燃燒
怎麼刺激那顆渾渾噩噩
失去了烈火激情的大腦
吹風就感冒淋雨就發燒有愛就好

jQuery

2010-11-23T23:29:00.001+08:00

jQuery小練習。下拉選單或點圖可以變換人物，下方的文字也會跟著變動。都在client-side完成。

javascript

2010-11-22T23:49:00.001+08:00

其實蠻好玩的嘛，不知道之前在怕個什麼勁。以下用javascript寫的小功能，隨機generate兩個數字算最大公因數。

A Web App

2010-11-20T04:17:00.001+08:00

Deployed a simple web app to Google App Engine, using Python. The web app has a form that let users input book name and book price and store data to database. It checks whether user inputs are valid. And it displays all stored data and let users choose the display order.

It is really amazing to have database functionality without having to maintain a database server.

feel free to try it and add some new entries on tagtraumapp.appspot.com.

Google App Engine !

2010-11-19T22:00:00.001+08:00

Which is really cool. Enjoyed the excitement of cloud computing for the first time!

App Engine Python Overview

周柏豪 - 走狗

2010-11-12T22:21:00.000+08:00

作曲: 張佩瑩
填詞: 林夕

吃我最不喜愛料理吃到我歡喜
有了你犧牲我習慣免惹你生氣
如果爭執只想討好你不必講理
還期望穿衣穿到彷彿很襯你

像你所講隨時要聽候你都講過愛是終身獻奉
不計較亦無求原來未足夠
勉強遷就只可加劇你渴求
依足你任何吩咐更無權去攔住你拖手

誰想到聽講聽教令我個性也生銹
誰想到只聽你話連自尊也再沒有
馴服地吠不出口令你我也看不起我遞上手
會拖多幾晝

像你所講難捱也接受你都講過愛是堅忍退讓
將妥協換自由原來未足夠
我的溫柔根本不是你所求
依足你任何吩咐更無權去攔住你拖走

誰想到聽講聽教令我個性也生銹
誰想到只聽你話連自尊也再沒有
馴服地吠不出口令你我也看不起我
只敢附和只懂求和情感拖得太久

誰相信嘔心瀝血令我血性也失守
明白我賣相全為迎合你醜到未知醜
誰連賣力討好你令我變了你的狗命我走便要走

寵你寵到嘔心瀝血令我血性也失守
明白我賣相全為迎合你醜到未知醜
誰連賣力討好你令我變了你的狗若我走我終於忍夠

周柏豪 - 最好不過

2010-11-12T22:19:00.000+08:00

作曲：陳光榮
填詞：馮曦妤
編曲：周柏豪 / 陳光榮
監製：舒文 / 陳光榮

叮囑我小心千句萬句
看顧在身邊一歲又一歲
生長於小堡壘是我仍陶醉
愉快在於簡單喝汽水

走出這溫室奔向夢想追
風雨下濕身走到肉身都破碎
人大了為何憔悴愉快為何減退
太過累偏偏收到來自你掌心的汽水

餘生都不會掉低我全因有你荊棘困難撐得過
當宇宙逆轉過家裡仍像當初
磨練過勞累過回家最好不過

當我又出走從來沒追究
當軟弱灰心誰人像好友
即使我事事犯錯體恤我亦肯定我
安撫我開心簡單來做我不必想太多

餘生都不會掉低我全因有你荊棘困難撐得過
當宇宙逆轉過家裡仍像當初
磨練過勞累過回家最好不過

餘生都不會掉低我全因有你荊棘困難撐得過
當宇宙逆轉過家裡仍像當初
流淚過沉澱過回家最好不過

周柏豪 - 乞丐王子

2010-11-12T22:16:00.000+08:00

作曲：周博賢
填詞：周博賢
編曲：周博賢
監製：周博賢

披搭著污穢破碎故衣執拾著棄置膠袋似失理智
那灰黑眼窩憂鬱帶點失意

生活在下層談何容易坑伴饅頭被浸濕都不介意
耐性進食不放肆

充當瘋漢半輩子給笑太過癡突然被世界注視千萬次
留言像諷刺衣著具創意人氣飆升不止

他身處赤貧有誰會在意他身世永被當玩笑玩意
他心理變異還是理智為何全沒鬥志變餐桌間的事

他一切照舊每日繼續試找生計過活卻未太如意
身邊每一個都介意這個乞男兒討最低工資都不得已

出身清苦無財無人事低學歷卻有不死鳥的意志
每天工作擔舉洗刷都可以

可是現實拿窮人歧視爭逐上游沒契機灰心喪志
受壓過度失理智

充當瘋漢半輩子給笑太過癡突然被世界注視千萬次
留言像諷刺衣著具創意連遠方鄉親也知

他身處赤貧有誰會在意他身世永被當玩笑玩意
他心理變異還是理智為何全沒鬥志變餐桌間的事

他一切照舊每日繼續試找生計過活卻未太如意
身邊每一個都介意這個乞男兒討最低工資都不得已

世態詭異雖耕種肯去試期望會結果實幼稚
即使滿腔戰意永不躲懶實幹過日子
因果已前後倒置滅貧仍沒有法子

他多悲慘哪有誰會在意他身世秘密當玩笑玩意
他心理變異還是理智為何隨地上廁要窺探得個「知」

他穿梭鄉鎮每日拼命試找生計過活卻遇上敵意
身邊每位眼光懷疑憎厭這男兒討最低工資都不可以

Install northwind and pubs sample database on SQL Server 2008

2010-11-02T23:45:00.001+08:00

I’m pretty new to database. This is how I installed northwind and pubs sample database on SQL Server 2008.

1. Download “SQL2000SampleDb.msi” and execute the msi file, which will extract files under “C:\SQL Server 2000 Sample Databases”
2. Run “SQL Server Management Studio” and connect to “Database Engine”
3. Choose File->Open->File and select the “instnwnd.sql” (for northwind database) or “instpubs.sql” (for pubs database) under “C:\SQL Server 2000 Sample Databases” folder.
4. Click “Execute” on the toolbar or “Query->Execute” to execute the sql commands.

My ACM Solved Problem List

2010-10-31T20:07:00.001+08:00

Volumn I

100 - The 3n + 1 problem
101 - The Blocks Problem
102 - Ecological Bin Packing
103 - Stacking Boxes
104 - Arbitrage
105 - The Skyline Problem
106 - Fermat vs. Pythagoras
108 – Maximum Sum
109 – SCUD Buster
110 - Meta-Loopless Sorts

111 – History Grading
112 – Tree Summing
113 – Power of Cryptography
114 – Simulation Wizardry
115 – Climbing Trees
116 – Unidirectional TSP
117 - The Postal Worker Rings Once
118 - Mutant Flatworld Explorers
119 - Greedy Gift Givers
120 - Stacks of Flapjacks

121 - Pipe Fitters
122 – Trees on the level
123 – Searching Quickly
124 – Following Orders
125 – Numbering Paths
126 - The Errant Physicist
127 - "Accordian" Patience
128 - Software CRC
129 – Krypton Factor
130 – Roman Roulette

131 - The Psychic Poker Player
132 - Bumpy Objects
133 – The Dole Queue
134 - Loglan-A Logical Language
135 – No Rectangles
136 – Ugly Numbers
137 – Polygons
138 – Street Numbers

147 – Dollars

166 – Making Change

Volumn III

357 – Let Me Count The Ways

Volumn V

562 – Dividing Coins

Volumn VI

624 – CD

674 – Coin Change

Volumn IX

990 – Diving for Gold

list: 2010年看的戲劇

2010-10-31T20:07:00.000+08:00

last update: 2010.10.31

港
＊＊＊＊＊	公主嫁到(2010)
＊＊＊＊＊	疑情別戀(2008)
＊＊＊	古靈精探B(2009)

台
＊＊	轉角遇到愛(2007)

韓
＊＊＊＊+	Air City(2007)
＊＊＊	Pasta
＊＊	拜託小姐

日
＊＊＊＊	四個謊言/四謊記(2008)

list: 2010年看的電影

2010-10-31T20:06:00.000+08:00

last update: 2010.11.1

＊＊＊＊	Shoot ‘Em Up (2007)
＊＊＊	21 (2008)
＊＊	The Da Vinci Code (2006)
＊＊＊+	賭神3之少年賭神 (1996)
＊＊＊	雀聖2自摸天后 (2005)
＊＊	獨家試愛 (2006)
＊＊＊＊	Inception (2010)

Jul
＊＊＊＊	District 9 (2009)
＊＊	The Bounty Hunter (2010)
＊＊＊＊	72家租客 (2010)
＊＊＊＊	Couples Retreat (2009)
＊＊＊	Cloudy with a Chance of Meatballs (2009)

Jun
＊＊＊	Date Night (2010)
＊＊＊＊＊	Up in the Air (2009)
＊＊＊	重慶森林 (1994)
＊＊＊＊	下弦之月 (2004)

May
＊＊＊＊＋	Breakfast at Tiffany's (1961)

Mar
＊＊＊＊	螢火蟲之墓 (火垂るの墓) (1988)
＊＊＊＊	Alice in Wonderland (2010) (3D Version)
＊＊＊＊	Modern Times (1936)
＊＊+	The Lovely Bones (2009)
＊＊＊＊＋	Artificial Intelligence: AI (2001)
＊＊＊	Lilo & Stitch 2: Stitch Has a Glitch (2005)
＊＊＊	Lilo & Stitch (2002)
＊＊＊	Monster Inc. (2001)
＊＊＋	老港正傳

Jan
＊＊＊＋	2012 (2009)
＊＊	(500) Days of Summer (2009)
＊＊	得閒飲茶 (2006)
＊＊＊	天水圍日與夜 (2008)

Regex Hero

2010-10-29T23:16:00.001+08:00

http://regexhero.net/tester/

Great tool to play with and practice regular expression.

ACM: 674 – Coin Change

2010-10-22T17:02:00.001+08:00

Another coin change problem, much the same as 357. I experimented replacing cin/cout by scanf/printf, and the runtime do reduced dramatically!

CODE

#include <iostream>

enum { MAX = 7489, COINS = 5 };

int main(){

    const int coin[] = {1, 5, 10, 25, 50};

    long long w[MAX+1] = {};

    w[0] = 1;

    for(int i=0; i<COINS; ++i)

        for(int j=coin[i]; j<=MAX; ++j)

            w[j] += w[j-coin[i]];

    int n;

    while( scanf("%d", &n) != EOF )

        printf("%d\n", w[n]);

    return 0;

ACM: 357 – Let Me Count The Ways

2010-10-22T16:37:00.001+08:00

Straightforward DP coin change problem. To find the number of possible ways that make up certain amount of money.

My runtime is 0.012. Maybe the way to further reduce runtime is reducing times of i/o?

CODE

#include <iostream>

enum { MAX = 30000 };

int main(){

    const int coin[] = {1, 5, 10, 25, 50};

    long long w[MAX+1] = {};

    w[0] = 1;

    for(int i=0; i<5; ++i)

        for(int j=coin[i]; j<=MAX; ++j)

            w[j] += w[j-coin[i]];

    int n;

    while( scanf("%d", &n) != EOF )

        if( w[n] == 1 )

            printf("There is only 1 way to produce %d cents change.\n", n);

        else

            printf("There are %lld ways to produce %d cents change.\n", w[n], n);

    return 0;

ACM: 166 – Making Change

2010-10-22T13:58:00.001+08:00

換零錢的問題，要使用有限量的錢幣去支付一個商品，要找出支付和找錢(假設商家錢幣為無限量)所使用的總錢幣數量為最小。我的做法是，先找出在每一個金額，商家找錢使用的最少錢幣數量。然後根據買家的錢幣組合，找出所有可以支付的金額所使用的最少錢幣數量。最後找出支付+找錢總使用最少的錢幣數量。

在計算支付的部分，似乎怪怪的，應該有更有效率的做法，但是還想不到怎麼改，繼續研究。

CODE

#include <iostream>

#include <climits>

using namespace std;

enum { COINS = 6, MAX_CHANGE = 10000 };

int main(){

    const int coin[] = {1, 2, 4, 10, 20, 40};

    int p, q, //price

        w[COINS], //wallet

        change[MAX_CHANGE+1]; //change

    int i, j, k, m, sum;

    change[0] = 0;

    for(i=1; i<=MAX_CHANGE; ++i)

        change[i] = INT_MAX;

    for(i=0; i<COINS; ++i)

        for(j=coin[i]; j<=MAX_CHANGE; j++)

            change[j] = min(change[j-coin[i]]+1, change[j]);

    while(1){

        sum = 0;

        for(i=0; i<COINS; ++i){

            scanf("%d", &w[i]);

            sum += w[i] * coin[i];

        if( sum == 0 ) break;

        scanf("%d.%d", &p, &q);

        p = (p*100+q)/5;

        int* pay = (int*)malloc((sum+1) * sizeof(int));

        int* use = (int*)malloc((sum+1) * sizeof(int));

        if( pay == NULL || use == NULL ) exit(1);

        pay[0] = 0;

        for(i=1; i<=sum; ++i)

            pay[i] = INT_MAX;

        for(i=0; i<COINS; ++i){

            for(j=1; j<=coin[i]; ++j){

                m = w[i];

                for(k=j; k<=sum; k+=coin[i]){

                    if( pay[k] != INT_MAX ){

                        m = w[i];

                    else if( k < coin[i] ){ break; }

                    else if( m > 0 ){

                        pay[k] = pay[k-coin[i]] + 1;

                        --m;

                }//k

            }//j

            memset(use, 0, (sum+1) * sizeof(int));

            for(j=coin[i]; (j<=sum) && (use[j-coin[i]] < w[i]) ; ++j){

                if( (pay[j-coin[i]] != INT_MAX) && (pay[j-coin[i]]+1 <= pay[j]) ){

                    pay[j] = pay[j-coin[i]] + 1;

                    use[j] = use[j-coin[i]] + 1;

        }//i: coins

        int total = INT_MAX;

        for(i=p; i<=sum; ++i)

            if( pay[i] != INT_MAX )

                total = min(pay[i]+change[i-p], total);

        printf("%3d\n", total);

        free(pay);

        free(use);

    return 0;

ACM: 147 - Dollars

2010-10-20T22:14:00.001+08:00

也是一直想學的DP換零錢問題，很有趣。

NOTE

注意浮點數誤差的問題

REFERENCE

Coin Change

CODE

#include <iostream>

enum { MAX = 300 * 100 / 5, COINS = 11 };

int main(){

    const int coin[] = {1, 2, 4, 10, 20, 40, 100, 200, 400, 1000, 2000}; //value*100/5

    long long r[MAX+1];

    int i, j;

    for(i=0; i<=MAX; ++i)

        r[i] = 1;

    for(i=1; i<COINS; ++i)

        for(j=coin[i]; j<=MAX; ++j)

            r[j] = r[j-coin[i]] + r[j];

    while( (scanf("%d.%d", &i, &j) != EOF) && (i+j != 0) )

        printf("%3d.%02d%17lld\n", i, j, r[(i*100+j)/5]);

    return 0;

ACM: 624 - CD

2010-10-20T22:07:00.001+08:00

Straightforward 0/1 Knapsack problem. Tried malloc, memset, free in 2D array.

CODE

#include <iostream>

enum { TRACK = 30 };

int main(){

    int n, t, d[TRACK];

    int i, j;

    while( scanf("%d%d", &n, &t) != EOF ){

        for(i=0; i<t; ++i)

            scanf("%d", &d[i]);

        //malloc

        bool** pick = (bool**)malloc(t * sizeof(bool*));

        for(i=0; i<t; ++i)

            pick[i] = (bool*)malloc((n+1) * sizeof(bool));

        int* tape = (int*)malloc((n+1) * sizeof(int));

        if( pick == NULL || tape == NULL )

            exit(1);

        for(i=0; i<t; ++i)

            memset(pick[i], 0, (n+1)*sizeof(bool));

        memset(tape, 0, (n+1)*sizeof(int));

        for(i=t-1; i>=0; --i){

            for(j=n; j>=d[i]; --j){

                if( tape[j-d[i]]+d[i] > tape[j] ){

                    tape[j] = tape[j-d[i]] + d[i];

                    pick[i][j] = 1;

            }//j

        }//i

        for(i=0, j=n; i<t; ++i){

            if( pick[i][j] ){

                printf("%d ", d[i]);

                j -= d[i];

        printf("sum:%d\n", tape[n]);

        //free

        for(i=0; i<t; ++i)

            free(pick[i]);

        free(pick);

        free(tape);

    return 0;

ACM: 990 – Diving for Gold

2010-10-20T01:19:00.001+08:00

也是0/1 Knapsack Problem，要輸出最後「背包」放入物品的總價值、物品數量，和輸出被放入的所有物品。

CODE

#include <iostream>

enum { CAPACITY = 1000, TREASURE = 30 };

int main(){

    int t, w, n, d[TREASURE], td[TREASURE], v[TREASURE];

    int i, j, mval[CAPACITY+1], items[CAPACITY+1];

    bool grab[TREASURE][CAPACITY+1], flag = 0;

    while( scanf("%d%d%d", &t, &w, &n) != EOF ){

        for(i=0; i<n; ++i){

            scanf("%d%d", &d[i], &v[i]);

            td[i] = d[i] * 3 * w;

        memset(mval, 0, sizeof(mval));

        memset(items, 0, sizeof(items));

        memset(grab, 0, sizeof(grab));

        for(i=n; i>=0; --i){

            for(j=t; j>=td[i]; --j){

                if( mval[j-td[i]]+v[i] > mval[j] ){

                    mval[j] = mval[j-td[i]] + v[i];

                    items[j] = items[j-td[i]] + 1;

                    grab[i][j] = 1;

            }//j

        }//i

        if( flag ) printf("\n");

        else flag = 1;

        printf("%d\n%d\n", mval[t], items[t]);

        for(i=0, j=t; i<n; ++i){

            if( grab[i][j] ){

                printf("%d %d\n", d[i], v[i]);

                j -= td[i];

    return 0;

ACM: 562 – Dividing Coins

2010-10-20T01:08:00.001+08:00

一直想學的背包問題，這題是0/1 Knapsack Problem。要把一堆面額不等的錢幣分成兩堆，使得兩堆錢幣總額的差距最小，輸出兩堆的差額。

在用Knapsack的做法之前還是先嘗試了一下greedy method，想看看在什麼情況greedy method會失敗。想法是：把錢幣由大排到小，從最大的開始，分給A、B，若A>B，就分給B，否則就分給A。這個做法在有些情況可以找到正確答案，但這個例子就不行：{50, 50, 49, 49, 48, 48, 2}。用這個做法會得到

A:{50, 49, 48, 2}
B:{50, 49, 48}

最小差距為2，但其實另一種分法就可以平分，A:{50, 49, 49}, B:{50, 48, 48, 2}，差距為0。

所以還是要用背包問題的DP做法，把錢幣盡量湊到總額的一半。

REFERENCES

良葛格學習筆記
 演算法筆記

CODE

#include <iostream>

using namespace std;

enum { MAX_M = 100, MAX_VAL = 500, MAX_SUM = MAX_VAL*MAX_M };

int main(){

    int n, m, c[MAX_M];

    int i, j, t, sum, half, p[MAX_SUM+1] = {};

    scanf("%d", &n);

    for(; n>0; --n){

        scanf("%d", &m);

        sum = 0;

        for(i=0; i<m; ++i){

            scanf("%d", &c[i]);

            sum += c[i];

        half = sum / 2;

        for(i=0; i<m; ++i) //all coins

            for(j=half; j>=c[i]; --j)

                p[j] = max(p[j], p[j-c[i]]+c[i]);

        cout << (((t = 2 * p[half] - sum) > 0) ? t : -1*t ) << endl;

        memset(p, 0, sizeof(p));

    }//n inputs

    return 0;

ACM: 138 – Street Numbers

2010-10-07T23:43:00.001+08:00

這題寫出來超開心！

要找到n, k，使得1 + 2 + 3 + … + (k-1) = (k+1) + (k+2) + … + n。這題是no input，要傳回前10對n, k。題目已經給出前2對，第一對是(6, 8)，因為1+2+3+4+5 = 7 + 8 = 15。

我一開始的做法是，left從1開始累加，當累加(k-1)時，right就從(k+1)開始往上加，直到right>=left為止，若right==left，則找到一對(n, k)。這個方法可以找到正確答案，但實在跑太久，我讓他跑了一個小時，才找到第8對。

想著想著突然間豁然開朗，發現更有效率的方法。新的想法是，已知第一對(n, k)，即是知道一對相等的left, right，從這裡開始。k每加一，left加入(k-1)，因為要納入原本的分隔點(k-1)，而right則減掉k，因為要扣掉新的分隔點k。接著right再從n+1開始累加上去，直到right>=left為止，若right==left，則找到一對(n, k)。然後n, k, left, right的值都保留繼續累加使用。

沒想到這樣的做法竟然快了非常多，馬上答案就出來了！在看到第10對(n, k)的時候簡直太感動了。用這個做法就不用先把答案算出來然後上傳hard code了，Runtime是0.328。

說回這個問題，1 + 2 + 3 + … + (k-1) = (k+1) + (k+2) + … + n，看起來好像是蠻容易滿足的條件，但第10對(n, k)竟然已經是8位數字了！數字真神奇啊。另外，查了資料也發現這個問題可以用數論的Pell’s equation直接求解，但看Wolfram Mathworld和Wikipedia都看不太懂，希望有天可以了解。

CODE

#include <iostream>

int main(){

    unsigned long long k, n, count, left, right;

    printf("%10d%10d\n%10d%10d\n", 6, 8, 35, 49);

    for(k=36, n=50, count=0, left=595, right=595; count!=8; ++k){

        left += (k - 1);

        right -= k;

        for(; right<left; ++n)

            right += n;

        if( left == right ){

            printf("%10llu%10llu\n", k, n-1);

            ++count;

    return 0;

ACM: 136 – Ugly Numbers

2010-10-07T16:13:00.000+08:00

Ugly number 是質因數只有2或3或5的數字。這題要找出第1500個ugly number。

原本只是單純的一個數字一個數字檢查質因數，直到找到第1500個ugly number為止，但雖然可以找到正確答案，卻會花很久的時間。查了一下討論區，才恍然大悟可以直接用2,3,5去生成倍數，也想出來了生成的方法，真開心！

CODE

#include <iostream>

#include <climits>

int main(){

    int u[1500], p[3] = {2, 3, 5};

    int i, j, k, t;

    u[0] = 1;

    for(i=1; i<1500; ++i){

        u[i] = INT_MAX;

        for(j=0; j<3; ++j){

            for(k=0; (t = u[k] * p[j]) <= u[i-1]; ++k);

            if( t < u[i] )

                u[i] = t;

        }//j: 2,3,5

    }//i: i'th ugly number

    printf("The 1500'th ugly number is %d.\n", u[i-1]);

    return 0;

CODE (naive and slow version)

#include <iostream>

using namespace std;

bool otherprime(int n){

  while( n%2 == 0 )

    n /= 2;

  while( n%3 == 0 )

    n /= 3;

  while( n%5 == 0 )

    n /= 5;

  if( n == 1 )

    return false;

  return true;

int main() {

  int n = 1; //start from 2

  int count = 1; //the 1st ugly number is 1

  while( count < 1500 ){

    ++n;

    if( (n % 2 == 0) || (n % 3 == 0) || (n % 5 == 0) ){

      if( !otherprime(n) )

        ++count;

  cout << n << endl;

  return 0;

ACM: 135 – No Rectangles

2010-10-06T22:01:00.001+08:00

要找到規律，畫一個k=6的解，就可以找到規律了。不過雖然找到了規律，卻還不知道為什麼規律是這樣。

CODE

#include <iostream>

int main(){
  int k, n;
  int block; //k-1
  bool flag = false;
  
  while( scanf("%d", &k) != EOF ) {
    if( flag )
      printf("\n");
    else
      flag = true;
      
    n = k * k - k + 1;
    block = k - 1;
    
    int i, j, t, p;
    int line = 0; //count total lines printed
    int starter = 1; //first number of every line
    int count = 2;
    
    //print first k lines
    for(i=0; i<k; ++i, ++line){
      printf("%d", starter);
      for(j=1; j<k; ++j, ++count){
        printf(" %d", count);
      }//j: k marks
      printf("\n");
    }//i: line
    
    //print (k-1) blocks, each block has (k-1) lines
    for(i=0; i<block && line<=n; ++i){
      ++starter;
      for(j=0; j<block; ++j, ++line){
        printf("%d", starter);
        p = j;
        printf(" %d", k+p+1);
        for(t=(k+block+1); t<n; t+=block){
          p = (p + i) % block;
          printf(" %d", t+p);
        }//t: go to starting point of each block
        printf("\n");
      }//j: lines
    }//i: blocks of lines
  }
  
  return 0;
}

Java Project: Reversi

2010-10-03T16:52:00.001+08:00

黑白棋遊戲。可兩人對戰或一個玩家跟電腦玩，也可以看電腦跟電腦瞬間對決。目前寫的AI只是單純選擇可以翻轉最多對手棋子的下一步，因此還蠻容易贏這個AI的。

功能：

1. 提供兩個玩家、一個玩家和一個電腦玩家、或兩個電腦玩家進行黑白棋遊戲。
2. 遊戲進行時，當滑鼠移動到可以下子的格點，顯示圖示提示。
3. 遊戲進行時，即時顯示目前下子方(黑子或白子)和目前分數。
4. 可隨時改變玩家設定(選擇由電腦或人下棋)，設定將在下一次輪到該顏色棋子下棋時執行。
5. 可隨時開啟新遊戲。

執行畫面：

檔案下載：

Reversi_v_1_0.rar (155 kb)

Java Project: SimplePad

2010-10-01T20:42:00.000+08:00

簡單的記事本軟體！

功能：
1. 可以選單或快速鍵執行開啟、儲存純文字檔案。
2. 開啟檔案或儲存檔案後，檔名顯示在標題列。
3. 可以選單或快速鍵執行剪下、複製、貼上功能。
4. 可開啟或關閉自動換行(Line Wrap)。
5. 可以讀寫中文！

執行畫面：

檔案下載：

SimplePad.rar (148 kb)

Java Project: Tic Tac Toe

2010-09-28T15:43:00.001+08:00

非常陽春的圈圈叉叉小遊戲，可以兩個人玩，但沒有電腦玩家。

練習和試驗一些基本的JAVA語法、事件，玩玩Swing的component。用JSmooth把檔案包成exe執行檔，可以直接在windows執行。

功能：
1. 兩個玩家玩井字遊戲。當獲勝者出現顯示獲勝者，若至遊戲結束皆無獲勝者則顯示"Draw"。
2. 隨時可按"New Game"或Alt+n開始新遊戲。

執行畫面：

檔案下載：
TicTacToe.rar (149 kb)

ACM: 134 - Loglan-A Logical Language

2010-09-18T14:54:00.000+08:00

這題要用給定的文法規則，去檢查輸入的句子是否符合文法。我直接暴力的遞迴...

TIP

雖然題目寫"You can assume that all words will be correctly formed"，但實際上加了判斷不和語法的單字才拿到AC。

CODE

#include <iostream>
#include <vector>
using namespace std;

enum { A, MOD, BA, DA, LA, NAM, PREDA };

vector<int> loglan;
int n;

bool vowel(char c){
  return ( c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' );
}

int convert_loglan(string s, int n){
  if( !vowel( s[n-1] ) ) return NAM;
  if( n == 1 ) return A;
  if( n == 2 ){
    switch( s[0] ){
      case 'g': return MOD;
      case 'b': return BA;
      case 'd': return DA;
      case 'l': return LA;
    }
  }
  if( n==5 && (( !vowel(s[0]) && !vowel(s[1]) && vowel(s[2]) && !vowel(s[3]) && vowel(s[4]) ) ||
   ( !vowel(s[0]) && vowel(s[1]) && !vowel(s[2]) && !vowel(s[3]) && vowel(s[4]) )) )
    return PREDA;
  return NAM;
}

bool predstring(int st, int ed){
  if( st == ed )
    return (loglan[st] == PREDA); //"PREDA"
  return (loglan[ed] == PREDA && predstring(st, ed-1)); //"<predstring> PREDA"
}

bool verbpred(int st, int ed){
  return (loglan[st] == MOD && predstring(st+1, ed)); //"MOD <predstring>"
}

bool predname(int st, int ed){
  if( st == ed )
    return (loglan[st] == NAM); //"NAM"
  return (loglan[st] == LA && predstring(st+1, ed)); //"LA <predstring>"
}

bool preds(int st, int ed){
  for(int i=st+1; i<ed; ++i){
    if( loglan[i] == A ){
      return (preds(st, i-1) && preds(i+1, ed)); //"<preds> A <predstring> -> <preds> A <preds>"
    }
  }
  return predstring(st, ed); //"<predstring>"
}

bool statement(void){
  for(int i=1; i<n; ++i){
    if( loglan[i] == MOD ){
      bool pv = predname(0, i-1) && verbpred(i, n-1); //"<predname><verbpred>"
      bool pvp = 0;
      for(int j=i+1; j<n-1; ++j)
        pvp += (predname(0, i-1) && verbpred(i, j) && predname(j+1, n-1)); //"<predname><verbpred><predname>"
      return (pvp || pv);
    }
  }
  return 0;
}

bool predclaim(void){
  if( loglan[0] == DA ){
    return preds(1, n-1); //"DA <preds>"
  }
  for(int i=1; i<n; ++i){
    if( loglan[i] == BA )
      return (predname(0, i-1) && preds(i+1, n-1)); //"<predname> BA <preds>"
  }
  return 0;
}

bool sentence(void){
  return ( statement() || predclaim() );
}

int main(){
  string s;
  while( (cin >> s) && (s[0] != '#') ){
    int len = s.size();
    if( s[len-1] == '.' ){
      s.erase(len-1);
      loglan.push_back( convert_loglan(s, len-1) );
      n = loglan.size();
      cout << (sentence() ? "Good" : "Bad!") << endl;
      //initialize
      loglan.clear();
    }
    else
      loglan.push_back( convert_loglan(s, len) );
  }//while
  return 0;
}

ACM: 133 – The Dole Queue

2010-09-17T21:18:00.000+08:00

simulation，類似Josephus problem，照著規則模擬。

CODE

#include <iostream>

#define MAX 20

int main(){
  int n, k, m;
  bool a[MAX];
  
  while( scanf("%d%d%d", &n, &k, &m) != EOF ){
    if( n==0 && k==0 && m==0 )
      break;
    
    for(int i=0; i<n; ++i)
      a[i] = 1;
    
    bool printed = 0;
    int i = -1, j = n, left = n;
    int cnt_k, cnt_m;
    while( left > 0 ){
      cnt_k = cnt_m = 0;
      while( cnt_k != k ){
        i = (i+1)%n;
        if( a[i] )
          ++cnt_k;
      }
      while( cnt_m != m ){
        j = (j+n-1)%n;
        if( a[j] )
          ++cnt_m;
      }
      
      if( printed )
        printf(",");
      else
        printed = 1;
        
      if( i == j ){
        a[i] = 0;
        --left;
        printf("%3d", i+1);
      }
      else{
        a[i] = a[j] = 0;
        left -= 2;
        printf("%3d%3d", i+1, j+1);
      }
    }//killing
    printf("\n");
  }//while
  return 0;
}

ACM: 137 - Polygons

2010-09-17T19:49:00.001+08:00

寫完132，打鐵趁熱繼續寫geometry的題目。這題很複雜，但要解決的問題很清楚，就是求兩個凸多邊形的非交集的面積(xor, 異域)。

我的算法如下：
A: 第一個凸多邊形點集合
B: 第二個凸多邊形點集合
C: A,B交集部分的點集合(初始為空集合)

1. 檢查A的每一個點，若落在B內部或邊上即將該點加入C。
2. 檢查B的每一個點，若落在A內部或邊上即將該點加入C。
3. 檢查A的每一邊，對B的每一邊逐邊檢查是否可以相交，若可相交即求交點，將交點加入C。
4. A,B交集求畢，將C集合的點逆時針排序。
5. 輸出異域面積為 (A + B – C) – C = A + B - 2C

實作方法

檢查P點是否落在圖形內部或邊上
逆時針檢查圖形的每一點，若「每一點到下一點的向量」與「每一點至P點的向量」皆為逆時針旋轉(外積>0)，則P點在圖型內部。當外積=0時，P點在圖形邊上。

檢查線段P1P2與P3P4是否相交
單純用外積檢查兩線段是否互相跨立。
當 (P1P2 x P1P3)*(P1P2 x P1P4) < 0 時代表P3, P4分別在線段P1P2的兩端，故外積異號。
當 (P3P4 x P3P1)*(P3P4 x P3P2) < 0 時代表P1, P2分別在線段P3P4的兩端，故外積異號。
當兩者皆成立時，線段P1P2與線段P3P4相交。

相交線段求交點
參考「平面內兩條線段的位置關係判定及交點求解」，用向量法求解，只需用到一次除法，減少精確度的問題。

點逆時針排序
先找最左下方的點，其他的點對該點做逆時針的極角排序。

凸多邊形面積

起點與終點必須為同一個點，即X0Y0 = XnYn，而所有的點必須照順時針或逆時針排序，當點為順時針排序時，總和為負數，逆時針排序時，總和為正數，但兩者絕對值相同。

TIPS
1. 製造測資時可考慮相離、相鄰、相交的情況，而相交的圖形可考慮「其中一圖有點在另一圖中」和「兩個圖形完全沒有點在另一個圖中，但有相交部份」的兩種情況。
2. 輸出時雖然每筆輸出之間不需換行，但最後結尾仍需要換行符號，否則會給WA，不是PE。

REFERENCES
平面內兩條線段的位置關係判定及交點求解

CODE

#include <iostream>
#include <vector>
using namespace std;

struct vertex{
  float x, y;
};

//return outer product of pa->pb
float cross(vertex p, vertex a, vertex b){
  return ( (a.x - p.x)*(b.y - p.y) - (b.x - p.x)*(a.y - p.y) );
}

float dist(vertex a, vertex b){
  return (b.x - a.x)*(b.x - a.x) + (b.y - a.y)*(b.y - a.y);
}

//return true if p is inside or on boundary of g
bool inside(vertex p, vector<vertex> g, int n){
  int i = n - 1;
  for(; i>=0 && (cross(g[i], g[(i+n-1)%n], p) >= 0); --i);
  return (i == -1);
}

bool intersects(vertex p1, vertex p2, vertex p3, vertex p4){
  return ((cross(p1, p2, p3) * cross(p1, p2, p4) < 0) && (cross(p3, p4, p1) * cross(p3, p4, p2) < 0));
}

vertex intersection(vertex p1, vertex p2, vertex p3, vertex p4){
  float b1 = (p2.y - p1.y)*p1.x + (p1.x - p2.x)*p1.y;
  float b2 = (p4.y - p3.y)*p3.x + (p3.x - p4.x)*p3.y;
  float d = (p2.x - p1.x)*(p4.y - p3.y) - (p4.x - p3.x)*(p2.y - p1.y);
  float d1 = b2*(p2.x - p1.x) - b1*(p4.x - p3.x);
  float d2 = b2*(p2.y - p1.y) - b1*(p4.y - p3.y);
  vertex p0;
  p0.x = d1/d;
  p0.y = d2/d;
  return p0;
}

void check_intersect(vertex p1, vertex p2, vector<vertex> g, int n, vector<vertex> &gc){
  for(int i=0; i<n; ++i){
    if( intersects(p1, p2, g[i], g[(i+1)%n]) ){
      vertex inter = intersection(p1, p2, g[i], g[(i+1)%n]);
      gc.push_back(inter);
    }
  }
}

//check if ga vertices are inside gb
void check_vertices(vector<vertex> ga, int na, vector<vertex> gb, int nb, vector<vertex> &gc, bool calc_inter){
  for(int i=0; i<na; ++i){
    if( inside(ga[i], gb, nb) )
      gc.push_back(ga[i]);
    if( calc_inter )
      check_intersect(ga[i], ga[(i+1)%na], gb, nb, gc);
  }//i
}

void sort_vertices(vector<vertex> &g, int n){
  if( n > 0 ){
    int i, j, m = 0;
    for(i=1; i<n; ++i)
      if(g[i].y < g[m].y || (g[i].y == g[m].y && g[i].x < g[m].y))
        m = i;
    swap(g[m], g[0]);
    for(i=1; i<n; ++i){
      m = i;
      for(j=i+1; j<n; ++j){
        float t = cross(g[0], g[m], g[j]);
        if( t < 0 || (t == 0 && dist(g[0], g[j]) < dist(g[0], g[m])) )
          m = j;
      }//j
      swap(g[m], g[i]);
    }//i
  }
}

float area(vector<vertex> g, int n){
  float a = 0;
  for(int i=0; i<n; ++i)
    a += (g[(i+n-1)%n].x * g[i].y) - (g[i].x * g[(i+n-1)%n].y);
  return (a < 0) ? ( a / -2 ) : (a / 2);
}

int main(){
  int na, nb, nc; //number of vertices of graph a, b, c
  while( scanf("%d", &na) && (na != 0) ){
    vector<vertex> ga, gb, gc;
    vertex temp;
    
    for(int i=0; i<na; ++i){
      scanf("%f%f", &temp.x, &temp.y);
      ga.push_back(temp);
    }
    scanf("%d", &nb);
    for(int i=0; i<nb; ++i){
      scanf("%f%f", &temp.x, &temp.y);
      gb.push_back(temp);
    }
    
    check_vertices(ga, na, gb, nb, gc, 1);
    check_vertices(gb, nb, ga, na, gc, 0);
    nc = gc.size();
    sort_vertices(gc, nc);

    printf("%8.2f", area(ga, na) + area(gb, nb) - (2 * area(gc, nc)));
  }//while
  printf("\n");
  return 0;
}

ACM: 132 - Bumpy Objects

2010-09-16T00:10:00.000+08:00

Geometry的題目，給一個圖形的所有端點座標，和圖形的質心座標，要先找出可以讓圖形「站立」的邊，即當該邊水平時，質心在邊上方並在兩端點之間。一個圖形可能有大於一個可以站立的邊，邊的代號為該邊所經過最大編號(依輸入順序)的點，最後要輸出所有可以站立的邊中，最小的邊代號。

我的做法分為兩部分，第一部分是找convex hull，用graham scan，找出圖形的凸包。第二部分用內積檢查凸包的每個邊是否可以讓圖形站立，即質心到邊兩端點的夾角是否都小於90度(內積>0)。

TIPS

UVa討論區有大量本題測資

CODE

#include <iostream>
#include <vector>
using namespace std;

class vertex{
public:
  int x, y;
};

int n;
vertex mass;
vector<vertex> v; //original order
vector<int> p; //vertices id sorted by polar angle

//return outer product of pa->pb
int cross(vertex p, vertex a, vertex b){
  return ( (a.x - p.x)*(b.y - p.y) - (b.x - p.x)*(a.y - p.y) );
}
//return true if pa dot pb > 0 (<90 degree)
bool dot(vertex p, vertex a, vertex b){
  return ( (a.x - p.x)*(b.x - p.x) + (a.y - p.y)*(b.y - p.y) ) > 0;
}

int dist(vertex a, vertex b){
  return ((b.x - a.x)*(b.x - a.x) + (b.y - a.y)*(b.y - a.y));
}
//return true if a should be placed first than b to form counter-clockwise order
bool issmaller(vertex p, vertex a, vertex b){
  int f = cross(p, a, b);
  return ( f < 0 || ( f == 0  && dist(p, b) < dist(p, a) ) );
}

void quicksort(int left, int right){
  if( left < right ){
    int i = left + 1;
    int j = right;
    while(1){
      for(; (i<=right) && issmaller(v[p[0]], v[p[left]], v[p[i]]); ++i);
      for(; (j>left) && !issmaller(v[p[0]], v[p[left]], v[p[j]]); --j);
      if( i >= j )
        break;
      swap(p[i], p[j]);
    }
    swap(p[left], p[j]);
    quicksort(left, j-1);
    quicksort(j+1, right);
  }
}

int main(){
  string s;
  vertex temp;
  int i, j, tmp, minv, qn;
  
  while( (cin >> s) && (s[0] != '#') ){
    scanf("%d%d", &mass.x, &mass.y);
    v.clear();
    p.clear();
    i = 0;
    while( scanf("%d%d", &temp.x, &temp.y) ){
      if( temp.x == 0 && temp.y == 0 )
        break;
      v.push_back(temp);
      p.push_back(i++);
    }
    n = v.size();
    
    //find lowest-left
    for(minv=0, i=1; i<n; ++i)
      if( (v[i].y < v[minv].y) || (v[i].y == v[minv].y && v[i].x < v[minv].x) )
        minv = i;
    swap(p[minv], p[0]);
    //sort all vertices counter clockwisely by polar angle
    quicksort(1, n - 1);
    
    //graham scan
    vector<int> q; //stack of convex hull
    q.push_back(p[0]);
    q.push_back(p[1]);
    for(i=2; i<n; ++i){
      qn = q.size() - 1;
      if( (tmp = cross( v[ q[qn-1] ], v[ q[qn] ], v[ p[i] ] )) > 0 )
        q.push_back(p[i]);
      else if( tmp == 0 ){
        q.pop_back();
        q.push_back(p[i]);
      }
      else{
        q.pop_back();
        --i;
      }
    }//i:all vertices
    q.push_back(p[0]);
    
    //find stable sides
    qn = q.size();
    for(minv=n-1, i=1; i<qn; ++i){
      if( (cross(v[q[i-1]], mass, v[q[i]])!=0) && (dot(v[q[i-1]], mass, v[q[i]])>0) && (dot(v[q[i]], mass, v[q[i-1]])>0) )
        if( (tmp = (q[i] > q[i-1]) ? q[i] : (n - 1)) < minv )
          minv = tmp;
    }

    cout << s;
    for(i=s.size(); i<20; ++i)
      printf(" ");
    printf("%d\n", minv + 1);
  }//while
  return 0;
}

ACM: 131 - The Psychic Poker Player

2010-09-14T14:37:00.001+08:00

給玩家五張撲克牌，桌上有另五張的撲克牌，玩家可選擇捨棄0~5張牌，並從桌上依序補充同數量的牌。輸出可以達到的最大牌型(poker hand)。

用了bool陣列去窮舉所有捨棄牌的方式，遞補相同數量的牌後，再一一檢查牌型。

CODE

#include <iostream>
#include <algorithm>
using namespace std;

enum { C, D, H, S };
enum { SF, FOAK, FH, FL, ST, TOAK, TP, OP, HC };
bool result[9]={0,0,0,0,0,0,0,0,0};
char line[9][16] = {"straight-flush", "four-of-a-kind", "full-house", 
"flush", "straight", "three-of-a-kind", "two-pairs", "one-pair", "highest-card"};

class poker{
public:
  int denom;
  int suit;
};

int next(bool *slot);
void check(poker *c);

int main(){
  int i, j, k;
  poker cards[2][5];
  char s[10][3];
  
  i = j = k = 0;
  while( scanf("%s", s[k]) != EOF ){
    if( s[k][0]>='2' && s[k][0]<='9' )
      cards[i][j].denom = s[k][0]-'0';
    else if( s[k][0] == 'A' )
      cards[i][j].denom = 1;
    else if( s[k][0] == 'T' )
      cards[i][j].denom = 10;
    else if( s[k][0] == 'J' )
      cards[i][j].denom = 11;
    else if( s[k][0] == 'Q' )
      cards[i][j].denom = 12;
    else if( s[k][0] == 'K' )
      cards[i][j].denom = 13;
    
    switch ( s[k][1] ){
      case 'C':
        cards[i][j].suit = C;
        break;
      case 'D':
        cards[i][j].suit = D;
        break;
      case 'H':
        cards[i][j].suit = H;
        break;
      case 'S':
        cards[i][j].suit = S;
        break;
    }//s[0]
    
    if( i==0 && j==4 ){
      i = 1;
      j = 0;
    }
    else if( i==1 && j==4 ){
      int count = 5;
      bool slot[5]={0, 0, 0, 0, 0};
      poker temp[5];
      while(1){
        j = 0;
        for(i=0; i<5; ++i){
          if( slot[i] )
            temp[i] = cards[1][j++];
          else
            temp[i] = cards[0][i];
        }
        check(temp);
        if( count == 0 )
          break;
        count = next(slot);
      }//search
      
      //output
      printf("Hand: ");
      for(i=0; i<5; ++i)
        printf("%s ", s[i]);
      printf("Deck: ");
      for(; i<10; ++i)
        printf("%s ", s[i]);
      printf("Best hand: ");
      for(i=0; i<9 && result[i]==0; ++i);
      printf("%s\n", line[i]);
      //initialize
      for(i=0; i<9; ++i)
        result[i] = 0;
      i = j = 0;
      k = -1;
    }
    else
      ++j;
    ++k;
  }//while get data
  
  return 0;
}

int next(bool *slot){
  if( slot[0] == 0 )
    slot[0] = 1;
  else{
    int i = 0;
    while( slot[i] == 1 )
      slot[i++] = 0;
    slot[i] = 1;
  }
  int count = 0;
  for(int i=0; i<5; ++i)
    if( slot[i] == 0 )
      ++count;
  return count;
}

void check(poker *c){
  int denoms[14]={0,0,0,0,0,0,0,0,0,0,0,0,0,0};
  int suits[4]={0,0,0,0};
  
  //sort
  int i, j, min, maxsuit = 0;
  for(i=0; i<5; ++i){
    min = i;
    for(j=i+1; j<5; ++j)
      if( c[j].denom < c[min].denom )
        min = j;
    swap(c[i], c[min]);
    ++denoms[ c[i].denom ];
    if( ++suits[ c[i].suit ] > maxsuit )
      maxsuit = suits[ c[i].suit ];
  }
  
  //find if straight
  bool straight = 0;
  for(i=1; i<5 && (c[i].denom == c[i-1].denom + 1); ++i);
  if( i == 5 )
    straight = 1;
  if(!straight && (c[0].denom == 1)){
    for(i=2; i<5 && (c[i].denom == c[i-1].denom + 1); ++i);
    if( i == 5 )
      straight = 1;
  }
  if( straight ){
    if( maxsuit == 5 )
      result[SF] = 1; //straight flush
    else
      result[ST] = 1; //straight
  }
  if( maxsuit == 5 )
    result[FL] = 1; //flush
  
  int three = 0, two = 0;
  for(i=1; i<=13; ++i){
    switch ( denoms[i] ){
      case 4:
        result[FOAK] = 1; //four of a kind
        break;
      case 3:
        result[TOAK] = 1; //three of a kind
        ++three;
        break;
      case 2:
        ++two;
    }
  }//i
  
  if( three == 1 && two == 1 )
    result[FH] = 1; // full house
  else if( two == 2 )
    result[TP] = 1; //two pairs
  else if( two == 1 )
    result[OP] = 1; //one pair
  else
    result[HC] = 1; //highest card
}

Ubuntu!

2010-09-12T22:07:00.001+08:00

裝了Wubi，直接從Windows像安裝應用程式一樣安裝了Ubuntu！不需要分割硬碟，也不需設定虛擬機器。裝的是Ubuntu 10.x，好漂亮，語言支援也很方便，雖然安裝的是英文版，但顯示中文完全沒問題，中文輸入也可以很方便的直接從System->Preference->iBus打開！

不過還要慢慢摸索linux，還是裝個Virtual Box同時用Windows跟Ubuntu吧。

Rails 3.0初體驗

2010-09-11T22:40:00.000+08:00

終於成功嘗試Ruby on Rails了。安裝的是rails 3.0.0，一些以舊版rails為基礎的教學文件語法不同，後來找到了rails 3版本的教學文件"Getting Started with Rails"，終於step by step照著敲出了個最基礎的blog平台，有blog文章增刪修、comment增刪、tag，三項功能。

資料庫使用的是預設的SQLite，先照著查到的資料排除找不到"sqlite3.dll"的錯誤訊息。

ACM 30 題

2010-09-10T21:16:00.000+08:00

不知不覺把121 - 130寫完了，這10題練習了C++的vector、string和其提供的函式。題目本身的話，印象最深的是DP的"125 – Numbering Paths"和學到運用餘數的"128 – Software CRC"。

ACM: 130 – Roman Roulette

2010-09-10T20:53:00.001+08:00

simulation，但規則有點看不懂，看了中譯才搞清楚...

CODE

#include <iostream>
#include <vector>
using namespace std;

int n, k;
int kill(int i, vector<int> v);

int main(){
  int i, t;
  vector<int> r;
  
  while( (cin >> n >> k) && (n != 0) ){
    r.clear();
    for(i=1; i<=n; ++i)
      r.push_back(i);
    
    t = kill(0, r) - 1;
    t = (n - t) % n;
    cout << t + 1 << endl;
  }//while
  return 0;
}

int kill(int i, vector<int> v){
  int p;
  --i;
  while( v.size() > 1 ){
    i = p = (i+k) % v.size(); //p: killed
    v.erase(v.begin()+i);
    i = (i+k-1) % v.size(); //i: burier
    v.insert(v.begin()+p, v[i]);
    if( i >= p )
      ++i;
    v.erase(v.begin()+i);
    if( i >= p )
      i = p % v.size();
    else
      i = (p - 1) % v.size();
  }
  return v[0];
}

ACM: 129 – Krypton Factor

2010-09-10T20:41:00.001+08:00

生成所有排序(permutations)，但要檢查生成的permutation是否有連續的重複組合，如有連續的重複組合即為無效的permutatoin，若否則為有效的permutation。如"ABAB"為無效，因連續出現"AB"組合，但"ABCAB"則為有效。輸出指定的第n個有效permutation。

CODE

#include <iostream>
using namespace std;

#define MAX 80
int n, let, seqn;
bool check(char *s, int len);
void gen(char *s, int len);
void output(char *s, int len);

int main(){
  char s[MAX];
  while( (cin >> n >> let) && (n != 0) ){
    seqn = 0;
    gen(s, 0);
  }//while
  return 0;
}

//return true if string is "hard", false when "easy"
bool check(char *s, int len){
  int i, j, k;
  for(i=0; i<len; ++i){
    for(j=0; j<i; ++j){
      for(k=j; k<i && s[k]==s[i+k-j]; ++k) ;//k
      if( k == i )
        return false;
    }//j
  }//i
  return true;
}

void gen(char *s, int len){
  for(int i=0; i<let && seqn<n; ++i){
    s[len] = 'A' + i;
    s[len+1] = '\0';
    if( check(s, len+1) ){
      if( ++seqn == n ){
        output(s, len+1);
        return;
      }
      if( seqn < n )
        gen(s, len+1);
    }
  }//i
}

void output(char *s, int len){
  for(int i=0; i<len; ++i){
    if( i == 64 )
      cout << endl;
    else if( i>0 && i%4==0 )
      cout << ' ';
    cout << s[i];
  }//i
  cout << endl << len << endl;
}

ACM: 127 - "Accordian" Patience

2010-09-09T20:50:00.001+08:00

simulation。給52張撲克牌，向左一張或左三張合併同數字或同花色，輸出合併完成後剩下的堆數和每一堆的張數。每合併一次，要檢查是否可以繼續再向左合併。

CODE

#include <iostream>
using namespace std;

#define MAX 52

int main(){
  int i, j, k, moveto;
  char pile[MAX][MAX+MAX], remain[MAX];
  int len[MAX];
  
  while( (cin >> pile[0]) && (pile[0][0] != '#') ){
    len[0] = 2;
    for(i=1; i<MAX; i++){
      cin >> pile[i];
      len[i] = 2;
    }//i: read in all cards
    
    i=1;
    while( i < MAX ){
      moveto = i;
      for(j=i-1; j>=0 && len[j]==0; --j);//1 left
      if( (j >= 0) && (pile[j][ len[j]-2 ] == pile[i][ len[i]-2 ] || pile[j][ len[j]-1 ] == pile[i][ len[i]-1 ]) )
        moveto = j;
      for(--j; j>=0 && len[j]==0; --j);//2 left
      for(--j; j>=0 && len[j]==0; --j);//3 left
      if( (j >= 0) && (pile[j][ len[j]-2 ] == pile[i][ len[i]-2 ] || pile[j][ len[j]-1 ] == pile[i][ len[i]-1 ]) )
        moveto = j;
      if( i != moveto ){
        len[i] -= 2;
        pile[moveto][ len[moveto]++ ] = pile[i][ len[i] ];
        pile[moveto][ len[moveto]++ ] = pile[i][ len[i]+1 ];
        i = moveto;
      }
      else
        for(++i; i<MAX && len[i]==0; ++i);
    }
    
    k = 0;
    for(i=0; i<MAX; i++)
      if( len[i] > 0 )
        remain[k++] = i;
    cout << k << ( k == 1 ? " pile" : " piles" ) << " remaining:";
    for(i=0; i<k; i++)
      cout << ' ' << (len[ remain[i] ] / 2);
    cout << endl;
  }//while
  
  return 0;
}

ACM: 126 - The Errant Physicist

2010-09-09T04:37:00.001+08:00

給多項式，輸出x降冪y升冪排序後的多項式相乘結果。重點在於字串處理，要找到方法把輸入字串拆解出可以運算的係數及次方數。

TIPS

記得移除(不要輸出)合併同類項後係數為0的項

CODE

#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <cstring>
using namespace std;

class term{
public:
  int coef; //coefficient
  int pow_x;
  int pow_y;
};

vector<term> poly[2], result;

void get_terms(int no, string s);
void multiply(term a, term b);
void sort_terms(int left, int right);
void comb_terms(void);
bool isbigger(int a, int b);
string atostring(int num);

int main(){
  int i, j, n;
  string s, line1, line2;
  
  while( cin >> s ){
    if( s[0] == '#' )
      break;
    
    get_terms(0, s);
    cin >> s;
    get_terms(1, s);
    
    result.clear();
    for(i=0; i<poly[1].size(); i++)
      for(j=0; j<poly[0].size(); j++)
        multiply(poly[1][i], poly[0][j]);
    
    sort_terms(0, result.size()-1); //sort
    comb_terms(); //combine like terms
    
    line1.clear();
    line2.clear();
    for(i=0; i<result.size(); i++){
      //sign
      if( i > 0 ){
        line1.append("   ");
        if( result[i].coef > 0 )
          line2.append(" + ");
        else
          line2.append(" - ");
      }
      //coefficient
      if( result[i].coef < 0 ){
        result[i].coef *= -1;
        if( i==0 ){
          line1.push_back(' ');
          line2.push_back('-');
        }
      }
      if( result[i].coef > 1 ){
        s = atostring(result[i].coef);
        line2.append(s);
        n = s.size();
        for(j=0; j<n; j++)
          line1.push_back(' ');
      }
      else if( result[i].coef == 1 && result[i].pow_x == 0 && result[i].pow_y == 0 ){
        line1.push_back(' ');
        line2.push_back('1');
      }
      //power of x
      if( result[i].pow_x >= 1 ){
        line1.push_back(' ');
        line2.push_back('x');
      }
      if( result[i].pow_x > 1 ){
        s = atostring(result[i].pow_x);
        line1.append(s);
        n = s.size();
        for(j=0; j<n; j++)
          line2.push_back(' ');
      }
      //power of y
      if( result[i].pow_y >= 1 ){
        line1.push_back(' ');
        line2.push_back('y');
      }
      if( result[i].pow_y > 1 ){
        s = atostring(result[i].pow_y);
        line1.append(s);
        n = s.size();
        for(j=0; j<n; j++)
          line2.push_back(' ');
      }
    }//i
    cout << line1 << endl << line2 << endl;
  }//while
  
  return 0;
}

void get_terms(int no, string s){
  poly[no].clear(); //initialize polynomial vector
  
  term temp;
  string number;
  int sign = 1;
  int size = s.size();
  char flag = '+';
  
  for(int i=0; i<=size; i++){
    if( i==0 || i == size || s[i] == '+' || s[i] == '-' ){
      //if end of term
      if( i > 0 ){
        if( flag == '+' || flag == '-' )
          temp.coef = atoi(number.c_str()) * sign;
        else if( flag == 'x' ){
          if( s[i-1] == 'x' )
            temp.pow_x = 1;
          else
            temp.pow_x = atoi(number.c_str());
        }
        else if( flag == 'y' ){
          if( s[i-1] == 'y' )
            temp.pow_y = 1;
          else
            temp.pow_y = atoi(number.c_str());
        }
        poly[no].push_back(temp);
      }
      //initialize term
      temp.coef = temp.pow_x = temp.pow_y = 0;
      sign = 1;
      flag = '+';
      number.clear();
      //new term
      if( i < size && s[i] == '-' ){
        sign = -1;
        flag = '-';
      }
    }//term break point
    
    if( s[i] == 'x' || s[i] == 'y' ){
      if( i == 0 )
        temp.coef = sign;
      else if( flag == '+' || flag == '-' ){
        if( s[i-1] == flag )
          temp.coef = sign;
        else
          temp.coef = atoi(number.c_str()) * sign;
      }
      else if( flag == 'x' ){
        if( s[i-1] == 'x' )
          temp.pow_x = 1;
        else
          temp.pow_x = atoi(number.c_str());
      }
      else if( flag == 'y' ){
        if( s[i-1] == 'y' )
          temp.pow_y = 1;
        else
          temp.pow_y = atoi(number.c_str());
      }
      flag = s[i];
      number.clear();
    }
    else if( s[i] >= '0' && s[i] <= '9' )
      number.push_back(s[i]);
  }//i
}

void multiply(term a, term b){
  term temp;
  temp.coef = a.coef * b.coef;
  temp.pow_x = a.pow_x + b.pow_x;
  temp.pow_y = a.pow_y + b.pow_y;
  result.push_back(temp);
}

void sort_terms(int left, int right){
  if( left < right ){
    int i = left + 1;
    int j = right;
    while(1){
      for(; i<=right && !isbigger(i, left); i++);
      for(; j>left && isbigger(j, left); j--);
      if( i >= j )
        break;
      swap(result[i], result[j]);
    }//while
    swap(result[j], result[left]);
    sort_terms(left, j-1);
    sort_terms(j+1, right);
  }
}

//return true when a>b, false when a<=b
bool isbigger(int a, int b){
  if( result[a].pow_x < result[b].pow_x )
    return true;
  if( result[a].pow_x > result[b].pow_x )
    return false;
  if( result[a].pow_y > result[b].pow_y )
    return true;
  return false;
}

void comb_terms(void){
  int i = 0;
  while( i < result.size() ){
    if( result[i].coef == 0 )
      result.erase(result.begin()+i);
    else if( i < (result.size()-1) && (result[i].pow_x == result[i+1].pow_x) && (result[i].pow_y == result[i+1].pow_y) ){
      result[i].coef += result[i+1].coef;
      result.erase(result.begin()+i+1);
    }
    else
      i++;
  }
}

string atostring(int num){
  stringstream ss;
  ss << num;
  return ss.str();
}

ACM: 125 – Numbering Paths

2010-09-07T05:07:00.000+08:00

這題頗有挑戰性，給有向圖(directed graph)，要找出圖上是否有環(cycle)，也要找出所有點之間存在的所有路徑數量，當路徑經過環(即代表路徑數量無窮大)，路徑數量要輸出-1。

我的作法是先以dp(Floyd-Warshall做變化)找出所有點之間存在的所有路徑數量，接著判斷是否有k->k (k = 1….n)路徑存在，若存在即為環存在，再跑一次迴圈將所有可與k相連的路徑的值設為-1。

在寫的時候原本Floyd-Warshall的觀念還是沒想清楚，在最外面多加了一層算「經過幾個點」的迴圈，寫出來超冗長且bug連連。後來改用recursive去產出所有組合，想當然Time Limit Exceed。苦思良久才領悟到不必多加那一層迴圈，也搞清楚找到環以後如何去刪掉所有受影響的節點了。柳暗花明，最後看到了清爽的程式碼 :))

不過仍然是跑了兩次三層迴圈，應該算O(2 * n^3)吧，一定可以更省，就繼續研究吧。

CODE

#include <iostream>
using namespace std;

#define MAX 30

int main(){
  int i, j, k;
  int maxn, side, d1, d2, total;
  int matrix[MAX][MAX]; //total number of paths
  
  total = 0;
  while( cin >> side ){
    for(i=0; i<MAX; i++)
      for(j=0; j<MAX; j++)
        matrix[i][j] = 0;
        
    maxn = -1;
    for(i=0; i<side; i++){
      cin >> d1 >> d2;
      matrix[d1][d2] = 1;
      if( d1 > maxn ) maxn = d1;
      if( d2 > maxn ) maxn = d2;
    }
    maxn++;
  
    //findout all paths
    for(k=0; k<maxn; k++)
      for(i=0; i<maxn; i++)
        for(j=0; j<maxn; j++)
          if( matrix[i][k] * matrix[k][j] > 0 )
            matrix[i][j] += matrix[i][k];
    
    //eliminate paths involved cycles
    for(k=0; k<maxn; k++)
      if( matrix[k][k] != 0 ) //cycle
        for(i=0; i<maxn; i++)
          for(j=0; j<maxn; j++)
            if( matrix[i][k] * matrix[k][j] != 0 )
              matrix[i][j] = -1;
    
    //output
    cout << "matrix for city " << total << endl;
    for(i=0; i<maxn; i++){
      cout << matrix[i][0];
      for(j=1; j<maxn; j++)
        cout << ' ' << matrix[i][j];
      cout << endl;
    }
    
    total++;
  }//while
  return 0;
}

ACM: 124 – Following Orders

2010-09-06T02:55:00.000+08:00

真開心再用vector寫出了這題，嘗試用vector的push_back()及erase()產生所有的組合。在取出元素時檢查未被取出的元素是否有小於該元素的元素(小的元素應該先被取出)。

這題是給一些元素，再給其中部分元素的大小關係，依字典順序輸出在給定的大小關係下所有可能的元素組合。

CODE

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define MAX_LET 26

vector<char> vars; //variables
bool consts[MAX_LET][MAX_LET]; //constraints

void sort_vars(int left, int right);
void comb(vector<char> current, vector<char> pool);

int main(){
  int i, j;
  char c, d1, d2;
  bool flag = false;
  
  for(i=0; i<MAX_LET; i++)
    for(j=0; j<MAX_LET; j++)
      consts[i][j] = false;
  
  while( (c = getchar()) != EOF ){
    if( c >= 'a' && c <= 'z' ){
      vars.push_back(c);
    }//get variables
    else if( c == '\n' ){
      while( (d1 = getchar()) != '\n' ){
        if( d1 >= 'a' && d1 <= 'z' ){
          cin >> d2;
          consts[d2-'a'][d1-'a'] = true;
        }
      }//while get constraints
      
      if(flag == true)
        puts("");
      sort_vars(0, vars.size()-1); //sort variables
      vector<char> tmp;
      comb(tmp, vars); //produce combinations
      
      //initialize
      flag = true;
      vars.clear();
      for(i=0; i<MAX_LET; i++)
        for(j=0; j<MAX_LET; j++)
          consts[i][j] = false;
    }//get constraints
  }  
  
  return 0;
}

void sort_vars(int left, int right){
  if( left < right ){
    int i = left + 1;
    int j = right;
    
    while(1){
      for(; (i<=right) && (vars[i] <= vars[left]); i++);
      for(; (j>left) && (vars[j] > vars[left]); j--);
      if( i>=j )
        break;
      swap(vars[i], vars[j]);
    }
    swap(vars[j], vars[left]);
    sort_vars(left, j-1);
    sort_vars(j+1, right);
  }
}

void comb(vector<char> current, vector<char> pool){
  vector<char>::size_type i, j;
  if( pool.empty() ){
    for(i=0; i!=current.size(); i++)
      cout << current[i];
    cout << endl;
    return;
  }
  
  vector<char> tmp_cur, tmp_pool;
  vector<char>::size_type psize = pool.size();
  for(i=0; i<psize; i++){
    for(j=0; j<psize; j++){
      if( consts[ pool[i]-'a' ][ pool[j]-'a' ] )
        break;
    }
    if( j == psize ){
      tmp_pool = pool;
      tmp_cur = current;
      tmp_cur.push_back(pool[i]);
      tmp_pool.erase(tmp_pool.begin()+i);
    
      comb(tmp_cur, tmp_pool);
    }
  }//i
  return;
}

ACM: 123 – Searching Quickly

2010-09-05T23:30:00.000+08:00

這題是要在所給的一連串字串中，排除特定一些關鍵字，再將排除後剩餘的所有單字連同原字串順序輸出。

寫出來相當開心！第一次嘗試使用C++的class與string, vector等STL(Standard Template Library)，也使用了自訂class來做vector！string和vector乍看之下有點抽象，但實作起來還蠻方便有趣的，C++ Primer的作者在書中不斷警告使用者在C++要減少使用char*和array。

CODE

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

class cls_kwords{
public:
  string keyword;
  int title_no;
  int position; //ending position of keyword in title
};

const int to_low = 'a' - 'A';
vector<string> words; //vector of words to ignore
vector<string> titles;
vector<cls_kwords> keywords;

void sort_words(int left, int right);
void sort_keywords(int left, int right);
bool isignore(string line);
bool isbigger(int a, int b);

int main(){
  string s;
  
  while( cin >> s ){
    if( s[0] == ':' ) break;
    words.push_back(s);
  }//words to ignore
  
  //sort words to ignore
  sort_words(0, words.size()-1);
  
  //get titles
  int total = 0;
  string key;
  string::size_type i, len;
  cls_kwords tmp;
  
  while( getline(cin, s) ){
    if( !s.empty() ){
      len = s.size();
      for(i=0; i<=len; i++){
        if( i == len || s[i] == ' ' ){
          if( !key.empty() ){
            if( !isignore(key) ){
              tmp.keyword = key;
              tmp.title_no = total;
              tmp.position = i;
              keywords.push_back(tmp);
            }
            key = "";
          }
        }
        else if( s[i] >= 'A' && s[i] <= 'Z' ){
          s[i] += to_low;
          key += s[i];
        }
        else if( s[i] >= 'a' && s[i] <= 'z' )
          key += s[i];
      }//i

      titles.push_back(s);
      total++;
    }
  }//while get titles
  
  int ksize, st, j;
  //sort keywords
  ksize = keywords.size();
  sort_keywords(0, ksize-1);
  
  //output
  for(int k=0; k!=ksize; k++){
    len = titles[ keywords[k].title_no ].size();
    st = keywords[k].position - keywords[k].keyword.size();
    for(j=0; j<st; j++)
      cout << titles[ keywords[k].title_no ][j];
    for(; j<keywords[k].position; j++)
      printf("%c", titles[ keywords[k].title_no ][j] - to_low);
    for(; j<len; j++)
      cout << titles[ keywords[k].title_no ][j];
    cout << endl;
  }
  
  return 0;
}

void sort_words(int left, int right){
  if( left < right ){
    int i = left + 1;
    int j = right;
    
    while(1){
      for(; (i<=right) && (words[i]<=words[left]); i++);
      for(; (j>left) && (words[j]>words[left]); j--);
      if( i >= j )
        break;
      swap(words[i++], words[j--]);
    }//while
    swap(words[j], words[left]);
    sort_words(left, j-1);
    sort_words(j+1, right);
  }
}

bool isignore(string line){
  vector<string>::size_type i, max = words.size();

  for(i=0; i<max; i++){
    if( line < words[i] ) break;
    else if( line == words[i] ) return true;
  }

  return false;
}

void sort_keywords(int left, int right){
  if( left < right ){
    int i = left + 1;
    int j = right;
    
    while(1){
      for(; (i<=right) && (!isbigger(i, left)) ; i++);
      for(; (j>left) && (isbigger(j, left)) ; j--);
      if( i >= j )
        break;
      swap(keywords[i++], keywords[j--]);
    }
    swap(keywords[j], keywords[left]);
    sort_keywords(left, j-1);
    sort_keywords(j+1, right);
  }
}

//return true when a>b, false when a<=b
bool isbigger(int a, int b){
  if( a == b ) return false;
  
  if( keywords[a].keyword > keywords[b].keyword ) return true;
  else if( keywords[a].keyword < keywords[b].keyword ) return false;
  
  if( keywords[a].title_no > keywords[b].title_no ) return true;
  else if( keywords[a].title_no < keywords[b].title_no ) return false;
  
  if( keywords[a].position > keywords[b].position ) return true;
  else if( keywords[a].position < keywords[b].position ) return false;
  
  return false;
}

ACM: 122 – Trees on the level

2010-09-04T23:51:00.001+08:00

這題是用文字給出二元樹，檢查是否是完整的樹，如果是完整的樹即輸出廣度優先搜尋(BFS, Bread First Search)的結果。

我用的方法是用quicksort先對字串排序(eg, L, R, LL, LR, RL, RR,…)，接著檢查是否是完整的樹，最後再照字串順序輸出該node的數字。Runtime 0.008，程式碼也相當龐大，在這題來說顯然有更快更精簡的方法，也許可以考慮使用struct, C++的STL函式庫，也許會有更好的表現。

CODE

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

#define MAX_LEN 300
#define MAX_NODE 256

int total, num[MAX_NODE], len[MAX_NODE];
char line[MAX_NODE][MAX_NODE];
bool rep;

void sort_tree(int left, int right);
bool isbigger(int a, int b);
void swapnode(int a, int b);
bool valid_tree(void);

int main(){
  char c, snum[MAX_LEN], sline[MAX_LEN];
  int p, pnum, pline;
  int i;
  
  rep = false;
  total = 0;
  for(i=0; i<MAX_NODE; i++)
    num[i] = -1;
    
  while( (c = getchar()) != EOF ){
    if( c == '(' ){
      p = pnum = pline = 0;
    }
    else if( c == ')' ){
      if( p == 0 ){        
        sort_tree(0, total-1);
        
        if( valid_tree() ){
          cout << num[0];
          for(i=1; i<total; i++)
            cout << ' ' << num[i];
          cout << endl;
        }
        else
          cout << "not complete" << endl;
        //initialize
        rep = false;
        total = 0;
        for(i=0; i<MAX_NODE; i++)
          num[i] = -1;
      }//end of tree
      else{
        if( pnum > 0 ){
          snum[pnum] = '\0';
          sscanf(snum, "%d", &num[total]);
          
          for(i=0; i<pline; i++)
            line[total][i] = sline[i];
          line[total][pline] = '\0';
          len[total] = pline;
        }//if pnum > 0
        total++;
      }//end of node
    }
    else if( c == ',' ){
      p++;
    }
    else if( c >= '0' && c <= '9' ){
      snum[pnum++] = c;
      p++;
    }
    else if( c == 'L' || c == 'R' ){
      sline[pline++] = c;
      p++;
    }
    else ;
  }//while
  
  return 0;
}

void sort_tree(int left, int right){
  if( left < right ){
    int i = left + 1;
    int j = right;
    
    while(1){
      for(i; (isbigger(i, left)==false) && (i<=right); i++);
      for(j; (isbigger(j, left)==true) && (j>left); j--);
      if( i >= j )
        break;
      swapnode(i, j);
      i++;
      j--;
    }//while
    
    swapnode(left, j);
    sort_tree(left, j-1);
    sort_tree(j+1, right);
  }
}

//return true if a > b, return false if a <= b
bool isbigger(int a, int b){
  if( a == b )
    return false;
  if( len[a] > len[b] )
    return true;
  if( len[a] < len[b] )
    return false;
  
  for(int i=0; i<len[a]; i++){
    if( line[a][i] > line[b][i] )
      return true;
    else if( line[a][i] < line[b][i] )
      return false;
  }
  
  rep = true;
  return false;
}

void swapnode(int a, int b){
  swap(num[a], num[b]);
  swap(len[a], len[b]);
  
  char tmps[MAX_LEN];
  strcpy(tmps, line[a]);
  strcpy(line[a], line[b]);
  strcpy(line[b], tmps);
}

bool valid_tree(void){  
  if( (num[0] == -1) || (len[0] != 0) )
    return false;
  if( rep )
    return false;
  
  int i, j;
  bool flag;
  char tmps[MAX_LEN];
  for(i=1; len[i]<=1 && i<total; i++)
    if( num[i] == -1 )
      return false;
  for(i; i<total; i++){
    if( num[i] == -1 )
      return false;
      
    flag = false;
    for(j=0; j<(len[i]-1); j++)
      tmps[j] = line[i][j];
    tmps[j] = '\0';
    for(j=(i-1); (j>=0) && (len[j]>=(len[i]-1)); j--)
      if( strcmp(line[j], tmps) == 0 ){
        flag = true;
        break;
      }

    if( !flag )
      return false;
  }//i
  
  return true;
}

《約耳談軟體》

2010-09-03T18:31:00.000+08:00

把線上版的《約耳談軟體》(Joel On Software)照著實體書出版目錄至少看過了一遍，是融合技術、經驗、娛樂、還有勵志性的好看的書！書內談許多軟體專案開發的實務技巧，強調寫規格、定時程、Daily Build的重要性，也談及專案管理及軟體商業策略等等。

雖然有些內容還無法完全了解，但似乎對軟體業多了一分認識，也從〈軟體人員面試教戰守則〉中，思考怎樣是業界所需要的人。而勵志的〈邊開火邊移動〉更鼓勵讀者不要擔心每天只前進一點點，重點是每天都前進一點點。除此之外，由於作者曾經在微軟工作過，許多寫到關於微軟的管理風格、策略的部分都看得很過癮啊！

One more step ahead

2010-08-31T00:25:00.000+08:00

很開心又跨出多一步，終於from C to C++了。

ACM: 121 - Pipe Fitters

2010-08-31T00:13:00.001+08:00

這題是數學題，給矩形的長和寬，問最多可以擺幾個直徑為1單位的圓圈。只需考慮題目提供的grid或skew兩種排列方式。

值得一記的是，這題也算是我的第一個C++程式！

TIPS

測資 "0.9 10"，output是 "0 grid"

CODE

#include <iostream>
#include <cmath>
using namespace std;

int skew(float width, float height);

int main()
{
  int p, count;
  char c, s[20];
  float side[2];
  
  p = count = 0;
  while( (c = getchar()) != EOF ){
    if( (c >= '0' && c <= '9') || c == '.' )
      s[p++] = c;
    else if( c == ' ' ){
      if( p > 0 ){
        s[p] = '\0';
        sscanf(s, "%f", &side[count++]);
        p = 0;
      }//if valid input
    }//else if c == '0'
    else if( c == '\n' ){
      if( p > 0 ){
        s[p] = '\0';
        sscanf(s, "%f", &side[count]);
        
        int max, mtype = 0, tmp;
        char type[2][5] = {"grid", "skew"};
        if( count == 0 ){
          max = (int)side[0] * (int)side[0];
          if( (tmp = skew(side[0], side[0])) > max ){
            max = tmp;
            mtype = 1;
          }
        }//if square
        else{
          max = (int)side[0] * (int)side[1];
          if( (tmp = skew(side[0], side[1])) > max ){
            max = tmp;
            mtype = 1;
          }
          if( (tmp = skew(side[1], side[0])) > max ){
            max = tmp;
            mtype = 1;
          }
        }//if rectangle
        
        cout << max << ' ' << type[mtype] << '\n';
        p = count = 0;
      }//if valid input
    }//else if c == '\n'
    else ;
  }//while input
  
  return 0;
}

int skew(float width, float height){  
  if( width < 1.0 || height < 1.0 )
    return 0;
  
  int dh, sum = 0;
  float th;//height of triangle
  
  th = sqrt(3)/2;
  dh = (int)( (height-1)/th );
  dh++;
  
  sum += (int)width * dh;
  if( (width - (int)width) < 0.5 )
    sum -= (int)( dh/2 );
    
  return sum;
}

烏龍派出所片尾曲

2010-08-28T14:39:00.000+08:00

01〈スマイル〉

02〈いいことあるさ〉

03〈淑女の夢は万華鏡〉

04〈ブウェーのビヤビヤ〉

Ruby筆記

2010-08-27T23:01:00.001+08:00

Ruby是一個跨平台的直譯式物件導向程式設計語言，訴求語法自然快捷，增進程式設計者的愉悅。
由Ruby寫成的Ruby on Rails(Rails/RoR)是open source的web application framework，由於能大幅減少網路應用服務的開發時間而受到歡迎。

安裝Ruby

http://www.ruby-lang.org/zh_TW/downloads/

IDE

RadRails: http://aptana.com/products/radrails
(跨平台的Ruby和Rails的IDE)

入門體驗

Try Ruby: 15分鐘的線上即時Ruby體驗
二十分鐘 Ruby 體驗: 官網的入門教學

書

Beginning Ruby: From Novice to Professional
Programming Ruby 1.9: The Pragmatic Programmers' Guide

中文線上資源

中文官方網站
 Ruby Taiwan Community

幾本不錯的Ruby和Ruby On Rails電子書下載

My First Ruby Program

2010-08-27T21:20:00.001+08:00

用Ruby試寫了一個找質數的程式，再加了簡單排版功能讓輸出比較好看。用到10000000只是想測試Ruby的陣列可以開到這麼大，而最能感受到Ruby快靚正的地方，應該就在 i.to_s.length 這句了，只要一行就能知道數字長度！

Max = 10000000
num = []
length = 0

(Max+1).times { |i| num << i }

2.upto(Max) do |i|
  if num[i] == i
    print i
    (i+i).step(Max, i) { |j| num[j] = 0 }
    
    #排版
    length += i.to_s.length
    if length > 40
      print "\n"
      length = 0
    else print " "
    end
  end
end

Software Engineering

2010-08-26T19:01:00.000+08:00

軟體工程的目標在於在有限的時間、資源、人力下開發出達成預期目標的軟體。

Scope
From Wikipedia

1. Software requirements
2. Software design
3. Software development
4. Software testing
5. Software maintenance
6. Software configuration management
7. Software engineering management
8. Software development process
9. Software engineering tools
10. Software quality

書
轉自<前 100 名最佳軟體工程書籍>

1. Steve McConnell, Code Complete: A Practical Handbook of Software Construction
中文版：軟體建構之道

2. Elisabeth Freeman, etc., Head First Design Patterns
中文版：深入淺出設計模式

3. Steve McConnell, Rapid Development
中文版：軟體快速開發

4. Erich Gamma, Design Patterns: Elements of Reusable Object-Oriented Software
中文版：物件導向設計模式

5. Bruce Schneier, Applied Cryptography: Protocols, Algorithms, and Source Code (2nd Edition)

6. Robert C. Martin, Agile Software Development: Principles, Patterns and Practices
中文版：敏捷軟體開發－原則、樣式及實務

7. Joel Spolsky, Joel on Software
中文版：約耳談軟體（網站）

8. Tom DeMarco, Timothy Lister, Peopleware: Productive Projects and Teams (2nd Edition)
中文版：Peopleware：腦力密集產業的人才管理之道

9. Frederick P. Brooks, The Mythical Man-Month, Anniversary Edition (2nd Edition)
中文版：人月神話

10. Martin Fowler, Refactoring: Improving the Design of Existing Code
中文版：重構－改善既有程式的設計

ACM 20 題

2010-08-26T16:01:00.000+08:00

寫到了第二個10題，讚。111 ~ 120因為有許多simulation題，比前10題相對輕鬆一點點，但還是學到了LIS、尤拉路徑、接觸到簡化的TSP(Travelling Salesman Problem)問題，也練習不少recurssive。加油，總有一天要寫出runtime 0.000的code！

ACM: 120 - Stacks of Flapjacks

2010-08-26T15:38:00.001+08:00

這一題是給一疊大小不一的鬆餅，要用整個堆疊旋轉的方式，讓鬆餅從小到大排序。輸出結果不需是最佳解，只要能夠讓鬆餅排序就可以了。我覺得寫這題就是頭腦要清楚啊，因為input資料是從top開始，但要輸出的flip數字卻要從bottom算起！

CODE

#include <stdio.h>

#define MAX 30

int n, cake[MAX];

int makenum(int p, int *a);
void flipcake(int p);

int main(){
  int i, k, max, flag;
  int p, num[3];
  char c;

  n = p = flag = 0;
  while( (c = getchar()) != EOF ){
    if( c >= '0' && c <= '9' ){
      num[p++] = c - '0';
    }/*if '0'<= c <='9'*/
    else if( c == ' ' ){
      cake[n++] = makenum(p, num);
      p = 0;
    }/*if c == ' '*/
    else if( c == '\n' ){
      if( p > 0 )
        cake[n++] = makenum(p, num);
      
      if( n > 0 ){
        printf("%d", cake[0]);
        for(i=1; i<n; i++)
          printf(" %d", cake[i]);
        printf("\n");
        
        for(i=0; i<n; i++){
          max = 0;
          for(k=1; k<(n-i); k++){
            if( cake[k] > cake[max] )
              max = k;
          }/*k: find max pancake*/
          
          /*flip biggest pancake to top*/
          if( max>0 && max<(n-i-1) ){
            flipcake(max);
            if( flag == 1 ) printf(" ");
            else flag = 1;
            printf("%d", n-max);
          }
          /*flip biggest pancake to current bottom*/
          if( max<(n-i-1) ){
            flipcake(n-i-1);
            if( flag == 1 ) printf(" ");
            else flag = 1;
            printf("%d", i+1);
          }
        }/*j: sort the pancake*/
        
        if( flag == 1 ) printf(" ");
        printf("0\n");
      }/*if valid input*/
            
      n = p = flag = 0;
    }/*if c == '\n'*/
    else ;
  }/*while*/
  
  exit(0);
}

int makenum(int p, int *a){
  if( p == 3 )
    return 100;
  if( p == 2 )
    return (a[0]*10 + a[1]);
  return a[0];
}

void flipcake(int p){
  int i, j, tmp;
  
  for(i=0, j=p; i<=j; i++, j--){
    tmp = cake[i];
    cake[i] = cake[j];
    cake[j] = tmp;
  }
}

ACM: 119 - Greedy Gift Givers

2010-08-26T12:59:00.000+08:00

也是很單純的simulation題，唯一要注意的是gift taker數量可能為0，要排除除以0的情況。

CODE

#include <stdio.h>
#include <string.h>

#define MAX_P 10
#define MAX_LEN 12

int n;
char names[MAX_P][MAX_LEN+1];

int findname(char *name);

int main(){
  int i, j, k, flag;
  int gift, taker, net[MAX_P];
  char s[MAX_LEN+1];
  
  flag = 0;
  while( scanf("%d", &n) != EOF ){
    if( flag == 1 )
      printf("\n");
    
    for(i=0; i<n; i++){
      scanf("%s", names[i]);
      net[i] = 0;
    }
    
    for(i=0; i<n; i++){
      scanf("%s %d %d", s, &gift, &taker);
      k = findname(s);
      
      if( taker != 0 ){
        net[k] -= gift;
        net[k] += (gift % taker);
        gift /= taker;
      }
      
      for(j=0; j<taker; j++){
        scanf("%s", s);
        k = findname(s);
        net[k] += gift;
      }/*j: give gift to taker*/
    }/*i*/
    
    for(i=0; i<n; i++)
      printf("%s %d\n", names[i], net[i]);
    
    flag = 1;
  }/*while more groups data*/
  
  exit(0);
}

int findname(char *s){
  int i;
  
  for(i=0; i<n; i++)
    if( strcmp(s, names[i]) == 0 )
      return i;
}

ACM: 118 - Mutant Flatworld Explorers

2010-08-26T12:53:00.000+08:00

很單純的simulation題，就是照著規則去模擬。

CODE

#include <stdio.h>
#include <string.h>

#define MAX 50
#define MAX_LEN 100

int main(){
  int i, len;
  int mx, my, x, y, dir, t[MAX+1][MAX+1];
  int dx[4]={0, 1, 0, -1}, dy[4]={1, 0, -1, 0};
  char c, cmd[MAX_LEN], nesw[4]="NESW";
  
  scanf("%d %d", &mx, &my);
  while( scanf("%d %d %c", &x, &y, &c) != EOF ){
    scanf("%s", cmd);
    
    for(i=0; i<4; i++)
      if( c == nesw[i] )
        dir = i;
    
    len = strlen(cmd);
    for(i=0; i<len; i++){
      switch ( cmd[i] ){
        case 'L':
          dir--;
          break;
        case 'R':
          dir++;
          break;
        case 'F':
          while( dir < 0 )
            dir += 4;
          dir = dir % 4;
          if( (x+dx[dir])<0 || (x+dx[dir])>mx || (y+dy[dir])<0 || (y+dy[dir])>my ){
            if( t[x][y] != 1 ){
              t[x][y] = 1;
              i = len;
            }
          }
          else{
            x += dx[dir];
            y += dy[dir];
          }
          break;
        default: break;
      }/*switch*/
    }/*i*/
    
    while( dir < 0 )
      dir += 4;
    dir = dir % 4;
    printf("%d %d %c", x, y, nesw[dir]);
    if( i > len )
      printf(" LOST");
    printf("\n");
  }/*while*/
  
  exit(0);
}

ACM: 117 - The Postal Worker Rings Once

2010-08-25T21:20:00.000+08:00

這一題是給許多條「街道」，找出將每條街至少走過一次，並回到原點的最短路徑，傳回路徑總長。可以視作一個graph，找出將每個邊至少走一次，並回到原點的最小路徑權重值。這題有以下背景知識：

Eulerian Circuit/Eulerian Path (尤拉路徑)

題目有兩個要點，將這題指向尤拉路徑:
1. In each postal route there will be a path between all intersections, i.e., the intersections are connected. (所有的道路可以接通，即是這是一個連通圖)
2. There will be at most two intersections with odd degree. All other intersections will have even degree, i.e., an even number of streets meeting at that intersection. (圖裡最多只有兩個點會有奇數個邊，其他點都會有偶數個邊)

Eulerian Circuit是判斷一個圖(無向圖)存不存在一個路徑，能從一點開始不經過重複的邊走完全圖，再回到原點。存在的條件如下:
圖形上每一個端點(vertex)皆有偶數個邊(degree為偶數)
因為若有一個端點有奇數個邊，勢必有一條路只能去不能回。

Eulerian Path(Eulerian Chain)則是一筆劃問題，找圖上是否存在一個路徑，從一點開始不經過重複的邊走完全圖，但不一定要回到原點。存在的條件如下:
圖形上最多只有兩個端點有奇數個邊，其餘端點皆有偶數個邊
而在有端點為奇數degree的情況下，Eulerian Path必定從奇數degree的端點開始，並且結束於奇數degree的端點。因為拿掉造成奇數degree的邊，圖形就可以回到原點，因此Eulerian Path可以想成是先走完一圈回到原點，再去特別走「多出來」的路徑，所以一定開始結束在奇數degree的端點。

因此這題是Eulerian Path的問題，當所有端點的degree皆為偶數時，最短路徑即是所有路徑的總和；而因為需要回到原點，當有奇數degree端點存在時，需再找出奇數degree端點之間的最小路徑，以回到原點。

Handshaking Lemma (握手定裡)

題目寫了"There will be at most two intersections with odd degree"，是「最多」兩個端點有奇數degree，但只有一個端點有奇數degree的情況是否可能存在呢？

從handshaking lemma可以了解這個情況是不可能的，因為好比兩人握手的時候，必然是兩個人都伸出手來，因此一個端點有奇數個邊，也必然有相應的點去連接那個邊，雙向計算的結果是，任何一個(無向)圖，擁有奇數個邊的端點數是偶數！

因此這個題目只有兩種情況：全部端點皆有偶數個邊，或只有兩個端點有奇數個邊。

寫出來Runtime 0.008，這題平均runtime超短的，要怎樣才能寫到0.000的境界呢！！我想也許在找shortest path的部分還可以再更快一點。

REFERENCES

117 - The Postal Worker Rings Once
Euler Circuit / Euler Path
Handshaking lemma

CODE

#include <stdio.h>
#include <string.h>

#define MAX 26
#define MAX_LEN 1000

int t[MAX][MAX], od[2];

void initialize(void);
int odegree(void);
int shortest(int a, int b);

int main(){
  int i, j;
  int sum, len;
  char s[MAX_LEN];
  
  sum = 0;
  initialize();
  while( scanf("%s", s) != EOF ){
    if( strcmp(s, "deadend") == 0 ){
      if( odegree() == 1 ){
        sum += shortest(od[0], od[1]);
        printf("%d\n", sum);
      }
      else
        printf("%d\n", sum);
      
      sum = 0;
      initialize();
    }/*output*/
    else{
      len = strlen(s);
      sum += len;
      t[ s[0]-'a' ][ s[len-1]-'a' ] = t[ s[len-1]-'a' ][ s[0]-'a' ] = len;
    }/*read data*/
  }/*while input data*/
  
  exit(0);
}

void initialize(void){
  int i, j;
  
  for(i=0; i<MAX; i++)
    for(j=0; j<MAX; j++)
      t[i][j] = 0;
  return;
}

int odegree(void){
  int i, j, k, d;
  
  d = 0;
  for(i=0; i<MAX; i++){
    k = 0;
    for(j=0; j<MAX; j++)
      if( t[i][j] > 0 )
        k++;
    if( k%2 == 1 )
      od[d++] = i;
  }
  
  if( d > 0 )
    return 1;
  return 0;
}

int shortest(int a, int b){
  int i, j, k, tmp;
  
  for(k=0; k<MAX; k++){
    for(i=0; i<MAX; i++){
      for(j=0; j<MAX; j++){
        if( t[i][k]*t[k][j] != 0 ){
          tmp = t[i][k] + t[k][j];
          if( tmp < t[i][j] || t[i][j] == 0 )
            t[i][j] = tmp;
        }
      }/*j*/
    }/*i*/
  }/*k*/
  
  return t[a][b];
}

ACM: 116 - Unidirectional TSP

2010-08-25T00:14:00.001+08:00

這一題要找一個table從左走到右的最小和路徑。題目寫的很像可以用brute force，但用brute force會超過time limit。後來想到DP的方法，很開心。DP真是一種很神奇的概念。

寫出來後一直runtime error，看很久才發現是表格頭接尾，尾接頭的部分沒有用餘數的方法讓他自動接，造成有漏洞會陣列越界讀取。改成餘數的方法就解決了。果然越好的演算法越不會有奇怪的洞啊。

CODE

#include <stdlib.h>
#include <stdio.h>

#define MAX_M 10
#define MAX_N 100

int main(){
  int i, j, k, min, tmp;
  int m, n, t[MAX_M][MAX_N], p[MAX_M][MAX_N];
  int mod[2] = {-1, 1};
  
  while( scanf("%d %d", &m, &n) == 2 ){
    for(i=0; i<m; i++)
      for(j=0; j<n; j++)
        scanf("%d", &t[i][j]);
    
    for(j=(n-2); j>=0; j--){
      for(i=0; i<m; i++){
        min = i;
        for(k=0; k<2; k++){
          tmp = (i+mod[k]+m) % m;
          if( t[tmp][j+1] < t[min][j+1] )
            min = tmp;
          else if( t[tmp][j+1] == t[min][j+1] )
            if( tmp < min )
              min = tmp;
        }/*k*/
        p[i][j] = min;
        t[i][j] += t[min][j+1];
      }/*i: row*/
    }/*j: col*/
    
    k = 0;
    for(i=1; i<m; i++)
      if( t[i][0] < t[k][0] )
        k = i;
    
    j = k;
    printf("%d", k+1);
    for(i=0; i<n-1; i++){
      printf(" %d", p[j][i]+1);
      j = p[j][i];
    }
    printf("\n%d\n", t[k][0]);
  }/*while input data*/ 
  
  exit(0);
}

Mourning

2010-08-24T18:12:00.001+08:00

Mourning to the hostage victims at Manila. May their souls rest in peace, and their families be comforted…

ACM: 115 - Climbing Trees

2010-08-24T16:45:00.001+08:00

這題寫出來也很感動，原因一是自己想到演算法解出了graph題！原因二是寫完以後de了超久的bug，明明自己測試output都正確，一直找不到runtime error的原因。看超久才發現原來是把一個變數放錯資料型別，改了以後總算AC了！

我用一個一維陣列存每個child的parent，再不斷trace。

CODE

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_NAMES 300
#define LEN_NAME 31

int tree[MAX_NAMES], maxn;
char name[MAX_NAMES][LEN_NAME+1];

int addname(char *s);
int findname(char *s);
void qry(int p, int q);
void showtrace(int t);
int isdescendent(int p, int q, char *s);
int iscousin(int p, int q);

int main(){
  int pk, qk;
  char p[LEN_NAME+1], q[LEN_NAME+1];
  
  maxn = 0;
  while( scanf("%s %s", p, q) == 2 ){
    if( strcmp(p, "no.child") == 0 )
      break;
    else{
      pk = addname(p);
      qk = addname(q);
      tree[pk] = qk;
    }
  }/*while parent-child pairs input*/
  
  /*read query*/
  while( scanf("%s %s", p, q) == 2 ){
    pk = findname(p);
    qk = findname(q);
    qry(pk, qk);
  }/*while query input*/
  
  exit(0);
}

int addname(char *s){
  int i;
  
  /*check if name exists*/
  for(i=0; i<maxn; i++)
    if( strcmp(s, name[i]) == 0 )
      return i;
  
  /*add new name*/
  strcpy(name[maxn], s);
  tree[maxn] = maxn;
  maxn++;
  
  return (maxn-1);
}

int findname(char *s){
  int i;
  
  for(i=0; i<maxn; i++)
    if( strcmp(s, name[i]) == 0 )
      return i;
  
  return -1;
}

void qry(int p, int q){ 
  if( p != -1 && q != -1 ){
    if( tree[p] == tree[q] ){
      printf("sibling\n");
      return;
    }
    if( isdescendent(p, q, "child") == 1 )
      return;
    if( isdescendent(q, p, "parent") == 1 )
      return;
    if( iscousin(p, q) == 1 )
      return;
  }/*if p, q != -1 */
  
  printf("no relation\n");
  return;
}

void showtrace(int t){
  int i;
  
  if( t == 0 )
    return;
  for(i=t; i>1; i--)
    printf("great ");
  printf("grand ");
}

int isdescendent(int p, int q, char *s){
  int tp, trace;
  
  tp = p;
  trace = 0;
  while( tree[tp] != tp ){
    tp = tree[tp];
    if( tp == q ){
      showtrace(trace);
      printf("%s\n", s);
      return 1;
    }
    trace++;
  }
  
  return 0;
}

int iscousin(int p, int q){
  int tp, tq, m, n;
  
  tp = p;
  tq = q;
  m = n = 0;
  while( tp != tree[tp] ){
    tp = tree[tp];
    while( tq != tree[tq] ){
      tq = tree[tq];
      if( tp == tq ){
        if( m > n ){
          printf("%d cousin ", n);
          printf("removed %d\n", (m-n));
        }
        else if( m == n )
          printf("%d cousin\n", m);
        else{
          printf("%d cousin ", m);
          printf("removed %d\n", (n-m));
        }
        return 1;
      }/*if common ancestor found*/
      n++;
    }/*while: trace q*/      
    tq = q;
    n = 0;
    m++;
  }/*while: trace p*/
  
  return 0;
}

ACM: 114 - Simulation Wizardry

2010-08-23T22:08:00.001+08:00

相對輕鬆一點的有趣Simulation題目，就是要仔細把文字敘述看清楚，了解遊戲規則。我覺得最重要的應該是這句話:

"A ball ''hits'' an obstacle during a timestep when it would otherwise move on top of the bumper or wall grid point. A hit causes the ball to ``rebound'' by turning right (clockwise) 90 degrees, without ever moving on top of the obstacle and without changing position (only the direction changes as a result of a rebound)."

即是球撞到障礙物(牆或bumper)，都會留在原位不動，只改變下一步的方向。

其他就是照著遊戲規則simulation了。Runtime 0.044，Ranking進前100，開心開心。

CODE

#include <stdio.h>

#define MAX 50

#define GAME 0
#define VALUE 1
#define COST 2

#define RIGHT 0
#define UP 1
#define LEFT 2
#define DOWN 3

int m, n, g[3][MAX+1][MAX+1];

int pinball(int x, int y, int dir, int life);
void nextmove(int x, int y, int dir, int *arr);
int chgdir(int dir);

int main(){
  int i, j, t;
  int x, y, v1, v2, sum;
  
  scanf("%d %d", &m, &n);
  scanf("%d", &t); /*cost of hitting the wall*/
  
  /*initialize the pinball game & set walls*/
  for(i=1; i<=m; i++){
    g[GAME][1][i] = g[GAME][n][i] = 1;
    g[VALUE][1][i] = g[VALUE][n][i] = 0;
    g[COST][1][i] = g[COST][n][i] = t;
  }
  for(i=2; i<n; i++){
    for(j=1; j<=m; j++){
      if( j==1 || j==m ){
        g[GAME][i][j] = 1;
        g[VALUE][i][j] = 0;
        g[COST][i][j] = t;
      }
      else
        g[GAME][i][j] = g[VALUE][i][j] = g[COST][i][j] = 0;
    }/*j*/
  }/*i*/
  
  /*read bumpers*/
  scanf("%d", &t); /*number of bumpers*/
  for(i=0; i<t; i++){
    scanf("%d %d %d %d", &x, &y, &v1, &v2);
    
    g[GAME][x][y] = 1;
    g[VALUE][x][y] = v1;
    g[COST][x][y] = v2;
  }/*i*/
  
  /*read balls*/
  sum = t = 0;
  while( scanf("%d %d %d %d", &x, &y, &v1, &v2) != EOF ){
    t = pinball(x, y, v1, v2);
    sum += t;
    printf("%d\n", t);
  }/*while*/
  
  printf("%d\n", sum);
  exit(0);
}

int pinball(int x, int y, int dir, int life){
  int v, move[2];
  
  v = 0;
  while( life > 1 ){
    nextmove(x, y, dir, move);
    if( g[GAME][ move[0] ][ move[1] ] == 1 ){   
      life -= g[COST][ move[0] ][ move[1] ];
      v += g[VALUE][ move[0] ][ move[1] ];
      dir = chgdir(dir);
    }
    else{
      x = move[0];
      y = move[1];
    }
    
    life--;
  }/*while life > 1*/
  
  return v;
}

void nextmove(int x, int y, int dir, int *arr){
  arr[0] = x;
  arr[1] = y;
  
  switch (dir) {
    case RIGHT:
      arr[0]++;
      break;
    case UP:
      arr[1]++;
      break;
    case LEFT:
      arr[0]--;
      break;
    case DOWN:
      arr[1]--;
      break;
    default: break;
  }
}

int chgdir(int dir){
  if( dir == RIGHT )
    dir = DOWN;
  else
    dir--;
    
  return dir;
}

ACM: 111 – History Grading

2010-08-22T19:34:00.001+08:00

這一題即是稍做變化的Longest Increasing Subsequence (LIS)問題，但要注意的是input資料。input資料是Event的Order:

Event: 1 2 3 4 5 6 7 8 9 10
Order: 3 1 2 4 9 5 10 6 8 7

即是Event by Order是: 2, 3, 1, 4, 6, 8, 10, 9, 5, 7。學生的回答也需要做如此的調整，比對出來才是正確的解答。原本沒有搞清楚，就想不通為什麼sample output跟自己算的答案不一樣了！

REFERENCE

Longest Increasing Subsequence

CODE

#include <stdio.h>

#define MAX 20

int main(){
  int i, j, t;
  int n, c[MAX+1], r[MAX+1], lis[MAX+1], max;
  
  scanf("%d", &n);
  
  /*Read Correct Order*/
  for(i=1; i<=n; i++)
    scanf("%d", &c[i]);
    
  /*Read Student Response*/
  while( scanf("%d", &t) != EOF){
    r[t] = 1;
    max = lis[1] = 1;
    for(i=2; i<=n; i++){
      scanf("%d", &t);
      r[t] = i;
      lis[i] = 1;
    }
    
    for(i=2; i<=n; i++){
      for(j=1; j<i; j++)
        if( c[ r[i] ] > c[ r[j] ] )
          if( lis[i] < (lis[j] + 1) )
            lis[i] = lis[j] + 1;
      
      if( max < lis[i] )
        max = lis[i];
    }/*i*/
       
    printf("%d\n", max);
  }/*while*/

  exit(0);
}

ACM: 112 - Tree Summing

2010-08-22T19:19:00.001+08:00

這題要讀取以字串表現的binary tree，並找出是否有root-to-leaf path能產生指定的數字和。因為字串跟數字混在一起，如何處理字串可說是這題的罩門，但其實想清楚了這題S-expression的模式，字串處理起來就沒有想像中的複雜了。

因為原本卡在如何擷取字串，也是第一次寫bin tree的東西，所以寫出來很開心！再進了百大，超超興奮！

TIPS

1. 數字會有負數
2. 注意 0 () 的測資，output應該要是 no

CODE

#include <stdio.h>

int a, found;

int tree(int parent_sum);
int makenum(int *a, int n, int sign);

int main(){
  char c;
  
  while( scanf("%d", &a) != EOF ){
    while( (c = getchar()) !=EOF )
      if( c == '(' )
        break;
    
    found = 0;
    tree(0);
    if( found == 1 )
      printf("yes\n");
    else
      printf("no\n");
  }/*while*/
  
  exit(0);
}

/*return 0 if is empty node*/
int tree(int p){
  int sign, line[10], e, num;
  int flag, le, re;
  char c;
  
  flag = le = re = 1;
  sign = 1;
  e = num = 0;
  while( flag == 1 ){
    c = getchar();
    
    if( c == '-' )
      sign = -1;
    else if( c >= '0' && c <= '9' ){
      line[e] = c - '0';
      e++;
    }
    else if( c == '(' ){
      /*make number*/
      num = makenum(line, e, sign);
      
      /*left tree*/
      if ( tree( num+p ) == 0 )
        le = 0;

      /*read '('*/
      while( (c = getchar()) !=EOF )
        if( c == '(' )
          break;

      /*right tree*/
      if ( tree( num+p ) == 0 )
        re = 0;
    }
    else if( c == ')' )
      flag = 0;
    else ;
  }/*while flag is 1*/
  
  if( (le + re == 0) && ((num+p) == a) ){
    found = 1;
    return 1;
  }
  
  if( e == 0 )
    return 0;
    
  return 1;
}

int makenum(int *a, int n, int sign){
  int i, j, p, r;
  
  r = a[n-1];
  p = 1;
  for(i=0; i<(n-1); i++){
    for(j=1; j<=(n-i-1); j++)
      p *= 10;
    r += ( a[i] * p );
  }
  r *= sign;
  
  return r;
}

ACM 第一個10題

2010-08-20T17:24:00.000+08:00

寫到了第一個10題！目前暫缺還找不到WA原因的107，不然就有100 - 110連號了！一步一腳印覺得學了很多，Floyd-Warshall、Kadane’s Algorithm、Graham Scan、Number Theory… 很有趣，也有嚐到一點小小的甜頭，繼續加油加油，要看到第二個10題。

ACM: 110 - Meta-Loopless Sorts

2010-08-20T17:06:00.001+08:00

這題要寫出一個程式generate另一段程式碼。練習遞迴。Runtime 0.084，Ranking進入前100，超開心。

CODE

#include <stdio.h>

#define MAX 8

void showarr(int n, int *array);
void showspace(int sp);
void copyarr(int n, int *to, int *frm);
void insertarr(int n, int position, int end, int k, int *array);
void showmeta(int n, int pos, int *array);

int main(){
  int i, j;
  int m, n, a[MAX];
  
  scanf("%d", &m);
  
  for(i=0; i<m; i++){
    scanf("%d", &n);
    
    for(j=0; j<n; j++)
      a[j] = j;
    
    if( i > 0 )
      printf("\n");
        
    printf("program sort(input,output);\n");
    printf("var\n");
    showarr(n, a);
    printf(" : integer;\n");
    printf("begin\n");
    printf("  readln(");
    showarr(n, a);
    printf(");\n");
    
    if( n == 1 )
      printf("  writeln(a)\n");
    else
      showmeta(n, 1, a);
    printf("end.\n");
  }/*i: m inputs*/
  
  exit(0);
}

void showarr(int n, int *arr){
  int i;
  
  printf("%c", 'a'+arr[0]);
  for(i=1; i<n; i++)
    printf(",%c", 'a'+arr[i]);
}

void showspace(int sp){
  int i;
  
  for(i=1; i<=sp; i++)
    printf("  ");
}

void copyarr(int n, int *to, int *frm){
  int i;
  
  for(i=0; i<n; i++)
    to[i] = frm[i];
}

void insertarr(int n, int p, int e, int k, int *arr){
  int i;
  
  if( p == e )
    arr[p] = k;
  else{
    for(i=e; i>p; i--)
      arr[i] = arr[i-1];
    arr[p] = k;
  }
}

void showmeta(int n, int p, int *arr){
  int i, cpy[MAX];
  
  if( p == (n-1) ){
    for(i=p; i>=0; i--){
      copyarr(n, cpy, arr);
      insertarr(n, i, p, p, cpy);
      
      showspace(p);
      if( i == p )
        printf("if %c < %c then\n", 'a'+cpy[i-1], 'a'+p);
      else if( i == 0 )
        printf("else\n");
      else
        printf("else if %c < %c then\n", 'a'+cpy[i-1], 'a'+p);
      
      showspace(p+1);
      printf("writeln(");
      showarr(n, cpy);
      printf(")\n");
    }/*i*/
  }
  else{
    for(i=p; i>=0; i--){
      copyarr(n, cpy, arr);
      insertarr(n, i, p, p, cpy);
      
      showspace(p);
      if( i == p )
        printf("if %c < %c then\n", 'a'+cpy[i-1], 'a'+p);
      else if( i == 0 )
        printf("else\n");
      else
        printf("else if %c < %c then\n", 'a'+cpy[i-1], 'a'+p);
      
      showmeta(n, p+1, cpy);
    }/*i*/
  }
}

ACM: 109 – SCUD Buster

2010-08-19T18:50:00.000+08:00

這題寫出來超想放煙火慶祝的！學了Convex Hull、Graham Scan。生平第一次覺得外積是這麼有用、了不起兼神奇的發明(發現?)啊。只需要乘法，就可以找出兩個向量的角度關係，因此可以避免用到除法的機器浮點數問題，這實在是太神奇了。

一次AC，感動。不過是超嫩的Runtime 0.016，我確定單在sorting就有很大的進步空間。但能夠把一組一組零散的座標，讓電腦連成一個圖形，再算出面積，相當有成就感。

REFERENCES

Graham Scan
Computational Geometry (ppt)

CODE

#include <stdio.h>

#define MAX_KINGDOM 20
#define MAX_VERTEX 100

int k, g[MAX_KINGDOM][MAX_VERTEX][2], gn[MAX_KINGDOM];

int findaim(int x, int y);
int isinside(int kingdom, int x, int y);
float findarea(int kingdom);

int main(){
  int i, j, s, tmp, min;
  int v, mx, my, at;
  int vx[MAX_VERTEX][2], attack[MAX_KINGDOM];
  float tot;
  
  /*Kingdom data*/
  v = 0;
  k = -1;
  while( scanf("%d", &v)!=EOF && v!=-1 ){
    k++;
    
    for(i=0; i<v; i++)
      scanf("%d %d", &vx[i][0], &vx[i][1]);
    
    /*find lowest point; if more than one point are the lowest, find the most left one*/
    min = 0;
    for(i=1; i<v; i++){
      if( vx[i][1] < vx[min][1] )
        min = i;
      else if( vx[i][1] == vx[min][1] )
        if( vx[i][0] < vx[min][0] )
          min = i;
    }
    if( min != 0 ){
      tmp = vx[min][0];
      vx[min][0] = vx[0][0];
      vx[0][0] = tmp;
      
      tmp = vx[min][1];
      vx[min][1] = vx[0][1];
      vx[0][1] = tmp;
    }
    
    /*sort rest points by counter clockwise with outer product*/
    for(i=1; i<v; i++){
      min = i;
      for(j=(i+1); j<v; j++){
        tmp = ( (vx[min][0]-vx[0][0])*(vx[j][1]-vx[0][1]) ) - ( (vx[j][0]-vx[0][0])*(vx[min][1]-vx[0][1]) );
        if( tmp < 0 )
          min = j;
      }/*j*/
      if( min != i ){
        tmp = vx[min][0];
        vx[min][0] = vx[i][0];
        vx[i][0] = tmp;
        
        tmp = vx[min][1];
        vx[min][1] = vx[i][1];
        vx[i][1] = tmp;
      }
    }/*i*/
    
    /*Graham Scan*/
    for(i=0; i<3; i++){
      g[k][i][0] = vx[i][0];
      g[k][i][1] = vx[i][1];
    }
    s = 2; /*s: current stack*/
    for(i; i<v; i++){
      tmp = ( (g[k][s][0]-g[k][s-1][0])*(vx[i][1]-g[k][s-1][1]) ) - ( (vx[i][0]-g[k][s-1][0])*(g[k][s][1]-g[k][s-1][1]) );
      if( tmp > 0 ){
        s++;
        g[k][s][0] = vx[i][0];
        g[k][s][1] = vx[i][1];
      }
      else if( tmp == 0 ){
        g[k][s][0] = vx[i][0];
        g[k][s][1] = vx[i][1];
      }
      else{
        s--;
        i--;
      }
    }
    s++;
    g[k][s][0] = g[k][0][0];
    g[k][s][1] = g[k][0][1];
    gn[k] = s;
    
  }/*while kingdom data input*/
  
  /*Missile attacks*/
  while( scanf("%d %d", &mx, &my) != EOF ){
    at = findaim(mx, my);
    if( at != -1 )
      attack[at] = 1;
  }/*while missile attacks input*/
  
  /*Output*/
  tot = 0.0;
  for(i=0; i<=k; i++)
    if( attack[i] == 1 )
      tot += findarea(i);
  printf("%.2f\n", tot);
  
  exit(0);
}

int findaim(int x, int y){
  int i;
  
  for(i=0; i<=k; i++){
    if( isinside(i, x, y) == 1 )
      return i;
  }/*i: scan through all kingdoms*/

  return -1;
}

int isinside(int kd, int x, int y){
  int i, tmp;
  
  if( y < g[kd][0][1] )
    return 0;
    
  for(i=0; i<gn[kd]; i++){
    tmp = ( ( g[kd][i+1][0]-g[kd][i][0] )*( y-g[kd][i][1] ) ) - ( ( x-g[kd][i][0] )*( g[kd][i+1][1]-g[kd][i][1] ) );
    if( tmp < 0 )
      return 0;
  }
  return 1;
}

float findarea(int kd){
  int i;
  float tmp, sum;
  
  sum = 0.0;
  for(i=1; i<=gn[kd]; i++){
    tmp = ( (g[kd][i-1][0])*(g[kd][i][1]) )-( (g[kd][i][0])*(g[kd][i-1][1]) );
    tmp /= 2;
    sum += tmp;
  }
  
  return sum;
}

ACM: 108 - Maximum Sum

2010-08-18T15:48:00.001+08:00

這一題是給一個二維陣列，要找出有最大和的子陣列，傳回和的值。原本想不出更好的方法，只好用brute force搜尋所有子陣列，但預料之內的Time Limit Exceed(UVa好厲害啊)。查了資料，才知道解決之道在於 Kadane’s Algorithm。

Kadane’s Algorithm可以O(n)找到一維陣列的最大和子序列，Algorithmist上的pseudo code如下：

Kadane's Algorithm(arr[1..n])
begin
    (max, a, b) := (-INFINITY, 0, 0)
    curr := 0
    aa := 1
    for bb := 1 to n do
        curr := curr + arr[bb]
        if curr > max then
            (max, a, b) := (curr, aa, bb)
        endif

        if curr < 0 then
            curr := 0
            aa := bb + 1
        endif
    endfor

    return (max, a, b)
end

即是從陣列頭開始，不斷累加陣列元素值，同時不斷更新最大值，一旦累加和<0，就把累加變數歸零。因為一旦是負數，下一個元素值不管是正數或負數，都只會越加越小，所以不可能會是maximum了。如此，只需要讀過一次陣列就可以找到最大和子序列，真是神奇啊！

CODE

#include <stdio.h>

#define MAX 100

int main(){
  int i, j, k;
  int n, t[MAX][MAX], sum, max;
  
  scanf("%d", &n);
  for(i=0; i<n; i++)
    for(j=0; j<n; j++)
      scanf("%d", &t[i][j]);
  
  /*calculate vertical sum*/
  for(i=0; i<n; i++){
    for(j=1; j<n; j++){
      t[j][i] += t[j-1][i];
    }/*j: row*/
  }/*i: column*/
  
  max = t[0][0];
  /*find max sum*/
  for(i=0; i<n; i++){
    for(j=i; j<n; j++){
      sum = 0;
      for(k=0; k<n; k++){
        if( i==j || i==0 )
          sum += t[j][k];
        else
          sum += ( t[j][k] - t[i-1][k] );
        
        if( sum > max )
          max = sum;
        else if( sum < 0 )
          sum = 0;
      }
    }/*j: ending row*/
  }/*i: starting row*/
  
  printf("%d\n", max);
  exit(0);
}

ACM: 104 - Arbitrage

2010-08-17T21:29:00.000+08:00

這一題我原先使用了brute force找出所有的換匯途徑，再檢查是否獲利，但這樣會超過time limit，有效率的解法必須使用Floyd-Warshall演算法。參考了Mat所轉錄的文章，研究了一陣，才了解Floyd-Warshall演算法一層層找最佳中繼點，最後再重建路徑回去的方法！但想通了真覺得Floyd-Warshall很美妙呢！

這題可說是找一個weighted graph從一點開始再回到一點的最短路徑，例如(0,.., 0)，先找第一個最佳中繼點(0, k1, 0)，紀錄下這個k1後，再找第二層中繼點(k1, k2, 0)，再紀錄下k2然後繼續…。最後，再從最後kn中繼點，重建回k1，便可以重建(0, k1, k2, .., kn, 0)的完整路徑了。

在我的code裡面，我一找到獲利的路徑後就跳出floyd-warshall。跟這題奮鬥多天的結果是Runtime 0.044，Rank 88！開心！

CODE

#include <stdio.h>

#define MAX 20

double profit[MAX][MAX][MAX];
int n, st, path[MAX][MAX][MAX];

int fw(void);

int main(){
  int i, j, s;
  int final[MAX];
  
  while( scanf("%d", &n) != EOF ){
    /*initialize profit array*/
    for(s=0; s<n; s++){
      for(i=0; i<n; i++){
        for(j=0; j<n; j++){
          profit[s][i][j] = 0.0;
        }/*j*/
      }/*i*/
    }/*s*/
    
    /*read rates table*/
    for(i=0; i<n; i++){
      for(j=0; j<n; j++){
        if( i==j )
          profit[0][i][j] = 1.0;
        else
          scanf("%lf", &profit[0][i][j]);
        path[0][i][j] = i;
      }
    }
    
    /*Floyd-Warshall*/
    if( (s = fw()) > 0 ){
      /*Re-construct path*/
      final[0] = j = st;
      i = s;
      for(i; i>0; i--){
        final[i] = path[i][st][j];
        j = final[i];
      }
      
      for(i=0; i<=s; i++){
        printf("%d ", final[i]+1);
      }
      printf("%d\n", st+1);
    }
    else{
      printf("no arbitrage sequence exists\n");
    }
  }/*while input data*/
  
  exit(0);
}

/*Return step when arbitrage exists; Return 0 when no arbitrage exists*/
int fw(void){
  int i, j, k, p;
  int s;
  double tmp;
  
  for(s=1; s<n; s++){
    for(k=0; k<n; k++){
      for(i=0; i<n; i++){
        for(j=0; j<n; j++){
          tmp = profit[s-1][i][k] * profit[0][k][j];
          if( tmp > profit[s][i][j] ){
            profit[s][i][j] = tmp;
            path[s][i][j] = k;
          }
        }/*j*/
      }/*i*/
    }/*k: intermediate node*/
    
    
    /*check if arbitrage exists*/
    for(p=0; p<n; p++){
      if( profit[s][p][p] > 1.01 ){
        st = p;
        return s;
      }
    }
  }/*s: step*/
  
  return 0;
}

106 - Fermat vs. Pythagoras

2010-08-16T17:57:00.001+08:00

106 – Fermat vs. Pythagoras

這一題是給一個數字N：
1. 找出所有小於等於N的正整數中，互質的畢式組數(如: (3, 4, 5)是一組互質的畢式組數)數量。
2. 找出所有小於等於N的正整數中，不能構成畢式組數(不需是互質的畢式組數)的數字數量。

乍看之下只要用brute force找出所有的畢式數對即可，但由於N最大值是1,000,000，光要建立小於1,000,000的質數表就已經超過3秒鐘的Time Limit，所以一定要找其他方法。

參考Algorithmist，才發現使用畢式定理的通解，處理時間會大大的縮短。

X^2 + Y^2 = Z^2
( r^2 - s^2 )^2 + ( 2rs )^2 = ( r^2 + s^2 )^2

由於Z=(r^2+s^2)，要找出 Z<N 即是 (r^2+s^2)<N，因此r, s < N^(1/2)，搜尋數量縮減到根號N，也就是最大1000！

而互質且一奇一偶的(r, s)，可以產生所有互質的畢式組數。在乘上倍數後便可以找出其他非互質的畢式組數了。

TIPS

記錄數字是否為畢式組數的陣列要用char型別，int型別無法開到1,000,000

CODE

#include <stdio.h>

int p, prime[200];

void findprime(void);
int rp(int a, int b);

int main(){
  int i, j;
  int n, r, s, rsq, ssq, rpt;
  char num[1000002]="";
  
  /*Find all prime numbers between 1 and 1000*/
  findprime();
  
  while( scanf("%d", &n) != EOF ){
    rpt = 0;
    
    for(r=2; (rsq = r*r)<n; r++){
      for(s=1; s<r && (rsq+(ssq = s*s)<=n); s++){
        if( ((r%2 == 1) ^ (s%2 == 1)) && (rp(r,s) == 1) ){
          rpt++;
          
          /*time the triple pair*/
          for(i=1; (i*(rsq+ssq))<=n; i++)
            num[ i*(rsq - ssq) ] = num[ i*(2*r*s) ] = num[ i*(rsq + ssq) ] = 1;
        }/*(r, s) pair can generate relatively prime triple*/
      }/*s*/
    }/*r*/
    
    printf("%d ", rpt);
    j = 0;
    for(i=1; i<=n; i++){
      if( num[i] == 1 )
        num[i] = 0;
      else
        j++;
    }
    printf("%d\n", j);
  }/*while input data*/

  exit(0);
}

void findprime(void){
  int i, j, tmp[1001];
  
  for(i=2; i<1001; i++)
    tmp[i] = 1;
  
  p = 0;
  for(i=2; i<1001; i++){
    if( tmp[i] == 1 ){
      prime[p] = i;
      p++;
      
      for(j=(i+i); j<1001; j+=i)
        tmp[j] = 0;
    }
  }
}

int rp(int a, int b){
  int i;
  
  for(i=0; i<p && prime[i]<a ; i++)
    if( (a % prime[i] == 0) && (b % prime[i] == 0) )
      return 0;
  
  return 1;
}

ACM

2010-08-16T17:12:00.000+08:00

從頭開始一題一題寫，目前為止11天寫了7題，很好，加油加油加油！

石田同學

2010-08-01T22:35:00.001+08:00

我們這一家的石田同學，我行我素地太可愛了！冷面笑匠一流角色，但她自己卻不覺得有什麼好笑的，哈哈。以下幾集有石田：

『不可思議的孩子』
『石田的通心粉』
『石田不說謊』

Lion Army: Battle To Survive

2010-06-30T21:25:00.003+08:00

前個星期在Nat Geo Wild看了"Lion Army: Battle To Survive"(片名譯作：獅子大軍)，看了真覺得獅子好有王者之風呢！影片最讓我印象深刻的有三個地方

1. 獅群狩獵原來有“陣式”的，不是看到獵物就撲出去那麼簡單。年輕獅子負責在幾個點埋伏、甚至阻擋獵物可能去路，而領頭的母獅在佈局完成後伺機發動出擊！而獵物如鹿、斑馬、長頸鹿等也不斷在留意是否有獵食者在附近，不會傻傻地等自己落入陷阱。

2. 獅群是由母獅帶領幼獅及年輕的獅子組成，公獅會在離獅群一段距離的範圍內巡邏保護獅群。片中有一段由於年輕獅子狩獵經驗不足，獅群五天沒有吃東西了，那日夜晚，獅群集體發出一種悲戚的聲音。在這之後，這兩頭外圍公獅竟在夜幕中緩緩出現！兩頭公獅英姿煥發、睥睨天下般地走來，檢視獅群，原本在打鬧的年輕獅子在公獅駕臨後竟不敢再玩了！隔天公獅帶領狩獵，並擔任咬住獵物頭的重要位置，大家都有飯吃，公獅實在Man爆！

3. 新生獅子太可愛了，跟母獅玩時竟是四腳朝天的！另一個驚訝在於，獅群裡的年輕母獅竟會用一隻前肢放在新生獅背上表示關心！但小獅並不領情，令我想到幼童時最不喜歡被親戚捏臉頰之類的，哈哈。

Youtube上有這影片，還是High Definition的！

Part 1

Part 2

Part 3

Part 4

Part 5

Part 6

周杰倫 - 好久不見

2010-06-05T21:27:00.004+08:00

周杰倫這張新專輯《跨時代》裡，我喜歡的兩首是＜好久不見＞和＜自導自演＞，這篇先寫前者。＜好久不見＞雖然講的是要女朋友回到他身邊，但不是苦情一路的，反而唱得溫暖到甜甜的。MV是2010台北花博的推廣片，也是甜到看著不自覺露出微笑呢。曲子間中用台語分飾主角的朋友蠻有趣的，似乎這張專輯加入了比較多台語。

好久不見
作詞：周杰倫
作曲：周杰倫
編曲：蔡庭貴
好久不見你還好嗎你的小狗長大了嗎
我的圍巾還圍著嗎我的相片都丟了吧
我剪不到後面頭髮這個藉口還不錯吧(哎喲不錯)
一把剪刀一堆廢話還不是想求求你回來吧
麥擱一個人咧生氣乎伊煩惱乎伊操心
雖然不關我ㄟ代誌誰叫他是我ㄟ兄弟耶
攏這麼久就唰唰去想想秋天就馬過去耶
冬天來臨他會怕冷你不回來甘講要我抱伊按呢甘好
是我不好我沒有緊緊抱住你你說淚留著很危險
如果等雨一起(等雨一起) 流下不讓同情發現
我對天空這個那個流星大喊後會不會有奇蹟
就算做朋友也沒關係為你改變了自己都不認識自己
不是我跑去了整形只是我拿出真心
開一瓶這個那個香檳去我的Mr.J餐廳
點蠟燭順便吃個甜品慶祝你打死不連絡的毅力
冷戰早已經不流行趕快回來到我身邊
歌詞轉載自：Mojim歌詞網

list: 2010年聽的專輯

2010-06-05T20:45:00.003+08:00

last update: 5 Jun 2010

Jun
＊＊＊＊+	周杰倫 - 跨時代

Feb
＊＊＊＊＊	World End’s Girlfriend – Hurt Break Wonderland
＊＊	楊丞琳 - 雨愛
＊＊+	謝安琪 - Binary

Jan
＊＊＊＊	徐佳瑩 – LaLa首張創作專輯
＊＊＊	中島美嘉 – No More Rules
＊＊＊	中島美嘉 – Over Load

Game, set, match, Soderling

2010-06-05T03:17:00.000+08:00

Soderling played a tough match against No.15 seed T. Berdych at Semifinal today. The match go into the 5th set. And not before the last 3 games did Sod seem to have an edge. After 3 hours and 26 mins from the start of the match, the first and the only match point finally came for Sod. Congrats Sod for achieving his second ticket to Roland Garros finals.

Further: As it happened: Soderling v Berdych

Le sod

2010-06-02T01:53:00.000+08:00

Robin Soderling defeated No.1 ranking Roger Federer at 1 June 3-6, 6-3, 7-5, 6-4, ending his 12-match loosing streak to Fed. It was a good match. Sod played aggressively yet cautious of any faults. In the 2.5 hours match, Sod performed 14 aces, 49 winners, 6 double faults versus Fed's 12 aces, 40 winners, 2 double faults. Comparing to last year, Soderling is improving amazingly fast I think. Keep going, le sod!

Further: Soderling Stuns Federer For Semi-final Berth; Battle For No.1 Intensifies

The copyright of above image belongs to Roland Garros

cute!!!

2010-05-25T09:32:00.000+08:00

Learned the Verreaux's sifaka from this month's scientific american. It's a kind of sifaka (狐猴) living in Madagascar. Can't believe there's such a cute and interesting creature in the world!

Now

2010-05-19T07:37:00.000+08:00

It's raining and thundering in Hong Kong now. Although its 3 pm, the outside just dark as 3 am.

林峰 - 忘記傷害

2010-03-29T04:25:00.000+08:00

律政新人王的主題曲，初初聽到時並不覺得怎樣，但就越聽越耐聽，我想林夕的詞功不可沒。

忘記傷害 - 林峰(「律政新人王」主題曲)

曲：馮翰銘　詞：林夕

當　這感覺未發生　不知道你光臨
我大概還可繼續散心

無奈我的心　不經意著了燈
為得不到的吸引　令我不糾纏亦不忍

當　他手放在你身
才想到我是好友永遠沒權利去傷感

＃忘記受過傷害　施捨最假的愛
也會令我肯相信這段感情避不開

忘記如何忍耐
但期待一夜之間醒過來
我和你便已如戀人熱愛＃

想　想一世待你好　不需要有出路
那是我唯一快樂

其實期望未算高　不擁抱便跌倒
付出的都不苦惱　被愛的當然未知道

好　即使我未夠好連哭一聲都不配你便提示我怎做

ｒｅｐｅａｔ　＃

My Song Is Love Unknown by Wells Cathedral Choir

2010-03-29T01:17:00.000+08:00

My song is love unknown,
My Saviour’s love to me;
Love to the loveless shown,
That they might lovely be.
O who am I, that for my sake
My Lord should take frail flesh and die?

He came from His blest throne
Salvation to bestow;
But men made strange, and none
The longed-for Christ would know:
But O! my Friend, my Friend indeed,
Who at my need His life did spend.

Sometimes they strew His way,
And His sweet praises sing;
Resounding all the day
Hosannas to their King:
Then “Crucify!” is all their breath,
And for His death they thirst and cry.

Why, what hath my Lord done?
What makes this rage and spite?
He made the lame to run,
He gave the blind their sight,
Sweet injuries! Yet they at these
Themselves displease, and ’gainst Him rise.

They rise and needs will have
My dear Lord made away;
A murderer they save,
The Prince of life they slay,
Yet cheerful He to suffering goes,
That He His foes from thence might free.

In life, no house, no home
My Lord on earth might have;
In death no friendly tomb
But what a stranger gave.
What may I say? Heav’n was His home;
But mine the tomb wherein He lay.

Here might I stay and sing,
No story so divine;
Never was love, dear King!
Never was grief like Thine.
This is my Friend, in Whose sweet praise
I all my days could gladly spend.

Lyric source: Wikipedia

6分の1の夢旅人（「水曜どうでしょう」主題曲）

2010-03-26T06:36:00.000+08:00

曲名：6分の1の夢旅人
演唱：樋口了一

【日文歌詞】

まわるよ、まわる、地球はまわる
何もなかった頃から同じように
いつもいつでも、飛び出せるように
ダイスのように転がっていたいから

泣きたくなるような時も
君に逢いに行きたくなっても
強がるだけ
今は何もわからない

世界中を僕らの涙で埋めつくして
やりきれないこんな思いが今日の雨を降らせても
新しいこの朝がいつものように始まる
そんな風にそんな風に
僕は生きたいんだ、生きていきたいんだ

一人きりではできないことも
タフな笑顔の仲間となら乗り切れる
たどり着いたらそこはスタート
ゴールを決める余裕なんて今はない

誰かを愛することが
何かを信じ続けることが
何より今、この体を支えてくれるんだ

世界中を僕らの涙で埋めつくして
疲れきった足元から全て凍り尽くしても
いつの日にかきっと南風が歌い出す
そんな風にそんな風に
僕は笑いたいんだ笑っていたいんだ

【中文翻譯】

環繞、環繞、環繞地球
就像什麼都沒發生過
一直一直、像是飛出去一樣
因為我想要像骰子一樣滾動

哭泣的時候
害怕走向你的時候
只需要勇敢一點
現在我什麼也不知道

讓這個世界充滿我流淚的痕跡
即使今天的大雨讓我覺得失去力量
還是要像新的早晨般重新開始
就是這樣就是這樣
我想要生活下去想要生活下去

獨自一個人做不到的事
是在同伴露出堅強微笑時跟他分享心情
從遍嘗人生百味的地方啟程
而終點現在沒有多餘的時間決定

相信我能愛什麼人
帶著我所相信的什麼繼續走下去
最重要的是我願意站在我自己這邊

讓這個世界充滿我流淚的痕跡
即使疲憊的雙腳又在嚴寒中凍僵透心寒意讓我不知所措
溫暖白日一定會在什麼時候來到南風之歌便會飄揚
就是這樣就是這樣
我想要笑出來想要笑出來

list: 口袋歌單

2010-03-17T11:40:00.000+08:00

需要力量的時候...

咖啡王子一號店 - La la la, It's Love !

Humming Urban Stereo (feat.Yozoh) - Coffee Hanjan Eottae?

Casker - Mocha

哆啦A夢 - 夢をかなえてドラえもん

太鼓達人wii - どん子のファーストデート

中島美嘉 - 雪之華

黃靖倫 - 傻裡傻氣

陳嘉唯 - 幸福導航

張韶涵 - Journey

張韶涵 - 手心的太陽

張韶涵 - 遺失的美好

徐佳瑩 - 出口

City Quiz

2010-02-28T04:31:00.000+08:00

Taken "what's your city" quiz from here and it said that the city for me is Buenos Aires! After playing the game Chocolatier 2, Buenos Aires is linked with Oranges in my mind...

Your City is Buenos Aires

You are cultured, sophisticated, and quite old fashioned. You believe traditions are important, but you are still quite vibrant.
People don't know you well at all, and if they do, they totally misunderstand what you are all about.

You are more interesting and more intelligent than anyone gives you credit for. You are a bit of a hidden treasure.
You are creative, ambitious, beautiful, and fun. You may have a rough past, but you are always getting better.

徐佳瑩 - P.S我愛你

2010-02-15T05:57:00.000+08:00

一年前的節目了，今天才在youtube上偶然聽到，真是很喜歡lala溫暖的聲音。

P.S.我愛你 (原唱：A-Lin)

詞：鄔裕康曲：劉勇志

我想要成為你的眼
把最美的風景收進你的心中

我想要成為你的手
好讓我從現在到以後
佔有你溫柔一刻不放過

恨不得把明天沒收
讓你永遠不會變動
專注的愛著我

我愛你沒有保留
我愛你就到最後
有些人值得等候
有些悲傷值得忍受

我愛你不是衝動
生命盡頭反正一場空
只要你記得我們那麼愛過

我要替你收集笑容
怕未來快樂變得貴重
要是少了我你有多寂寞

恨不得把明天沒收
讓你永遠不會變動
專注的愛著我

我愛你沒有保留
我愛你就到最後
有些人值得等候
有些悲傷值得忍受

我愛你不是衝動
生命盡頭反正一場空
只要你記得我們那麼愛過

太陽不會放棄天空
哪怕你不再屬於我
我會在不同的窗口給你擁抱

我愛你沒有保留
我愛你就到最後
有些人值得等候
有些悲傷值得忍受

我愛你不是衝動
生命盡頭反正一場空
只要你記得我們那麼愛過

我忘不掉你第一次吻我

歌詞轉載自：Mojim

陳嘉唯 - 幸福導航

2010-02-15T05:30:00.000+08:00

作詞：徐世珍
作曲：梁偉豐
編曲：洪信傑
製作：薛忠銘

＊天空是灰色的可是有陽光
　幸福是一定的很遠又怎樣
　快樂忘了出場天使折了翅膀
　我還是要希望

　眼淚是溫熱的跟擁抱一樣
　我不會放棄的雖然會受傷
　通往你的路上不會隨風飄蕩
　想你我的心就有重量＊

＃我跟著幸福導航奔向有你的地方
　不管距離夢想起起伏伏多漫長
　當時間逼著我害怕　我卻偏偏不害怕
　無路可退就會堅強

　放手讓幸福導航忘了所有的悲傷
　因為奇蹟會是堅持的人的獎賞
　當我終於學會了飛　能夠擁有全世界
　我想要的只有一樣　在你身旁＃

REPEAT＊＃＃

時時刻刻　在你身旁

歌詞轉載自：Mojim

J. P. Chenet Colombard-Chardonnay

2010-02-15T01:17:00.000+08:00

First time for white wine. Nice color and scent, green apple flavor, a bit salty. Good balance of sweet and sour.

More: Lion Distributors, WBS, snooth

中島美嘉 - 雪の華(雪之華)

2010-02-14T09:51:00.000+08:00

Beautiful voice, beautiful lyrics. Heart-braking and brave.

中島美嘉 - 雪の華

のびた人陰(かげ)を　舗道に並べ
夕闇のなかをキミと歩いてる
手を繋いでいつまでもずっと
そばにいれたなら泣けちゃうくらい

風が冷たくなって
冬の匂いがした
そろそろこの街に
キミと近付ける季節がくる

今年　最初の雪の華を　２人寄り添って
眺めているこの時間(とき)に
シアワセがあふれだす
甘えとか弱さじゃない
ただ　キミを愛してる　心からそう思った

キミがいるとどんなことでも
乗りきれるような気持ちになってる
こんな日々がいつまでもきっと　続いてくことを祈っているよ

風が窓を揺らした　夜は揺り起こして
どんな悲しいことも　ボクが笑顔へと変えてあげる

舞い落ちてきた雪の華が　窓の外ずっと
降りやむことを知らずに　ボクらの街を染める
誰かのために何かを　したいと思えるのが　愛ということを知った

もし　キミを失ったとしたなら　星になってキミを照らすだろう
笑顔も　涙に濡れてる夜も　いつもいつでもそばにいるよ

今年　最初の雪の華を　２人寄り添って
眺めているこの時間(とき)　シアワセがあふれだす
甘えとか弱さじゃない　ただ　キミとずっと
このまま一緒にいたい　素直にそう思える

この街に降り積もってく　真っ白な雪の華
２人の胸にそっと想い出を描くよ

不斷延伸的影子在紅磚道上並列
在深夜與你並肩走著
永遠緊緊牽著手只要能在你身旁
我就感動得快要哭泣

風兒變得寒冷有了冬天的味道
這條街也即將到了能和你接近的季節來臨

今年最初的雪花向我倆靠近
在眺望著的這個時間裡
充滿了幸福的喜悅沒有撒嬌和脆弱
只是愛你打從心底愛你

只要有你在無論發生什麼
都會有可以克服的心情
我祈禱著這樣的日子一定會直到永遠

風兒吹得窗搖把夜晚搖醒
無論多麼悲傷的事我用笑容為你改變

雪花飛舞飄落在窗外一定
不知何時雪已停把我們的街道染色
想為某人做些什麼事原來這就是愛

如果我失去了你我會變成星星照耀你
微笑或被淚水沾濕的夜晚我會永遠在你身旁

今年最初的雪花向我倆靠近
再眺望著的這個時間裡充滿了幸福的喜悅
沒有撒嬌和脆弱只是想永遠地
就這麼一直一起我真心地這麼想

在這條街上堆積的純白雪花
悄悄地在我倆胸口畫上回憶
從今而後也要永遠和你在一起

（歌詞轉錄自：狂人夢囈）

Hayley Westenra (海莉) English version:

Together hand in hand we walked through evening gloom
Long shadows on the pavement, cast from the sunset sky
If only this would last until the end of time
And if this is forever I swear that I could cry

The northern wind starts to blow
And the smell of winter’s in the air
As we take each step upon the ground
The season of love grows near

We could share the very first snowflowers of the year
In your arms where I belong
Watch as the city turns from grey to white
The day turns into night
Love that floats like wayward clouds, that’s not what we’re about
Sure and strong is my love for you
And it comes from the bottom of my heart

With you by my side, to catch me when I fall
I can cast my fears aside; feel twice as tall
If only this would last, this smile upon my face
And if this is forever, you’re my saving grace

The nights were so cold without you
And the days were always short on light
Now a fire’s warming me through
And suddenly this upturned world is feeling right
Yuki no Hana (Snow Flower - English Version) lyrics on

We could share the very first snowflowers of the year
In your arms where I belong
Watch as the city turns from grey to white
The day turns into night
Love that floats like wayward clouds, that’s not what we’re about
Sure and strong is my love for you
And it comes from the bottom of my heart

If there comes a time when you have lost your way
I’ll turn myself into a star to guide you through
If ever you find tears upon your face
I will be there, always be there for you

We could share the very first snowflowers of the year
In your arms where I belong
Watch as the city turns from grey to white
The day turns into night
Love that floats like wayward clouds, that’s not what we’re about
Sure and strong is my love for you
The city turns from grey to white
The day turns into night

We could share the very first snowflowers of the year
In your arms where I belong

Cold winds from the North blow
The sky casts its last glow
But you and I are standing strong

（歌詞轉錄自：yeucahat）

國語版：蔡淳佳《對不起，我愛你》

你空出一雙手　穿過黑夜握住我
兩個人的手心裡有一整片寬闊的天空
誰都沒有開口　星星也忘了閃爍
有你陪著我就可以走到天涯的盡頭

＃那時候　還記得那時候　從手心傳過來的溫柔
　如果說　只能活這一天　曾經與你深深相愛　我已沒有遺憾

＊我用回憶溫暖了想你的每一刻　不讓你離我太遙遠
　走在這個適合擁抱的季節　愛在心裡所以我不可憐

※回憶溫暖了想你的每一刻
　緊緊抱著你說過的誓言
　等待著我們說好的永遠

並肩的兩個人　在銀白色的街頭
印下的腳印還一直　在我的心裡往前走
從愛的第一秒　直到最後一分鐘

Repeat ＃,＊,※

當走過的路流過的淚　被落葉掩沒
是你的溫柔讓我的心重新活過來
就算相愛的人無論如何暫時要離開
別問未來怎麼辦　我只需要等待

Repeat ＊,＊

回憶溫暖了想你的每一刻　把最後的合照擺在窗前
想像著你也許跟我一樣　正在倒數再見的時間
等著給我說好的永遠

（歌詞轉錄自：華人歌詞網）

Logorama

2010-02-12T08:33:00.000+08:00

在Gizmodo看到這個提名2010奧斯卡Best Animated Short的短片，麥當勞叔叔果然怎麼看都是邪惡怪叔叔。看了這個影片後，也覺得如果有個"7-11rama"可能也相當可觀，應該會有open小將抓狂或亂殺人的場面。