[FGISC。Nanro] 未來開端

應學妹們正要複習陣列與開始運用字串
整理的講義～
沒有寫太多太深的東西，但是基本的東西都在了
應該是很好的參考資料:)
(而且是彩色編排的版本唷:P)

適合服用：[初階]→[入門]→[進階]
感謝sa提供初始清單～

這題運用到拓璞排序(Topological Sort)

基本上，拓璞排序使用的是有向圖 (也就是圖的每個邊都是有方向性的)

像是這樣子的一個有向圖：
        A → B → C
                     ↗
                 D

Binary Search Tree的第一題實做
//給好孩子的註解
//如果你還沒有學過樹(Tree)、樹的拜訪(traversal)、二元樹(Binary Search Tree)
//那麼你可以先去學完這些東西，再來看這題
//這是前輩良心的建議，加油′▽`)

可以練指標的好題(拇指)
//我用了一卡車(指標陣列都出來了v(￣︶￣)y)

＊何謂篩法？
    我們這裡所說的篩法，是Eratosthenes篩法(Sieve)。它是一種由古希臘數學家
    Eratosthenes提出的，主要的功能是用來找出不大於n的所有質數。

＊篩法的原理
    篩法的主要原理就是，把不大於n的所有質數的倍數都砍掉，沒被砍到的就是質數。

＊篩法的實作
    一般而言，我們會開一個夠大的陣列(到n)，紀錄相對索引值是否已經被砍掉。
    之後，我們開始去窮舉每一個數，如果發現他是質數，便將其倍數通通砍掉，並記錄下
    來，如果不是就跳過。這樣，便能得到不大於n的所有質數了。
    順帶一提，我們通常會把2當成特例，然後從3開始砍。

＊較有效率的篩法…
    1. 假設現有一個質數p，那我們可以從p*p這個數開始砍起。
       因為，若現有一個數q並非質數，則知道必有一個小於等於sqrt(q)的因數
       若一數q小於p*p會被p砍到，則必有一個質因數小於p。換言之，也就是q/p<p且q/p
       也為某個小於p的質數的倍數。
    2. 跳過偶數
       把2作為特殊處理之後，剩下的偶數便都是合數了。
       在砍質數倍數時，記得每次加兩倍，跳過偶數倍。
    3. 有要砍東西的質數最高到sqrt(n)，故sqrt(n)以上的質數另外處理，不用砍，只需
       記錄即可。

＊試做題
    ACM Q10791
    是一題質數with greedy的題目。
    細節有機會再補。

<感謝sa幫忙提點、校正。>
＊什麼是Heap？

Heap呢，有些地方翻做「錐型結構」或「錐疊」，電腦辭典譯作「堆積」，聽起來跟堆疊有點像，而且也可以用陣列來實做，但是對heap來說，他是一種樹狀的結構(且必須是完整二元樹)，而不是堆疊那樣純粹的線性結構。

而基本上heap分成兩種，一種是min-heap，另一種即是max-heap而他的特色，便是「任一節點，其值恆小/大於子節點」，且如此一來，root永遠是所有之中最小/最大的一個。
 (下面我們用min-heap當做講解範例)

(中譯by sa072686)
Making the Grade

做分數

185 Toman Numerals

        早期羅馬人使用的最原始的書寫數字非常的簡單但是卻很麻煩。許多字母被用來代表一些重要的數字，且這些字母被綁在一起時可以代表另外一個數字(這些綁在一起的字母，其值是從左至右單純地遞減)。他們用的字母和代表的數值列在下表：

                                        I       1                V     5

                                        X     10              L      50

                                        C     100            D     500

                                        M     1000                        

Q10668:Expanding Rods

　　當一根長度為L的細竿子被加熱了n度，它會膨脹到一個新的長度L’=(1+n*C)*L，其中C是竿子材質的膨脹係數。

　　當細竿子被放在兩個堅固的牆之間被加熱時，它會膨脹而變成圓形的一部分，原始的竿子則會成為一段弦。

　　你的任務是去計算弧跟弦的中心點之間的距離。

input

　　輸入包含多筆測資。每一行測資包含了三個非負的數值：竿子的初始長度、變化的溫度、以及膨脹係數。輸入的數值保證不會膨脹到大於原來的1.5倍。最後一行包括了三個負數，且這筆測資不需要被處理。

Output

　　對於每一筆輸入，請輸出弧跟弦中心點之間的距離(精確度到小數點後三位)

Sample input

　　1000 100 0.0001

　　15000 10 0.00006

　　10 0 0.001

　　-1 -1 -1

Output for sample input

　　61.329

　　225.020

　　0.000