Submission #13537430

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
	*this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

long long A, B, C, D;
long long INF = 5e18;

void min_self(long long& a, long long b) {
	a = min(a, b);
}

map<long long, long long> mapka;

long long f(long long goal) {
	if(goal == 0) {
		return 0;
	}
	if(goal == 1) {
		return D;
	}
	if(mapka.count(goal)) {
		return mapka[goal];
	}
	long long best = INF;
	if(D < INF / goal) {
		min_self(best, D * goal);
	}
	for(int i = 0; i < 3; ++i) {
		int mul = vector<int>{2,3,5}[i];
		long long cost = vector<long long>{A,B,C}[i];
		if(goal % mul == 0) {
			min_self(best, cost + f(goal / mul));
		}
		else {
			long long down = goal / mul * mul;
			min_self(best, cost + D * (goal - down) + f(goal / mul));
			long long up = down + mul;
			min_self(best, cost + D * (up - goal) + f(goal / mul + 1));
		}
	}
	return mapka[goal] = best;
}

void test_case() {
	long long N;
	cin >> N;
	cin >> A >> B >> C >> D;
	cout << f(N) << endl;
	mapka.clear();
}

int main() {
	int T;
	cin >> T;
	while(T--) {
		test_case();
	}
}

Submission Info

Judge Result