# 題目: UVa 11633 - Food portion sizes
# 題目說明
大學學生餐廳不希望任何學生離開餐廳時沒吃飽
所以只要學生的肚子還餓，他就能免費拿到另一份餐點
為了節省時間，學生餐廳統一了每份餐點的份量，但這會導致浪費的發生
給兩個常數a及b，你需要找到a * x + b * y的最小值
x為浪費的餐點量y為學生領餐的次數
INPUT:
每筆資料第一行有一個整數N，代表學生的數量
下一行有兩個整數a與b
接下來有N個整數，代表每個學生吃的份量
當N = 0時結束程式
OUTPUT:
輸出a * x + b * y的最小值
如果為分數需要分開輸出
例如17.5輸出為35 / 2
# 解題方法
- 由於可能跑
1、2、3次，通分為6，所以先將所有輸入乘以6儲存，並找出最大值 - 窮舉所有符合條件的可能(不取餐超過3次)，依序計算
x、y次數 - 將最小的
a * x + b * y紀錄，最後輸出
# 參考程式碼
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int main()
{
// fast io
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int N, a, b, x;
while (cin >> N, N)
{
// init
vector<int> student;
int maxn = 0;
pair<int, int> minn = { INT_MAX, 1 };
// store data
cin >> a >> b;
for (int i = 0; i < N; ++i)
{
cin >> x;
student.emplace_back(x * 6);
maxn = max(maxn, x * 6);
}
// run all posible of n
for (int div = 1; div <= 3; ++div) for (auto& i : student)
{
int s1 = i / div;
int x = 0, y = 0;
if (s1 * 3 < maxn) continue;
for (auto& j : student)
{
int s2 = j;
while (s1 - s2 < 0) s2 -= s1, ++y;
x += (s1 - s2);
++y;
}
minn = min(minn, { x * a + y * b * 6, div });
}
auto& [i, j] = minn;
if (i % 6 == 0) cout << i / 6;
else cout << i * j / 6 << " / " << j;
cout << "\n";
}
return 0;
}