CVL-Editorial

editorial
1

PROBLEM LINK:CodeChef: Practical coding for everyone

Practice

Author: susheel_akd4
Tester: imreally_john

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;
}