HackerEarth Benny and Balls problem solution

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.

#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