Problem : 272 - 出納員的僱用

Problem Statistics

Solved Member: 8　　Submission: 31　　User Tried: 9

Statement:

　　德黑蘭的一家每天24小時營業的超市，需要一批出納員來滿足它的需求。超市經理僱傭你來幫他解決一個問題──超市在每天的不同時段需要不同數目的出納員（例如，午夜只需一小批，而下午則需要很多）來為顧客提供優質服務，他希望僱傭最少數目的納員。

　　超市經歷已經提供一天裡每一小時需要出納員的最少數量──R(0),R(1),...,R(23）。 R（0）表示從午夜到凌晨1:00所需要出納員的最少數目；R(1)表示凌晨1：00到2：00之間需要的；以此類推。每一天，這些數據都是相同的。有N人申請這項工作，每個申請者i在每天24小時當中，從一個特定的時刻開始連續工作恰好8小時。定義ti(0<=ti<=23)為上面提到的開始時刻，也就是說，如果第i個申請者被錄用，他（或她）將從ti時刻開始連續工作8小時。

　　試著編寫一個程式，輸入R(i),i=0，...，23，以及ti，i=1，...，N，它們都是非負整數，計算為滿足上述限制需要僱用的最少出納員數目、在每一時刻可以有比對應R(i)更多的出納員在工作。

Input:Output:

第一行為24個整數，表示R（0），R（1），...，R(23)，R(i)最大可以取到1000。

接下來一行是一個整數N，表示申請者的數目，0<=N<=1000。

接下來有N行，每行為一個整數ti，0<=ti<=23,測試數據之間沒有空行。

輸出佔一行，為需要僱用的出納員的最少數目，如果沒有解則輸出"No Solution"。

Sample Input:Sample Output:

1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
5
0
23
22
1
10

HINT:

算法藝術 p.306 ( Bellman-Ford 例題 )

Source:

ICPC Tehran 2000

Problem Setter

hanhan0912

Testdata:

Test	Time	Memory	Score
0	500ms	65536kb
1	500ms	65536kb	2
2	500ms	65536kb	3
3	500ms	65536kb	3
4	500ms	65536kb	2
5	500ms	65536kb	10
6	500ms	65536kb	10
7	500ms	65536kb	10
8	500ms	65536kb	10
9	500ms	65536kb	10
10	500ms	65536kb	10
11	500ms	65536kb	10
12	500ms	65536kb	10
13	500ms	65536kb	10