In this HackerEarth Special Shop problem solution, Creatnx now wants to decorate his house by flower pots. He plans to buy exactly N ones. He can only buy them from Triracle's shop. There are only two kind of flower pots available in that shop. The shop is very strange. If you buy X flower pots of kind 1 then you must pay A x X^2 and B x Y^2 if you buy Y flower pots of kind 2. Please help Creatnx buys exactly N flower pots that minimizes money he pays.


HackerEarth Special Shop problem solution


HackerEarth Special Shop problem solution.

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int test; cin >> test;
    assert(1 <= test && test <= 1e5);
    while (test--) {
        int n, a, b; cin >> n >> a >> b;
        assert(1 <= n && n <= 1e5);
        assert(1 <= a && a <= 1e5);
        assert(1 <= b && b <= 1e5);
        int x = (int) round((long double) b * n / (a + b));
        int y = n - x;
        cout << (long long) a * x * x + (long long) b * y * y << "\n";
    }
}

int main(int argc, char* argv[]) {
    ios_base::sync_with_stdio(0), cin.tie(0);
    if (argc > 1) {
        assert(freopen(argv[1], "r", stdin));
    }
    if (argc > 2) {
        assert(freopen(argv[2], "wb", stdout));
    }
    solve();
    cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
    return 0;
}

Second solution

t = int(raw_input())
 
for ___ in xrange(t):
    n,a,b = map(int, raw_input().split())
 
    r1 = b * n / (a + b)
 
    ans = 10101010101010101010
    for x in xrange(r1-10,r1+10):
        if 0 <= x <= n:
            ans = min(ans, x*x*a + (n-x)*(n-x)*b)
    print ans