Employment of cashier [differential constraint]

subject ：

A supermarket needs to $24$ Hours open , In order to meet business needs , Need to hire a large number of cashiers .

It is known that the number of cashiers required in different time periods is different , In order to be able to hire as few people as possible , To reduce costs , The manager of this supermarket asked you to help with some advice .

The manager provides you with a list of the minimum number of cashiers required in each time period $R(0),R(1),R(2),\dots ,R(23)$.

$R(0)$ It means midnight $00:00$ Into the morning $01:00$ Minimum required quantity of ,$R(1)$ Morning Express $01:00$ Into the morning $02:00$ Minimum required quantity of , And so on .

Altogether $N$ A qualified applicant applies for a position , The first i Applicants can choose from ti Start working continuously all the time $8$ Hours .

There is no replacement between cashiers , Will work completely $8$ Hours , There must be enough cash registers .

Now give your cashier's demand list , Please calculate the minimum number of cashiers you need to hire .

Input format
The first line contains one that does not exceed $20$ The integer of , Number of groups representing test data .

For each group of test data , The first line contains $24$ It's an integer , respectively $R(0),R(1),R(2),\dots ,R(23)$.

The second line contains integers N.

Next $N$ That's ok , Each line contains an integer $t_i$.

Output format
Each group of data outputs a result , Each result takes up one line .

If there is no arrangement to meet the needs , Output No Solution.

Data range
$0\le R(0)\le 1000,$
$0\le N\le 1000,$
$0\le t_i\le 23$
sample input ：

1
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

sample output ：

1

Topic ideas ：

Because at least , So use the longest way .

---

num[i]： The first i The number of people who apply for posts at any time
x[i]： The first i The number of people actually on duty at any time
r[i]： The first i The minimum demand of the moment
s[i]: from 1 To i The number of people applying for employment
The first i At which moment can the person take the post ：$x[i-7]+x[i-6]+x[i-5]+...+x[i]$

---

The number of people applying for employment at every moment must be greater than 0：$0<=x[i]<=num[i]$
The first i The number of people on duty at one time must be greater than or equal to r[i], therefore $x[i-7]+x[i-6]+x[i-5]+...+x[i]>=r[i]$;
Because it's the sum of a paragraph , So we can use prefix and find

Convert to prefix and post ：$0<=x[i]<=num[i]$ -> $0<=s[i]-s[i-1]<=num[i]$ ①
$x[i-7]+x[i-6]+x[i-5]+...+x[i]>=r[i]$ -> $s[i]-s[i]-8>=r[i]$ ②
Because time is cyclical 24:00 And then 1:00, So we should discuss the second formula according to the situation
i>=8$s[i]-s[i-8]>=r[i]$
i<8$s[i]+s[24]-s[i+16]>=r[i]$

---

After finishing, I have to
$s[i]>=s[i-1]$ ①
$s[i-1]>=s[i]-num[i]$ ②
$s[i]>=s[i-8]+r[i]$ ③
$s[i]=s[i+16]-s[24]+r[i]$ ④
Because the form of difference constraint is x[i]>=x[j]+c, ad locum s[24] Is the final answer , And the applicant is 0_{1000, So we can enumerate 0}1000 To make s[24] Become constant
Because we enumerated s[24], So this point has been fixed , Then we can use these two formulas to fix this point (c Answer for enumeration )
$s[24]>=c$$s[24]<=c$ -> $s[24]>=s[0]+c$$s[24]<=s[0]+c$

---

Finally it is concluded that
s[i]>=s[i-1] ①
s[i-1]>=s[i]-num[i] ②
s[i]>=s[i-8]+r[i] ③
s[i]=s[i+16]-s[24]+r[i] ④
s[24]>=s[0]+c ⑤
s[0]>=s[24]-c ⑥

---

AC Code （C++）：

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

const int N=30,M=100;

int n,t;
int h[N],e[M],ne[M],w[M],idx;
int dist[N];
int cnt[N];
bool st[N];
int num[N],r[N];

void add(int a,int b,int c){
    
    w[idx]=c;
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}

bool spfa(int c){
    
    memset(h,-1,sizeof h);
    idx=0;
    memset(dist,-0x3f,sizeof dist);
    memset(cnt,0,sizeof cnt);
    memset(st,0,sizeof st);
    
    for(int i=1;i<=24;i++){
    
        add(i-1,i,0);
        add(i,i-1,-num[i]);
        if(i>=8) add(i-8,i,r[i]);
        if(i<8) add(i+16,i,r[i]-c);
    }
    add(0,24,c),add(24,0,-c);
    
    queue<int> q;
    q.push(0);
    dist[0]=0;
    st[0]=true;
    
    while(q.size()){
    
        int t=q.front();
        q.pop();
        st[t]=false;
        cnt[t]++;
        if(cnt[t]>=N) return true;
        
        for(int i=h[t];i!=-1;i=ne[i]){
    
            int j=e[i];
            if(dist[j]<dist[t]+w[i]){
    
                dist[j]=dist[t]+w[i];
                if(!st[j]){
    
                    q.push(j);
                    st[j]=true;
                }
            }
        }
    }
    return false;
}

int main(){
    
    scanf("%d",&t);
    while(t--){
    
        memset(num,0,sizeof num);
        for(int i=1;i<=24;i++) scanf("%d",&r[i]);
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
    
            int x;
            scanf("%d",&x);
            num[x+1]++;
        }
        
        bool f=true;
        for(int i=0;i<=1000;i++){
    
            if(!spfa(i)){
    
                printf("%d\n",i);
                f=false;
                break;
            }
        }
        if(f) printf("No Solution\n");
    }
    return 0;
}