Desafios de Programação no Verão

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

» 31 de janeiro de 2011

Hora de início: 2011-01-31 09:11:00 -0200   Hora de término: 2011-01-31 13:11:00 -0200

Problemas

POS Competidor Resultado Pontuação A B C D E F G H I J  
1 hackermath 8 (1112) 33 +1 +0 +3 +0 +7 +0   +2 +1    
2 [IME-USP] Isso é tudo pessoal 7 (762) 31 +0   +3 +0   +0 -25 +1 +0 +3  
3 aWARush/ 7 (851) 29 +0 +0 +3 +0   +2   +0 +1 -5  
4 Garotos da OBI 7 (961) 27 +1 +1 +1 +2   +0   +5 +0    
5 [ITA] Carteado 7 (1133) 25 +2 +0 +3 +1   +3   +1 +5    
6 SUDO 5 (635) 23     +0 +2   +1   +1 +0 -2  
7 Depois a gente diz! 5 (701) 21     +1 +0   +2   +0 +1    
8 Grito da Trypanosoma 5 (917) 19     +3 +0   +0   +4 -3 +2  
9 Convex Null 4 (437) 17 -1   +0 +0       +1 +0    
10 Unicamp Alpha 4 (455) 15 +0   +1 +1 -4 -4   +1 -1    
11 AUHAUAH Balões Mano 4 (473) 13     +0 +0   -2   +0 +2    
12 Razao Cruzada 4 (640) 11     +2 +2       +1 +0    
13 Estação PrIMEira da XurupITA 3 (286) 9     +2 +1   -5   +0      
14 RGA 3 (412) 7     -4 +1   -1   +3 +0    
15 ACM-1PT 2 (298) 5     +2         +0      
16 dalhebugre 1 (76) 3     -6         +1      
17 Senta A Pua! 1 (273) 1     -1         +3 -1   </div>

Vídeo: Discussão sobre os problemas

Algumas soluções dos competidores

Cyclic antimonotonic permutations (por [IME-USP] Isso é tudo pessoal)

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

#define MAX 1000001
int v[MAX];

int testa(int N) {
	for(int i = 2; i < N; i++) {
		int at = v[i];
		if(at < v[i+1] && at > v[i-1]) return 0;
		if(at > v[i+1] && at < v[i-1]) return 0;
	}
	int opa[MAX];
	memset(opa, 0, sizeof(opa));
	int at = 1;
	int cnt = 0;
	while(!opa[at]) {
		opa[at] = 1;
		cnt++;
		at = v[at];
	}
	if(cnt < N) return 0;
	return 1;
}

void roda(int N) {
	int M = (N+1) / 2;
	vector<int> impar_cima, impar_baixo, par_cima, par_baixo;
	for(int i = 5; i <= M; i += 2) {
		impar_baixo.push_back(i);
	}
	for(int i = 4; i <= M; i += 2) {
		par_baixo.push_back(i);
	}
	for(int i = M+1; i <= N; i++) {
		if(i <= 3) continue;
		if(i&1) impar_cima.push_back(i);
		else par_cima.push_back(i);
	}
	v[3] = 1;
	int at = 1;
	for(vector<int>::iterator it = impar_baixo.begin(); it != impar_baixo.end(); it++) {
		v[at] = *it;
		at = *it;
	}
	v[at] = 2;
	at = 2;

	for(vector<int>::iterator it = par_cima.begin(); it != par_cima.end(); it++) {
//		printf("COLOCA %d em %d\n", *it, at);
		v[at] = *it;
		at = *it;
	}
	reverse(impar_cima.begin(), impar_cima.end());
	reverse(par_baixo.begin(), par_baixo.end());
	while(impar_cima.size() + par_baixo.size()) {

		int last = impar_cima[ impar_cima.size() - 1 ];
		v[at] = last;
//		printf("%d em %d, xx\n", last, at);
		at = last;
		impar_cima.pop_back();

		if(par_baixo.empty()) break;

		last = par_baixo[ par_baixo.size() - 1 ];
		v[at] = last;
//		printf("%d em %d, x\n", last, at);
		at = last;
		par_baixo.pop_back();

	}
//	printf("FIM em %d\n", at);
	v[at] = 3;

	printf("%d", v[1]);
	for(int i = 2; i <= N; i++) {
		printf(" %d", v[i]);
	}
	printf("\n");

}



int main() {
	int N;

	while(scanf("%d", &N) == 1 && N) {
		roda(N);
	}
	return 0;
}

Even digit counts (por SUDO)

#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 INF 0x3f3f3f3f

long long table[20][1024], table_nlz[20][1024];

int main() {
	int t;
	
	memset(table[0],0,sizeof(table[0]));
	memset(table_nlz[0],0,sizeof(table_nlz[0]));
	table[0][0] = table_nlz[0][0] = 1;
	
	for (int i=1; i < 20; i++) {
		for (int mask=1023; mask >= 0; mask--) {
			table[i][mask] = 0;
			table_nlz[i][mask] = 0;
			for (int k=0; k < 10; k++) {
				table[i][mask] += table[i-1][mask^(1<<k)];
				table_nlz[i][mask] += table_nlz[i-1][mask^(1<<k)];
			}
		}
		table_nlz[1][1] = 0;
	}
	
	cin >> t;
	while (t--) {
		long long n;
		int len;
		
		cin >> n;
		
		for (len=2; n-table_nlz[len][0] > 0; len+=2) {
			n -= table_nlz[len][0];
		}
		
		string ans = "";
		int mask = 0;
		
		for (int i=0; i < len; i++) {
			int k;
			for (k=!i; n-table[len-i-1][mask^(1<<k)] > 0; k++) {
				n -= table[len-i-1][mask^(1<<k)];
			}
			ans += (char)(k + '0');
			mask ^= 1 << k;
		}
		
		cout << ans << endl;
	}
	
	return 0;
}

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

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

using namespace std;

#define SMAX 1048576

typedef long long lld;

char st[SMAX];
lld m, n;

lld strtonumber(char *s) {
	int sz = strlen(s);
	lld row = 0, col = 0;
	for (int i = 0; i < sz; i++) {
		if ('A' <= s[i] && s[i] <= 'Z') {
			col*= 26;
			col+= s[i] - 'A' + 1;
		} else {
			row*= 10;
			row+= s[i] - '0';
		}
	}
	return (row - 1ll) * n + col;
}

string numbertostr(lld x) {
	x--;
	lld row = x / n;
	lld col = x % n;

	string s = "";
	s = 'A' + (col % 26);
	col/= 26;
	while (col > 0) {
		s+= 'A' + ((col - 1) % 26);
		col--;
		col/= 26;
	}
	reverse(s.begin(), s.end());

	char t[64];
	sprintf(t, "%lld", row+1);
	s+= t;

	return s;
}

int main() {
	scanf("%lld %lld", &m, &n);
	int tests;
	scanf("%d", &tests);
	while (tests--) {
		scanf("%s", st);
		if ('A' <= st[0] && st[0] <= 'Z') {
			printf("%lld\n", strtonumber(st));
		} else {
			printf("%s\n", numbertostr(atoll(st)).c_str());
		}
	}
	return 0;
}

Any fool can do that (por [IME-USP] Isso é tudo pessoal)

#include<cstdio>
#include<cstring>
#define MAX 256
char v[MAX];
int pdset[MAX][MAX];
int pdlist[MAX][MAX];
int set(int a,int b);
int atom(int a) {
	return v[a] == '{' || v[a] == '}' || v[a] == ',';
}

int element(int a,int b) {
	if(a+1 == b && atom(a)) {
		return 1;
	}
	return set(a,b);
}

int list(int a,int b) {
	if(pdlist[a][b] != -1) return pdlist[a][b];
	if(element(a,b)) return 1;
	for(int i = a;i < b; i++) {
		if(v[i] == ',') {
			if(element(a,i) && list(i+1, b)) {
				return pdlist[a][b] = 1;
			}
		}
	}
	return pdlist[a][b] = 0;
}

int element_list(int a,int b) {
	if(a >= b) return 1;
	return list(a,b);
}

int set(int a,int b) {
	if(a + 1 >= b) return 0;
	if(pdset[a][b] != -1) return pdset[a][b];
	if(v[a] == '{' && v[b-1] == '}' && element_list(a+1, b-1)) {
		return pdset[a][b] = 1;
	} else {
		return pdset[a][b] = 0;
	}
}

int main() {
	int T;
	scanf("%d", &T);
	for(int i = 0;i < T;i++) {
		scanf("%s", v);
		printf("Word #%d: ", i+1);
		memset(pdset, -1, sizeof(pdset));
		memset(pdlist, -1, sizeof(pdlist));
		if(set(0, strlen(v))) {
			printf("Set\n");
		} else {
			printf("No Set\n");
		}
	}
	return 0;
}

Forest (por hackermath)

#include <iostream> 
#include <algorithm>
#include <vector>
#include <cstdio>
#include <cstring>
#include <sstream>
#include <vector>
#include <string>
#include <iomanip>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <numeric>
using namespace std;
inline int cmp(double a, double b, double eps = 1e-09){
	return a + eps < b ? -1 : a - eps > b ? 1 : 0;
}
struct point{
	double x, y;
	point(double a = 0, double b = 0): x(a), y(b){}
	
	point rotate(double angle){
		double c = cos(angle), s = sin(angle);
		return point(x * c - y * s, x * s + y * c);
	}
	point operator *(double k){return point(x * k, y * k);}
	point operator /(double k){return point(x / k, y / k);}  
	point operator -(const point& q){return point(x - q.x, y - q.y);}
	inline double mod(){return hypot(x, y);}
	double angle(){return atan2(x, y);}
};
point cent[2000], tangp[3000];
vector<pair<double, double> > part[2000];
double rad[2000];
double pi = acos(-1);

vector<pair<double, double> > parte(point& a, point& b){
	double t1 = a.angle(), t2 = b.angle();
	vector<pair<double, double> > res;
	//cout << t1 << " " << t2 << endl;
	if(t2 < 0 && t1 > 0)  res.push_back(make_pair(-pi, t2)), res.push_back(make_pair(t1, pi));
	else res.push_back(make_pair(t1, t2));
	/*if(t1 < 0) t1 += 2 * pi;
	if(t2 < 0) t2 += 2 * pi;
	
	if(t1 > t2) swap(t1, t2);
	if(t2 - t1 > pi) res.push_back(make_pair(t2, 2 * pi)), res.push_back(make_pair(0, t1));
	else res.push_back(make_pair(t1, t2));
	*/return res;
}
bool used[2000];
bool can[2000];
pair<double, double> final[3000];
struct tri{
	double first, second; int who;
	tri(double x = 0, double y = 0, int i = 0): first(x), second(y), who(i){}
	bool operator <(const tri& B) const{
		if(first != B.first) return first < B.first;
		return second < B.second;
	}
};
tri angulos[3000];
int main(){
			int n;
			while(scanf("%d", &n) && n){
				for(int i = 0; i < n; i++) scanf("%lf %lf %lf", &cent[i].x,&cent[i].y, &rad[i]);
				double best = 0;
				int sz = 0;
				for(int i = 0; i < n; i++){
					point u = cent[i];
					double a = sqrt(u.x*u.x + u.y*u.y - rad[i] * rad[i]);
					double theta = acos(a / u.mod());
					point p = u.rotate(theta) / u.mod() * a;
					point q = u.rotate(-theta) / u.mod() * a;
					tangp[i * 2] = p;
					tangp[i * 2 + 1] = q;
					part[i] = parte(p, q);
					for(int j = 0; j < part[i].size(); j++) angulos[sz++] = tri(part[i][j].first, part[i][j].second, i);
				}
				sort(angulos, angulos + sz);
				
				for(int pivot = 0; pivot < n; pivot++){
					double enclose = tangp[2 * pivot].mod();
					can[pivot] = false;
					for(int i = 0; i < n; i++) if(pivot != i)
						if(cmp(tangp[i * 2].mod(), enclose) <= 0 || cmp(tangp[i * 2 + 1].mod(), enclose) <= 0)
							can[i] = true;
						else can[i] = false;
												
					memset(used, 0, sizeof used);
					int len = 0;
					for(int i = 0; i < sz; i++) if(!used[i] && can[angulos[i].who]){
						double le = angulos[i].first, ri = angulos[i].second;
						for(int j = i; j < sz; j++) 
							if(cmp(angulos[j].first, ri) <= 0 && can[angulos[j].who]) ri = max(ri, angulos[j].second), used[j] = true; 
							else if(can[angulos[j].who]) break;
						final[len++] = make_pair(le, ri);
					}
					vector<pair<double, double> > segs = part[pivot];
					bool sirve = false;
					for(int i = 0; i < segs.size(); i++){
						bool contenido = false;
						for(int j = 0; j < len; j++) if(cmp(final[j].first, segs[i].first) <= 0 && cmp(final[j].second, segs[i].second) >= 0) contenido = true;
						if(!contenido) sirve = true;
					}
					if(sirve) best = max(best, cent[pivot].mod() - rad[pivot]);
				}
				printf("%.03f\n", best);				
			}
}	

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

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

int n, M;
int v[128];
int p[128], id[128], ja[128];

int main() {
	n = 0;
	int aux;
	while(scanf("%d", &aux) == 1) {
		v[n++] = aux;
	}
	int nn = n/2;
	M = v[0];
	for(int i = 0; i < nn; i++) {
		p[i] = v[i];
		M = min(M, v[i]);
	}
	for(int i = nn; i < n; i++) {
		id[i-nn] = v[i];
	}
	n = nn;

	int r = 0;
	memset(ja, 0, sizeof(ja));
	for(int i = 0; i < n; i++) {
		if(!ja[i]) {
			int soma = 0, menor = p[i], at  = i, t =0;
			while(!ja[at]) {
				ja[at] = 1;
				t++;
				soma += p[at];
				menor = min(menor, p[at]);
				at = id[at];
			}
			int s = soma, m = menor;
			int a = s - m + (t-1)*m;
			int b = (s-m) + 2*(m+M) + (t-1)*M;
			r += min(a,b);
		}
	}

	printf("%d\n", r);

	
	return 0;
}

Get away! (por Grito da Trypanosoma)

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cassert>
#include <cmath>
using namespace std;
int T;
int X,Y,M;

int cmp(double a, double b) {
    if(fabs(a-b)<=1e-8)
        return 0;
    if(a<b)
        return -1;
    return 1;
}

struct point {
    double x,y;
    point() {}
    point(double a, double b) : x(a), y(b) {}
    point operator+(const point& a) const {
        return point(x+a.x,y+a.y);
    }
    point operator-(const point& a) const {
        return point(x-a.x,y-a.y);
    }
    point operator/(double a) const {
        return point(x/a,y/a);
    }
};

double sqrdist(const point& a, const point &b) {
    return (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y);
}


struct line {
    double a,b,c;
    line() {}
    line(const point& a1,const point& a2) {
        a=a1.y-a2.y;
        b=a2.x-a1.x;
        c=a1.x*a2.y-a2.x*a1.y;
    }
    line(double a, double b, double c) : a(a), b(b), c(c) {}
    line(double ang) : a(-ang), b(1.0), c(0.0) { }
    line passa_por(const point& p) const {
        return line(a,b,-a*p.x-b*p.y);
    }
    line ortogonal() const {
        return line(-b,a,c);
    }
    bool paralela(const line& l) const {
        return cmp((-a*l.b),(-l.a*b))==0;
    }
};
point intersection(const line& l, const line& l2) {
    return point((l.b*l2.c-l.c*l2.b)/(l.a*l2.b-l2.a*l.b),(-l.a*l2.c+l.c*l2.a)/(l.a*l2.b-l2.a*l.b));;
}

point pontos[2000];

point polygon[2000];
int npolygon;

point polaux[2000];

int npolaux;
int main(void) {
    scanf("%d",&T);
    while(T--) {
        scanf("%d %d %d",&X,&Y,&M);
        for(int i=0;i<M;i++)
            scanf("%lf %lf",&pontos[i].x,&pontos[i].y);

        double ansd=-1;
        point ans;

        for(int i=0;i<M;i++) {
            npolygon=4;
            polygon[0]=point(0,0);
            polygon[1]=point(0,Y);
            polygon[2]=point(X,Y);
            polygon[3]=point(X,0);
            for(int j=0;j<M;j++) if(pontos[i].x!=pontos[j].x or pontos[i].y!=pontos[j].y) {
                line biseccao = line(pontos[i],pontos[j]).ortogonal().passa_por((pontos[i]+pontos[j])/2.0);
                int inter[8];
                int ninter=0;
                for(int k=0;k<npolygon;k++) {
                    int l=(k+1)%npolygon;
                    double l1=biseccao.a*polygon[k].x + biseccao.b*polygon[k].y + biseccao.c;
                    double l2=biseccao.a*polygon[l].x + biseccao.b*polygon[l].y + biseccao.c;
                    //considera que a ponta do comeco intersecta e a ponta do final nao intersecta
                    if( (cmp(l1,0.0)<=0 and cmp(l2,0.0)>0) or (cmp(l1,0.0)>=0 and cmp(l2,0.0)<0) ) {
                        inter[ninter++]=k;
                    }
                }
                assert(ninter<=2);
                if(ninter==2) {
                    double lp=biseccao.a*pontos[i].x + biseccao.b*pontos[i].y + biseccao.c;
                    double lpol=biseccao.a*polygon[(inter[0]+1)%npolygon].x + biseccao.b*polygon[(inter[0]+1)%npolygon].y + biseccao.c;
                    //verifica se a ordem do loop precisa ser trocada
                    if( (cmp(lp,0)<0 and cmp(lpol,0)>0) or (cmp(lp,0)>0 and cmp(lpol,0)<0) )
                        swap(inter[0],inter[1]);
                    npolaux=0;
                    polaux[npolaux++]=intersection(biseccao,line(polygon[inter[0]],polygon[(inter[0]+1)%npolygon]));
                    for(int k=(inter[0]+1)%npolygon;k!=inter[1];k=(k+1)%npolygon) {
                        polaux[npolaux++]=polygon[k];
                    }
                    polaux[npolaux++]=polygon[inter[1]];
                    polaux[npolaux++]=intersection(biseccao,line(polygon[inter[1]],polygon[(inter[1]+1)%npolygon]));
                    //se os 2 ultimos pontos coincidirem
                    if(cmp(polaux[npolaux-1].x,polaux[npolaux-2].x)==0 and cmp(polaux[npolaux-1].y,polaux[npolaux-2].y)==0)
                        npolaux--;
                    memcpy(polygon,polaux,sizeof(polygon[0])*npolaux);
                    npolygon=npolaux;
                }
            }
            for(int j=0;j<npolygon;j++)
                if(sqrdist(pontos[i],polygon[j]) > ansd) {
                    ansd=sqrdist(pontos[i],polygon[j]);
                    ans=polygon[j];
                }
        }
        printf("The safest point is (%.1lf, %.1lf).\n",ans.x,ans.y);

    }

    return 0;
}

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

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <map>
#include <vector>

#define sz 601

#define bsz 32
#define mod 10000

using namespace std;

struct bigint {
	int v[bsz];
	bigint operator + (const bigint &b) const {
		bigint p;
		for (int i = 0; i < bsz; i++) {
			p.v[i] = v[i] + b.v[i];
		}
		for (int i = 0; i+1 < bsz; i++) {
			if (p.v[i] > mod) {
				p.v[i+1]+= p.v[i] / mod;
				p.v[i]%= mod;
			}
		}
		if (p.v[bsz - 1] >= mod) {
			printf("estoura\n");
			exit(1);
		}
		return p;
	}
	bool operator < (const bigint &b) const {
		for (int i = bsz - 1; i >= 0; i--) {
			if (v[i] < b.v[i]) {
				return 1;
			} else if (v[i] > b.v[i]) {
				return 0;
			}
		}
		return 0;
	}
};

bool is_zero(bigint b) {
	for (int i = 0; i < bsz; i++) {
		if (b.v[i] != 0) {
			return 0;
		}
	}
	return 1;
}

bigint *P, *Q;

int main() {
	int n;
	scanf("%d", &n);
	P = (bigint *) malloc(sizeof(bigint) * sz);
	Q = (bigint *) malloc(sizeof(bigint) * sz);
	memset(P, 0, sizeof(bigint) * sz);
	P[0].v[0] = 1;
	for (int i = 1; i <= n; i++) {
		memset(Q, 0, sizeof(bigint) * sz);
		for (int j = 0; j < sz; j++) {
			for (int k = 1; j+k < sz && k <= 6; k++) {
				Q[j+k] = Q[j+k] + P[j];
			}
		}
		swap(P, Q);
	}
	map < bigint, vector<int> > M;
	for (int i = 0; i < sz; i++) {
		if (!is_zero(P[i])) {
			M[P[i]].push_back(i);
		}
	}
	for (map< bigint, vector<int> >::reverse_iterator it = M.rbegin(); it != M.rend(); it++) {
		for (int j = 0; j < it->second.size(); j++) {
			printf("%d\n", it->second[j]);
		}
	}
	return 0;
}

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

#include<cstdio>
#include<cstring>

int main() {
	int casos;
	scanf("%d", &casos);
	while(casos--) {
		int n;
		scanf("%d", &n);
		int x = 0;
		int sohum = 1;
		for(int i =0 ; i < n; i++) {
			int aux;
			scanf("%d", &aux);
			if(aux != 1) sohum = 0;
			x ^= aux;
		}
		if(sohum) {
			x ^= 1;
		}
		if(!x) {
			printf("Alla\n");
		} else {
			printf("Haluc\n");
		}
	}
	return 0;
}

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

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAX 64
#define inf (1<<30)
int N;
int X[MAX];
int Y[MAX];
int pd[MAX][MAX];
int left(int p, int a, int b) {
	return (X[a] - X[p]) * (Y[b] - Y[p]) - (Y[a] - Y[p]) * (X[b] - X[p]);
}
int f(int a,int b) {
	if(b - a < 2) return 0;
	if(pd[a][b] != -1) return pd[a][b];
	int otimo = inf;
	for(int x = a+1; x < b; x++) {
		int l = left(b,a,x);
		if(l > 0) {
			int M = max(f(a, x), f(x, b));
			otimo = min(otimo, max(M, left(b, a, x)));
		}
	}
	return pd[a][b] = otimo;
}
int main() {
	int t;
	scanf("%d", &t);
	while(t--) {
		scanf("%d", &N);
		long long a = 0;
		for(int i = 0;i < N; i++) {
			scanf("%d %d", X + i, Y + i);
		}
		for(int i = 0 ; i < N; i++) {
			a += left(0, i, (i+1)%N);
		}
		if(a < 0) {
			reverse(X, X+N);
			reverse(Y, Y+N);
		}
		memset(pd,-1,sizeof(pd));
		printf("%.1f\n", f(0, N-1)/2.0);
	}

	return 0;
}
blog comments powered by Disqus
Licença Creative Commons
Esta obra foi licenciada com uma Licença
Creative Commons - Atribuição - Uso Não-Comercial - Obras Derivadas Proibidas 3.0 Não Adaptada.