TopCoder

$\huge 南ことり$
$ε=ε=ε=(~ ̄▽ ̄)~烙跑囉$

User's AC Ratio

84.9% (73/86)

Submission's AC Ratio

25.6% (111/434)

Tags

Description

  冬天到了,Q國境內一種因細菌變種導致的流行性感冒疫情一發不可收拾。各大醫院組成了一個疫苗研發小組,以求能在第一時間控制住全國的疫情。他們首先確定疫情的起源,是由於一種學名為耶西耶姆的細菌。為了培育適量的耶西耶姆細菌來做疫苗研究之用,研究人員發現,以一種Z射線照射在細菌,可使得該區域內的所有細菌在瞬間一分為二,使總細菌數變得原來的兩倍。

  而為了試驗疫苗所需濃度,研究團隊以生物微晶片的技術來有效率地進行疫苗劑量實驗。先將100,000,000單位的細菌均勻散布在一片1公分(=10,000微米)見方的微晶片中。則每微米平方的區域內,會恰好有一隻細菌。而由電腦控制的Z射線可以非常精確地打在微晶片上任何一個指定的矩形中,此矩形可以精確地對準在以微米為基本刻度的位置上。為了讓微晶片中的不同區域擁有不同數量的細菌,專家們設定了一系列的Z射線照射指令。因為不同區域被照射的次數不同會使該區域的細菌個數不同,各個區域的細菌個數得以被精密地控制,如圖1。

  由於細菌放進微晶片經過Z射線的照射以後,細菌數量難以實地量測。但其實若能得到先前Z射線操作指令的數據,我們可以寫出一個電腦程式來精確算出總細菌的個數。身為團隊中具有電腦專才的你,自告奮勇地要來完成這個任務。

Input Format

  輸入檔可能包含多筆的測試資料。

  每一筆測試資料的第一行只有一個數字n (1 ≤ n ≤ 200),表示Z射線操作指令的個數。接下來一共n行,每一行有4個整數left top right bottom,數值介於0到10000之間,分別表示Z射線照射區域的左﹑上﹑右﹑下的位置(以微米為刻度單位),如圖2。

  當測試資料第一行的輸入n為0時表示輸入檔結束,程式不需要對這行輸入作處理。

Output Format

每一筆測試資料中的Z射線照射指令都操作在一塊新的微晶片上,每一塊微晶片規格和細菌散佈情形都相同(請參考上述題目說明)。對於每一筆測試資料,請輸出指令操作完畢後微晶片中的總細菌個數(你可以假設這個數字會小於8*1018)。

Sample Input 1

4
0 0 10000 10000
0 0 8000 8000
2000 2000 10000 10000
4000 4000 6000 6000
5
0 0 10000 10000
0 0 1000 1000
0 0 100 100
0 0 10 10
0 0 1 1
0

Sample Output 1

560000000
202040816

Hints

Problem Source

原TIOJ1045 / NPSC2003決賽(prob A)

Subtasks

No. Testdata Range Score
1 0 100

Testdata and Limits

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