Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #include <ext/pb_ds/assoc_container.hpp>
- #include <ext/pb_ds/tree_policy.hpp>
- using namespace std;
- using namespace __gnu_pbds;
- template <class T>
- using pbds =
- tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
- #define cerr if(false)cerr
- #define int long long
- #define pb push_back
- #define F first
- #define S second
- #define yes cout << "Yes\n"
- #define no cout << "No\n"
- #define yn(x) x ? yes : no
- #define f(i, s, e) for (int i = s; i < e; i++)
- #define vi vector<int>
- #define vb vector<bool>
- #define pii pair<int, int>
- #define vpi vector<pii>
- #define all(x) x.begin(), x.end()
- #define minele(x) *min_element(all(x))
- #define maxele(x) *max_element(all(x))
- #define endl '\n'
- #define in(v, x) binary_search(all(v), x)
- const int N = 2e5;
- const int MOD = 1e9 + 7;
- const int inf = LLONG_MAX;
- const int minf = LLONG_MIN;
- #ifndef ONLINE_JUDGE
- #define debug(x) \
- cerr << (#x) << " is "; \
- _print(x)
- #define dbg(x...) \
- cerr << (#x) << " is "; \
- _print(x)
- #else
- #define debug(x)
- #define dbg(x)
- #define dbg(x...)
- #endif
- template <typename T>
- void _print(T a) {
- cerr << a;
- }
- template <typename T1, typename... T2>
- void _print(T1 t1, T2... t2) {
- cerr << t1 << ", ";
- _print(t2...);
- cerr << endl;
- }
- template <typename T>
- void print(T a) {
- cout << a << ' ';
- }
- template <typename T>
- void println(T a) {
- cout << a << endl;
- }
- template <class T>
- istream &operator>>(istream &is, vector<T> &a) {
- for (auto &x : a) is >> x;
- return is;
- }
- template <class T>
- ostream &operator<<(ostream &os, const vector<T> &a) {
- for (const auto &x : a) os << x << ' ';
- return os;
- }
- template <class T, class V>
- void _print(pair<T, V> p);
- template <class T>
- void _print(vector<T> v);
- template <class T>
- void _print(set<T> v);
- template <class T, class V>
- void _print(map<T, V> v);
- template <class T>
- void _print(multiset<T> v);
- template <class T, class V>
- void _print(pair<T, V> p) {
- cerr << "{";
- _print(p.F);
- cerr << ",";
- _print(p.S);
- cerr << "} ";
- }
- template <class T>
- void _print(vector<T> v) {
- cerr << "[ ";
- for (T i : v) {
- _print(i);
- cerr << " ";
- }
- cerr << "]";
- cerr << endl;
- }
- template <class T>
- void _print(set<T> v) {
- cerr << "[ ";
- for (T i : v) {
- _print(i);
- cerr << " ";
- }
- cerr << "]";
- cerr << endl;
- }
- template <class T>
- void _print(multiset<T> v) {
- cerr << "[ ";
- for (T i : v) {
- _print(i);
- cerr << " ";
- }
- cerr << "]";
- cerr << endl;
- }
- template <class T, class V>
- void _print(map<T, V> v) {
- cerr << "[ ";
- for (auto i : v) {
- _print(i);
- cerr << " ";
- }
- cerr << "]";
- cerr << endl;
- }
- template <class T, class V>
- void _print(unordered_map<T, V> v) {
- cerr << "[ ";
- for (auto i : v) {
- _print(i);
- cerr << " ";
- }
- cerr << "]";
- cerr << endl;
- }
- void fast() {
- ios_base::sync_with_stdio(false);
- cin.tie(NULL);
- cout.tie(NULL);
- }
- void init_code() {
- #ifndef ONLINE_JUDGE
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- freopen("error.txt", "w", stderr);
- #endif // ONLINE_JUDGE
- }
- int lcm(int a, int b) { return a * b / __gcd(a, b); }
- int ops(int from, int to) {
- if (to >= from) return to - from;
- // from > to
- int nxt = ((from + to - 1) / to) * to;
- return nxt - from;
- }
- vector<vi> vals;
- int n;
- int fun(vi &v, int i, bool a, bool b, bool c,
- vector<vector<vector<vector<int>>>> &dp) {
- if (i == n) {
- if (a & b & c)
- return 0;
- else
- return 1e18;
- }
- if (dp[i][a][b][c] != -1) return dp[i][a][b][c];
- return dp[i][a][b][c] = min({fun(v, i + 1, a, b, c, dp),
- vals[i][0] + fun(v, i + 1, 1, b, c, dp),
- vals[i][1] + fun(v, i + 1, a, 1, c, dp),
- vals[i][2] + fun(v, i + 1, a, b, 1, dp),
- vals[i][3] + fun(v, i + 1, 1, 1, c, dp),
- vals[i][4] + fun(v, i + 1, a, 1, 1, dp),
- vals[i][5] + fun(v, i + 1, 1, b, 1, dp),
- vals[i][6] + fun(v, i + 1, 1, 1, 1, dp)});
- }
- void solve() {
- int a, b, c;
- cin >> n >> a >> b >> c;
- vi v(n);
- cin >> v;
- debug(v);
- vector<vector<vector<vector<int>>>> dp(n, vector<vector<vector<int>>>(2, vector<vector<int>>(2, vector<int>(2, -1))));
- // a, b, c, lc(a,b), lc(b,c), lc(c, a);
- int lab = lcm(a, b);
- int lbc = lcm(b, c);
- int lca = lcm(c, a);
- int labc = lcm(a, lcm(b, c));
- vals.assign(n, vi(7));
- for (int i = 0; i < n; i++) {
- vals[i] = {ops(v[i], a), ops(v[i], b), ops(v[i], c),
- ops(v[i], lab), ops(v[i], lbc), ops(v[i], lca),
- ops(v[i], labc)};
- }
- debug(vals);
- cout << fun(v, 0, 0, 0, 0, dp) << endl;
- }
- signed main() {
- // init_code();
- fast();
- int t = 1;
- cin >> t;
- while (t--) {
- solve();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment