HackerEarth C - GukiZ Height problem solution

In this HackerEarth C – GukiZ Height problem solution 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.

The 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.

Additionally, 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.

Note that A may contain negative elements (because GukiZ can go down from some hill). Moreover, his height could become negative, or even his goal!

You can assume that both GukiZ’s height and goal change at the same moment (immediately and simultaneously) in the middle of a day.

Could you calculate the number of days in the GukiZ’s hike?

HackerEarth C – GukiZ Height problem solution.

#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("%dn",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;
 }

Second solution

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int nax = 1e5 + 5;
int t[nax];

ll extra(int a) {
    return (ll) a * (a + 1) / 2;
}

int main() {
    int n;
    ll goal;
    scanf("%d%lld", &n, &goal);
    ll total = 0;
    for(int i = 1; i <= n; ++i) {
        scanf("%d", &t[i]);
        total += t[i];
        if(total + extra(i) >= goal) {
            printf("%dn", i);
            return 0;
        }
    }
    int ANS = -1;
    for(int day = 1; day <= n; ++day) {
        goal -= t[day];
        #define f(x) (x * total + extra(x * n + day))
        int cycles = 0;
        for(int bit = 30; bit >= 0; --bit) {
            int maybe = cycles + (1 << bit);
            if((ll) maybe * n + day >= (1LL << 31))
                continue;
            if(f(maybe) < goal)
                cycles = maybe;
        }
        assert(f(cycles) < goal);
        ++cycles;
        assert(f(cycles) >= goal);
        int can = cycles * n + day;
        if(ANS == -1 || can < ANS)
            ANS = can;
    }
    printf("%dn", ANS);
    return 0;
}

HackerEarth C – GukiZ Height problem solution

HackerEarth C – GukiZ Height problem solution.

Second solution

Leave a Reply

Pages

Practice