GJC 2018 Q1A

'use strict';
// Use path PATH=bin\;F:\Python27\;F:\Python27\Scripts;C:\Windows\system32;C:\Windows;C:\Windows\System32\Wbem;F:\bin
// Run with node stdio.js < A-small.in
const assert = require('assert');
const fs = require('fs');

function err() {
  process.stderr.write(Array.prototype.join.call(arguments, ' ') + '\n');
}

let tok = (function () {
  let is_eof = false;
  let start = 0;
  let idx = 0;
  let did_last = false;
  let buffer = Buffer.alloc(1024*1024);
  return function (want_number) {
    // otherwise, read some, repeat
    do {
      // skip past initial delims
      while (start < idx && buffer[start] <= 32) {
        ++start;
      }
      // try to find valid string between start and idx, if so return
      for (let end=start; end < idx; end++) {
        let c = buffer[end];
        if (c <= 32) {
          if (want_number && buffer[start] >= 48 && buffer[start] < 58) {
            let r = 0;
            for (let ii = start; ii < end; ++ii) {
              r *= 10;
              r += buffer[ii] - 48;
            }
            start = end;
            return r;
          }
          let ret = buffer.toString('utf8', start, end);
          start = end;
          return want_number ? Number(ret) : ret;
        }
      }
      if (is_eof) {
        // must be last token, return it
        assert(!did_last);
        did_last = true;
        let ret = buffer.toString('utf8', start, idx);
        return want_number ? Number(ret) : ret;
      }
      // Need to read more
      if (idx >= buffer.length) {
        // buffer is full, shuffle to beginning of buffer
        assert(idx - start < start);
        buffer.copy(buffer, 0, start);
        idx -= start;
        start = 0;
      }
      try {
        let bytes_read = fs.readSync(process.stdin.fd, buffer, idx, buffer.length - idx);
        if (bytes_read) {
          idx += bytes_read;
        } else {
          is_eof = true;
        }
      } catch (e) {
        // this exception happens on Linux
        //is_eof = true;
      }
    } while (true);
  };
}());

function f() {
  let D = tok(true);
  let P = tok();
  let pow = 1;
  let powidx = 0;
  let sum = 0;
  let count = [0];
  let total_shoot = 0;
  for (let ii = 0; ii < P.length; ++ii) {
    if (P[ii] === 'C') {
      powidx++;
      count[powidx] = 0;
      pow *= 2;
    } else {
      total_shoot++;
      sum += pow;
      count[powidx]++;
    }
  }
  if (total_shoot > D) {
    return 'IMPOSSIBLE';
  }
  let r = 0;
  while (sum > D) {
    pow /= 2;
    if (count[powidx] * pow < sum - D) {
      // remove all
      sum -= count[powidx] * pow;
      count[powidx-1] += count[powidx];
      r += count[powidx];
    } else {
      // remove some
      return r + Math.ceil((sum - D) / pow);
    }
    powidx--;
  }
  return r;
}

function doit() {
  let N = tok(true);
  for (let ii = 0; ii < N; ++ii) {
    let r = f();
    console.log(`Case #${ii + 1}: ${r}`);
  }
}

doit();