TopCoder

AA 競程
AA 競程是最強的!

User's AC Ratio

96.1% (74/77)

Submission's AC Ratio

59.6% (134/225)

Tags

Description

日本的貴族學校「Agnes」要來台開設分校了!
這間在日本以優秀研究成果享譽國際的大學,五年前在Agnes學園校長DE(學園高層充滿著不為人知的機密,故校長的名稱用神秘的代號DE稱之)熟嫻的外交手段經營下,向業界招募了五年五千億的大筆資金,並在極短的時間內超英趕美,登上全世界大學的TOP10。
在經過多年考核後,董事會決定在台灣設立國外第一所分校,台大校長在聽聞此消息後,準備從今年高中生中挑出間諜,潛入該學校收集情報,而你就是那位被挑中的天才高中生。
為了確保你可以通過「Agnes」的入學考試(雖然你是台灣最天才的高中生,但是要面對世界各地的高中生仍是一件不容易的事情!),台大派出校園內馬尾綁最好的學妹向「Agnes」的教學長蜜蜂騙取得了入學考試的題目(沒想到教學長喜歡馬尾女孩的傳聞是真的!)。
在看過入學考試的題目後,你對於拿滿分非常有自信,但為了降低間諜任務失敗的機率(任務失敗你就…嘿嘿嘿…),你決定在考前事先研究出計算該題目最快的方法(因為答案實在太難記了)。

以下便是「Agnes」的入學考試題目:

聰明的你很快就發現了幾件重要的事實:
1. A矩陣的Column數目一定要等於B矩陣的Row數目才可以做∮運算。

  1. C矩陣的大小一定會是Row(A)*Column(B),也就是Row(C)=Row(A)且Column(C)=Column(B)。

  2. 彼彼運算需要大量的計算時間,計算一次C=∮(A,B)需要
    Row(A)* Column(A)*Column(B) 個彼彼運算。

  3. 要計算超過2個以上的tera operation時,依照不同的順序會需要不同的彼彼運算次數。
    例如:要計算A∮B∮C的話,有兩種選擇:
    ((A∮B) ∮C) 或者 (A∮(B∮C))。
    假設A是7x10的矩陣,B是10x22的矩陣,C是22x37的矩陣,則
    (A∮B) ∮C需要(7*10*22) + (7*22*37) = 7238次彼彼運算
    A∮(B∮C) 需要(10*22*37)+(7*10*37) = 10730次彼彼運算

  4. 雖然利用其它的特殊技巧可以更快速的計算出答案,但為了防止自己算錯,你決定只利用添加括號的方式來加快運算速度(也就是改變運算的順序)。

根據你不平凡的智力,計算500次彼彼運算需要一張A4白紙,因此一張雙面A4總共可計算1000次,因為此次入學考試由正直的DE親自監考,正直的DE常常懷疑學生不正直,故你最好事先計算出最低所需的計算紙數量,以免當天考試因為帶太多計算紙而被正直的DE懷疑你的身份!

Input Format

輸入檔以一個數字T為開頭,代表題目卷共有T個小題(1<=T<=5)。
每個小題以一個整數N(1<=N<= 1000),代表有幾個矩陣需要做運算,接著有N行輸入,Ri和Ci分別代表矩陣Ai的Row及Column大小(1<=Ri<=1000, 1<=Ci<=1000,1<=i<=N)。

Output Format

對每一組小題,你應該輸出一個非負整數H,代表若單獨計算該小題最少需要幾張計算紙,且在最後一行輸出整場考試最少需使用幾張計算紙。

Sample Input 1

2
3
7 10
10 22
22 37
6
30 35
35 15
15 5
5 10
10 20
20 25

Sample Output 1

8
16
23

Hints

Problem Source

原TIOJ1488 / NPSC2007決賽(prob D)

Subtasks

No. Testdata Range Score
1 0 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 10000 65536 262144 1