1c_2009_c.js

#!/usr/bin/env node
var util = require('util');

process.stdin.resume();
process.stdin.setEncoding('utf8');

var chunks = [],
    cache = {};

function cache_key(prisoners) {
  return prisoners[0] + ',' + prisoners[prisoners.length - 1];
}

function parse_base10_int(v) {
  return parseInt(v, 10);
}

function release_prisoners(prisoners, root, indices) {
  var cell_count = prisoners.length,
      indices = indices || [0, cell_count - 1],
      candidates = [],
      key = cache_key(indices),
      cached = cache[key],
      val;

  if (cached) {
    return cached;
  }

  if (indices[1] - indices[0] === 1) {
    return 0;
  }

  for (var i = indices[0] + 1, l = indices[1]; i < l; i++) {
    candidates.push(
      prisoners[indices[1]] - prisoners[indices[0]] - 2 +
        release_prisoners(prisoners, false, [indices[0], i]) +
        release_prisoners(prisoners, false, [i, indices[1]])
    );
  }

  val = Math.min.apply(this, candidates);
  cache[key] = val;

  return val;
}

function end_trigger() {
  var lines = chunks.join('').split('\n'),
      line_count = parseInt(lines[0], 10),
      line_i = 1,
      cell_info, prisoners_to_release;

  for (var i = 0; i < line_count; i++) {
    cell_info = lines[line_i].split(' ').map(parse_base10_int);
    line_i++
    prisoners_to_release = lines[line_i].split(' ').map(parse_base10_int);
    line_i++

    prisoners_to_release.unshift(0);
    prisoners_to_release.push(cell_info[0] + 1)

    cache = {}

    console.log('Case #%d: %d', i + 1, release_prisoners(
      prisoners_to_release,
      true
    ));
  }
}

process.stdin.on('data', function(chunk) {
  chunks.push(chunk)
});

process.stdin.on('end', end_trigger);

// real 0m5.663s
// user 0m5.635s
// sys  0m0.062s