# PROBLEM LINK:CodeChef: Practical coding for everyone

Practice

Author: susheel_akd4
Tester: imreally_john

Math

# EXPLANATION:

Let’s code the following process. Go one circle across the stalls,calculate the total cost C of candies bought and the number S of candies bought. Now you can decrease you money down to T=T mod C and add S ⋅ (T div C) to answer. It represents that you went maximum number of such circles. The later circles will have smaller cost. Let’s continue this process until T

becomes smaller than the minimum priced candy.

The number of operations made is O(logT)
. Let Tcur be the amount of money before some operation, Ccur be the total cost of candies bought on that operation and Tnew=Tcur mod Ccur. Tnew is actually smaller than Ccur (that’s how modulo works) and smaller than TcurCcur (that’s also how modulo works). And these inequalities imply that Tnew<Tcur/2. That leads to about O(logT)

steps to reach the minimal price.

Overall complexity: O(nlogT)

# SOLUTIONS:

Setter's Solution
``````#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

const int N = 200 * 1000 + 13;

typedef long long li;

int n;
int a[N];

void get(li T, li& pr, li& cnt){
pr = 0, cnt = 0;
forn(i, n){
if (T >= a[i]){
T -= a[i];
pr += a[i];
++cnt;
}
}
}

int main() {
li T;
scanf("%d%lld", &n, &T);
forn(i, n)
scanf("%d", &a[i]);

int mn = *min_element(a, a + n);
li ans = 0;
while (T >= mn){
li pr, cnt;
get(T, pr, cnt);
ans += cnt * (T / pr);
T %= pr;
}
printf("%lld\n", ans);
return 0;
}
``````