NC15341. Magical Water Cup
描述
There are N cups of water which are numbered from 1 to N. The ith cup contains Ai liters of water, and the magical value of the ith cup is Bi.
The 1st operation will pour B1 liters of water from the 1st cup to the 2nd cup.
The Nth operation will pour BN liters of water from the Nth cup to the 1st cup.
The (N + 1)th operation will pour B1 liters of water from the 1st cup to the 2nd cup.
......
If the water in the cup is not enough to perform the operation, the game will stop immediately. The question is if this game will keep running forever? If not, how many times will it be operated?
输入描述
The first line contains an integer T, where T is the number of test cases. T test cases follow.
For each test case, the first line contains one integer N, where N is the number of cups.The second line contains N integers A1, A2, ... , AN, where Ai is the volume of water in the ith cup.The third line contains N integers B1, B2, ... , BN, where Bi is the magical value of the ith cup.
输出描述
For each test case, output one line containing “Case #x: y”, where x is the test case number (startingfrom 1). If the game will keep running forever, y is “INF”. Otherwise, y is the operation times.• 1 ≤ T ≤ 102.• 2 ≤ N ≤ 102.• 0 ≤ Ai ≤ 109.• 1 ≤ Bi ≤ 109.
示例1
输入:
2 3 4 5 6 1 3 6 3 2 0 1 1 1 1
输出:
Case #1: 7 Case #2: INF
C(clang 3.9) 解法, 执行用时: 6ms, 内存消耗: 492K, 提交时间: 2019-03-04 17:58:26
#include<stdio.h>
typedef long long ll;
ll a[110],b[110],c[110];
main(void)
{
int t;
scanf("%d",&t);
for(int z=1;z<=t;z++)
{
int n;
int flag=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
for(int i=1;i<=n;i++)scanf("%lld",&b[i]);
c[1]=b[n]-b[1];
for(int i=2;i<=n;i++)
{
c[i]=b[i-1]-b[i];
if(c[i]<0) flag=1;
}
if(c[1]<0) flag=1;
if(a[1]<b[1])
{printf("Case #%d: 0\n",z);continue;}
a[1]=a[1]-b[1];
ll sum=1;
ll d;
int mm;
ll min=-1;
if(flag==1)
{
for(int i=1;i<=n;i++)
{
if(c[i]<0)
{
d=a[i]/abs(c[i]);
if(i==1)
d=d+1;
if(d<min||min==-1)
{min=d;mm=i;
}
}
}
sum=min*n+mm-1;
printf("Case #%d: %lld\n",z,sum);
}
else printf("Case #%d: INF\n",z);
}
}
C++11(clang++ 3.9) 解法, 执行用时: 6ms, 内存消耗: 616K, 提交时间: 2018-03-31 20:36:24
#include<bits/stdc++.h>
using namespace std;
#define LL long long
LL A[110],B[110];
int main(){
int T,cas=1;
scanf("%d",&T);
while(T--){
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)scanf("%lld",&A[i]);
for(int i=0;i<n;i++)scanf("%lld",&B[i]);
if(B[0]>A[0]){
printf("Case #%d: 0\n",cas++);
continue;
}
int flg=0;
LL minv=1e18;
A[0]-=B[0];
for(int i=0;i<n;i++){
int L=(i-1+n)%n;
if(B[i]-B[L]>0){
flg=1;
LL minm=A[i]/(B[i]-B[L]);
minm=minm*n+i;
if(i==0)minm+=n;
minv=min(minv,minm);
}
}
if(flg==0)printf("Case #%d: INF\n",cas++);
else printf("Case #%d: %lld\n",cas++,minv);
}
}