ACM ICPC Bolivia 2013

[latexpage]Problem Set: ACM ICPC Bolivia 2013 problem-set

Online judge: SPOJ Bolivia

Hints

A – La mejor Empresa: When cutting the best solution in two, both sides are always positive integers
B – Cuantos Grafos: From 1 to 4999 there aren’t many edges in the graph. With DFSs can get the total number of connected graphs
C – Ajtapi: The letters ‘a’, ‘e’, ‘i’, ‘o’ and ‘u’ can be represented as masks of  $2^5$ and you will need a DP to get the best decisions. Another solution implicate a flow in a Graph 😉
D – Cachinitaball: Draw a line between the initial point (center of the cachinitaball) and the end point
E – Engranajes: Divide the graph in subgraphs, for each subgraph verify that it possible to rotate the gears. Rotate one gear and solve the subgraph using that gear
F – Inundacion: N = 1000 generates a graph with a maximum of 1000000 edges and you only need N-1 edges to connect the graph
G – Llama ola k ase: my preciousssss XD lcm to find something interesting
H – Poquer de huevo: Easy, Implementation

Solutions

C – Ajtapi

int n;
vector<pair<string, string> > food;

bool solve() {
	vector<bool> DP(1<<5, false);
	DP[0] = true;
	for(int i=0; i<n ;i++) {
		int x = 0, y = 0;
		set<int> v;
		for(int j=0; j<food[i].first.size() ;j++) {
			switch(food[i].first[j]) {
				case 'a': x |= 1; break;
				case 'e': x |= 1<<1; break;
				case 'i': x |= 1<<2; break;
				case 'o': x |= 1<<3; break;
				case 'u': x |= 1<<4;
			}
		}
		for(int j=0; j<food[i].second.size() ;j++) {
			switch(food[i].second[j]) {
				case 'a': y |= 1; break;
				case 'e': y |= 1<<1; break;
				case 'i': y |= 1<<2; break;
				case 'o': y |= 1<<3; break;
				case 'u': y |= 1<<4;
			}
		}
		for(int j=0; j<DP.size() ;j++) if(DP[j]) {
			v.insert(j|x);
			v.insert(j|y);
		}
		for(set<int>::iterator it=v.begin(); it!=v.end() ;it++) {
			DP[(*it)] = true;
		}
	}
	return DP[(1<<5)-1];
}

int main(){
	cin >> n;
	while(n) {
		food.resize(n);
		for(int i=0; i<n ;i++)
			cin >> food[i].first >> food[i].second;
		if(solve()) printf("EXISTEn");
		else printf("NO EXISTEn");
		cin >> n;
	}
}

G – Llama ola k ase
H – Poquer de huevo

vector<int> dados(5);

void leer() {
	for(int i=0; i<5 ;i++) {
		cin >> dados[i];
	}
}

int main(){
	leer();
	while(dados[0]) {
		vector<int> vis(7, 0);
		int val = 0;
		for(int i=0; i<5 ;i++) {
			vis[ dados[i] ]++;
			if(vis[ dados[i] ] == 3)
				val = dados[i];
		}
		if(val && vis[ 7-val ])
			printf("Poquer de huevon");
		else
			printf("Non");
		leer();
	}
}