# PROBLEM LINK:CodeChef: Practical coding for everyone

* Author:* susheel_akd4

*imreally_john*

**Tester:**# PREREQUISITES:

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 Tcur − Ccur (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;
}
```