We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
long minimumPasses(long m, long w, long p, long n) {
using i128 = __int128_t;
long long passes = 0;
long long best = (long long)ceil((long double)n / (long double)(m * 1.0L * w));
long long candies = 0;
while (true) {
long long prod = (long long)min((i128)m * (i128)w, (i128)LLONG_MAX / 2);
if (candies >= n) {
best = min(best, passes);
break;
}
best = min(best, passes + (long long)((n - candies + prod - 1) / prod));
if (candies < p) {
long long need = p - candies;
long long wait = (need + prod - 1) / prod;
if (wait <= 0) wait = 1;
passes += wait;
i128 gained = (i128)prod * (i128)wait;
if (gained > (i128)LLONG_MAX - candies) gained = (i128)LLONG_MAX - candies;
candies += (long long)gained;
continue;
}
long long canBuy = candies / p;
candies -= canBuy * p;
if (m < w) {
long long diff = w - m;
long long add = min(diff, canBuy);
m += add;
canBuy -= add;
} else if (w < m) {
long long diff = m - w;
long long add = min(diff, canBuy);
w += add;
canBuy -= add;
}
long long half = canBuy / 2;
m += half;
w += (canBuy - half);
passes += 1;
i128 gained = (i128)m * (i128)w;
if (gained > (i128)LLONG_MAX - candies) gained = (i128)LLONG_MAX - candies;
candies += (long long)gained;
}
return best;
}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Making Candies
You are viewing a single comment's thread. Return to all comments →
long minimumPasses(long m, long w, long p, long n) { using i128 = __int128_t; long long passes = 0; long long best = (long long)ceil((long double)n / (long double)(m * 1.0L * w)); long long candies = 0; while (true) { long long prod = (long long)min((i128)m * (i128)w, (i128)LLONG_MAX / 2); if (candies >= n) { best = min(best, passes); break; } best = min(best, passes + (long long)((n - candies + prod - 1) / prod)); if (candies < p) { long long need = p - candies; long long wait = (need + prod - 1) / prod; if (wait <= 0) wait = 1; passes += wait; i128 gained = (i128)prod * (i128)wait; if (gained > (i128)LLONG_MAX - candies) gained = (i128)LLONG_MAX - candies; candies += (long long)gained; continue; } long long canBuy = candies / p; candies -= canBuy * p; if (m < w) { long long diff = w - m; long long add = min(diff, canBuy); m += add; canBuy -= add; } else if (w < m) { long long diff = m - w; long long add = min(diff, canBuy); w += add; canBuy -= add; } long long half = canBuy / 2; m += half; w += (canBuy - half); passes += 1; i128 gained = (i128)m * (i128)w; if (gained > (i128)LLONG_MAX - candies) gained = (i128)LLONG_MAX - candies; candies += (long long)gained; } return best; }