Codeforces Round #547 (Div. 3)E. Superhero Battle

E. Superhero Battle

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

A superhero fights with a monster. The battle consists of rounds, each of which lasts exactly nn minutes. After a round ends, the next round starts immediately. This is repeated over and over again.

Each round has the same scenario. It is described by a sequence of nn numbers: d1,d2,…,dnd1,d2,…,dn (−106≤di≤106−106≤di≤106). The ii-th element means that monster's hp (hit points) changes by the value didi during the ii-th minute of each round. Formally, if before the ii-th minute of a round the monster's hp is hh, then after the ii-th minute it changes to h:=h+dih:=h+di.

The monster's initial hp is HH. It means that before the battle the monster has HH hit points. Print the first minute after which the monster dies. The monster dies if its hp is less than or equal to 00. Print -1 if the battle continues infinitely.

Input

The first line contains two integers HH and nn (1≤H≤10121≤H≤1012, 1≤n≤2⋅1051≤n≤2⋅105). The second line contains the sequence of integers d1,d2,…,dnd1,d2,…,dn (−106≤di≤106−106≤di≤106), where didi is the value to change monster's hp in the ii-th minute of a round.

Output

Print -1 if the superhero can't kill the monster and the battle will last infinitely. Otherwise, print the positive integer kk such that kk is the first minute after which the monster is dead.

题意：给定一个初始值，一个总数为n的数列，第i次加上这个数列的第（i-1）%n+1个数，如果值小于等于0就退出，无解输出-1

思路：扫一遍记录能减小的最小值

无解情况是初始值减最小值大于零且每一轮结束不减少，二分能进行的最大轮数（剩下的生命值模拟即可）

// luogu-judger-enable-o2
#include<bits/stdc++.h>
#include<unordered_set>
#define rg register ll
#define inf 2147483647
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
#define ll long long
#define maxn 200005
const double eps = 1e-8;
using namespace std;
inline ll read()
{
	char ch = getchar(); ll s = 0, w = 1;
	while (ch < 48 || ch>57) { if (ch == '-')w = -1; ch = getchar(); }
	while (ch >= 48 && ch <= 57) { s = (s << 1) + (s << 3) + (ch ^ 48); ch = getchar(); }
	return s * w;
}
inline void write(ll x)
{
	if (x < 0)putchar('-'), x = -x;
	if (x > 9)write(x / 10);
	putchar(x % 10 + 48);
}
ll n,ans,a[maxn],sum=0,h,minn=inf;
inline bool check(ll x)
{
    return h-x*abs(sum)<=abs(minn)?1:0;
}
int main()
{
	h=read(),n=read();
	for(rg i=1;i<=n;i++)
    {
        cin>>a[i];
        sum+=a[i];
        minn=min(sum,minn);
    }
    if(h+minn>0&&sum>=0)
    {
        cout<<-1<<endl;
        return 0;
    }
    ll l=1,r=h/(abs(sum)),res=0;
    if(h+minn>0)
    {
    while(l<=r)
    {
        ll mid=(l+r)>>1;
        if(check(mid))
        {
            ans=mid;
            r=mid-1;
        }
        else l=mid+1;
    }
    res+=ans*n;
    h-=ans*abs(sum);
    }
    for(rg i=1;i<=n;i++)
    {
        h+=a[i];
        res++;
        if(h<=0)break;
    }
    cout<<res<<endl;
 
 
 
	return 0;
}