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

Vídeo: Discussão sobre os problemas

Algumas soluções dos competidores

Semi-prime H-numbers (por [IME-USP] Isso é tudo pessoal)

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

using namespace std;

int A[1<<20];
int M[1<<20];

int main() {
	memset(M, 0, sizeof(M));
	M[1] = 1;
	for (int i = 5; i <= (1<<10); i+= 4) {
		if (!M[i]) {
			for (int j = i*i; j < (1<<20); j+= 4*i) {
				M[j] = 1;
			}
		}
	}
	set <int> S;
	int p = 0;
	for (int a = 1; a <= (1<<8); a++) {
		if (!M[4*a + 1]) {
			for (int b = a; b <= (1<<20); b++) {
				if (!M[4*b + 1]) {
					int x = 16*a*b + 4*(a+b) + 1;
					if (x > (1<<20)) {
						break;
					}
					S.insert(x);
				}
			}
		}
	}
	for (set<int>::iterator it = S.begin(); it != S.end(); it++) {
		A[p++] = *it;
	}

	int n;
	while (scanf("%d", &n) && n) {
		int ans = lower_bound(A, A+p, n+1) - A;
		printf("%d %d\n", n, ans);
	}
	return 0;
}

GCD extreme (por AUHAUAH Balões Mano)

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

#define MAXN 200010LL

using namespace std;

int isprime[MAXN], nprim;
long long prim[MAXN];
long long sol[MAXN], phim[MAXN];

void fatora(int n, vector<pair<int, int> > &a)
{
	for(int i = 0; i < nprim && n > 1 && !isprime[n]; i++)
	{
		int pot = 0;
		while(!(n%prim[i]))
		{
			n/=prim[i];
			pot++;
		}
		if(pot) a.push_back(make_pair(prim[i], pot));
	}
	if(n > 1 && isprime[n])
		a.push_back(make_pair(n, 1));	
}

void calcdiv(vector<int> &div, vector<pair<int, int> > &fat, int d = 0)
{
	int pr = fat[d].first;
	if(d == fat.size()) return;
	calcdiv(div, fat, d+1);
	int sz = div.size();
	for(int i = 0; i < fat[d].second; i++, pr *= fat[d].first)
	{
		for(int j = 0; j < sz; j++)
			div.push_back(div[j]*pr);
	}
}

long long phi(int n)
{
	long long res = 1;
	for(int i = 0; i < nprim && n > 1 && !isprime[n]; i++)
	{
		if(!(n%prim[i]))
		{
			n/=prim[i];
			res = res*(prim[i]-1);
			while(!(n%prim[i]))
			{
				res = res*prim[i];
				n /= prim[i];
			}
		}
	}
	if(n > 1 && isprime[n])
		res = res*(n-1);
	return res;
}

int main()
{
	long long i = 2;
	nprim = 0;
	memset(isprime, -1, sizeof(isprime));
	
	prim[nprim] = i; nprim++;
	for(long long j = i*i; j < MAXN; j+=i)
		isprime[j] = 0;
		
	for(i = 3; i*i <= MAXN; i+=2)
	{
		if(isprime[i])
		{
			prim[nprim] = i; nprim++;
			for(long long j = i*i; j < MAXN; j+=i)
				isprime[j] = 0;
		}
	}

	for(; i < MAXN; i++)
		if(isprime[i])
			prim[nprim++] = i;
			
	for(i = 2; i < MAXN; i++)
		phim[i] = phi(i);
	sol[2] = 1;
	
	for(i = 3; i < MAXN; i++)
	{
		sol[i] = sol[i-1];
		if(isprime[i]) sol[i] += i-1;
		else
		{
			vector<pair<int, int> > fat;
			vector<int>div;
			div.push_back(1);
			fatora(i, fat);
			calcdiv(div, fat);
			for(int j = 0; j < div.size(); j++)
				sol[i] += div[j]*phim[i/div[j]];
		}
	}
	for(;;)
	{
		int n;
		scanf("%d", &n);
		if(!n) return 0;
		printf("%lld\n", sol[n]);
	}
	return 0;
}

Maximum sum on a torus (por [IME-USP] Isso é tudo pessoal)

#include<cstdio>
#include<algorithm>
using namespace std;
#define MAX 128
int S[MAX][MAX],pd[MAX][MAX];
int SL[MAX][MAX],SC[MAX][MAX];
int v[MAX][MAX],N;
int aux[MAX];
const int inf = 1<<28;
int sum(int x,int y) {
	if(x < 0 || y < 0 || x >= N || y >= N) return 0;
	if(S[x][y] != -inf) return S[x][y];
	return S[x][y] = sum(x-1, y) + sum(x,y-1) - sum(x-1,y-1) + v[x][y];
}

void arrastalinha() {
	for(int i = 0;i < N;i++) {
		aux[i] = v[0][i];
	}
	for(int i = 1; i < N; i++) {
		for(int j = 0;j < N; j++) {
			v[i-1][j] = v[i][j];
		}
	}
	for(int i = 0;i < N; i++) {
		v[N-1][i] = aux[i];
	}
}
void arrastacoluna() {
	for(int i = 0;i < N; i++) {
		int a = v[i][0];
		for(int j = 1;j < N; j++) {
			v[i][j-1] = v[i][j];
		}
		v[i][N-1] = a;
	}
}

int f(int x,int y) {
	if(x < 0 || y < 0 || x >= N || y >= N) return 0;
	if(pd[x][y] != -inf) return pd[x][y];
	return pd[x][y] = max(sum(x,y) , max(f(x,y-1), f(x-1,y)));
}

void zera() {
	for(int i = 0;i < N; i++) {
		for(int j = 0; j < N; j++) {
			S[i][j] = -inf;
			pd[i][j] = -inf;
			SC[i][j] = -inf;
			SL[i][j] = -inf;
		}
	}
}

int sumC(int x,int y) {
	if(x < 0) return 0;
	if(SC[x][y] != -inf) return SC[x][y];
	return SC[x][y] = sumC(x-1,y) + v[x][y];
}
int sumL(int x,int y) {
	if(y < 0) return 0;
	if(SL[x][y] != -inf) return SL[x][y];
	return SL[x][y] = sumL(x,y-1) + v[x][y];
}
int maxd[MAX];
int maxe[MAX];

int janelaC(int l) {
	int sum = 0;
	int otimo = -inf;
	sum = maxe[0] = sumC(l,0);
	for(int i = 1;i < N; i++) {
		sum += sumC(l,i);
		maxe[i] = max(maxe[i-1], sum);
	}
	sum = maxd[N-1] = sumC(l,N-1);
	for(int i = N-2;i >= 0; i--) {
		sum += sumC(l,i);
		maxd[i] = max(maxd[i+1], sum);
	}
	for(int i = 0;i < N-1; i++) {
		otimo = max(otimo, maxe[i] + maxd[i+1]);
	}
	sum = 0;

	for(int i = 0;i < N; i++) {
		sum += sumC(l,i%N);
		otimo = max(otimo,sum);
		if(sum <= 0) {
			sum = 0;
		}
	}
	return otimo;
}	
int janelaL(int c) {
	int sum = 0;
	int otimo = -inf;
	sum = maxe[0] = sumL(0,c);
	for(int i = 1;i < N; i++) {
		sum += sumL(i,c);
		maxe[i] = max(maxe[i-1], sum);
	}
	sum = maxd[N-1] = sumL(N-1,c);
	for(int i = N-2;i >= 0; i--) {
		sum += sumL(i,c);
		maxd[i] = max(maxd[i+1], sum);
	}
	for(int i = 0;i < N-1; i++) {
		otimo = max(otimo, maxe[i] + maxd[i+1]);
	}
	sum = 0;

	for(int i = 0;i < N; i++) {
		sum += sumL(i%N,c);
		otimo = max(otimo,sum);
		if(sum <= 0) {
			sum = 0;
		}
	}
	return otimo;
}
void imprime() {
	for(int i = 0;i < N; i++) {
		for(int j = 0; j < N; j++) {
			printf("%5d", v[i][j]);
		}
		puts("");
	}
}

int main() {
	int test;
	scanf("%d", &test);
	while(test--) {
		scanf("%d", &N);
		for(int i = 0;i < N; i++) {
			for(int j = 0;j < N; j++) {
				scanf("%d", &v[i][j]);
			}
		}
		int resp = 0;
		/*
		for(int i = 0;i < N; i++) {
			arrastalinha();
			for(int j = 0;j < N; j++) {
				arrastacoluna();
				zera();
				resp = max(resp, f(N-1,N-1));
			}
		}
		printf("%d\n", resp);
		*/
		resp = -inf;
		for(int i = 0; i < N; i++) {
			arrastalinha();
		//	imprime();
			zera();
			for(int l = 0;l < N; l++) {
				resp = max(janelaC(l), resp);
			}
	//		printf("%d\n", resp);
		}
		for(int i = 0; i < N; i++) {
			arrastacoluna();
		//	imprime();
			zera();
			for(int c = 0;c < N; c++) {
				resp = max(janelaL(c), resp);
			}
	//		printf("%d\n", resp);
		}

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

Roxor (por AUHAUAH Balões Mano)

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

using namespace std;

int dp[(1<<16)+9];

int N;
vector<int> vet;
int a;
int MOD[1024];
int pile[64];

int pode(int mask){
	
	if( dp[mask] != -1 ) return dp[mask];
	for(int i = 0; i < N; i++){
		for(int j = i+1; j < N; j++){
			for(int k = j; k < N; k++){
				if( (mask & (1<<i)) == 0 ) continue;
				
				int temp = mask;
				temp &= ~(1 << i);
				if( temp & ( 1 << j ))	
					temp &= ~(1<<j);
				else temp |= ( 1<< j);
				if( temp & ( 1 << k ) )	
					temp &= ~(1<<k);
				else temp |= ( 1<< k);
				if( !pode(temp) ) return dp[mask] = 1;
			}
		}
	}
	return dp[mask] = 0;
}

int main (void){
	
	
	char linha[1000];
	int tc = 1;
	while(scanf("%d", &pile[0]) == 1){
		memset(dp, -1, sizeof(dp));
		// printf("!%d ", pile[0]);
		int c = 1;
		int mask = 0;
		while(1){
			scanf(" %s", linha);
			if( linha[0] == '.' ) break;
			sscanf(linha, "%d", &pile[c++]);
		}
		N = c;
		for(int i = 0 ; i < N; i++){
			// printf("%d ", pile[i]);
			if( pile[i] % 2 ) mask |= (1<<(i));
		}
		// printf("\n");

		bool achei = false;
		int res1, res2, res3;
		for(int i =  0 ; i < N ; i++){
			for(int j = i+1 ; j < N ; j++){
				for(int k = j ; k < N; k++){
					if( pile[i] == 0 ) continue;
					int temp = mask;
					if( (mask & (1<<i)) == 0 ) {
						temp |= (1 << i);
					}
					else{
						temp &= ~(1 << i);
					}
				
					if( temp & ( 1 << j ))	
						temp &= ~(1<<j);
					else temp |= ( 1<< j);
					if( temp & ( 1 << k ) )	
						temp &= ~(1<<k);
					else temp |= ( 1<< k);
					 
					if( !pode(temp)){
						res1 = i;
						res2 = j;
						res3 = k;
						achei = true;
						break;
					}
				}
				if( achei ) break;
			}
			if ( achei ) break;
		}
	
		if( achei ) printf("%d %d %d\n", res1, res2, res3);
		else printf("loser\n");
	}
}

4 Values whose Sum is 0 (por [IME-USP] Isso é tudo pessoal)

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

using namespace std;

#define NMAX 4096

int A[NMAX][4];
int X[NMAX*NMAX], Y[NMAX*NMAX];

int main() {
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d %d %d %d", &A[i][0], &A[i][1], &A[i][2], &A[i][3]);
	}
	int x = 0, y = 0;
	for (register int i = 0; i < n; i++) {
		register int a = A[i][0], c = A[i][2];
		for (register int j = 0; j < n; j++) {
			X[x++] = a + A[j][1];
			Y[y++] = c + A[j][3];
		}
	}
	sort(X, X+x);
	sort(Y, Y+y);
	long long count = 0;
	int i = 0, j = y - 1;
	while (i < x && j >= 0) {
		int a = X[i] + Y[j];
		if (a < 0) {
			i++;
		} else if (a > 0) {
			j--;
		} else {
			register int xx = X[i], yy = Y[j];
			register int cx = 0, cy = 0;
			while (i < x && X[i] == xx) {
				++i;
				cx++;
			}
			while (j >= 0 && Y[j] == yy) {
				--j;
				cy++;
			}
			count+= (long long) cx * (long long) cy;
		}
	}
	printf("%lld\n", count);
	return 0;
}

Marbles on a tree (por [IME-USP] Isso é tudo pessoal)

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

using namespace std;

#define N 10000
vector<int> adj[N];
int qtd[N];
int n;

int qtdV[N], qtdM[N];

int Abs(int x) {
	return x < 0 ? -x : x;
}

int dfsV(int v, int pai) {
	int r = 1;
	for(int i = 0; i < (int) adj[v].size(); i++) {
		int viz = adj[v][i];
		if(viz == pai) continue;
		r += dfsV(viz, v);
	}
	return qtdV[v] = r;
}
int dfsM(int v, int pai) {
	int r = qtd[v];
	for(int i = 0; i < (int) adj[v].size(); i++) {
		int viz = adj[v][i];
		if(viz == pai) continue;
		r += dfsM(viz, v);
	}
	return qtdM[v] = r;
}

int dfs(int v, int pai) {
	int r = 0;
	for(int i = 0; i < (int) adj[v].size(); i++) {
		int viz = adj[v][i];
		if(viz == pai) continue;
		r += dfs(viz, v) + Abs( qtdV[viz] - qtdM[viz] );
	}
	return r;
}

int main() {
	while(scanf("%d", &n) == 1 && n) {
		for(int i = 0; i < n; i++) adj[i].clear();
		for(int i = 0; i < n; i++) {
			int id;
			scanf("%d", &id);
			id--;
			scanf("%d", &qtd[id]);
			int m;
			scanf("%d", &m);
			for(int j = 0; j < m; j++) {
				int viz;
				scanf("%d", &viz);
				viz--;
				adj[id].push_back(viz);
				adj[viz].push_back(id);
			}
		}
		dfsV(0, -1);
		dfsM(0, -1);
		printf("%d\n", dfs(0, -1));
	}
}

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

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
using namespace std;

#define maxN 256

int n, match[maxN], Head, Tail, Queue[maxN], Start, Finish, NewBase, Father[maxN], Base[maxN], Count;
bool graph[maxN][maxN], InQueue[maxN], InPath[maxN], InBlossom[maxN];

char tab[maxN][maxN];
int ja[maxN][maxN];

vector< pair<int,int> > vert;
int dx[] = {-1, -1, -1, 0, 1 , 1, 1, 0};
int dy[] = {-1, 0, 1, 1, 1, 0, -1, -1};

int N,M;

int pode(pair<int,int> p) {
	if(p.first < 0 || p.first >= N || p.second < 0 || p.second >= M) return 0; 
	if(tab[p.first][p.second] == '#') return 0;
	if(ja[p.first][p.second]) return 0;
	return 1;
}

void bfs(int x, int y) {
	queue< pair<int,int> > fila;
	vert.clear();
	memset(ja, 0,sizeof(ja));
	fila.push( make_pair(x,y) );
	ja[x][y] = 1;
	while(!fila.empty()) {
		pair<int,int> aux = fila.front(); fila.pop();
		vert.push_back(aux);
		for(int i =0 ; i < 8; i++) {
			pair<int,int> viz = make_pair( aux.first + dx[i], aux.second + dy[i]);
			if(pode(viz))  {
				fila.push(viz);
				ja[viz.first][viz.second] = 1;
			}
		}
	}
}

int adja(pair<int,int> a, pair<int,int> b) {
	int dx = a.first - b.first;
	int dy = a.second - b.second;
	return abs(dx) <= 1 && abs(dy) <= 1;
}

void CreateGraph(int op) {
	memset(graph, 0, sizeof(graph));
	if(op == 0) {
		scanf("%d %d", &N, &M);
	}
	int x,y;
	for(int i = 0; i < N; i++){
		if(op == 0) {
			scanf("%s", tab[i]);
		}
		for(int j = 0; j < M; j++) {
			if(tab[i][j] == 'K') {
				x = i;
				y = j;
			}
		}
	}

	bfs(x,y);
	n = vert.size();
	for(int i = op; i < vert.size(); i++) {
		for(int j = op; j < vert.size(); j++) {
			if(adja(vert[i],vert[j])) {
				graph[i+1][j+1] = 1;
			}
		}
	}

}

void Push(int u) {
	Queue[Tail++] = u;
	InQueue[u] = true;
}

int Pop() {
	return Queue[Head++];
}

int FindCommonAncestor(int u, int v) {
	memset(InPath, 0, sizeof(InPath));
	while (true) {
		u = Base[u];
		InPath[u] = true;
		if (u == Start) break;
		u = Father[match[u]];
	}
	while (true) {
		v = Base[v];
		if (InPath[v]) break;
		v = Father[match[v]];
	}
	return v;
}

void ResetTrace(int u) {
	int v ;
	while (Base[u] != NewBase) {
		v = match[u];
		InBlossom[Base[u]] = 1;
		InBlossom[Base[v]] = 1;
		u = Father[v];
		if (Base[u] != NewBase) Father[u] = v;
	}
}

void BlossomContract(int u, int v) {
	NewBase = FindCommonAncestor(u, v);
	memset(InBlossom, 0, sizeof(InBlossom));
	ResetTrace(u);
	ResetTrace(v);
	if (Base[u] != NewBase) Father[u] = v;
	if (Base[v] != NewBase) Father[v] = u;
	for (u = 1; u <= n; u++) {
		if (InBlossom[Base[u]]) {
			Base[u] = NewBase;
			if (!InQueue[u]) Push(u);
		}
	}
}

void FindAugmentingPath() {
	int u, v;
	memset(InQueue, false, sizeof(InQueue));
	memset(Father, 0, sizeof(Father));
	for (u = 1; u <= n; u++) Base[u] = u;
	Head = 1;
	Tail = 1;
	Push(Start);
	Finish = 0;
	while (Head < Tail) {
		u = Pop();
		for (v = 1; v <= n; v++) {
			if ((graph[u][v]) && (Base[u] != Base[v]) && (match[u] != v)) {
				if ((v == Start) || ((match[v] > 0) && (Father[match[v]] > 0)))
					BlossomContract(u, v);
				else if (Father[v] == 0) {
					Father[v] = u;
					if (match[v] > 0) {
						Push(match[v]);
					} else {
						Finish = v;
						return;
					}
				}
			}
		}
	}
}

void AugmentPath() {
	int u, v, w;
	u = Finish;
	while (u > 0) {
		v = Father[u];
		w = match[v];
		match[v] = u;
		match[u] = v;
		u = w;
	}
}

void Edmonds() {
	int u;
	memset(match, 0, sizeof(match));
	for (u = 1; u <= n; u++) {
		if (match[u] == 0) {
			Start = u;
			FindAugmentingPath();
			if (Finish > 0) AugmentPath();
		}
	}
}

int PrintMatch() {
	int emp = 0;
	int u;
	for (u = 1; u <= n; u++) {
		if (match[u] > 0) emp++;
	}
	return emp;

	int sobra = (n - emp);
	//printf("n = %d, emp = %d, sobra = %d\n", n, emp, sobra);
	if(sobra) {
		printf("B\n");
	} else {
		printf("A\n");
	}
	for (u = 1; u <= n; u++) {
//		if (u < match[u]) printf("%d %d\n", u, match[u]);
	}

}

int main() {
	int casos;
	scanf("%d", &casos);
	for(int t = 1; t <= casos; t++) {
		CreateGraph(0);
		Edmonds();
		int q1 = PrintMatch();
		CreateGraph(1);
		Edmonds();
		int q2 = PrintMatch();
		printf("Case #%d: %c\n", t, q1 != q2 ? 'A' : 'B');
	}
	return 0;
}

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

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

using namespace std;

int ini[4][4];

int ok() {
	for(int i = 0; i < 4; i++) {
		for(int j = 1; j < 4; j++) {
			if(ini[i][j] < ini[i][j-1]) return 0;
			if(ini[j][i] < ini[j-1][i]) return 0;
		}
	}
	return 1;
}

int pode(int v, int x, int y) {
	if(ini[x][y] < v) return 0;
	for(int i = x+1; i < 4; i++) {
		if(ini[i][y] < v) return 0;
	}
	for(int j = y+1; j < 4; j++) {
		if(ini[x][j] < v) return 0;
	}
	for(int i = 0; i < x; i++) {
		if(ini[i][y] > v) return 0;
	}
	for(int j = 0; j < y; j++) {
		if(ini[x][j] > v) return 0;
	}

	return 1;
}

int resolve(int v) {
	if(v == 17) return 0;
	if(ok()) return 0;
	int x, y;
	for(int i = 0; i < 4; i++) {
		for(int j = 0; j < 4; j++) {
			if(ini[i][j] == v) {
				x = i;
				y = j;
				i = 10;
				j = 10;
			}
		}
	}

	int r = 10000;


	for(int i = 0; i < 4; i++) {
		for(int j = 0; j < 4; j++) {
			int soma = 1;
			if(i == x && j == y) soma = 0;
			if(pode(v, i, j)) {
				swap(ini[x][y], ini[i][j]);
				r = min(r, resolve(v+1)+soma);
				swap(ini[x][y], ini[i][j]);
			}
		}
	}
	return r;
}

int main() {
	while(1) {
		
		for(int i = 0; i < 4; i++) {
			for(int j = 0; j < 4; j++) {
				if(scanf("%d", &ini[i][j]) != 1) return 0;
			}
		}
		printf("%d\n", resolve(1));
	}
	return 0;
}