#codeofduty 2011 c++ solution

codeofduty_solution.cpp

/*!
**\file   main.cc
**\author Matthieu Garrigues <matthieu.garrigues@googglemail.com>
**\date   Sat Jun 11 13:53:44 2011
**
**\brief  Solution of Code of Duty 2011
**
**
*/

#include <iostream>
#include <fstream>
#include <cmath>
#include <vector>
#include <cassert>
using namespace std;

/*!
** Compute sums[i] = v[0] + ... + v[i]
**
** \param v input vector
** \param sums result vector
*/
void sum(vector<unsigned>& v, vector<unsigned>& sums)
{
  assert(v.size() == sums.size());
  unsigned s = 0;
  for (unsigned i = 0; i < v.size(); i++)
  {
    s += v[i];
    sums[i] = s;
  }
}

/*!
** Solve the problem on v and output result in of.
**
** \param v input vector
** \param of output stream
*/
void solve(vector<unsigned>& v, ofstream& of)
{
  unsigned N = v.size();
  vector<unsigned> sums(N);

  // Compute sums[i] = v[0] + ... + v[i]
  sum(v, sums);

  // N must divide sums[N-1]
  if (sums[N-1] % N) // Check if a solution exists
  {
    of << "-1" << endl << endl;
    return;
  }

  // Reference value.
  unsigned vref = sums[N-1] / N;

  vector<vector<unsigned> > h; // history
  h.push_back(v);

  unsigned it = 0; // Iteration number

  int first = 0;
  int last = N-1;
  while (first < last) // While the solution is not found
  {
    // Compute sums[i] = v[0] + ... + v[i]
    sum(v, sums);

    // vector<unsigned> bkp = v; // Save v's state at previous 
    int next = 0;
    for (unsigned i = first; i <= last; i++)
    {
      if ((v[i] - next) == 0) // Nothing to move, continue.
      {
        next = 0;
        continue;
      }

      // Sum on the left
      unsigned sl = i == 0 ? 0 : (sums[i] - (v[i] - next));
      // Sum on the right
      unsigned sr = i == N-1 ? 0 : (sums[N-1] - sums[i]);

      next = 0;

      // If needed, pass one unit to one neighbors.
      if (sl < vref*i)
      {
        v[i - 1]++; // move one unit to the left
        v[i]--;
      }
      else if (sr < vref*(N-i-1))
      {
        v[i + 1]++; // move one unit to the right
        v[i]--;
        next = 1;
      }
    }
    while (first < N && v[first] == vref) first++;
    while (last > 0 && v[last] == vref) last--;

    h.push_back(v); // Fill history.
    it++;
  }

  // Output results
  of << it << endl;

  for (unsigned i = 0; i < h.size(); i++)
  {
    of << i << " : (" << h[i][0];
    for (unsigned j = 1; j < N; j++)
      of << ", " << h[i][j];
    of << ")" << endl;
  }
  of << endl;
}

int main(int argc, char* argv[])
{
  ifstream in("input.txt");
  ofstream of("output.txt");
  if (!in.good())
    cout << "Cannot open file input.txt" <<  endl;

  while (true)
  {
    unsigned N; in >> N; // Size of vector
    if (N == 0) return 0;

    vector<unsigned> v(N);
    for (unsigned i = 0; i < N; i++)
      in >> v[i]; // Read input vector
    solve(v, of);
  }

  return 0;
}