UVa 11633 Problem F: Food portion size
Problem F: Food portion size
http://uva.onlinejudge.org/external/116/11633.html
問題概要
学校に生徒がn人いる。
それぞれの生徒が食べたいご飯の量がきまっている。
ご飯は弁当で与えられる。
弁当はすべて同じ量である。
食べる量に達しないと生徒はさらに新しい弁当を食べる。
余った分は捨てる。
余った分をx、必要な弁当の数をyとしたとき、
ax+byを最小にせよ。
a, bは与えられる。
ただし、生徒は3個までしか弁当を食べれない。
解法
調べるべき値だけ調べる。
必要な弁当の数が変化するのは
すべての生徒に対して弁当の量が、その生徒の食べたい量の1/3, 1/2 1/1のときである。
それぞれの生徒に対して、この3通りがあるので3000通りを
決めて、それにたいしてax+byがどのようになるか。
すべての生徒の食べたい量を3個までで補えるか確認する。
ソース
#include<cstdlib> #include<cassert> #include<cstdio> #define REP(i,b,n) for(int i=b;i<(int)n;i++) #define rep(i,n) REP(i,0,n) using namespace std; const int INF = 1000000000; const int N = 1000; template<typename Integer> inline Integer GCD(Integer a, Integer b){ return b==0?a:GCD(b,a%b); } struct Rational{ int p,q; Rational():p(1),q(1){} Rational(int p, int q):p(p),q(q){} inline const Rational Simplify(){ int r = GCD(abs(p),abs(q)); p /= r; q /= r; return *this; } }; int main(){ int n; while(scanf("%d", &n) == 1){ if(n == 0)break; int mini = INF, a, b, t[N]; scanf("%d%d", &a, &b); rep(i, n){ scanf("%d", &t[i]); t[i] *= 6; } rep(i, n){ rep(j, 3){ int pSize = t[i] / (j+1); bool ok = true; int y = 0, x = 0; rep(k, n){ rep(num, 3){ if(pSize * (num+1) < t[k]){ if(num == 2)ok = false; continue; } else { x += (num+1)* pSize - t[k]; y += (num+1)*6; break; } } if(!ok)break; } if(!ok)continue; if(x * a + y * b < mini){ mini = x * a + y * b; } } } Rational ans(mini, 6); ans.Simplify(); printf("%d", ans.p); if(ans.q != 1){ printf(" / %d", ans.q); } printf("\n"); } return 0; }