Desafios de Programação no Verão

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

» 13 de janeiro de 2011

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

Problemas

POS Competidor Resultado Pontuação A B C D E  
1 Eduardo Ribas 4 (252) 99 +0 +0 +0 +0 -1  
2 Tiago Madeira 3 (332) 97 +0 +0 +0      
3 Guilherme Souza 3 (346) 95 +5 +1 +0 -6    
4 walter erquinigo 3 (369) 93 -17 +2   +0 +1  
5 Atol Fortin 3 (439) 91 +1 +0 +6 -5    
6 Felipe Abella 3 (473) 89 +1 +2 +1      
7 Ricardo Hahn 2 (190) 87 +1 +1 -1 -2    
8 Ricardo Oliveira 2 (222) 85 +2 +0 -2      
9 Gabriel Luís Mello Dalalio 2 (223) 83 +1       +0  
10 Daniel Ribeiro Moreira 2 (263) 81 -1 +0 +3      
11 Cesar Kawakami 2 (277) 79 +2 +1   -8    
12 Natan Costa Lima 2 (414) 77 +5 +0 -2      
13 Leonardo Marchetti 2 (418) 75 +3 +1   -2    
14 Pedro Veras 2 (579) 73 +6   +4      
15 Phyllipe Cesar 1 (50) 71 -7 +0        
16 Cesar Gamboa 1 (109) 69 -2 +0 -3      
17 Andre Hahn 1 (119) 67 +2          
18 Jesus Alejandro 1 (126) 65   +1        
19 Felipe Menezes Machado 1 (163) 63 +5 -9 -4      
20 Caique Porto Lira 1 (167) 61 +1 -1        
21 Rafael Brandão 1 (168) 59 -4 +0        
22 daniel soncco 1 (196) 57   +1        
23 Igor Ramos 1 (196) 55 -4 +5        
24 Douglas Santos 1 (196) 53   +1        
25 Gaston Ingaramo 1 (259) 51   +2     -2  
38 Filipe Martins 1 (308) 25 +7          
38 Luiz Afonso 0 (0) 25   -1 -3      
38 Adriana Libório 0 (0) 25            
38 Igor R. de Assis 0 (0) 25            
38 Leonardo Martinez 0 (0) 25   -1        
38 Eric Destefanis 0 (0) 25 -3          
38 Renan Ferraz Pires 0 (0) 25            
38 Davi Duarte Pinheiro 0 (0) 25 -4          
38 Vinicius Ruoso 0 (0) 25   -1 -4      
38 gustavo pacianotto gouveia 0 (0) 25   -9        
38 Victor Jatobá 0 (0) 25            
38 Leonardo Inácio 0 (0) 25 -12          
38 Alex Alves da Paixão 0 (0) 25            
38 Thiago Sonego Goulart 0 (0) 25 -5   -7      
38 Renato Parente 0 (0) 25   -1        
38 Renato Ferreira 0 (0) 25 -5   -2      
38 Matias Daniel Tealdi 0 (0) 25 -4          
38 Arthur 0 (0) 25   -3        
38 Paulo Costa 0 (0) 25 -7          
38 Leonardo Flores Zambaldi 0 (0) 25     -2      
38 Vinicius Flores Zambaldi 0 (0) 25   -6        
38 Nicolas Gumiel 0 (0) 25     -10      
38 Victor Hugo Paredes Mora 0 (0) 25     -1      
38 Edwin Macelo Guzman Buezo 0 (0) 25   -1        
38 Pablo Pinheiro 0 (0) 25 -8 -1       </div>

Vídeo: Discussão sobre os problemas

Algumas soluções dos competidores

Regata de Cientistas (por Renato Ferreira)

#include <cstdio>
#include <vector>
#include <utility>
#include <set>
#include <cstdlib>
#include <cmath>
#include <climits>

#define abs(x) ((x) < 0 ? (-(x)) : (x))

#define INF (2000000000.0)

using namespace std;

const int MAX_N = 500;

pair < int, int > points[MAX_N];
int seg[MAX_N];
pair < pair < int, int >, pair < int, int > > segs[MAX_N];
int n;
int np;
long double adj[MAX_N][MAX_N];
long double dist[MAX_N];
vector < int > ladj[MAX_N];

int prod(int x1, int y1, int x2, int y2, int x3, int y3) {
	return x1*(y2 - y3) + x2*(y3 - y1) + x3*(y1 - y2);
}

bool intersec(int i, int j, int k) {
	int x1 = points[i].first, y1 = points[i].second;
	int x2 = points[j].first, y2 = points[j].second;
	int x3 = segs[k].first.first, y3 = segs[k].first.second;
	int x4 = segs[k].second.first, y4 = segs[k].second.second;

	int p1 = prod(x1, y1, x2, y2, x3, y3);
	int p2 = prod(x1, y1, x2, y2, x4, y4);
	int p3 = prod(x3, y3, x4, y4, x1, y1);
	int p4 = prod(x3, y3, x4, y4, x2, y2);

	if (p1 == 0 || p2 == 0 || p3 == 0 || p4 == 0)
		return false;

	int s1 = p1 / abs(p1);
	int s2 = p2 / abs(p2);
	int s3 = p3 / abs(p3);
	int s4 = p4 / abs(p4);

	return s1 != s2 && s3 != s4;
}

int dcmp(const int &a, const int &b, double EPS = 1e-9) {
	if (a + EPS >= b) {
		if (b + EPS >= a)
			return 0;
		return 1;
	}
	return -1;
}

struct cmp {
	bool operator () (const int &a, const int &b) {
		double da = hypot(abs(points[np - 1].first - points[a].first), abs(points[np - 1].second - points[a].second));

		double db = hypot(abs(points[np - 1].first - points[b].first), abs(points[np - 1].second - points[b].second));
		int r = dcmp(dist[a] + da, dist[b] + db);
		if (r != 0)
			return (r == -1);
		return a < b;
	}
};

void dijkstra() {
	for (int i = 0; i < np; i++)
		dist[i] = INF;
	dist[0] = 0;
	set < int, cmp > vert;
	vert.insert(0);
	while (!vert.empty()) {
		int u = *vert.begin();
		vert.erase(vert.begin());
		for (int i = 0; i < (int) ladj[u].size(); i++) {
			int v = ladj[u][i];
			if (dcmp(dist[u] + adj[u][v], dist[v]) == -1) {
				vert.erase(v);
				dist[v] = dist[u] + adj[u][v];
				vert.insert(v);
			}
		}	
	}
}

int main() {
	int x1, y1, x2, y2;
	while (scanf("%d %d %d %d %d", &x1, &y1, &x2, &y2, &n)) {
		if (x1 == 0 && y1 == 0 && x2 == 0 && y2 == 0 && n == 0)
			break;

		int cp = 0;
		points[cp++] = make_pair(x1, y1);
		int cs = 0;
		int css = 0;
		seg[cs++] = -1;
		for (int i = 0; i < n; i++) {
			int x, y, xx, yy;
			scanf("%d %d %d %d", &x, &y, &xx, &yy);

			points[cp++] = make_pair(x, y);
			points[cp++] = make_pair(xx, yy);

			seg[cs++] = i;
			seg[cs++] = i;

			segs[css++] = make_pair(make_pair(x, y), make_pair(xx, yy));
		}
		seg[cs++] = -2;
		points[cp++] = make_pair(x2, y2);
		np = cp;

		for (int i = 0; i < np; i++)
			ladj[i].clear();

		for (int i = 0; i < np; i++) for (int j = i + 1; j < np; j++) {
			bool lose = false;
			for (int k = 0; k < css; k++) if (intersec(i, j, k)) {
				lose = true;
				break;
			}
			if (lose)
				continue;

			adj[i][j] = adj[j][i] = hypot(abs(points[i].first - points[j].first), abs(points[i].second - points[j].second));
			ladj[i].push_back(j);
			ladj[j].push_back(i);
		}

		dijkstra();
		printf("%.2Lf\n", dist[np - 1]);
	}

	return 0;
}

Rota crítica (por Renato Ferreira)

#include <cstdio>
#include <vector>
#include <map>
#include <string>

using namespace std;

const int MAX_N = 110;

int n, m;
int adj[MAX_N][MAX_N];
bool vis[MAX_N];
bool intree[MAX_N][MAX_N];
bool needed[MAX_N][MAX_N];

void make_tree(int u) {
	vis[u] = true;
	for (int v = 0; v < n; v++) if (!vis[v] && adj[v][u]) {
		intree[v][u] = true;
		make_tree(v);
	}
}

void dfs(int u) {
	vis[u] = true;
	for (int v = 0; v < n; v++) if (!vis[v] && adj[u][v])
		dfs(v);
}

int main() {
	while (scanf("%d %d", &n, &m) && (n != 0 || m != 0)) {
		map < string, int > ids;
		for (int i = 0; i < n; i++) {
			char buffer[30];
			scanf("%s", buffer);
			ids[string(buffer)] = i;
			vis[i] = false;
		}

		for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
			adj[i][j] = 0;
			intree[i][j] = false;
			needed[i][j] = false;
		}

		vector < string > va, vb;
		for (int i = 0; i < m; i++) {
			string a, b;
			char buffer[30];
			scanf("%s", buffer); a = buffer;
			scanf("%s", buffer); b = buffer;
			va.push_back(a);
			vb.push_back(b);

			adj[ids[a]][ids[b]]++;
		}

		make_tree(0);

		for (int u = 0; u < n; u++) for (int v = 0; v < n; v++) if (intree[u][v]) {
			adj[u][v]--;
			for (int w = 0; w < n; w++)
				vis[w] = false;
			dfs(u);
			if (!vis[0])
				needed[u][v] = true;
			adj[u][v]++;
		}

		bool has = false;
		for (int i = 0; i < m; i++) {
			int u = ids[va[i]];
			int v = ids[vb[i]];
			if (needed[u][v]) {
				printf("%s %s\n", va[i].c_str(), vb[i].c_str());
				has = true;
			}
		}

		if (!has)
			printf("Nenhuma\n");

		printf("\n");
	}

	return 0;
}

Set (por Renato Ferreira)

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

using namespace std;

struct Kind {
	int a, b, c;
	Kind() {}
	Kind(int _a, int _b, int _c) : a(_a), b(_b), c(_c) {}
};

int cnt[3][3];
vector < pair < Kind, Kind > > sets;

int solve(int curr) {
	if (curr == (int) sets.size()) {
		int ans = 0;
		for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++)
			ans += cnt[i][j] / 3;
		return ans;
	}

	int ans = 0;
	for (int am = 0; am < 3; am++) {
		pair < int, int > c1 = make_pair(sets[curr].first.a, sets[curr].second.a);
		pair < int, int > c2 = make_pair(sets[curr].first.b, sets[curr].second.b);
		pair < int, int > c3 = make_pair(sets[curr].first.c, sets[curr].second.c);
		if (am > cnt[c1.first][c1.second])
			continue;
		if (am > cnt[c2.first][c2.second])
			continue;
		if (am > cnt[c3.first][c3.second])
			continue;
		
		cnt[c1.first][c1.second] -= am;
		cnt[c2.first][c2.second] -= am;
		cnt[c3.first][c3.second] -= am;
		ans = max(ans, am + solve(curr + 1));
		cnt[c1.first][c1.second] += am;
		cnt[c2.first][c2.second] += am;
		cnt[c3.first][c3.second] += am;
	}

	return ans;
}

int main() {
	sets.push_back(make_pair(Kind(0,0,0), Kind(0,1,2)));
	sets.push_back(make_pair(Kind(1,1,1), Kind(0,1,2)));
	sets.push_back(make_pair(Kind(2,2,2), Kind(0,1,2)));

	sets.push_back(make_pair(Kind(0,1,2), Kind(0,0,0)));
	sets.push_back(make_pair(Kind(0,1,2), Kind(1,1,1)));
	sets.push_back(make_pair(Kind(0,1,2), Kind(2,2,2)));

	sets.push_back(make_pair(Kind(0,1,2), Kind(0,1,2)));
	sets.push_back(make_pair(Kind(0,1,2), Kind(0,2,1)));
	sets.push_back(make_pair(Kind(0,1,2), Kind(1,0,2)));
	sets.push_back(make_pair(Kind(0,1,2), Kind(1,2,0)));
	sets.push_back(make_pair(Kind(0,1,2), Kind(2,0,1)));
	sets.push_back(make_pair(Kind(0,1,2), Kind(2,1,0)));

	int n;
	while (scanf("%d", &n) && n > 0) {
		fill(*cnt, *cnt + 3*3, 0);
		for (int i = 0; i < n; i++) {
			char s[50], t[50];
			scanf("%s %s", s, t);

			int a = 2, b = 2;
			if (s[0] == 'u')
				a = 0;
			if (s[0] == 'd')
				a = 1;

			if (t[0] == 't')
				b = 0;
			if (t[0] == 'q')
				b = 1;

			cnt[a][b]++;
		}

		printf("%d\n", solve(0));
	}

	return 0;
}

Olimpíadas (por Felipe Abella)

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <numeric>
#include <climits>
#include <sstream>
#include <cstring>
#include <cassert>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <map>
#include <set>

#define INF (INT_MAX/3)
#define MAXV 51
#define MAXA 51
#define MAXT (MAXV+MAXA+2)

typedef long long lint;

using namespace std;

int caps[MAXT][MAXV][MAXV], revcaps[MAXT][MAXV][MAXV];
int mark[MAXT][MAXV], until, n;

int augment(int t, int v, int maxf)
{
	if (v == n-1)
		return maxf;

	mark[t][v] = 1;

	for (int v2 = 0; v2 < n; v2++)
		if (t+1 <= until && !mark[t+1][v2] && caps[t][v][v2] > 0) {
			int x = augment(t+1, v2, min(maxf, caps[t][v][v2]));
			if (x > 0) {
				caps[t][v][v2] -= x;
				revcaps[t][v2][v] += x;
				return x;
			}
		}

	for (int v2 = 0; v2 < n; v2++)
		if (t-1 >= 0 && !mark[t-1][v2] && revcaps[t-1][v][v2] > 0) {
			int x = augment(t-1, v2, min(maxf, revcaps[t-1][v][v2]));
			if (x > 0) {
				revcaps[t-1][v][v2] -= x;
				caps[t][v2][v] += x;
				return x;
			}
		}

	return 0;
}

int main(int argc, char ** argv)
{
	int m, A;

	while (scanf("%d %d %d", &n, &m, &A), !(n == 0 && m == 0 && A == 0)) {
		int maxt = n+A+2;

		for (int w = 0; w < maxt; w++)
			for (int v = 0; v < n; v++)
				for (int v2 = 0; v2 < n; v2++)
					caps[w][v][v2] = revcaps[w][v][v2] = 0;

		for (int i = 0; i < m; i++) {
			int s, t, size;
			scanf("%d %d %d", &s, &t, &size);
			s--, t--;
			for (int w = 0; w+1 < maxt; w++)
				caps[w][s][t] += size;
		}
		for (int w = 0; w+1 < maxt; w++)
			for (int v = 0; v < n; v++)
				caps[w][v][v] = INF;

		int t, flow = 0;
		for (t = 0; flow < A && t < maxt; t++) {
			int x;
			until = t+1;
			while (memset(mark, 0, sizeof(mark)), x = augment(0, 0, INF), x) {
				flow += x;
				if (flow >= A)
					break;
			}
		}
		printf("%d\n", t);
	}

	return 0;
}

Registrador de Deslocamento (por Felipe Abella)

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <numeric>
#include <climits>
#include <sstream>
#include <cstring>
#include <cassert>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <map>
#include <set>

#define INF (INT_MAX/3)
#define MAXB 32

typedef unsigned int uint;
typedef long long lint;

using namespace std;

int pip[MAXB], nbit;
int matrix[MAXB][MAXB], invmatrix[MAXB][MAXB];
int md[MAXB][MAXB], curr[MAXB][MAXB], temp[MAXB][MAXB];

void mult(int C[MAXB][MAXB], const int A[MAXB][MAXB], const int B[MAXB][MAXB])
{
	for (int i = 0; i < nbit; i++)
		for (int j = 0; j < nbit; j++) {
			C[i][j] = 0;
			for (int k = 0; k < nbit; k++)
				C[i][j] += A[i][k] * B[k][j];
			C[i][j] %= 2;
		}
}

void exp(int A[MAXB][MAXB], int B[MAXB][MAXB], int y)
{
	for (int i = 0; i < nbit; i++) {
		for (int j = 0; j < nbit; j++)
			A[i][j] = 0;
		A[i][i] = 1;
	}

	for (int i = 0; y; i++) {
		if (y&(1<<i)) {
			y -= (1<<i);
			memcpy(temp, A, sizeof(temp));
			mult(A, temp, B);
		}
		memcpy(temp, B, sizeof(temp));
		mult(B, temp, temp);
	}
}

uint getval(int M[MAXB][MAXB], uint state)
{
	int A[MAXB], B[MAXB];
	for (int i = 0; i < nbit; i++) {
		A[i] = state%2U;
		state /= 2U;
	}
	for (int i = 0; i < nbit; i++) {
		B[i] = 0;
		for (int j = 0; j < nbit; j++)
			B[i] += A[j] * M[j][i];
		B[i] %= 2;
	}

	uint ret = 0;
	for (int i = nbit-1; i >= 0; i--)
		ret = 2U*ret + B[i];

	return ret;
}

int main(int argc, char ** argv)
{
	int npip;

	while (scanf("%d %d", &nbit, &npip), nbit) {
		uint start, end;
		const int D = 1<<((nbit+1)/2);

		fill(pip, pip+nbit, 0);

		for (int i = 0; i < npip; i++) {
			int x;
			scanf("%d", &x);
			pip[x] = 1;
		}
		
		scanf("%x %x", &start, &end);

		memset(matrix, 0, sizeof(matrix));
		for (int y = 1, x = 0; y < nbit; y++, x++)
			matrix[y][x] = 1;
		for (int y = 0; y < nbit; y++)
			matrix[y][nbit-1] = pip[y];

		memset(invmatrix, 0, sizeof(invmatrix));
		for (int y = 0, x = 1; x < nbit; y++, x++)
			invmatrix[y][x] = 1;
		for (int y = 0; y < nbit; y++)
			invmatrix[y][0] = pip[(y+1)%nbit];

		map <uint, int> cands;

		uint val = end;
		for (int r = 0; r < D; r++) {
			if (cands.find(val) == cands.end())
				cands[val] = r;
			val = getval(invmatrix, val);
		}

		exp(md, matrix, D);

		val = start;
		for (int q = 0; q <= D; q++) {
			if (cands.find(val) != cands.end()) {
				lint result = (lint)q * (lint)D + (lint)cands[val];
				uint ret = result;
				printf("%u\n", ret);
				goto done;

			}
			val = getval(md, val);
		}
		printf("*\n");
	done:
		;
	}

	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.