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;
}