Desafios de Programação no Verão de 2011 - Prova 12 - Individual

POS	Competidor	Resultado	Pontuação	A	B	C	D	E	F	G	H	I	J
1	walter erquinigo	6 (527)	99	+0		+0	+1	+0		-3		+1	+0
2	daniel soncco	6 (1031)	97	+0			+4	+2	+2	+1		+0
3	Felipe Abella	5 (637)	95	+1		+1		+0		-1		+0	+1
4	Adriana Libório	4 (319)	93	+0				+0				+0	+0
5	Jesus Alejandro	4 (391)	91	+0				+0	+0				+1
6	Eric Destefanis	4 (510)	89	+0			-3	+0			+6		+2
7	Eduardo Ribas	4 (586)	87	+1	+8			+1					+1
8	Arthur	3 (93)	85	+0				+0				+0	-1
9	Renato Parente	3 (173)	83	+0				+2				+0	-2
10	Thiago Sonego Goulart	3 (201)	81	+0	+1			+0				-1	-3
11	Davi Duarte Pinheiro	3 (222)	79	+0		+0		+0
12	Rafael Brandão	3 (238)	77	+0				+0				+0
13	Filipe Martins	3 (245)	75	+2			-1	+0				+0	-7
14	Guilherme Souza	3 (291)	73	+2	-2			+0				+2
15	Gaston Ingaramo	3 (303)	71	+0				+0					+2
16	Leonardo Inácio	3 (346)	69	+0		+1		+0
17	Daniel Ribeiro Moreira	3 (350)	67	+0			+0	+1
18	Andre Hahn	3 (412)	65	+0		+1		+4					-2
19	Igor R. de Assis	3 (420)	63	+0				+1				+1	-5
20	Tiago Madeira	3 (466)	61	+0				+0				+3
21	Cesar Gamboa	3 (550)	59	+2			+3	+1
22	Renato Ferreira	2 (96)	57	+0		-1		+0					-2
23	Felipe Menezes Machado	2 (96)	55	+0				+0
24	Leonardo Marchetti	2 (101)	53	+0				+0
25	Pedro Veras	2 (134)	51	+0				+0				-4
26	Renan Ferraz Pires	2 (142)	49	+0				+0
27	gustavo pacianotto gouveia	2 (203)	47	+0				+2		-4
28	Ricardo Oliveira	2 (214)	45	+0		-1		+0
29	Pablo Pinheiro	2 (221)	43	+1				+1				-2
30	Leonardo Martinez	2 (226)	41	+0				+0					-5
31	Matias Daniel Tealdi	2 (271)	39	+1				+0					-2
32	Luiz Afonso	2 (297)	37	+0		-3		+2
33	Natan Costa Lima	2 (308)	35	+1				+1					-7
34	Igor Ramos	2 (314)	33	+0				+4				-1
35	Ricardo Hahn	2 (366)	31	+3				+0
36	Douglas Santos	2 (422)	29			+2		+4
37	Phyllipe Cesar	2 (443)	27	+5				+5				-2
38	Cesar Kawakami	2 (445)	25	+5			+0
39	Atol Fortin	1 (19)	23	+0				-3
40	Vinicius Flores Zambaldi	1 (61)	21	+0				-1
46	Caique Porto Lira	1 (267)	9	+2
46	Vinicius Ruoso	0 (0)	9	-7				-2
46	Gabriel Luís Mello Dalalio	0 (0)	9
46	Paulo Costa	0 (0)	9
46	Leonardo Flores Zambaldi	0 (0)	9
46	Alex Alves da Paixão	0 (0)	9
46	Nicolas Gumiel	0 (0)	9
46	Victor Hugo Paredes Mora	0 (0)	9	-1
46	Edwin Macelo Guzman Buezo	0 (0)	9	-1
46	Victor Jatobá	0 (0)	9											</div>

Vídeo: Discussão sobre os problemas

Algumas soluções dos competidores

Antimonotonicity (por Renato Ferreira)

#include <cstdio>
#include <algorithm>

using namespace std;

const int MAX_N = 30005;

int tree_big[MAX_N], tree_small[MAX_N];
int val[MAX_N];

int bit_get(int id, int tree[]) {
	int ans = 0;
	while (id > 0) {
		ans = max(ans, tree[id]);
		id -= (id & -id);
	}
	return ans;
}

void bit_update(int id, int val, int tree[]) {
	while (id < MAX_N) {
		tree[id] = max(tree[id], val);
		id += (id & -id);
	}
}

int main() {
	int t; scanf("%d", &t);
	while (t--) {
		int n; scanf("%d", &n);
		for (int i = 0; i < n; i++)
			scanf("%d", &val[i]);

		fill(tree_big, tree_big + MAX_N, 0);
		fill(tree_small, tree_small + MAX_N, 0);

		for (int i = n - 1; i >= 0; i--) {
			//i big
			bit_update(n - val[i] + 1, bit_get(val[i], tree_small) + 1, tree_big);

			//i small
			bit_update(val[i], bit_get(n - val[i], tree_big) + 1, tree_small);
		}

		printf("%d\n", bit_get(n - 1 + 1, tree_big));
	}

	return 0;
}

O Problema da Parada (por Thiago Sonego Goulart)

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <cassert>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <algorithm>
#include <utility>

using namespace std;

#define MOD 1000

struct Cmd {
	string cmd, op1, op2;
	int jump;
	Cmd(string a, string b = "", string c = "") {
		cmd = a, op1 = b, op2 = c;
		jump = 0;
	}
};

int stoi(string s) {
	int ans;
	istringstream iss(s);
	iss >> ans;
	return ans;
}

void fix(int &r) {
	r = ((r % MOD) + MOD) % MOD;
}

#define R(s) r[stoi((s).substr(1))]
#define OP(s) ((s[0] == 'R') ? R(s) : stoi(s))

vector <Cmd> v;
int visited[MOD], inuse[MOD], ret[MOD], ans = 0;

bool calc(int input) {
	int r[10];
	int pc = 0;
	
	if (inuse[input]) {
		return false;
	}
	
	if (visited[input]) {
		ans = ret[input];
		return true;
	}
	
	visited[input] = 1;
	inuse[input] = 1;
	
	memset(r,0,sizeof(r));
	r[0] = input;
	
	while (true) {
		if (v[pc].cmd == "MOV") R(v[pc].op1) = OP(v[pc].op2);
		else if (v[pc].cmd == "ADD") R(v[pc].op1) += OP(v[pc].op2), fix(R(v[pc].op1));
		else if (v[pc].cmd == "SUB") R(v[pc].op1) -= OP(v[pc].op2), fix(R(v[pc].op1));
		else if (v[pc].cmd == "MUL") R(v[pc].op1) *= OP(v[pc].op2), fix(R(v[pc].op1));
		else if (v[pc].cmd == "DIV") {
			if (!OP(v[pc].op2)) R(v[pc].op1) = 0;
			else R(v[pc].op1) /= OP(v[pc].op2), fix(R(v[pc].op1));
		}
		else if (v[pc].cmd == "MOD") {
			if (!OP(v[pc].op2)) R(v[pc].op1) = 0;
			else R(v[pc].op1) %= OP(v[pc].op2), fix(R(v[pc].op1));
		}
		else if (v[pc].cmd == "IFEQ") {if (OP(v[pc].op1) != OP(v[pc].op2)) pc = v[pc].jump;}
		else if (v[pc].cmd == "IFNEQ") {if (OP(v[pc].op1) == OP(v[pc].op2)) pc = v[pc].jump;}
		else if (v[pc].cmd == "IFG") {if (OP(v[pc].op1) <= OP(v[pc].op2)) pc = v[pc].jump;}
		else if (v[pc].cmd == "IFL") {if (OP(v[pc].op1) >= OP(v[pc].op2)) pc = v[pc].jump;}
		else if (v[pc].cmd == "IFGE") {if (OP(v[pc].op1) < OP(v[pc].op2)) pc = v[pc].jump;}
		else if (v[pc].cmd == "IFLE") {if (OP(v[pc].op1) > OP(v[pc].op2)) pc = v[pc].jump;}
		else if (v[pc].cmd == "ENDIF") {} // nothing
		else if (v[pc].cmd == "RET") {
			r[9] = OP(v[pc].op1);
			break;
		}
		else if (v[pc].cmd == "CALL") {
			if (!calc(OP(v[pc].op1))) {
				return false;
			}
			r[9] = ans;
		}
		else {
			cout << v[pc].cmd << endl;
			assert(0);
		}
		pc++;
	}
	
	ans = r[9];
	inuse[input] = 0;
	ret[input] = ans;
	
	return true;
}

int main () {
	int l, n;
	
	while (scanf("%d %d ",&l,&n) == 2 && l) {
		char cmd[10], op1[10], op2[10];
		
		v.clear();
		
		for (int i=0; i < l; i++) {
			scanf("%s ",cmd);
			if (*cmd == 'E') {
				v.push_back(Cmd(cmd));
			}
			else if (*cmd == 'C' || *cmd == 'R') {
				scanf("%s ",op1);
				v.push_back(Cmd(cmd,op1));
			}
			else {
				scanf("%[^,],%s ",op1,op2);
				v.push_back(Cmd(cmd,op1,op2));
			}
		}
		
		for (int i=0; i < v.size(); i++) {
			if (v[i].cmd[0] == 'I') {
				int j, d;
				for (j=i+1,d=1; true; j++) {
					if (v[j].cmd[0] == 'I') d++;
					if (v[j].cmd[0] == 'E') d--;
					if (v[j].cmd[0] == 'E' && d == 0) break;
				}
				v[i].jump = j;
			}
		}
		
		memset(visited,0,sizeof(visited));
		memset(inuse,0,sizeof(inuse));
		
		if (!calc(n)) {
			puts("*");
		}
		else {
			printf("%d\n",ans);
		}
	}
	
	return 0;
}

Random Route (por Renato Ferreira)

#include <cstdio>
#include <map>
#include <string>
#include <algorithm>
#include <iostream>
#include <climits>
#include <vector>

#define INF (INT_MAX / 3)

using namespace std;

const int MAX_N = 55;

int get_vert(map < string, int > &vert_id, const string &s, int &n) {
	if (!vert_id.count(s))
		vert_id[s] = n++;
	return vert_id[s];
}

int main() {
	//ios_base::sync_with_stdio(false);

	int tests; scanf("%d", &tests);
	for (int test = 1; test <= tests; test++) {
		int n = 0, m;
		string source;
		cin >> m >> source;

		map < string, int > vert_id;
		int adj[MAX_N][MAX_N];
		fill(*adj, *adj + MAX_N*MAX_N, INF);
		
		vector < pair < pair < int, int >, int > > edges;

		get_vert(vert_id, source, n);

		string name[MAX_N];

		for (int i = 0; i < m; i++) {
			string a, b;
			int c;
			cin >> a >> b >> c;

			int u = get_vert(vert_id, a, n);
			int v = get_vert(vert_id, b, n);

			name[u] = a;
			name[v] = b;

			adj[u][v] = min(adj[u][v], c);
			edges.push_back(make_pair(make_pair(u, v), c));
		}

		int dist[MAX_N][MAX_N];
		for (int i = 0; i < MAX_N; i++) for (int j = 0; j < MAX_N; j++)
			dist[i][j] = adj[i][j];
		for (int i = 0; i < MAX_N; i++)
			dist[i][i] = 0;

		for (int k = 0; k < n; k++) for (int i = 0; i < n; i++) for (int j = 0; j < n; j++)
			dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

		double ways[MAX_N][MAX_N];
		fill(*ways, *ways + MAX_N*MAX_N, 0);

		for (int e = 0; e < m; e++) {
			int u = edges[e].first.first;
			int v = edges[e].first.second;
			int c = edges[e].second;
			if (dist[u][v] == c)
				ways[u][v]++;
		}

		for (int k = 0; k < n; k++) for (int i = 0; i < n; i++) for (int j = 0; j < n; j++)
			if (dist[i][j] == dist[i][k] + dist[k][j])
				ways[i][j] += ways[i][k] * ways[k][j];

		for (int i = 0; i < n; i++)
			ways[i][i] = 1;

		int nreach = 0;
		for (int u = 0; u < n; u++)
			nreach += (dist[0][u] < INF);

		double prob[MAX_N];
		fill(prob, prob + MAX_N, 0);
		for (int dest = 0; dest < n; dest++) if (dist[0][dest] < INF) {
			for (int e = 0; e < m; e++) {
				int u = edges[e].first.first;
				int v = edges[e].first.second;
				int c = edges[e].second;
				if (dist[0][dest] == dist[0][u] + c + dist[v][dest]) {
					/*
					printf("dest %s usando %s,%s (total %d)\n", name[dest].c_str(), name[u].c_str(), name[v].c_str(), dist[0][dest]);
					printf("ways[0][%s] = %.1f, ways[%s][%s] = %.1f, ways[0][%s] = %.1f, nreach = %d\n", 
							name[u].c_str(), ways[0][u], name[v].c_str(), name[dest].c_str(), ways[v][dest], 
							name[dest].c_str(), ways[0][dest], nreach);
					*/
					prob[e] += ways[0][u] * ways[v][dest] / ways[0][dest] / (double) (nreach - 1);
				}
			}
		}

		printf("Case #%d:", test);
		for (int e = 0; e < m; e++)
			printf(" %.7f", prob[e]);
		printf("\n");
	}

	return 0;
}

Stone Game Strategist (por Felipe Abella)

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <utility>

#define MAXN 64

using namespace std;

int list[MAXN], diff[MAXN];

int main(int argc, char ** argv)
{
	while (scanf("%d", &list[0]) == 1) {
		int n = 1;
		while (scanf("%d", &list[n]), list[n])
			n++;

		diff[0] = list[0];
		for (int i = 1; i < n; i++)
			diff[i] = list[i] - list[i-1];

		int cheeseor = 0;

		for (int i = 0; i < n; i++)
			if ((i%2) == ((n-1)%2))
				cheeseor ^= diff[i];

		if (cheeseor == 0)
			printf("YOU LOSE\n");
		else {
			pair <int, int> sol = make_pair(100000000, 100000000);
			for (int i = 0; i < n; i++)
				for (int v = 1; v <= list[i] && (i == 0 || list[i]-v >= list[i-1]); v++) {
					if ((i%2) == ((n-1)%2))
						cheeseor ^= diff[i];
					if (((i+1)%2) == ((n-1)%2) && i+1 < n)
						cheeseor ^= diff[i+1];
					if ((i%2) == ((n-1)%2))
						cheeseor ^= diff[i]-v;
					if (((i+1)%2) == ((n-1)%2) && i+1 < n)
						cheeseor ^= diff[i+1]+v;

					if (cheeseor == 0)
						sol = min(sol, make_pair(v, i));

					if (((i+1)%2) == ((n-1)%2) && i+1 < n)
						cheeseor ^= diff[i+1]+v;
					if ((i%2) == ((n-1)%2))
						cheeseor ^= diff[i]-v;
					if (((i+1)%2) == ((n-1)%2) && i+1 < n)
						cheeseor ^= diff[i+1];
					if ((i%2) == ((n-1)%2))
						cheeseor ^= diff[i];
				}

			printf("TAKE %d STONES FROM PILE %d\n", sol.first, sol.second);
		}
	}

	return 0;
}

Power Strings (por Renato Ferreira)

#include <cstdio>
#include <string>
#include <algorithm>
#include <cstring>

using namespace std;

const int MAX_N = 1000005;

char buffer[MAX_N];
string pattern, tmp;

int main() {
	while (scanf("%s", buffer) == 1) {
		if (buffer[0] == '.')
			break;

		pattern = "";
		pattern += buffer[0];
		int times = 0, pos = 0;

		int len = strlen(buffer);
		for (int i = 1; i < len; i++) {
//			printf("pattern %s pos %d times %d\n", pattern.c_str(), pos, times);

			if (pos == (int) pattern.size()) {
				times++;
				pos = 0;
			}

			if (buffer[i] == pattern[pos]) {
				pos++;
			}
			else {
				tmp = pattern;
				for (int j = 0; j < times; j++)
					pattern += tmp;
				pattern += buffer[i];
				pos = 0;
				times = 0;
			}
		}

		if (pos != (int) pattern.size()) {
			printf("1\n");
		}
		else {
			printf("%d\n", times + 2);
		}
	}

	return 0;
}

Ordenando o Trem (por Jesus Alejandro)

#include <vector>
#include <string>
#include <string.h>
#include <algorithm>
#include <sstream>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <bitset>
#include <cstdio>
#include <assert.h>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cfloat>
#include <numeric>
#include <iostream>
 
using namespace std;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define M 80*81
#define N 80*81

using namespace std;
long long modulo = 1000003;

long long factorial[1000003];


///TEOREMA DE LUCAS DESCOMPOSICION
// Para Sacar Combinatoria con modulo p, donde p es primo
long long lucas(long long n){
	if( n==0 ) return 1;
	
	long long res = lucas(n/modulo);
	res= (res * factorial[n%modulo]) % modulo;
	
	if( (n/modulo)%2==1 )
	     res = modulo-res;
	     
	return res;
}



long long powmod( long long b,  long long p, long long modulo )
{
    long long r = 1;
    for( long long i = ( 1LL << 32 ); i; i >>= 1 )
    {
        r *= r; r %= modulo;
        if( p & i ) { r *= b; r %= modulo; }
    }
    return ( long long)r;
}


long long coeficiente(long long n ){
	long long res = 0;
	while( n >0 ) {
	    n/=modulo, res+= n;
	   // cout<<n<<endl;
	    }
	return res;
}


int main(){
    long long n;
    
	factorial[0] = 1;
	for(int i=1;i<modulo;i++) 
	    factorial[i]=factorial[i-1]*i%modulo;
	
	long long dosn,ene,ene1;
	long long res;
	
	while( scanf("%lld",&n)==1 ){
	    //formado cerrada del catalan
		ene=n;
		ene1 = n+1;
		dosn=2*n;
		
		if( coeficiente(dosn)>coeficiente(ene)+coeficiente(ene1) )
        	printf("0\n");
		else{
			long long aux1 = lucas(dosn);
			//cout<<aux1<<endl;
			long long  aux2= lucas(ene) * lucas(ene1) % modulo;
			//inverso del modulo
			aux2 = powmod(aux2,modulo-2,modulo);
			//cout<<aux2<<endl;
		    res = aux1*aux2 % modulo;
			printf("%lld\n",res);
		}
	}

return 0;
}

Abelian Groups (por daniel soncco)

#include <iostream> 
#include <algorithm>
#include <vector>
#include <cstdio>
#include <cstring>
#include <sstream>
#include <string>
#include <iomanip>
#include <cmath>
#include <set>
#include <map>
#include <queue>


#define ll long long
#define f(i,x,y) for(int i = x; i < y; i++ )
#define fd(i,x,y) for(int i = x; i>=y; i-- )
#define all(v) (v).begin(), (v).end()
#define clr(A,x) memset( A,x,sizeof(x) )
#define vint vector<long long>
#define poner push_back
#define oo (1<<30)
#define MAX 1000005
using namespace std;

int part[] = { 1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176, 231, 297, 385, 490, 627, 792, 1002, 1255, 1575, 1958, 2436, 3010, 3718, 4565, 5604, 6842, 8349, 10143, 12310, 14883, 17977, 21637, 26015, 31185, 37338, 44583, 53174, 63261, 75175, 89134};

int isp[MAX];
int p[MAX];
int dd[MAX];

int main(){
//	cout <<part[40];
	memset(dd, -1, sizeof dd);
	for(int i = 2; i * i < MAX; i++)
		if(dd[i] == -1)
			for(int j = i * i; j < MAX; j += i)
				dd[j] = i;
	
	int sz = 0;
	f(i,0,MAX) isp[i] = 1;
	
	f(i,2,MAX)if( isp[i] ){	
		for(ll j = (ll)i*i; j<MAX;j+=i ) isp[j] = 0;
		p[sz++] = i; 
	}
//	puts("as");
//	f(i,0,20) cout << p[i] << " "; cout << endl; cout << sz<<endl;
	
	ll n; cin >> n;
	ll res = 1;
	f(i,0,sz){
		int ind = 0;
		while( n%p[i]==0 ) n/=p[i], ind++;
		res*= part[ind];
	}
	cout << res << endl;
	
	
	
}

Hexagon Game (por Eric Destefanis)

#include <sstream>
#include <cstdio> 
#include <queue>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <cstring>
#include <utility>
#include <iomanip>
#include <iostream>
#include <cmath>
#include <iomanip>
#include <string>
#include <map>
#include <deque>
#include <set> 



using namespace std;
#define ll long long
#define PB push_back
#define MP make_pair
#define MOD 1000000009LL
#define MM 7000
#define REP(j, N) for( int j = 0 ; j < (N) ; j ++ )
int N = 5, INF = 999999999;
int m[80][80];
int restarfil[80], sumarcol[80];
int afil[80] , acol[80];

void augment()
{
	int visfil[N], fromcol[N], mincol[N];
	queue<int> q;
	REP(j, N) fromcol[j] = -1, mincol[j] = INF;
	REP(i, N)
	{
		visfil[i] = 0;
		if( afil[i] == -1 ) q.push(i), visfil[i] = 1;
	}
	for(;;)
	{
		while(!q.empty())
		{
			int i = q.front(); q.pop();
			REP(j,N)
			{
				if( m[i][j] - restarfil[i]+sumarcol[j] == 0)
				{
					if( acol[j] == -1 )
					{
						while(afil[i] != -1 )
						{
							int prev = afil[i];
							afil[i] = j; acol[j] = i;
							j = prev; i = fromcol[j];
						}
						afil[i] = j; acol[j] = i;
						return;
					}else if( !visfil[acol[j]] )
					{
						fromcol[j] = i;
						q.push(acol[j]);
						visfil[acol[j]] = 1;
					}
				}else {
					mincol[j] = min( mincol[j], m[i][j]-restarfil[i]+sumarcol[j] );
				}
			}
		}
		int mini = INF;
		REP(j,N) if( fromcol[j] == -1 ) mini = min( mini, mincol[j] );
		REP(i, N) if( visfil[i]) restarfil[i] += mini;
		REP(j, N) if( fromcol[j] != -1 ) sumarcol[j] += mini;
		REP(j, N) if( fromcol[j] == -1 )
		{
			mincol[j] -= mini;
			if( mincol[j] == 0 )
			{
				REP(i, N) if( visfil[i] && m[i][j] - restarfil[i]+sumarcol[j] == 0 )
				{
					if( acol[j] == -1 )
					{
						while( afil[i] != -1 )
						{	
							int prev = afil[i];
							afil[i] = j; acol[j] = i;
							j = prev; i = fromcol[j];
						}
						afil[i] = j; acol[j] = i;
						return;
					}else if( !visfil[acol[j]]) 
					{
						fromcol[j] = i;
						q.push(acol[j]);
						visfil[acol[j]] = 1;
						
					}
					break;
				}
			}
		}
	}
}

int hungarian()
{
	REP(i, N)afil[i] = -1, restarfil[i] = INF;
	REP(j, N) acol[j] = -1, sumarcol[j] = 0;
	REP(i, N) REP(j, N) restarfil[i] = min( restarfil[i], m[i][j] );
	REP(i, N) augment();
	int rr = 0;
	REP(i, N) rr += m[i][afil[i]];
	return rr;
}

int cost[80];
int place[80][80];
int lugar[20000][2];
vector<int> pos;
int ok[80][80];

int res;

int seen[80][80];
int dr[6] = {1, 1, 0, -1, -1, 0};
int dc[6] = {0, 1, 1, 0, -1, -1};

void bfs(int node)
{
	int p = pos[node];
	memset(seen, 0x3f, sizeof(seen));
	queue<pair<int,int> > Q;
	Q.push(MP(lugar[p][0], lugar[p][1]));
	seen[lugar[p][0]][lugar[p][1]] = 0;
	
	
	if(  ok[lugar[p][0]][lugar[p][1]] >= 0 )
	{
		m[node][ok[lugar[p][0]][lugar[p][1]]] = 0;
	}
	int k;
	while( Q.size() )
	{
		int r =  Q.front().first, c = Q.front().second;Q.pop();
		
		if( ok[r][c] >= 0 )
		{
//			cout << " HOALNDA " << endl;
//			cout << r << "  " << c << "  " << seen[r][c] << endl;
			m[node][ok[r][c]] = seen[r][c];
		}
		
		for( k = 0 ; k < 6 ; k ++ )
		{
			int rr = dr[k] + r;
			int cc = dc[k] + c;
			if( rr < 0 or cc < 0 or place[rr][cc] < 0 ) continue;
			if( seen[rr][cc] <= seen[r][c] + cost[node] ) continue;
			seen[rr][cc] = seen[r][c] + cost[node];
			Q.push(MP(rr,cc));
		}
	}
}



void doit()
{
	for( int i = 0 ; i < N ; i ++ )	
		bfs(i);

	int val = hungarian();
//	cout << val << endl;
	res = min( res, val );
}





int main()
{
	int i,j ,k;
	int casos;
	string s;
	getline(cin, s);
	istringstream iss(s);

	iss >> casos;
	for( int h = 0 ; h < casos ;h  ++ )
	{
		getline(cin, s);
		istringstream iss(s);
		pos.clear();
		while( iss >> k )
		{
			k--;

			pos.PB(k);
		}
		N = pos.size();
		getline(cin, s);
		istringstream iss2 ( s );
		int paso= 0;
		while( iss2 >> k )
		{
			cost[paso] = k;
			paso ++;
		}
//		for( i = 0 ; i < N ; i ++ ) cout << cost[i] << endl;
		int ind = 0;
		memset(place, -1, sizeof(place));

		for( i = (N+1)/2 -1 ; i >= 0 ; i -- )
		{
			for( int c = 0 ; c < (N+1)-1-i ; c ++ )
			{
				lugar[ind][0] = i+c;
				lugar[ind][1] = c;
				place[i+c][c] = ind++;
				
			}
		}
		for( i = 1 ; i <= (N+1)/2-1 ; i  ++ )
		{
			for( int c = 0 ; c < (N+1)-1-i ; c ++ )
			{
				lugar[ind][0] = c;
				lugar[ind][1] = c+i;
				place[c][c+i] = ind++;
			}
		}
		/*
		for( i = 0 ; i < 10 ; i ++ ) 
		{
			for( j = 0 ; j < 10 ; j ++ )
				cout << place[i][j] << " " ; cout << endl;
		}*/
		
		// probamos la primer diagonal...
		res = INF;
		memset(ok, -1, sizeof(ok));
		for( i = 0 ; i < N ; i ++ ) ok[i][i] = i;
		doit(); 
		memset(ok, -1, sizeof(ok));
		for( i = 0 ; i < N ; i ++ )
			ok[i][(N+1)/2-1] = i;
		doit();
		memset(ok, -1, sizeof(ok));
		for( i = 0 ; i < N ; i ++ )
			ok[(N+1)/2-1][i] = i;
		doit();
		cout << "Case #" << h+1 << ": " << res << endl;
	}
	return 0;
}

GCD Extreme (II) (por Felipe Abella)

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>

#define MAXN 4000010

typedef long long lint;

using namespace std;

//vector <int> div[MAXN];
int prime[MAXN];
lint phi[MAXN], phisum[MAXN], diff[MAXN], ret[MAXN];

int main(int argc, char ** argv)
{
  prime[0] = prime[1] = 0;
  fill(prime+2, prime+MAXN, 1);

  phi[0] = 0;
  phi[1] = 0;
  for (int i = 2; i < MAXN; i++)
    phi[i] = i;

  for (int i = 2; i < MAXN; i++) {
    //    div[i].push_back(1);
    if (prime[i])
      for (int j = i; j < MAXN; j += i) {
	if (j > i)
	  prime[j] = 0;
	phi[j] = (phi[j]/i) * (i-1);
	//	div[j].push_back(i);
      }
  }

  phisum[0] = phi[0];
  for (int i = 1; i < MAXN; i++)
    phisum[i] = phisum[i-1] + phi[i];

  //  for (int i = 1; i <= 10; i++) {
  //    printf("%d, %lld %lld\n", i, phi[i], phisum[i]);
  //  }
  /*
    lint ret = 0;
  for (int i = 1; i < MAXN; i++) {
    for (int j = 0; j < div[i].size(); j++) {
      int g = div[i][j];
      ret += g*phi[i/g];
    }
  }

  return 0;
  */

  int _n;
  while (scanf("%d", &_n), _n != 0) {
    lint n = _n, res = 0;
    vector <int> pk;

    for (int g = 1; (g-2)*(g-2) <= n; g++) {
      pk.push_back(n/g);
      pk.push_back(g);
    }
    sort(pk.begin(), pk.end());
    pk.resize(unique(pk.begin(), pk.end())-pk.begin());

    for (int i = 0; i < pk.size(); i++) {
      int k = pk[i];
      if (k == 0 || k > n)
	continue;
      /* Which values of G are there such that floor(N/G) = K ? */

      lint g1 = (n)/k, g0 = (n+1+k)/(k+1);

      if (g1 >= g0) {
	res += (g1-g0+1)*(g0+g1)/2LL * (2LL*phisum[k]+1);
      }
    }

    res -= n*(n+1)/2LL;
    res /= 2LL;

    printf("%lld\n", res);
  }

  return 0;
#if 0
    lint n = 10, res = 0;

  for (lint g = 1; g <= n; g++) {
    res += g*(2LL*phisum[n/g]+1);
    //        printf("R = %lld (%lld)\n", res, n/g);
  }

  res -= n*(n+1)/2;
  res /= 2;

  printf("%lld\n", res);
  return 0;
#if 0
  for (int i = 0; i < MAXN; i++)
    diff[i] = 0;

  for (int g = 1; g < MAXN; g++)
    for (int k = 1; k < MAXN; k++) {
      int n0 = g*k, n1 = g*k+(g-1);
      if (n0 >= MAXN)
	break;
      diff[n0] += g*(2*phisum[k]+1);
      if (n1+1 < MAXN)
	diff[n1+1] += g*(2*phisum[k]+1);
    }

  lint v = 0;
  for (int i = 0; i < MAXN; i++) {
    v += diff[i];
    ret[i] = v;
  }

  int _n;
  while (scanf("%d", &_n) > 0) {
    lint n = _n;
    lint res = ret[n];
    res -= n*(n+1LL)/2LL;
    res /= 2LL;
    printf("%lld\n", res);
  }

  return 0;
#endif
#endif
}

No Cheating (por Felipe Abella)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>

#define MAXN 128
#define MAXM 128

using namespace std;

int height, width;
int broken[MAXM][MAXN], other[MAXM][MAXN];
int isfree[MAXM][MAXN];
int mark[MAXM][MAXN];
int mindist[MAXM][MAXM];
int dy[] = {0, 0, 1, 1, -1, -1}, dx[] = {-1, 1, -1, 1, -1, 1};

int dfs(int y, int x)
{
  if (mark[y][x])
    return 0;

  mark[y][x] = 1;

  if (x%2 == 1) {
    if (other[y][x] == -1)
      return 1;

    if (mindist[other[y][x]/width][other[y][x]%width] == mindist[y][x] + 1)
      return dfs(other[y][x]/width, other[y][x]%width);

    return 0;
  }

  for (int d = 0; d < 6; d++) {
    int y2 = y + dy[d], x2 = x + dx[d];
    if (0 <= y2 && y2 < height && 0 <= x2 && x2 < width && !broken[y2][x2]) {
      if (mindist[y2][x2] == mindist[y][x] + 1 && dfs(y2, x2)) {
	other[y2][x2] = width*y + x;
	isfree[y][x] = 0;
	return 1;
      }
    }
  }

  return 0;
}

int main()
{
  int ntest;

  scanf("%d", &ntest);

  for (int t = 0; t < ntest; t++) {
    int nok = 0;

    scanf("%d %d", &height, &width);

    for (int y = 0; y < height; y++)
      for (int x = 0; x < width; x++) {
	char c;
	scanf(" %c", &c);
	broken[y][x] = (c == 'x');
	if (!broken[y][x])
	  nok ++;
      }

    memset(other, -1, sizeof(other));

    for (int y = 0; y < height; y++)
      for (int x = 0; x < width; x++)
	isfree[y][x] = 1;

    int flow = 0, again;

    do {
      again = 0;
      memset(mark, 0, sizeof(mark));

      queue <pair <int, int> > q;

      for (int y = 0; y < height; y++)
	for (int x = 0; x < width; x ++)
	  mindist[y][x] = 1000000000;

      for (int y = 0; y < height; y++)
	for (int x = 0; x < width; x += 2)
	  if (isfree[y][x] && !broken[y][x]) {
	    q.push(make_pair(y, x));
	    mindist[y][x] = 0;
	  }

      while (!q.empty()) {
	pair <int, int> X = q.front();
	q.pop();
	int y = X.first, x = X.second;
	for (int d = 0; d < 6; d++) {
	  int y2 = y + dy[d], x2 = x + dx[d];
	  if (0 <= y2 && y2 < height && 0 <= x2 && x2 < width && !broken[y2][x2] && mindist[y2][x2] >= 1000000000) {
	    if (((x%2==0) && other[y2][x2] != width*y+x) || ((x%2 == 1) && other[y][x] == width*y2+x2)) {
	      mindist[y2][x2] = mindist[y][x] + 1;
	      q.push(make_pair(y2, x2));
	    }
	  }
	}
      }

    nextone:
      for (int y = 0; y < height; y++)
	for (int x = 0; x < width; x += 2)
	  if (isfree[y][x] && !mark[y][x] && !broken[y][x]) {
	    int r = dfs(y, x);
	    if (r) {
	      flow ++;
	      again = 1;
	      goto nextone;
	    }
	  }
    } while (again);

    printf("Case #%d: %d\n", t+1, nok - flow);
  }

  return 0;
}