740-A. Alyona and copybooks

2021-03-18 12:55:12 +0800 CST Tags: number-theory

出處：https://codeforces.com/contest/740/problem/A
提交：https://codeforces.com/contest/740/submission/110277415

問題：給定 $n, a, b, c\in[1,10^9]$ 四個正整數，說明一次買 1 本、2 本、3 本書分別可以花費 a、b、c 元，已知目前有 n 本書，請問最少需要再花費多少錢買新書才能和那 n 本書湊成 4 的倍數？

解法：
一開始當然很直覺地先算出 n 除以 4 的餘數，再用 4 去減它就會得到新書數量的餘數 k。所以說，當 k = 4 的時候很明顯不用再買書，但是當 k = 1 的時候，可以買 1, 5, 9, … 本書；當 k = 2 的時候，可以買 2, 6, 10, … 本書；當 k = 3 的時候，可以買 3, 7, 11, … 本書，那麼在這些不同的 k 底下分別究竟要買多少本書才能最便宜呢？我們需要全部的數量都嘗試過嗎？這便是這題的考點，答案是不用！只要嘗試一部份就好。這個事實會成立的關鍵便在於下面這個 lemma：當你新買了 $x_0$ 套 1 本、$y_0$ 套 2 本、$z_0$ 套 3 本書，那麼所有其他滿足「$x\ge x_0$ 套 1 本、$y\ge y_0$ 套 2 本、$z\ge z_0$ 套 3 本」的買法都不會比較便宜。接下來就讓我們來一一分析不同的 k 底下只需要考慮哪些買法就好。

Case k=1:
1=1   ==> 之後都不能再用到 1，否則一定比這個貴。
5=2+3 ==> 之後都不能再同時用到 2 和 3，否則一定比這個貴。
9=3x3 ==> 之後都不能再只用到 3，否則一定比這個貴。 ==> 希望之後的數字能只用 2 達成，
但是呢這個願望不可能成真，因為 4 的倍數 + 1 不可能是 2 的倍數，所以往後的數字我們都不考慮。
==> 餘數為 1 的 case 我們只需要考慮 a、b+c、3c。

Case k=2:
2=2   ==> 之後都不能再用到 2，否則一定比這個貴。
 =1x2 ==> 之後都不能再用到兩個以上的 1，否則一定比這個貴。
6=3x2 ==> 之後都不能再用到兩個以上的 3，否則一定比這個貴。
 =1x3+3 (用到兩個以上的 1 不合法)
 =1x6 (用到兩個以上的 1 不合法)
之後 10 以上就不可能因為至多一個 1 和至多一個 3 只能湊出 4。
==> 餘數為 2 的 case 我們只需要考慮 b、2a、2c。

Case k=3:
3=3   ==> 之後都不能再用到 3，否則一定比這個貴。
 =1+2 ==> 之後都不能再同時用到 1 和 2，否則一定比這個貴。
 =1x3 ==> 之後都不能再用到三個以上的 1，否則一定比這個貴。
上面的條件隱含後面 (只能用至多 2 個 1) 或 (只能用任意個 2) 來組成。
但是至多 2 個 1 只能湊出 2，而 4 的倍數 + 3 也不可能是 2 的倍數，所以往後的數字我們都不考慮。
==> 餘數為 3 的 case 我們只需要考慮 c、a+b、3a。

實作：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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

int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
    long long n, a, b, c;
    cin >> n >> a >> b >> c;
    n = 4 - (n % 4);
    if (n == 1) cout << min({a, b+c, 3*c});
    else if (n == 2) cout << min({b, 2*a, 2*c});
    else if (n == 3) cout << min({c, a+b, 3*a});
    else cout << 0;
    return 0;
}

結果：