Round 2 Problem B. World Cup 2010 small

Google Code Jam Round 1 は最高1008位でした。

あーあRound2へは進めないな・・・と思ったら、おめでとうメールが。
確認するとちょうど1000位になってるよ!

よくわからないけど、Round2に進めることになってしまったので、練習練習。


http://code.google.com/codejam/contest/dashboard?c=635102#s=p1
smallは簡単。
最初の方の試合は全部見ない。試合ごとに後何回見逃せるかを計算して、結果が0になる試合は見なきゃいけないので見る。

Large問題は始めの試合を観ておいたほうがコストが低い、と言う事があり得るから、このアルゴリズムじゃ無理。他の人のソースを見て勉強します・・・。

#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <vector>

using namespace std;

#define rep(i,a,b) for(int i=a;i<=b;i++)

int P;
int M[2000];
int prices[15][2000];

int cost(int 

int solve(int no)
{
	cin >> P;
	
	int teams = 1<<P;
	rep(i, 0, teams-1) cin >> M[i];
	rep(i, 1, P) {
		rep(j,0, (teams>>i) - 1) cin >> prices[i-1][j];
	}
	
	
	int cost = 0;
	rep(i, 1, P) {
		rep(j, 0, (teams>>i) - 1) {
			M[j] = min(M[j*2], M[j*2+1]);
			if(M[j]==0) cost++;
			else M[j]--;
		}
	}
	cout << "Case #" << no << ": " << cost() << endl;
}

int main()
{
	int T;
	cin >> T;
	rep(no, 1, T) {
		solve(no);
	}
	return 0;
}