card_game.py

import sys

MOD = 1000000007

def main():
  for (i, (n, k, cards)) in enumerate(testcases()):
    print "Case #{0}: {1}".format(i+1, subsum(n, k, cards))

def testcases(cin=sys.stdin):
  m = int(cin.next())
  for _ in xrange(m):
    n, k = map(int, cin.next().split())
    cards = map(int, cin.next().split())
    yield (n, k, cards)

def subsum(n, k, cards):
  ans = 0
  cards.sort()
  for i in xrange(k-1, n):
    ans += cards[i] * choose(i, k-1)
    ans %= MOD
  return ans

MAX_S = 10000
FACTS = [1]
for i in xrange(1, 1+MAX_S):
  FACTS.append((FACTS[-1]*i) % MOD)

def choose(n, k):
  return (FACTS[n]*modInv(FACTS[k]*FACTS[n-k])) % MOD

def modInv(a):
  x, nx, b = 0, 1, MOD
  while a > 0:
    q = b // a
    nx, x = x-q*nx, nx
    a, b = b-q*a, a
  return x

if __name__ == "__main__": sys.exit(main())

dead_pixels.cpp

#include <iostream>
#include <vector>

using namespace std;

typedef vector<int> VI;

// so lazy! (64-bit req. to do this)

int main() {
  int nc; cin >> nc;
  for (int cNum = 1; cNum <= nc; ++cNum) {
    int w, h, p, q, n; cin >> w >> h >> p >> q >> n;
    int x, y, a, b, c, d; cin >> x >> y >> a >> b >> c >> d;

    vector<VI> screen(w+1, VI(h+1));

    for (int i = 0; i < n; ++i) {
      screen[x][y] = 1;
      int tx = (x*a + y*b + 1) % w;
      int ty = (x*c + y*d + 1) % h;
      x = tx; y = ty;
      }

    int pCount = 0;
    for (int i = w-1; i >= 0; --i)
      for (int j = h-1; j >= 0; --j) {
        screen[i][j] += screen[i+1][j] + screen[i][j+1] - screen[i+1][j+1];
        if ((i+p <= w) && (j+q <= h) && (screen[i][j] == screen[i+p][j] + screen[i][j+q] - screen[i+p][j+q]))
          ++pCount;
        }

    cout << "Case #" << cNum << ": " << pCount << '\n';
    }
  }

dead_pixels_lite.cpp

#include <iostream>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VP;

// use sentinels to simplify sweep?

int process(int h, int q, const map<int, int> &activeY) {
  int ret = 0, last = 0;
  for (map<int, int>::const_iterator i = activeY.begin(); i != activeY.end(); ++i) {
    ret += max(0, i->first-last-q+1);
    last = i->first+1;
    }
  ret += max(0, h-last-q+1);
  return ret;
  }

int main() {
  int nc; cin >> nc;
  for (int cNum = 1; cNum <= nc; ++cNum) {
    int w, h, p, q, n; cin >> w >> h >> p >> q >> n;
    int x, y, a, b, c, d; cin >> x >> y >> a >> b >> c >> d;

    VP dead(n); dead[0] = PII(x, y);
    for (int i = 1; i < n; ++i) {
      dead[i].first = (dead[i-1].first*a + dead[i-1].second*b + 1) % w;
      dead[i].second = (dead[i-1].first*c + dead[i-1].second*d + 1) % h;
      }

    sort(dead.begin(), dead.end()); // duplicates are OK

    map<int,int> activeY;
    VP::const_iterator rP = dead.begin();
    VP::const_iterator lP = dead.begin();
    int curL = 0;
    while ((rP != dead.end()) && (rP->first < curL+p)) {
      ++activeY[rP->second];
      ++rP;
      }

    int pCount = 0, curC = process(h, q, activeY);
    while ((rP != dead.end()) || ((lP != dead.end()) && (lP->first < w-p))) {
      int nxtLR = (rP != dead.end()) ? rP->first-p : w;
      int nxtLL = (lP != dead.end()) ? lP->first : w;
      int nxtL = min(nxtLR, nxtLL) + 1;

      pCount += curC*(nxtL-curL);
      curL = nxtL;
      while ((rP != dead.end()) && (rP->first < curL+p)) {
        ++activeY[rP->second];
        ++rP;
        }
      while ((lP != dead.end()) && (lP->first < curL)) {
        --activeY[lP->second];
        if (!activeY[lP->second]) activeY.erase(lP->second);
        ++lP;
        }
      curC = process(h, q, activeY);
      }

    pCount += curC*(w-p+1-curL);

    cout << "Case #" << cNum << ": " << pCount << '\n';
    }
  }

security.cpp

#include <iostream>
#include <string>
#include <vector>
#include <queue>

using namespace std;

typedef vector<int> VI;

bool augment(int m, const vector<VI> &edgeL, vector<int> &match) {
  queue<int> q;
  VI pred(2*m, -1);

  for (int i = 0; i < m; ++i)
    if (match[i] == -1)
      q.push(i);

  while (!q.empty()) {
    int qL = q.size();
    while (qL--) {
      int t = q.front(); q.pop();
      for (VI::const_iterator i = edgeL[t].begin(); i != edgeL[t].end(); ++i)
        if (pred[m+*i] == -1) {
          pred[m+*i] = t;
          q.push(*i);
          }
      }
  
    qL = q.size();
    while (qL--) {
      int t = q.front(); q.pop();
      if (match[m+t] == -1) {
        int v = m+t;
        while (v != -1) {
          match[v] = pred[v];
          match[pred[v]] = v;
          v = pred[pred[v]];
          }
        return true;
        }
      else {
        pred[match[m+t]] = m+t;
        q.push(match[m+t]);
        }
      }
    }
  
  return false;
  }

int bipart(int m, const vector<VI> &edgeL) {
  vector<int> match(2*m, -1);
  int mSize = 0;
  while ((mSize < m) && augment(m, edgeL, match)) ++mSize;
  return mSize;
  }

bool compat(int m, const string &k1, const string &k2, int a, int b) {
  int sL = k1.size() / m;
  for (int k = 0; k < sL; ++k) {
    int i = sL*a + k, j = sL*b + k;
    if ((k1[i] != '?') && (k2[j] != '?') && (k1[i] != k2[j]))
      return false;
    }
  return true;
  }

string solve(int m, string k1, const string &k2) {
  vector<VI> edgeL(m);

  for (int i = 0; i < m; ++i)
    for (int j = 0; j < m; ++j)
      if (compat(m, k1, k2, i, j))
        edgeL[i].push_back(j);

  if (bipart(m, edgeL) != m) return "IMPOSSIBLE";

  int sL = k1.size() / m;
  for (int i = 0; i < m; ++i)
    for (int k = 0; k < sL; ++k)
      if (k1[sL*i+k] == '?') {
        char &c = k1[sL*i+k];
        VI pEdge = edgeL[i];
        for (c = 'a'; c <= 'f'; ++c) {
          edgeL[i].clear();
          for (VI::const_iterator j = pEdge.begin(); j != pEdge.end(); ++j)
            if (compat(m, k1, k2, i, *j))
              edgeL[i].push_back(*j);
          if (bipart(m, edgeL) == m) break;
          }
        }

  return k1;
  }

int main() {
  int nc; cin >> nc;
  for (int cNum = 1; cNum <= nc; ++cNum) {
    int m; cin >> m;
    string k1, k2; cin >> k1 >> k2;

    cout << "Case #" << cNum << ": " << solve(m, k1, k2) << '\n';
    }
  }