View Code of Problem 3850

    #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]));
    		}
    		ans+=1LL*(round+1)*n;
    		for(int i=0;i<n;i++)
    		{
    			a[i]+=res[i]*(round);
    		}
    		flag=0;
    		while(true)
    		{
    			int nnum=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*nnum;
    				flag=1;
    				break;
    			}
    			nnum++;
    		}
    		if(flag)
    			break;
    		}
    		printf("Case #%d: %lld\n",Case++,ans);
    	}
    	return 0;
    }