Gukiz

QUESTION

GukiZ loves hiking in the mountains. He starts his hike at the height 0 and he has some goal to reach, initially equal to H. Once he is at the height not less than his goal, he ends his hike.\n\nThe mountains are described by a 0-indexed sequence A of the length N. In the first day GukiZ will change his height by A0, in the second day by A1, and so on. Mountains are a regular structure so the pattern repeats after the first N days. In general, in the i-th day GukiZ will change his height by A(i-1)%N.\n\nAdditionally, GukiZ will become more and more tired and in the i-th day his goal will decrease by i. So, after the first i days his goal will be equal to H – i(i+1)/2.\n\nNote that A may contain negative elements (because GukiZ can go down from some hill). Moreover, his height could become negative, or even his goal!\n\nYou can assume that both GukiZ’s height and goal change at the same moment (immediately and simultaneously) in the middle of a day.\n\nCould you calculate the number of days in the GukiZ’s hike?\n\nInput format\n\nThe first line contains two integers N and H, denoting the length of an array A, and the initial goal.\n\nThe second line contains N integers A0, A1, …, AN-1.\n\nOutput format\n\nIn a single line print the number of days in the GukiZ’s hike.\n\nIt can be proved that for any input the answer exists.

“TESTCASE_1”: “3 45\n7 -4 5\n###—###SEPERATOR—###—\n7”, “TESTCASE_2”: “5 50\n10 9 20\n###—###SEPERATOR—###—\n5”, “TESTCASE_3”: “7 20\n6 1 9 2 -2 7 -4\n###—###SEPERATOR—###—\n3”, “TESTCASE_4”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_5”: “0\n###—###SEPERATOR—###—\n0

ANSWER

#include<iostream>
#include<stdio.h>
using namespace std;
const int si=2*1e9+1;
const long long big=1e15;
long long mini,n,h,p,o,l,r,day,p1;
long long a[1000000],sum[1000000];
int main()
 {
    cin >> n;
    cin >> h;
    for (int i=1;i<=n; i++)
        cin>>a[i];
     for (int i=1;i<=n;i++)
     {
        p=i;
        sum[i]=sum[i-1]+a[i];
        if (sum[i]>=h-(p*(p+1))/2)
        {
            printf("%d\n",i);
            return 0;
        }
     }
 mini=big;
 for (int i=1;i<=n;i++)
   {
       l=0;
       r=(si/n)+1;
     while (l<r-1)
     {
       o=(l+r)/2;
       day=o*n+i;
       if (h-(day*(day+1))/2 > o*sum[n]+sum[i]) l=o; else r=o;
     }
      p=i;
      p1=n;
     mini=min(mini,r*p1+p);
   }
   printf("%lld",mini);
  return 0;
}
Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.