HackerEarth Benny and Balls problem solution

YASH PAL, 31 July 202411 February 2026

In this HackerEarth Benny and Balls problem solution In this problem, Benny is looking for your help as usual. There are N baskets, which are numbered from 0 to N – 1. In each moment of time exactly, starting with t = 1, one ball appears in xi-th basket, where xi = (a * x(i-1) + b) % N.

The bottom of the i-th basket opens when there are not less than the p[i] balls in it, all the balls fall out of the basket, and then the bottom of the basket is closed again. How many times baskets’ bottoms will open to the T-th moment of time?

HackerEarth Benny and Balls problem solution

HackerEarth Benny and Balls problem solution.

#include <bits/stdc++.h>

using namespace std;

const long long N = (long long)1e5 + 10;

long long n, a, b, x, t;
long long p[N], add[N], id[N], sum[N];
long long ans = 0;
long long  xb, tb;

void read_data(){
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> p[i];
    cin >> x >> a >> b >> t;
    xb = x;
    tb = t;
}

long long solve(){
    long long px = x;
    long long tt = t;
    for (int i = 0; i < n; ++i) add[i] = sum[i] = 0, id[i] = -1;

    long long xc = x;
    long long step = 0;

    while (!add[xc]){
        add[xc]++;
        id[xc] = step++;
        xc = (a * xc + b) % n;
    }

    long long cycleLen = step - id[xc];
    long long preCycleLen = step - cycleLen;

    for (int i = 0; i < min(t, preCycleLen); ++i){
        sum[x]++;
        x = (1LL * a * x + b) % (long long)n;
    }

    t -= min(t, preCycleLen);

    int cntCycles = t / cycleLen;

    for (int i = 0; i < cycleLen; ++i){
        sum[x] += cntCycles;
        x = (1LL * a * x + b) % (long long)n;
    }

    t %= cycleLen;

    for (int i = 0; i < t; ++i){
        sum[x] += 1;
        x = (a * x + b) % n;
    }

    long long ans = 0;
    for (int i = 0; i < n; ++i) ans += sum[i] / p[i];
    x = px;
    t = tt;
    return ans;
}

void write_data(long long ans){
    cout << ans << endl;
}

long long bs[N];

long long brute(){
    long long ans = 0;
    for (int i = 0; i < n; ++i) bs[i] = 0;
    for (int i = 0; i < tb; ++i){
        bs[xb]++;
        xb = (a * xb + b) % n;
    }
    for (int i = 0; i < n; ++i) ans += bs[i] / p[i];
    return ans;
}

int main()
{
    ios_base::sync_with_stdio(false);
    srand(time(NULL));
    int cnt; cin >> cnt;
    while (cnt--){
        read_data();
        write_data(solve());
    }

    return 0;
}

Second solution

#include<bits/stdc++.h>

using namespace std;

const int INF = 1e9;
const int N = 100031;

int tests, n, cnt[N];

int x, a, b, t, p[N];

int main(){
  ios_base::sync_with_stdio(0);
  cin >> tests;

  for (; tests; --tests)
  {
    cin >> n;

    for (int i = 0; i < n; i++)
    {
      cin >> p[i];
      cnt[i] = 0;
    }
    cin >> x >> a >> b >> t;

    int ans = 0;

    for (int i = 1; i <= t; i++)
    {
      cnt[x]++;
      if (cnt[x] >= p[x])
      {
        ans++;
        cnt[x] = 0;
      }
      x = (1ll * x*a + b) % n;
    }
    cout << ans << endl;
  }

  return 0;
}

coding problems solutions HackerEarth HackerEarth

Leave a Reply