Desafios de Programação no Verão de 2011 - Prova 01 - Equipe

Vídeo: Discussão sobre os problemas

Algumas soluções dos competidores

Barcodes (por [IME-USP] Isso é tudo pessoal)

#include <stdio.h>
#include <string.h>
#include <string>
#include <algorithm>
#include <math.h>

using namespace std;

const int NMAX = 256;
int A[NMAX];
int n;

const double eps = 1e-10;

char character(int i) {
	char tmp[8];
	sprintf(tmp, "%d%d%d%d%d", A[i], A[i+1], A[i+2], A[i+3], A[i+4]);
	string str = tmp;
	if (str == "00001") {
		return '0';
	} else if (str == "10001") {
		return '1';
	} else if (str == "01001") {
		return '2';
	} else if (str == "11000") {
		return '3';
	} else if (str == "00101") {
		return '4';
	} else if (str == "10100") {
		return '5';
	} else if (str == "01100") {
		return '6';
	} else if (str == "00011") {
		return '7';
	} else if (str == "10010") {
		return '8';
	} else if (str == "10000") {
		return '9';
	} else if (str == "00100") {
		return '-';
	} else if (str == "00110") {
		return 'X';
	} else {
		return 'Y';
	}
}

string s;

double testabarras() {
	for (double i = 1; i <= 110; i+= 0.01) {
		int ok = 1;
		for (int j = 0; j < n && ok; j++) {
			if (fabs(A[j] - i) <= 0.05 * i + eps) {
			} else if (fabs(A[j] - 2*i) <= 0.05 * 2 * i + eps) {
			} else {
				ok = 0;
			}
		}
		if (ok) {
			return i;
		}
	}
	return -1;
}

int bad() {
	if (n % 6 != 5) {
		return 1;
	}
	for (int i = 5; i < n; i+= 6) {
		if (A[i] != 0) {
			return 1;
		}
	}
	if (character(0) != 'X') {
		reverse(A, A+n);
	}
	if (character(0) != 'X' || character(n - 5) != 'X') {
		return 1;
	}
	s = "";
	for (int i = 6; i+10 < n; i+= 6) {
		s+= character(i);
	}
	for (int i = 0; i < s.size(); i++) {
		if (s[i] == 'X' || s[i] == 'Y') {
			return 1;
		}
	}
	return 0;
}

int w(char c) {
	if (c == '-') {
		return 10;
	} else {
		return c - '0';
	}
}

int calcC() {
	int sum = 0;
	for (int i = 0; i < s.size() - 2; i++) {
		sum+= ((s.size() - 3 - i) % 10 + 1) * w(s[i]);
		sum%= 11;
	}
	return sum;
}

int calcK() {
	int sum = 0;
	for (int i = 0; i < s.size() - 1; i++) {
		sum+= ((s.size() - 2 - i) % 9 + 1) * w(s[i]);
		sum%= 11;
	}
	return sum;
}

int transforma() {
	double i = testabarras();
	if (i < 0) {
		return 0;
	}
	for (int j = 0; j < n; j++) {
		if (fabs(A[j] - i) <= 0.05 * i + eps) {
			A[j] = 0;
		} else if (fabs(A[j] - 2*i) <= 0.05 * 2 * i + eps) {
			A[j] = 1;
		}
	}
	return 1;
}

int main() {
	for (int test = 1; scanf("%d", &n) && n; test++) {
		for (int i = 0; i < n; i++) {
			scanf("%d", A+i);
		}
		printf("Case %d: ", test);
		if (!transforma() || bad()) {
			printf("bad code\n");
		} else {
			int C = calcC();
			int K = calcK();
			if (w(s[s.size() - 2]) != C) {
				printf("bad C\n");
			} else if (w(s[s.size() - 1]) != K) {
				printf("bad K\n");
			} else {
				s = s.substr(0, s.size() - 2);
				printf("%s\n", s.c_str());
			}
		}
	}
	return 0;
}

Tracking Bio-bots (por [IME-USP] Isso é tudo pessoal)

#include <stdio.h>
#include <string.h>
#include <set>
#include <map>
#include <algorithm>
#include <queue>

using namespace std;

typedef unsigned long long llu;
const int NMAX = 2048;
struct st {
	unsigned long long x1, y1, x2, y2;
} A[NMAX];
set <llu> xc, yc;
map <llu,int> xm, ym;
llu xi[NMAX], yi[NMAX];
int M[NMAX][NMAX];
int main() {
	llu rows, columns; int n;
	for (int test = 1; scanf("%llu %llu %d", &rows, &columns, &n) && (rows || columns || n); test++) {
		xc.clear(); yc.clear(); xm.clear(); ym.clear();
		for (int i = 0; i < n; i++) {
			scanf("%llu %llu %llu %llu", &A[i].x1, &A[i].y1, &A[i].x2, &A[i].y2);
			A[i].x2++; A[i].y2++;
			xc.insert(A[i].x1); xc.insert(A[i].x2);
			yc.insert(A[i].y1); yc.insert(A[i].y2);
		}
		xc.insert(0); xc.insert(columns - 1); xc.insert(columns);
		yc.insert(0); yc.insert(rows - 1); yc.insert(rows);
		int cx = 0, cy = 0;
		for (set<llu>::iterator it = xc.begin(); it != xc.end(); it++) {
			xm[*it] = cx; xi[cx++] = *it; }
		for (set<llu>::iterator it = yc.begin(); it != yc.end(); it++) {
			ym[*it] = cy; yi[cy++] = *it; }
		memset(M, 0, sizeof(M));
		for (int i = 0; i < n; i++) {
			int x1 = xm[A[i].x1];
			int y1 = ym[A[i].y1];
			int x2 = xm[A[i].x2];
			int y2 = ym[A[i].y2];
			for (int k = x1; k < x2; k++) {
				for (int l = y1; l < y2; l++) {
					M[k][l] = 1;
				}
			}
		}
		cx--; cy--;
		if (M[cx - 1][cy - 1] != 1) {
			queue < pair<int,int> > Q;
			Q.push(make_pair(cx - 1, cy - 1));
			M[cx - 1][cy - 1] = 1;
			while (!Q.empty()) {
				pair <int,int> u = Q.front(); Q.pop();
				int x = u.first, y = u.second;
				if (x - 1 >= 0 && M[x - 1][y] == 0) {
					Q.push(make_pair(x-1, y));
					M[x-1][y] = 1; }
				if (y - 1 >= 0 && M[x][y-1] == 0) {
					Q.push(make_pair(x, y-1));
					M[x][y-1] = 1; } } }
		llu output = 0;
		for (int i = 0; i < cx; i++) {
			for (int j = 0; j < cy; j++) {
				if (!M[i][j]) {
					output+= (xi[i+1] - xi[i]) * (yi[j+1] - yi[j]); } } }
		printf("Case %d: %llu\n", test, output); }
	return 0; }

Castles (por [IME-USP] Isso é tudo pessoal)

#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;

#define N 128
int n;

pair<int,int> C[N];
pair<int,int> PD[N][N];
vector<int> adj[N];

pair<int,int> calc(int at, int pai) {
	if(PD[at][pai].first != -1) return PD[at][pai];
	if(adj[at].size() == 1 && pai != n) return C[at];

	vector<pair<int,int> > v;
	for(int i = 0; i < (int) adj[at].size(); i++) {
		if( adj[at][i] != pai ) {
			v.push_back( calc(adj[at][i], at) );
		}
	}
	sort(v.begin(), v.end());
	reverse(v.begin(), v.end());
	int precisa = 0, tenho = 0, morre = 0;
	for(int i = 0; i < (int) v.size(); i++) {
		if( tenho < v[i].first ) {
			int dif = v[i].first - tenho;
			tenho = v[i].first;
			precisa += dif;
		}
		if( tenho < v[i].second ) {
			int dif = v[i].second - tenho;
			tenho = v[i].second;
			precisa += dif;
		}
		tenho -= v[i].second;
		morre += v[i].second;
	}
	return PD[at][pai] = make_pair( max(precisa + C[at].second, C[at].first), morre + C[at].second);
}

int main() {
	int teste = 1;
	while(scanf("%d", &n) && n) {
		for(int i = 0; i < n; i++) {
			int a,b,c;
			scanf("%d %d %d", &a, &b, &c);
			C[i].first = a;
			C[i].second = b + c;
			adj[i].clear();
		}
		for(int i = 0; i < n-1; i++) {
			int a,b;
			scanf("%d %d", &a, &b);
			a--; b--;
			adj[a].push_back(b);
			adj[b].push_back(a);
		}
		int resp = 1000000000;
		memset(PD, -1, sizeof(PD));

		if(n == 1) {
			resp = max( C[0].first, C[0].second );
		} else {
			for(int i = 0; i < n; i++) {
				pair<int,int> aux = calc(i,n);
				resp = min(resp, max(aux.first, aux.second));
			}
		}
		printf("Case %d: %d\n", teste++, resp);
	}
	return 0;
}

Channel (por Estação PrIMEira da XurupITA)

#include <stdio.h>
#include <map>
#include <string>
#include <algorithm>
using namespace std;
#define MAXN 30

struct state{
	int mask;
	string e;
	state(){}
	state( int a, string b ){
		mask=a;
		e=b;	
	}
};

struct classcomp {
	bool operator() (const state& a, const state& b) const{
		if( a.mask!=b.mask ){
			return (a.mask<b.mask);
		}
		else{
			return (a.e.compare(b.e)<0);
		}
	}
};

struct answer{
	int len;
	map<state,answer,classcomp>::iterator it;
	answer(){}
	answer( int l, map<state,answer,classcomp>::iterator i ){
		len=l;
		it=i;
	}
};

typedef map<state,answer,classcomp> stmap;

stmap p[MAXN];
stmap::iterator resp;
int n, m, v[MAXN], test;

/*void printbin( int k ){
	int i;
	for( i=0 ; i<m ; i++ ){
		printf("%d",((1<<i)&k)!=0);	
	}	
	printf("\n");
}*/

bool read(){
	int i, j;
	char l;
	scanf("%d %d",&n,&m);
	if( n==0 && m==0 ){
		return 0;	
	}
	for( i=1 ; i<=n ; i++ ){
		v[i]=0;	
		for( j=0 ; j<m ; j++ ){
			scanf(" %c",&l);
			if( l=='#' ){
				v[i]+=(1<<j);	
			}
		}
		//debug("%d: %d\n",i,v[i]);
	}
	return 1;
}

int bits( int k ){
	int ret=0;
	while( k>0 ){
		k-=k&-k;
		ret++;	
	}
	return ret;
}

int par( string e, int k ){
	string::iterator it;	
	for( it=e.begin()+1 ; it!=e.end() ; it+=2 ){
		if( *it==k+'0' ){
			return *(it+1)-'0';	
		}
		else if( *(it+1)==k+'0' ){
			return *it-'0';
		}
	}
	//printf("ERROR\n");
	//getchar();
	return -1;
}

int prox( int pos, int mask ){
	int k;
	//debug("		prox %d ",pos);
	//printbin(mask);
	if( ((1<<(pos+1))&mask)!=0 ){
		for( k=pos ; ((1<<k)&mask)!=0 ; k++ );
		//debug("		retorno %d\n",k-1);
		return k-1;
	}
	else{
		for( k=pos ; k>=0 && ((1<<k)&mask)!=0; k-- );
		//debug("		retorno %d\n",k+1);
		return k+1;
	}
}

int next( int pos, state& s, int mask ){
	int k;
	//debug("	next para %d\n",pos);
	for( k=prox(pos,mask) ; ((1<<k)&s.mask)!=0 ; k=prox(k,mask) ){
		if( k==prox(k,mask) ){
			break;	
		}
		else{
			k=par(s.e,k);	
		}
	}
	//debug("	retorna next %d\n",k);
	return k;
}

bool verif( state s, int mask, state& p ){
	string::iterator jt;
	int mm, i, j, k, ini;
	p.mask=mask;
	p.e="";
	for( jt=s.e.begin() ; jt!=s.e.end() ; jt++ ){
		k=*jt-'0';
		mm=(1<<(k-1))+(1<<(k+1));
		if( bits(mm&mask)==2 ){
			//debug("errado: duas pontas para %d\n",k);
			return 0;	
		}
	}
	for( jt=s.e.begin()+1 ; jt!=s.e.end() ; jt+=2 ){
		k=*(jt+1)-'0';
		mm=1<<(k+1);
		k=*jt-'0';
		mm-=1<<k;
		if( (mm&mask)==mm ){
			//debug("errado: juntou duas pontas %d e %d\n",*jt-'0',*(jt+1)-'0');
			return 0;
		}
	}
	ini=*s.e.begin()-'0';
	k=next(ini,s,mask);
	p.e.push_back(k+'0');
	ini=k;
	//debug("agora o ini esta em %d\n",ini);
	for( i=0 ; i<m ; ){
		if( (mask&(1<<i))==0 ){
			i++;
		}
		else{
			//debug("testando bit %d\n",i);
			j=i;
			k=prox(j,mask);
			//debug("segmento %d ate %d\n",j,k);
			i=k+1;
			if( j==k ){
				if(	(s.mask&(1<<k))==0 ){
					//debug("errado: bloco sozinho\n");
					return 0;	
				}
				else if( k!=ini ){
					j=next(par(s.e,k),s,mask);
					if( j>k ){
						p.e.push_back(k+'0');
						p.e.push_back(j+'0');
					}
				}
			}
			else{
				if(	(s.mask&(1<<k))==0 && (s.mask&(1<<j))==0 ){
					if( k-j<2 ){
						//debug("errado: segmento pequeno sozinho\n");
						return 0;
					}
					else{
						//debug("segmento %d ate %d criado\n",j,k);
						p.e.push_back(j+'0');
						p.e.push_back(k+'0');	
					}
				}
				else if( (s.mask&(1<<k))==0 ){
					if( k!=ini ){
						j=next(par(s.e,j),s,mask);
						if( j>k ){
							//debug("adicionado par %d %d\n",k,j);
							p.e.push_back(k+'0');
							p.e.push_back(j+'0');	
						}
					}
				}
				else if( (s.mask&(1<<j))==0 ){
					if( j!=ini ){
						k=next(par(s.e,k),s,mask);
						if( j<k ){
							//debug("adicionado par %d %d\n",j,k);
							p.e.push_back(j+'0');
							p.e.push_back(k+'0');
						}
					}
				}
				else{
					//debug("segmento ligando duas pontas\n");	
				}
			}
		}
	}
	return 1;
}

void solve(){
	int i, mask, mm, me;
	stmap::iterator it, ft;
	string::iterator jt;
	string aux;
	state s;
	p[0].clear();
	p[0][state(1,"0")]=answer(0,p[0].end());
	for( i=0 ; i<n ; i++ ){
		p[i+1].clear();
		for( it=p[i].begin() ; it!=p[i].end() ; it++ ){
			//printbin(it->first.mask);
			//debug("\"%s%\": %d\n",it->first.e.c_str(),it->second.len);
			mask=(1<<m)-1-v[i+1];
			mask-=mask&it->first.mask;
			me=0;
			aux=it->first.e;
			for( jt=aux.begin() ; jt!=aux.end() ; jt++ ){
				me+=(1<<(*jt-'0'));
			}
			if( (me&v[i+1])!=0 ){
				//debug("nao da pra continuar\n");
				continue;	
			}
			mask-=mask&((it->first.mask-me)<<1);
			mask-=mask&((it->first.mask-me)>>1);
			//debug("mask: ");
			//printbin(mask);
			for( mm=mask ; mm>=0 ; mm=mask&(mm-1) ){
				//printbin(mm+me);
				//getchar();
				if( verif(it->first,mm+me,s) ){
					//debug("deu!\n");
					ft=p[i+1].find(s);
					if( ft==p[i+1].end() ){
						p[i+1][s]=answer(it->second.len+bits(s.mask),it);
						//debug("nao tinha\n");
					}
					else{
						//debug("ja tinha\n");
						if( ft->second.len < it->second.len+bits(s.mask) ){
							ft->second=answer(it->second.len+bits(s.mask),it);
							//debug("e melhorou!\n");
						}
					}
				}
				else{
					//debug("nao deu\n");
				}
				if( mm==0 ){
					break;	
				}
			}
		}	
	}
	resp=p[0].end();
	aux="";
	aux.push_back(m-1+'0');
	//debug("ACHANDO RESPOSTA\n");
	for( it=p[n].begin() ; it!=p[n].end() ; it++ ){
		//printbin(it->first.mask);
		//debug("\"%s%\": %d\n",it->first.e.c_str(),it->second.len);
		if( it->first.e.compare(aux)==0 ){
			//debug("pode ser resposta!\n");
			if( resp==p[0].end() ){
				//debug("primeira resposta!\n");
				resp=it;	
			}
			else if( resp->second.len < it->second.len ){
				//debug("melhorou resposta!\n");
				resp=it;	
			}	
		}	
	}
}

void print( stmap::iterator r, int row ){
	int k;
	if( r->second.len==0 ){
		return;	
	}
	print(r->second.it,row-1);
	for( k=0 ; k<m ; k++ ){
		if( ((1<<k)&v[row])!=0 ){
			printf("#");
		}
		else if( ((1<<k)&r->first.mask)!=0 ){
			printf("C");	
		}
		else{
			printf(".");	
		}
	}
	printf("\n");
}

void write(){
	printf("Case %d:\n",test++);
	print(resp,n);
	printf("\n");
}

int main(){
	test=1;
	while( read() ){
		solve();
		write();	
	}
	return 0;	
}

Contour Mapping (por Estação PrIMEira da XurupITA)

#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
#define MAXN 260

typedef double ldouble;

int n , m;
int h, t[MAXN][MAXN];
ldouble d, resp;

ldouble len( ldouble l1, ldouble l2 ){
	return sqrt(l1*l1+l2*l2-l1*l2);	
}

int hfloor( int k ){
	return (int)floor(1.0*k/h)*h;	
}

int hceil( int k ){
	return (int)ceil(1.0*k/h)*h;	
}

void escal( int a, int b, int c ){
	int h1, h2;
	ldouble l1, l2;
	//printf("escal: %d %d %d\n",a,b,c);
	h1=hceil(a);
	h2=hfloor(b);
	if( h2>=h1 ){
		l1=len((h1-a)*d/(b-a),(h1-a)*d/(c-a));
		l2=len((h2-a)*d/(b-a),(h2-a)*d/(c-a));
		resp+=(l1+l2)*(((h2-h1)/h)+1)/2.0;
	}
	h1=hceil(b);
	if( h1==b ){
		h1+=h;	
	}
	h2=hfloor(c);
	if( h2>=h1 ){
		l1=len((c-h1)*d/(c-b),(c-h1)*d/(c-a));
		l2=len((c-h2)*d/(c-b),(c-h2)*d/(c-a));
		resp+=(l1+l2)*(((h2-h1)/h)+1)/2.0;
	}	
}

void isos( int a, int b ){
	int	h1, h2;
	ldouble l1, l2;
	//printf("isos: %d %d\n",a,b);
	if( a<b ){
		h1=hceil(a);
		h2=hfloor(b);
	}
	else{
		h1=hceil(b);
		h2=hfloor(a);
	}
	if( h2>=h1 ){
		l1=(h1-a)*d/(b-a);
		l2=(h2-a)*d/(b-a);
		resp+=(l1+l2)*(((h2-h1)/h)+1)/2.0;
	}
}

void ord( int& a, int& b, int& c ){
	if( b>c ){
		swap(b,c);
	}
	if( a>b ){
		swap(a,b);
	}
	if( b>c ){
		swap(b,c);
	}	
}

void tr1( int i, int j ){
	int a, b, c;
	if( t[i][j]==-1 || t[i][j+1]==-1 || t[i+1][j+1]==-1 ){
		return;	
	}
	a=t[i][j];
	b=t[i][j+1];
	c=t[i+1][j+1];
	ord(a,b,c);
	if( a==c  ){
		if( (a%h)==0 ){
			//printf("equil %d\n",a);
			if( t[i-1][j]!=a ){
				resp+=d;	
			}
			if( t[i+1][j]!=a ){
				resp+=d;	
			}
			if( t[i+1][j+2]!=a ){
				resp+=d;	
			}
		}
	}
	else if( a==b ){
		isos(c,a);
	}
	else if( b==c ){
		isos(a,c);	
	}
	else{
		escal(a,b,c);	
	}
}

void tr2( int i, int j ){
	int a, b, c;
	if( t[i][j]==-1 || t[i+1][j]==-1 || t[i+1][j+1]==-1 ){
		return;	
	}
	a=t[i][j];
	b=t[i+1][j];
	c=t[i+1][j+1];
	ord(a,b,c);
	if( a==c  ){
		if( (a%h)==0 ){
			//printf("equil %d\n",a);
			if( t[i][j-1]!=a ){
				resp+=d;	
			}
			if( t[i][j+1]!=a ){
				resp+=d;	
			}
			if( t[i+2][j+1]!=a ){
				resp+=d;	
			}
		}
	}
	else if( a==b ){
		isos(c,a);
	}
	else if( b==c ){
		isos(a,c);	
	}
	else{
		escal(a,b,c);	
	}
}

int main(){
	int i, j, k, test=1;
	while( scanf("%d",&n)>0 && n>0 ){
		scanf("%d %lf %d",&m,&d,&h);
		for( i=0 ; i<MAXN ; i++ ){
			for( j=0 ; j<MAXN ; j++ ){
				t[i][j]=-1;	
			}	
		}
		for( i=1 ; i<=n ; i++ ){
			if( i%2==1 ){
				k=m;	
			}
			else{
				k=m+1;	
			}
			for( j=1 ; j<=k ; j++ ){
				scanf("%d",&t[i][j+((i-1)/2)]);
			}
		}
		resp=0.0;	
		for( i=1 ; i<=200; i++ ){
			for( j=1 ; j<=200 ; j++ ){
				//j+=((i-1)/2);
				tr1(i,j);
				tr2(i,j);
				if( t[i][j]!=-1 && (t[i][j]%h)==0 ){
					if( t[i+1][j]==t[i][j] && t[i][j-1]!=-1 && t[i+1][j+1]!=-1 ){
						if( t[i][j-1]!=t[i][j] || t[i+1][j+1]!=t[i][j] ){
							//printf("%d %d: 1\n",i,j);
							resp-=d;	
						}
					}
					if( t[i+1][j+1]==t[i][j] && t[i+1][j]!=-1 && t[i][j+1]!=-1 ){
						if( t[i+1][j]!=t[i][j] || t[i][j+1]!=t[i][j] ){
							//printf("%d %d: 2\n",i,j);
							resp-=d;	
						}
					}
					if( t[i][j+1]==t[i][j] && t[i-1][j]!=-1 && t[i+1][j+1]!=-1 ){
						if( t[i-1][j]!=t[i][j] || t[i+1][j+1]!=t[i][j] ){
							//printf("%d %d: 3\n",i,j);
							resp-=d;	
						}
					}
				}
				//j-=((i-1)/2);
			}
		}
		printf("Case %d: %.0lf\n",test++,resp);
	}
	return 0;
}

The Islands (por [IME-USP] Isso é tudo pessoal)

#include <stdio.h>
#include <math.h>
#include <vector>

using namespace std;

const int NMAX = 128;

int n, x1, x2;
int X[NMAX], Y[NMAX];
double PD[NMAX][NMAX][NMAX];
int E[NMAX][NMAX][NMAX];

double sqr(double x) {
	return x*x;
}

double dist(int i, int j) {
	return sqrt(sqr(X[i] - X[j]) + sqr(Y[i] - Y[j]));
}

double pd(int act, int left, int right) {
	if (act == n - 1) {
		return dist(act, left) + dist(act, right);
	}
	if (PD[act][left][right] > -1) {
		return PD[act][left][right];
	}
	double *out = &PD[act][left][right];
	if (act == x1) {
		E[act][left][right] = 0;
		return *out = pd(act+1, act, right) + dist(act, left);
	}
	if (act == x2) {
		E[act][left][right] = 1;
		return *out = pd(act+1, left, act) + dist(act, right);
	}
	double a = pd(act+1, act, right) + dist(act, left);
	double b = pd(act+1, left, act) + dist(act, right);
	if (a < b) {
		E[act][left][right] = 0;
	} else {
		E[act][left][right] = 1;
	}
	return *out = a < b ? a : b;
}

int main() {
	for (int test = 1; scanf("%d %d %d", &n, &x1, &x2) && (n || x1 || x2); test++) {
		for (int i = 0; i < n; i++) {
			scanf("%d %d", X+i, Y+i);
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				for (int k = 0; k < n; k++) {
					PD[i][j][k] = -100;
				}
			}
		}
		printf("Case %d: %.2f\n", test, pd(1, 0, 0));
		vector <int> ida, volta;
		int left = 0, right = 0;
		for (int act = 1; act < n - 1; act++) {
			if (E[act][left][right] == 0) {
				ida.push_back(act);
				left = act;
			} else {
				volta.push_back(act);
				right = act;
			}
		}
		if (ida.size() > 0 && ida[0] != 1) {
			swap(ida, volta);
		}
		printf("0");
		for (int i = 0; i < ida.size(); i++) {
			printf(" %d", ida[i]);
		}
		printf(" %d", n - 1);
		for (int i = volta.size() - 1; i >= 0; i--) {
			printf(" %d", volta[i]);
		}
		printf(" 0\n");
	}
	return 0;
}

Robots on Ice (por [ITA] Carteado)

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<cmath>
#include<vector>
#include<set>
#include<map>
#include<list>
#include<deque>
#include<queue>
#include<stack>
#include<functional>
#include<sstream>
#include<iostream>
#include<ctime>
#include<algorithm>
using namespace std;

#define DEBUG(x...) printf(x)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).begin(),(v).rend()
#define _foreach(it,b,e) for(__typeof__(b) it=(b); it!=(e);++it)
#define foreach(x...) _foreach(x)

typedef long long int huge;

const int inf = 0x3f3f3f3f;
const huge hugeinf = 0x3f3f3f3f3f3f3f3fll;//dois L's
const double eps = 1e-9;

int n,m;
int pos[4][2];
int dist[4];
int ret = 0;
int next[65];
bool tab[8][8];
const int dx[4]={0,-1,0,1};
const int dy[4]={1,0,-1,0};

inline bool ok(int a,int b)
{
  return (a>=0 && b>=0 && a<n && b<m);
  
}
int lista[65],qte;
int mc[8][8];
int ct;
void dfs(int a,int b)
{
  if(!ok(a,b) || tab[a][b] || mc[a][b])
    return;
  ct++;
  mc[a][b]=true;
  for(int i=0;i<4;i++)
    dfs(a+dx[i],b+dy[i]);
    
}

inline bool is_valid(int a,int b,int s)
{
  if(ok(a,b) && !tab[a][b])
    {
      
      if(a==0 || b==0 || a==n-1 || b==m-1)
	{
	  for(int i=0;i<m;i++)
	    {
	      if(a==0 && b==i)
		return true;
	      if(!tab[0][i])
		return false;
	    }
	  for(int i=0;i<n;i++)
	    {
	      if(a==i && b==m-1)
		return true;
	      if(!tab[i][m-1])
		return false;
	    }
	  for(int i=0;i<m;i++)
	    {
	      if(a==n-1 && b==m-i-1)
		return true;
	      if(!tab[n-1][m-i-1])
		return false;
	    }
	 
	  for(int i=0;i<n;i++)
	    {
	      if(a==n-i-1 && b==0)
		return true;
	      if(!tab[n-i-1][0])
		return false;
	    }

	}

      return true;
    }
  return false;
}
void go(int a,int b,int s)
{
  // printf("%d %d\n",a,b);
  if(!is_valid(a,b,s))
    return;
  
  int av = next[s];
  
  for(int i=0;i<4;i++)
    if(a==pos[i][0] && b==pos[i][1] && i!=av)
      return;
  if(abs(a-pos[av][0])+abs(b-pos[av][1])>dist[av]-s)
    return;


  if(s==n*m)
    {
      ret++;
      return;
    }

  tab[a][b]=true;
  for(int i=0;i<4;i++)
    {
      go(a+dx[i],b+dy[i],s+1);
    }
  tab[a][b]=false;
}
int main ()
{
  int tt=1;
  while(1)
    {
      
      scanf("%d %d",&m,&n);
      if(n==0 && m==0)
	break;
      for(int i=0;i<3;i++)
	{
	  dist[i]=(i+1)*m*n/4;
	  scanf("%d %d",&pos[i][1],&pos[i][0]);
	 
	}

      pos[3][1]=0,pos[3][0]=1;
      dist[3]=n*m;
      for(int i=0;i<=n*m;i++)
	{
	  for(int j=0;j<4;j++)
	    if(dist[j]>=i)
	      {next[i]=j;break;}
	}
      
      memset(tab,0,sizeof(tab));
      ret = 0;
      go(0,0,1);
      printf("Case %d: %d\n",tt++,ret);
    }
  return 0;
}

Sharing Chocolate (por [IME-USP] Isso é tudo pessoal)

#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;

char pd[ 1<<15 ][ 128 ];
int n, v[15];

int vamo(int c, int m);

int tenta(int pos, int at, int c, int m) {
	if(pos == n) {
		if(at == 0 || at == c) return 0;

		int bt = c - at;

		int sa = 0, sb = 0;
		for(int i = 0; i < n; i++) {
			if(at & (1<<i)) sa += v[i];
			if(bt & (1<<i)) sb += v[i];
		}

		int ma,mb, s = sa+sb;

		int row = m, col = s / m;
		if(sa % row == 0) {
			ma = sa / row;
			mb = sb / row;
			if(vamo(at, max(ma, sa/ma)) && vamo(bt, max(mb, sb/mb))) return 1;
		}
		if(sa % col == 0) {
			ma = sa / col;
			mb = sb / col;
			if(vamo(at, max(ma, sa/ma)) && vamo(bt, max(mb, sb/mb))) return 1;
		}

		return 0;
	}

	if(tenta(pos+1, at, c, m)) return 1;
	if((1<<pos) & c) {
		if(tenta(pos+1, at | (1<<pos), c, m)) return 1;
	}


	return 0;
}

int vamo(int c, int m) {
	if(pd[c][m] != -1) return pd[c][m];
	int qtd = 0;
	for(int i = 0; i < n; i++) {
		if( (1<<i) & c ) qtd++;
	}
	if(qtd == 1) return pd[c][m] = 1;
	return pd[c][m] = tenta(0, 0, c, m);
}

int main() {
	int teste = 1;
	while(scanf("%d", &n) && n) {
		int r,c,s=0;
		scanf("%d %d", &r, &c);
		for(int i = 0; i < n; i++) {
			scanf("%d", v+i);
			s += v[i];
		}
		int ok = 0;
		memset(pd, -1, sizeof(pd));
		if(s == r*c) ok = vamo( (1<<n)-1, max(r,c) );
		printf("Case %d: %s\n", teste++, ok ? "Yes" : "No" ); 
	}
	return 0;
}

Paperweight (por [ITA] Carteado)

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <set>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;

const long double eps = 1e-9;

struct point
{
  long double x, y, z;
};

point cross(point a, point b)
{
  return (point){
    a.y*b.z - a.z*b.y,
      a.z*b.x - a.x*b.z,
      a.x*b.y - a.y*b.x};
}

long double dot(point a, point b)
{
  return a.x*b.x + a.y*b.y + a.z*b.z;
}

long double mixedproduct(point a, point b, point c)
{
  return dot(a, cross(b, c));
}

point operator-(const point &a, const point &b)
{
  return (point){a.x - b.x, a.y - b.y, a.z - b.z};
}

point operator+(const point &a, const point &b)
{
  return (point){a.x + b.x, a.y + b.y, a.z + b.z};
}

point operator/(const point &a, long double k)
{
  return (point){a.x / k, a.y / k, a.z / k};
}

point operator*(const point &a, long double k)
{
  return (point){a.x * k, a.y * k, a.z * k};
}

long double norm(point p) { return sqrt(dot(p, p)); }

bool ishullface(const vector<point> &poly, int a, int b, int c)
{
  long double mp[6];
  int pos=0,neg=0;
  for (int i=0; i<5; ++i)
    mp[i]=mixedproduct(poly[b] - poly[a], poly[c] - poly[a], poly[i] - poly[a]);
  for (int i=0;i<5;i++)
    {
      if (mp[i]<-eps)
	neg++;
      else if (mp[i]>eps)
	pos++;
    }
  if (neg*pos == 0)
    {
      //printf("ishullface(%d %d %d) = true\n", a, b, c);
      return true;
    }
  else
    {
      //printf("ishullface(%d %d %d) = false\n", a, b, c);
      return false;
    }
}

long double volume(point a, point b, point c, point d)
{
  return fabs(mixedproduct(b - a, c - a, d - a));
}

point cmass(point a, point b, point c, point d)
{
  return (a + b + c + d) / 4;
}

point totalcmass(const vector<point> &poly)
{
  point CM1 = cmass(poly[0], poly[1], poly[2], poly[3]);
  long double VM1 = volume(poly[0], poly[1], poly[2], poly[3]);
  point CM2 = cmass(poly[0], poly[1], poly[2], poly[4]);
  long double VM2 = volume(poly[0], poly[1], poly[2], poly[4]);
  return (CM1 * VM1 + CM2 * VM2) / (VM1 + VM2);
}

bool isinside(point p, point a, point b, point c)
{
  if (fabs(norm(cross(p - a, b - a)) + norm(cross(p - b, c - b)) + norm(cross(p - c, a - c)) - norm(cross(b - a, c - a))) < eps)
    return true;
  else
    return false;
}

point project(point p, point a, point b, point c)
{
  point v = cross(b - a, c - a);
  return p - v * dot(p-a, v) / dot(v, v);
}

long double pointlinedist(point p, point a, point b)
{
  return norm(cross(p - a, p - b)) / norm(b - a);
}

bool isreallyinside(point p, point a, point b, point c)
{
  if (pointlinedist(p, a, b) > .2 && pointlinedist(p, b, c) > .2 && pointlinedist(p, a, c) > .2)
    return true;
  else
    return false;
}

bool isreallyinside(point p, point a, point b, point c, point d)
{
  if (pointlinedist(p, a, c) > .2 && pointlinedist(p, b, c) > .2 && pointlinedist(p, a, d) > .2 && pointlinedist(p, b, d) > .2)
    return true;
  else
    return false;
}

bool isstable(const vector<point> &poly, int a, int b, int c)
{
  point tcmass = totalcmass(poly);
  point P = project(tcmass, poly[a], poly[b], poly[c]);
  //printf("%.2lf\n", mixedproduct(P - poly[a], P - poly[b], P - poly[c]));
  //bool isin = isinside(P, poly[a], poly[b], poly[c]);
  //printf("isinside(%d %d %d) = %d\n", a, b, c, isin);
  //bool isrein = isreallyinside(P, poly[a], poly[b], poly[c]);
  //printf("isreallyinside(%d %d %d) = %d\n", a, b, c, isrein);
  if (isinside(P, poly[a], poly[b], poly[c]) && isreallyinside(P, poly[a], poly[b], poly[c]))
    return true;
  else
    return false;
}

/// novo codigo
bool isstable(const vector<point> &poly, int a, int b, int c, int d)
{
  int other = 1 + 2 + 3 + 4 - a - b - c - d;
  point tcmass = totalcmass(poly);
  point P = project(tcmass, poly[a], poly[b], poly[c]);
  //printf("%.2lf\n", mixedproduct(P - poly[a], P - poly[b], P - poly[c]));
  //bool isin = isinside(P, poly[a], poly[b], poly[c]);
  //printf("isinside(%d %d %d) = %d\n", a, b, c, isin);
  //bool isrein = isreallyinside(P, poly[a], poly[b], poly[c]);
  //printf("isreallyinside(%d %d %d) = %d\n", a, b, c, isrein);
  if ((isinside(P, poly[a], poly[c], poly[d]) || isinside(P, poly[b], poly[c], poly[d]))
      && isreallyinside(P, poly[a], poly[b], poly[c], poly[d]))
    return true;
  else
    return false;
}

long double pointplanedist(point p, point a, point b, point c)
{
  return norm(p - project(p, a, b, c));
}

int main()
{
  vector<point> points;
  point F;
  
  for (int ncase = 1;;++ncase)
    {
      points.clear();
      for (int i=0; i<5; ++i)
	{
	  double x, y, z;
	  if (scanf(" %lf %lf %lf", &x, &y, &z) != 3)
	    return 0;
	  points.push_back((point){x, y, z});
	}

      scanf(" %Lf %Lf %Lf", &F.x, &F.y, &F.z);

      long double mindist = 1e100, maxdist = -1;

      for (int i=0; i<5; ++i)
	for (int j=0; j<i; ++j)		       
	  for (int k=0; k<j; ++k)
	    if (ishullface(points, i, j, k) && isstable(points, i, j, k))
	      {
		//printf("(%d %d %d)\n", i, j, k);
		mindist = min(mindist, pointplanedist(F, points[i], points[j], points[k]));
		maxdist = max(maxdist, pointplanedist(F, points[i], points[j], points[k]));
	      }

      for (int i=0; i<5; ++i)
	for (int j=0; j<i; ++j)
	  for (int k=0; k<j; ++k)
	    for (int l=0; l<k; ++l)
	      if (volume(points[i], points[j], points[k], points[l]) < eps && isstable(points, i, j, k, l))
	      {
		//printf("(%d %d %d)\n", i, j, k);
		mindist = min(mindist, pointplanedist(F, points[i], points[j], points[k]));
		maxdist = max(maxdist, pointplanedist(F, points[i], points[j], points[k]));
	      }

      printf("Case %d: %.5Lf %.5Lf\n", ncase, mindist, maxdist);
    }

  return 0;
}