1153 . 2.IC板檢測

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

94.4% (17/18)

Submission's AC Ratio

40.0% (24/60)

Tags

全國賽 2004-全國賽

Description

「奇上」IC板檢測工司擁有全國最多台的IC板自動檢測機，但是因為每台檢測系統購進的時間不一樣，因此各機台檢測一片IC板所需時間也都不同。因為該公司為24小時營運，因此整天任何時刻都會有小貨車將需要檢測的IC板送至該公司進行檢測。每當一輛小貨車抵達時，「奇上」公司就立即安排一台IC板自動檢測系統來負責該批所有的IC板檢測工作。為了爭取時效，「奇上」公司一定會安排能最快完成該批IC板所有檢測的機台來負責該批IC板檢測工作（即便該機台正在進行其它批IC板的檢測工作或有其他機台閒置中。例如：如果機台A正在檢測其他批IC，機台B閒置中，但是如果等機台A做完手上的工作後再來檢測該批IC的結束時間比由機台B來檢測該批IC的結束時間早的話，則會把該批IC板的檢測工作分配到機台A上。完成時間是以秒為單位，不足一秒無條件進位），如果同時有兩部以上的機台符合上述條件，則該批檢測工作會被分配到速度較快的機台。請寫一個程式來計算最後一批完成檢測工作的起始時間點及機台號碼。

Constraints

  • 「奇上」公司擁有n (n<=20) 台編號為1, 2, …, n的IC板檢測機。每台機器檢測的速度分別為每分鐘能檢測s1, s2, …, sn片IC板 (1≤s1, s2, …, sn ≤200, s1≠s2≠… ≠sn–1≠sn)。

  • 每台檢測機在開始檢測一批新的IC板前需要5分鐘的時間將該批IC板準備就緒，而在完成一批檢測工作後，也需要10分鐘的時間進行自動清理的工作。這些動作一定只能從每分鐘的0 秒開始進行。換句話說，如果有一批檢測工作在第23分鐘又30秒時完成，則下一批等待中的IC板檢測工作只能從第39(24+10+5)分鐘開始進行。（請注意！起始時間為第39分鐘而不是第34分鐘）

Input Format

輸入檔第一行只有一個正整數n，代表「奇上」公司IC板檢測機台數。
第二行有n個以空格分開的正整數，分別代表每一機台的檢測速度（即s1,s2,...,sn）。
接下來的數行每一行有兩個正整數，分別代表每台小貨車抵達「奇上」公司的時間（以分鐘計算）（≤50000）及所需檢測的IC板數量(≤1000)。其中每一行的第一個數字為非遞減(non-decreasing)（若抵達時間相同則依input順序處理）。此外，最後一行以兩個0來代表檔案結束（不要將其當作送檢資料處理）。（所有輸入都保證最後一批檢測工作的起始時間都在230內）

Output Format

請輸出最後一批完成檢測工作的起始時間點及該機台號碼，這兩個整數應以一個空格分開。輸入保證不會有兩批或兩批以上的工作在最後同時完成。

Sample Input 1

2
10 20
5 100
10 200
15 300
19 500
0 0

Sample Output 1

60 2

Hints

Problem Source

原TIOJ1153 / 93全國賽(prob 2)。

Subtasks

No. Testdata Range Score
1 0 20
2 1 20
3 2 20
4 3 20
5 4 20

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 900 65536 262144 1
1 900 65536 262144 2
2 900 65536 262144 3
3 900 65536 262144 4
4 900 65536 262144 5
Submit
Back to Top