UVa Online Judge -- 100 Submission

不是解題數。裡面寫超多 Ad Hoc 無腦簡單題，熟悉一下寫程式的感覺。

旭軟獲利股利雙登頂 今股價跳空漲停開出創2年新高

旭軟獲利股利雙登頂 今股價跳空漲停開出創2年新高

2013/05/02 09:35 鉅亨網 記者張欽發 台北

上櫃軟板廠旭軟電子 (3390) 2012年財報有佳績，全年稅後盈餘2.86億元，每股稅後盈餘達5.15元，30日經董事會通過對去年股利配發4元的現金股息，包括旭軟電子的去年盈餘及股利發放額度都創下歷史新高；而旭軟股價今天受此激勵也以跳空漲停47.9元開出，創24個月來新高。

在觸控產品、手持式產品市場大量推出新產品上市的挹注之下，旭軟電子在對新產品、新客戶的交貨量挺升之下，旭軟電子2013年第1季的業績表現亮麗，其營收3.27億元達到去年第4季旺季的水準；同時，旭軟董事會通過第1季財報稅後盈餘8956萬元，每股稅後盈餘也達1.47元。

旭軟電子董事會先前敲定6月14日召開股東會，而對於去年的盈餘分派，則在30日董事會敲定配發4元現金，以今天旭軟的開盤價47.9元計算，其配發4元的現金股息現金殖利率高達8.35%。

旭軟電子在對新產品、新客戶的交貨量自去年以來挺升，而旭軟電子2013年第1季的業績表現亮麗，其營收3.27億元達到去年第4季旺季的水準；旭軟2013年第1季財報稅後盈餘8956萬元，每股稅後盈餘也達1.47元。

而台郡科技 (6269) 2013年第1季每股稅後盈餘為2.02元。

Comments: 繼續觀察。

DFS 應用 -- 找 bipartite graph

Example: UVa 10004

完全沒有其他變化。



Source code (AC):
https://bitbucket.org/Menggen/uva/src/17251700c3506f8b3dbb52e9af85940698f5b297/UVa/acm_10004.cc?at=master

TopCoder 類似題 Marketing: https://bitbucket.org/Menggen/topcoder/src/e6eb73ba1909b6efb9fcbbe10e5de944479bf8af/TopCoder/GraphPractice/Marketing.cs?at=master

整數集合找出最長連續數列長度

例子：

(1) { 1, 2, 3, 4 } returns 4

(2) { 4, 5, 6, 10, 11 } returns 3

(3) { 1, 2, 4, 5, 7, 8 } returns 2



我的想法來自於 DFS 的經典題目：grafixMask



這是演算法教學系列文章：

http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=alg_index

裡面有一篇不錯，雖然大學有教 graph algorithms，可惜當時沒有熱情，

我說的就是這篇：

Introduction to Graphs and Their Data Structures

((現在有熱情的理由也是很瞎，Candy Crush Saga 激起我解決問題的衝動，

數學問題太難，演算法問題可難可易，很適合我解決問題))

總之以 C# 的語言來說，

先把 int[] input 丟到 HashSet<int> numberSet = new HashSet<int>(input)，

O(n)。

接著 iterate hash set，把每個整數點 p 當做一個 Node，

Edge 就是 p-1 或是 p+1，這個查詢只要 O(1)，因此我們可以建出一個 graph，

space O(n)

((上班說錯更正一下，直接用 linked list 實做 graph 就可以了))

接著 grafixMask 技巧用下去，直接結束。

time complexity O(n)

space complexity O(n)

不過這比起 Candy Crush Saga Level 361，簡直小巫見大巫，

這關有夠機車的。

Dijkstra's algorithm 及其他

1. Breadth-first Search ((BFS)) 加強版，原本的 queue 要改成 priority queue ((也就是 heap，heap 有分 min heap 或 max heap))


2. 問題的關鍵都是「如何抽象化成數學模型」，哪些是點 ((狀態，哪些 factors 該計入狀態？))，哪些是邊 ((有向或是無向，數字權重代表的意義是甚麼？))


3. 如果 N 不大，可以考慮用 Floyd-Warshall Algorithm，使用前思考一下為什麼使用這個演算法？這是對的演算法嗎？如何保證答案就是演算法算出來的答案？


4. DFS 與 BFS 是否可以互相取代？

Candy Crush Saga Level 361 -- 果子不會對齊

扭蛋機只是幌子，果子不一定會從扭蛋機出來，

當果子從最邊邊下來時，雖然可以移到旁邊但很辛苦根本就是整人。

多玩幾次，總有機會好運氣，

基本就是狂刷下面，拿條紋＋包裝狂刷，

很多關都是如此技巧 ((例如今天示範的181))，

條紋＋彩色糖適合大範圍消果凍亂消，但這關要刷四個綠色箭頭孔道。



這關是新單元最難的一關。

同場加映 Level 365，這關也很難，剛好最後一步過關，只要消掉綠色就可以了，

至少有四種移法，這種關就要盡量把糖果滅掉，

不管是怎樣的糖果，只要消的越多，

新出來的某色糖果也越多 ((當然包括藍色與綠色))，

倒數十步再來專心蒐集某種顏色糖果，

這是這類型關卡的要點。

Candy Crush Saga Level 181 -- 中文介面幫解

實驗證明，包裝＋條紋消的效果最棒，

彩色＋條紋的方向太難掌握，不過如果有現成的可以消，

當然先消先贏。