TopCoder

Thumb p
lawfung
In every morning , you can sleep with your dream or wake up to chase it .

User's AC Ratio

90.9% (10/11)

Submission's AC Ratio

45.9% (17/37)

Tags

Description

在犯罪行動越來越科技化的現代,就算是防護得很嚴謹的東西,仍然有被設備較好、頭腦較清楚,或者是擔任某電影主角(?)的人給破解並偷竊得逞。因此,從小展覽館到大型博物館的管理人,無不希望能有一套新的設施能有效抵制這種偷盜的行動,然而,大家所常聽到的紅外線感應器、重量偵測器等等仍然有辦法破解,例如某電影的主角就常常可以輕鬆用煙霧加上特製眼鏡還有其身手輕鬆得逞,而重量偵測的部分則可以用與原物品同樣重量的石塊等代替來騙過機器,但是,之所以會源源不絕的有人想動這種歪腦筋,根本的原因還是因為大部分的人都認為「就算被發現,只要溜得快就好了啊!」因此,不斷有人抱著試試看不會怎麼樣的心態來偷竊這些珍寶,讓各管理人十分傷腦筋。

因此,身為高級防盜系統的研發商,你看準了這個商機,於是,你研發出了一種雷射偵測網,與以往的紅外線不同,當偷盜者被「掃到」時,不僅僅只是警鈴大作,而是直接以高能的雷射光束掃斷偷盜者的身體(好可怕啊..),借此讓所有的偷盜者卻步!

現在,有一個大型博物館想跟你訂做一套這樣的設備,但是首先,必須依照各項物品的大小長寬等等的需求,來為它們「量身訂做」專門的防護網,所以你設計了三種模式給使用者來選擇:各種防護網都是由 n (3<=n<=3*106) 個「雷射發射器」所圍成的正 n 邊形構成的,而可以支援的雷射網形狀分別是 1.「銳角三角形」的偵測網 (如下圖的藍色雷射),此種形狀可以使用在長寬差不多的物體;2.「直角三角形」的偵測網(如下圖的綠色雷射),這種形狀是為了擺設在牆角的展覽品設計的,直角的形狀可以完美的配合牆角的轉折;3.「鈍角三角形」的偵測網(如下圖的紅色雷射),這種形狀則是為了細長的展覽品所設計的。

得知了這些別出心裁的設計後,博物館館長感到非常興奮!他想知道對於每一種多邊形、每一種形狀能構成幾種可能的防護網!請你寫個程式計算一下。

Input Format

本題有多筆測試資料,請讓你的程式用讀到輸入檔尾端 (EOF) 作為結束。

對於每筆測試資料都只有一行,該行有一個正整數$ n (3 \leq n \leq 3 \times 10^6)$,和一個字串代表館長想要知道的形狀,”Acute Triangle” 代表銳角三角形、”Right Triangle”代表直角三角形、”Obtuse Triangle”代表鈍角三角形。(不包括"")

Output Format

一個整數 k 代表在條件下能有 k 種防護網產生。

( 注意:旋轉被視為不允許的,因此兩個全等的三角形但由不同的發射器產生的視為不同 )

Sample Input

10 Right Triangle
18 Acute Triangle

Sample Output

40
168

Hints

Problem Source

原TIOJ1511 / Problem Setter: skyly

Subtasks

For Testdata: 0 ~ 0, Score: 100
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 5000 65536 65536