Hora de início: 2011-01-10 14:30:00 -0200 Hora de término: 2011-01-10 19:30:00 -0200
POS | Competidor | Resultado | Pontuação | A | B | C | D | E | F | G | H | I | J | K | |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
1 | Grito da Trypanosoma | 6 (646) | 33 | +0 | +1 | +0 | +1 | +1 | +3 | ||||||
2 | [ITA] Carteado | 6 (1011) | 31 | +2 | +1 | +0 | +1 | +1 | +4 | ||||||
3 | [IME-USP] Isso é tudo pessoal | 5 (1132) | 29 | +7 | +4 | +0 | +2 | +0 | |||||||
4 | aWARush/ | 4 (600) | 27 | -4 | +1 | +0 | +0 | -4 | +4 | ||||||
5 | Razao Cruzada | 4 (779) | 25 | +1 | +0 | +0 | -4 | +0 | |||||||
6 | hackermath | 4 (1186) | 23 | +12 | +0 | +0 | -5 | +7 | |||||||
7 | SUDO | 3 (704) | 21 | +5 | +0 | +5 | |||||||||
8 | AUHAUAH Balões Mano | 3 (725) | 19 | +7 | +4 | -1 | -1 | +0 | |||||||
9 | Estação PrIMEira da XurupITA | 2 (169) | 17 | -5 | +0 | +0 | -2 | ||||||||
10 | Unicamp Alpha | 2 (659) | 15 | +1 | -1 | +4 | |||||||||
11 | Garotos da OBI | 1 (201) | 13 | +1 | -3 | ||||||||||
12 | Depois a gente diz! | 1 (208) | 11 | -5 | +0 | ||||||||||
15 | Convex Null | 1 (352) | 5 | -5 | +3 | ||||||||||
15 | dalhebugre | 0 (0) | 5 | ||||||||||||
15 | Senta A Pua! | 0 (0) | 5 | ||||||||||||
15 | RGA | 0 (0) | 5 | -3 | -2 | -1 | |||||||||
15 | ACM-1PT | 0 (0) | 5 | </div> |
#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; }
#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; }
#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; }
#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; }
#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; }
#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; }
#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; }
#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; }
#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; }