contest.cc.txt

Ulm大学2003-2004年竞赛题

// Problem   Fixed Partition Contest Management
// Algorithm Brute Force
// Runtime   O(m^n*n^2)
// Author    Walter Guttmann
// Date      22.02.2003

#include <cassert>
#include <cmath>
#include <fstream>
#include <iostream>

using namespace std;

ifstream in ("contest.in");

int main ()
{
  cout.setf(ios::fixed);
  cout.precision(2);
  for (int kase=1 ; ; kase++)
  {
    int m, n;
    in >> m >> n;
    if (n == 0 && m == 0) break;
    assert(1 <= m && m <= 3);
    assert(1 <= n && n <= 10);
    int bright[16];
    for (int h=1 ; h<=m ; h++)
    {
      in >> bright[h];
      assert(1 <= bright[h]);
    }
    // IF soltime[j][h] == 0 THEN problem j cannot be solved by member h
    // ELSE problem j requires time soltime[j][h] if solved by member h
    int soltime[64][16];
    for (int j=1 ; j<=n ; j++)
    {
      int k;
      in >> k;
      assert(1 <= k && k <= 10);
      int s[16], t[16];
      for (int i=1 ; i<=k ; i++)
      {
        in >> s[i] >> t[i];
        assert(1 <= s[i]);
        assert(1 <= t[i]);
      }
      for (int i=1 ; i<=k-1 ; i++)
        assert(s[i] < s[i+1]);
      for (int h=1 ; h<=m ; h++)
      {
        soltime[j][h] = 0;
        for (int i=1 ; i<=k-1 ; i++)
          if (s[i] <= bright[h] && bright[h] < s[i+1])
            soltime[j][h] = t[i];
        if (s[k] <= bright[h])
          soltime[j][h] = t[k];
      }
    }
    int minsumtime = 0, minassign[64], minptime[64];
    // try all m^n assignments of problems to team members
    int mn = 1;
    for (int j=1 ; j<=n ; j++)
      mn *= m;
    for (int q=0 ; q<mn ; q++)
    {
      // in this assignment problem j is assigned to member assign[j]
      int assign[64];
      for (int j=1,qq=q ; j<=n ; j++,qq/=m)
        assign[j] = 1 + qq%m;
      // all problems must be solvable by the assigned members
      bool valid = true;
      for (int j=1 ; j<=n ; j++)
        if (soltime[j][assign[j]] == 0)
          valid = false;
      if (!valid)
        continue;
      // for each member, problems with shorter solution times are solved first
      int sumtime = 0;
      int ptime[64];
      for (int j1=1 ; j1<=n ; j1++)
      {
        int h = assign[j1];
        ptime[j1] = 0;
        for (int j2=1 ; j2<=n ; j2++)
          if (assign[j2] == h)
            if (soltime[j2][h] < soltime[j1][h] ||
                soltime[j2][h] == soltime[j1][h] && j2 <= j1)
              ptime[j1] += soltime[j2][h];
        sumtime += ptime[j1];
      }
      if (minsumtime == 0 || sumtime < minsumtime)
      {
        minsumtime = sumtime;
        for (int j=1 ; j<=n ; j++)
        {
          minassign[j] = assign[j];
          minptime[j] = ptime[j];
        }
      }
    }
    double avgtime = (double) minsumtime / n;
    avgtime = floor(avgtime * 100.0 + 0.5) / 100.0;
    cout << "Case " << kase << endl;
    cout << "Average solution time = " << avgtime << endl;
    for (int j=1 ; j<=n ; j++)
      cout << "Problem " << j << " is solved by member " << minassign[j]
           << " from " << minptime[j]-soltime[j][minassign[j]]
           << " to " << minptime[j] << endl;
    cout << endl;
  }
  return 0;
}