算法題「坑爹的黑店」：最小找零優化與動態規劃/貪心解法

題目大意

飲料價格：礦泉水 150 分、可樂 200 分、橙汁 350 分。給 N 分（N≤10000），買任意組合飲料，找零最少（即最大花費不超過 N）。輸出最小找零。

錯誤貪心反例

先用 350 再 200 再 150：N=450 時買 350 剩 100，實際可買 3×150=450 找零 0。

正確解法：數學規律 / 三重循環

因價格公約數為 50，N≥300 時找零僅取決於 N%50。官方 O(1) 解：

if (n < 150) ans = n;
else if (n <= 200 || n >= 300) ans = n % 50;
else ans = n - 200; // 200 < n < 300 區間

通用三重循環（易理解）

int max = 0;
for (int i = n/350; i >= 0; i--)
  for (int j = (n-i*350)/200; j >= 0; j--)
    for (int k = (n-i*350-j*200)/150; k >= 0; k--)
      max = MAX(max, i*350 + j*200 + k*150);
printf("%d\n", n - max);

複雜度極低（N≤10000 時循環次數極少），AC 絕無問題。

測試樣例

Input:
2
900
250
Output:
0
50