#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <vector> #include <queue> #include <algorithm> using namespace std; int n; long long a[1200],b[1200]; long long tmp[1200]; long long res[1200]; int main() { int T; scanf("%d",&T); int Case=1; while(T--) { scanf("%d",&n); for(int i=0;i<n;i++) { scanf("%lld",&a[i]); tmp[i]=a[i]; } for(int i=0;i<n;i++) scanf("%lld",&b[i]); int flag=0; long long ans=0; for(int i=0;i<n;i++) { if(i==n-1) { a[i]-=b[i]; a[0]+=b[i]; } else { a[i]-=b[i]; a[i+1]+=b[i]; } if(a[i]<0) { flag=1; ans=i; break; } } if(flag==1) { printf("Case #%d: %lld\n",Case++,ans); continue; } if(a[0]<b[0]) { printf("Case #%d: %lld\n",Case++,n); continue; } flag=0; for(int i=0;i<n;i++) { if(a[i]==tmp[i]) { flag++; } res[i]=a[i]-tmp[i]; } if(flag==n) { printf("Case #%d: INF\n",Case++); continue; } long long round=1e16; for(int i=0;i<n;i++) { if(res[i]>=0) continue; round=min(round,a[i]/(-1*res[i])); } int pp=a[0]; for(int i=1;i<=round;i++) { pp=pp+b[n-1]-b[0]; if(pp<0) { round=i; break; } } ans+=1LL*(round+1)*n; for(int i=0;i<n;i++) { a[i]+=res[i]*(round); } flag=0; for(int i=0;i<n;i++) { if(i==n-1) { a[i]-=b[i]; a[0]+=b[i]; } else { a[i]-=b[i]; a[i+1]+=b[i]; } if(a[i]<0) { ans+=1LL*i; break; } } printf("Case #%d: %lld\n",Case++,ans); } return 0; } |
Double click to view unformatted code.