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

Vídeo: Discussão sobre os problemas

Algumas soluções dos competidores

Fractal Labyrinth (por Renato Ferreira)

#include <cstdio>
#include <algorithm>
#include <set>
#include <climits>

using namespace std;

const int INF = (INT_MAX / 3);

const int MAX_D = 22;
const int MAX_K = 7;
const int MAX_N = MAX_D * MAX_K;

struct Path {
	int u, v;
	Path() {}
	Path(int _u, int _v) {
		u = _u, v = _v;
		if (u > v)
			swap(u, v);
	}
};

bool adj[MAX_N][MAX_N];
int dist[MAX_N][MAX_N];

bool operator < (const Path &a, const Path &b) {
	int da = dist[a.u][a.v];
	int db = dist[b.u][b.v];
	if (da != db)
		return da < db;
	if (a.u != b.u)
		return a.u < b.u;
	return a.v < b.v;
}

int main() {
	int d, k, m, source, dest;
	scanf("%d %d %d", &d, &k, &m);
	for (int i = 0; i < m; i++) {
		int a1, u1, a2, u2;
		scanf("%d.%d - %d.%d", &a1, &u1, &a2, &u2);
		int u = d*a1 + u1;
		int v = d*a2 + u2;
		adj[u][v] = adj[v][u] = true;
		//printf("%d adj %d\n", u, v);
	}
	scanf("%d %d", &source, &dest);
	if (source > dest)
		swap(source, dest);

	set < Path > paths;
	int n = d*(k + 1);
	for (int i = 0; i < n; i++) for (int j = i; j < n; j++) {
		dist[i][j] = dist[j][i] = INF;
		if (adj[i][j]) {
			dist[i][j] = dist[j][i] = 1;
			//printf("inserindo caminho %d a %d dist %d\n", i, j, dist[i][j]);
			paths.insert(Path(i, j));
		}
	}

	for (int i = 0; i < n; i++) {
		dist[i][i] = 0;
		paths.insert(Path(i, i));
	}

	while (!paths.empty()) {
		Path p = *paths.begin();
		paths.erase(paths.begin());
		int u = p.u, v = p.v;

		//printf("%d a %d dist %d\n", u, v, dist[u][v]);
		if (u == source && v == dest) {
			printf("%d\n", dist[u][v]);
			return 0;
		}

		if (u < d && v < d) {
			int uu = u + d, vv = v + d;
			while (uu < n && vv < n) {
				if (dist[u][v] < dist[uu][vv]) {
					paths.erase(Path(uu, vv));
					dist[uu][vv] = dist[vv][uu] = dist[u][v];
					paths.insert(Path(uu, vv));
					//printf("inseriu interno %d a %d dist %d\n", uu, vv, dist[uu][vv]);
				}
				uu += d, vv += d;
			}
		}

		int vert[] = { u, v };
		for (int i = 0; i < 2; i++) for (int k = 0; k < n; k++) if (dist[k][vert[1 - i]] < INF) {
			if (dist[u][v] + dist[k][vert[1 - i]] < dist[vert[i]][k]) {
				paths.erase(Path(vert[i], k));
				dist[vert[i]][k] = dist[k][vert[i]] = dist[u][v] + dist[k][vert[1 - i]];
				//printf("expandindo para %d a %d dist %d\n", vert[i], k, dist[vert[i]][k]);
				paths.insert(Path(vert[i], k));
			}
		}
	}

	printf("no solution\n");

	return 0;
}

Necessary Coins (por Renato Ferreira)

#include <cstdio>
#include <algorithm>

using namespace std;

const int MAX_N = 205;
const int MAX_C = 10005;

int val[MAX_N];
bool can[MAX_N][MAX_C];
bool can2[MAX_N][MAX_C];
bool needed[MAX_N];
bool vis[MAX_N][MAX_C];

int main() {
	int n, x;
	int total = 0;
	scanf("%d %d", &n, &x);
	for (int i = 0; i < n; i++) {
		scanf("%d", &val[i]);
		total += val[i];
	}

	for (int i = 0; i < n; i++)
		needed[i] = false;
	int ans = 0;
	
	for (int i = 0; i <= n; i++) for (int j = 0; j <= x; j++)
		can[i][j] = can2[i][j] = vis[i][j] = false;
	for (int i = 0; i <= n; i++) {
		can[i][x] = can2[i][x] = true;
		vis[i][0] = true;
	}

	for (int i = n-1; i > 0; i--) for (int j = x; j >= 0; j--) if (vis[i][j]) {
		if (j + val[i] <= x)
			vis[i - 1][j + val[i]] = true;
		vis[i - 1][j] = true;
	}

	for (int j = x; j >= 0; j--) for (int i = 0; i < n; i++) {
		if (i > 0 && j + val[i] <= x && can[i - 1][j + val[i]]) {
			can[i][j] = true;
		}
		if (i > 0 && can[i - 1][j]) {
			can[i][j] = can2[i][j] = true;
		}
		if (i == 0 && val[i] + j == x)
			can[i][j] = true;
	}

	for (int i = 0; i < n; i++) {
		bool ok = false;
		for (int j = 0; j <= x; j++) if (vis[i][j] && can2[i][j]) {
			ok = true;
			break;
		}
		if (!ok) {
			ans++;
			needed[i] = true;
		}
	}

	printf("%d\n", ans);
	bool first = true;
	for (int i = 0; i < n; i++) if (needed[i]) {
		if (!first)
			printf(" ");
		first = false;
		printf("%d", val[i]);
	}
	if (ans > 0)
		printf("\n");

	return 0;
}

Elementary Symmetric Functions (por Renato Ferreira)

#pragma comment(linker, "/STACK:16777216")

#include <cstdio>
#include <algorithm>
#include <utility>
#include <vector>
#include <cassert>

using namespace std;

typedef long long lint;

const int MAX_N = 80005;
const int MAX_T = 4*MAX_N;

int p;
lint tree[MAX_T][8];

void update(int id, int l, int r, int x, int delta) {
//	assert(id < MAX_T);
	
	if (x < l || x > r)
		return;
	if (x == l && x == r) {
		tree[id][0] = 1;
		tree[id][1] += delta;
		tree[id][1] %= p;
		while (tree[id][1] < 0)
			tree[id][1] += p;
	}
	else {
		update(2*id, l, (l + r)/2, x, delta);
		update(2*id + 1, (l + r)/2 + 1, r, x, delta);
		tree[id][0] = 1;
		for (int k = 1; k <= 4; k++) {
			lint sum = 0;
			for (int kk = 0; kk <= k; kk++)
				sum = (sum + tree[2*id][kk]*tree[2*id+1][k-kk]) % p;
			while (sum < 0)
				sum += p;
			tree[id][k] = sum;
		}
	}
}

struct T {
	lint ans[5];
};

T get(int id, int l, int r, int a, int b) {
	a = max(a, l);
	b = min(b, r);
	if (a > r || b < l) {
		T t;
		t.ans[0] = 1;
		t.ans[1] = t.ans[2] = t.ans[3] = t.ans[4] = 0;
		return t;
	}
	if (a == l && b == r) {
		T t;
		for (int k = 0; k <= 4; k++) {
			t.ans[k] = tree[id][k];
			//printf("de %d a %d k %d tree %lld\n", l, r, k, tree[id][k]);
		}
		return t;
	}
	else {
		T ta = get(2*id, l, (l + r)/2, a, b);
		T tb = get(2*id + 1, (l + r)/2 + 1, r, a, b);
		T t;
		t.ans[0] = 1;
		for (int k = 1; k <= 4; k++) {
			lint sum = 0;
			for (int kk = 0; kk <= k; kk++) {
				sum = (sum + ta.ans[kk]*tb.ans[k-kk]) % p;
			}
			t.ans[k] = sum;
		}
		return t;
	}
}

int main() {
	int n, m;
	scanf("%d %d %d", &n, &m, &p);
	if (n > 80000) {
		printf("Limites errados!\n");
		return 0;
	}
	for (int i = 1; i <= n; i++) {
		int val; scanf("%d", &val);
		update(1, 1, n, i, val);
	}

	for (int i = 0; i < m; i++) {
		char c; scanf(" %c", &c);
		if (c == 'I') {
			int id, delta;
			scanf("%d %d", &id, &delta);
			update(1, 1, n, id, delta);
		}
		else {
			int a, b, k;
			scanf("%d %d %d", &a, &b, &k);
			T t = get(1, 1, n, a, b);
			for (int i = 0; i <= k; i++) {
				if (i > 0)
					printf(" ");
				printf("%d", (int) (t.ans[i] % p));
			}
			printf("\n");
		}
	}

	return 0;
}

The Hobbit or There and Back Again 2 (por Renato Ferreira)

#include <cstdio>
#include <algorithm>
#include <utility>

using namespace std;

const int MAX_N = 1005;

int n;
pair < int, int > val[MAX_N];
int memo[MAX_N][MAX_N];
pair < int, int > best[MAX_N][MAX_N];
int go[MAX_N];

int solve(int a, int b) {
	if (a == n-1 && b == n-1)
		return 0;
	if (a == n-1) {
		best[a][b] = make_pair(n-1, n-1);
		return val[b].first*(1000/val[n-1].first);
	}
	if (b == n-1) {
		best[a][b] = make_pair(n-1, n-1);
		return val[n - 1].first*(1000/val[a].first);
	}
	
	int &ans = memo[a][b];
	if (ans != -1)
		return ans;
	
	int curr = max(a, b) + 1;
	int ans1 = val[curr].first*(1000/val[a].first) + solve(curr, b);
	int ans2 = val[b].first*(1000/val[curr].first) + solve(a, curr);
	if (ans1 < ans2) {
		ans = ans1;
		best[a][b] = make_pair(curr, b);
	}
	else {
		ans = ans2;
		best[a][b] = make_pair(a, curr);
	}

	return ans;
}

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		int x;
		scanf("%d", &x);
		val[i] = make_pair(x, i);
	}
	
	for (int i = 0; i <= n; i++) for (int j = 0; j <= n; j++)
		memo[i][j] = -1;
	
	sort(val, val + n);
	solve(0, 0);

	int a = 0, b = 0;
	while (a != n - 1 || b != n - 1) {
		int aa = best[a][b].first;
		int bb = best[a][b].second;
		if (aa != a)
			go[val[a].second] = val[aa].second;
		else
			go[val[bb].second] = val[b].second;
		a = aa, b = bb;
	}

	int curr = 0;
	do {
		if (curr != 0)
			printf(" ");
		printf("%d", curr + 1);
		curr = go[curr];
	} while (curr != 0);
	printf("\n");

	return 0;
}

Strange Planet (por Renato Ferreira)

#include <cstdio>
#include <string>

using namespace std;

typedef long long lint;

const lint MOD = 1000000007;
const int MAX_N = 100020;

string s[3];
char buffer[MAX_N];
lint fat[MAX_N];

lint mpow(lint a, lint b) {
	if (b == 0)
		return 1;
	if (b == 1)
		return a % MOD;
	if (b == 2)
		return (a*a) % MOD;
	lint ans = 1;
	if (b & 1)
		ans = a % MOD;
	lint mp = mpow(a, b/2);
	return (ans*((mp*mp)%MOD)) % MOD;
}

lint choose(lint a, lint b) {
	if (a < 0 || b < 0)
		return 0;
	if (b > a)
		return 0;
	if (b == 0)
		return 1;

	lint up = fat[a];
	lint down1 = mpow(fat[b], MOD - 2);
	lint down2 = mpow(fat[a - b], MOD - 2);
	lint down = (down1 * down2) % MOD;
	lint ans = (up * down) % MOD;
	return ans;
}

int main() {
	fat[0] = 1;
	for (int i = 1; i < MAX_N; i++)
		fat[i] = (i * fat[i - 1]) % MOD;

	int n;
	for (int i = 0; i < 3; i++) {
		scanf("%s", buffer);
		s[i] = buffer;
	}
	n = s[0].size();

	int ta = 0, tb = 0, tc = 0;
	lint mult = 1;
	for (int i = 0; i < n; i++) {
		if (s[0][i] == s[1][i] && s[0][i] == s[2][i])
			mult = (mult * 2LL) % MOD;
		if (s[0][i] != s[1][i] && s[0][i] != s[2][i])
			ta++;
		if (s[1][i] != s[0][i] && s[1][i] != s[2][i])
			tb++;
		if (s[2][i] != s[0][i] && s[2][i] != s[1][i])
			tc++;
	}

	lint ans = 0;
	for (int c = 0; c <= tc; c++) {
		int a2 = ta - tc + 2*c;
		int b2 = tb - tc + 2*c;

		if (a2&1 || b2&1)
			continue;

		int a = a2/2;
		int b = b2/2;

		lint ways = choose(tc, c);
		ways = (ways * choose(tb, b)) % MOD;
		ways = (ways * choose(ta, a)) % MOD;
		ans = (ans + ways) % MOD;
	}

	printf("%lld\n", (ans*mult)%MOD);

	return 0;
}

Buoys (por Renato Ferreira)

#include <cstdio>
#include <algorithm>

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

using namespace std;

const int MAX_N = 404;

int pos[MAX_N];

int main() {
	int n; scanf("%d", &n);
	for (int i = 0; i < n; i++)
		scanf("%d", &pos[i]);

	double ans = 10000000000.0, best = 0;
	int c = 0;
	for (int chosen = 0; chosen < n; chosen++) {
		double a = 1, b = 20000;
		while (b - a > 1e-9) {
			double x = (2*a + b) / 3.0;
			double y = (a + 2*b) / 3.0;
			double dx = 0, dy = 0;
			for (int i = 0; i < n; i++) {
				double pi = (double) pos[i];
				double pc = (double) pos[chosen];
				double prx = pc + (double) (i - chosen) * x;
				double pry = pc + (double) (i - chosen) * y;

				dx += abs(pi - prx);
				dy += abs(pi - pry);
			}

			//printf("x %lf dx %lf y %lf dy %lf chosen %d\n", x, dx, y, dy, chosen);

			if (dx < ans) {
				ans = dx;
				best = x;
				c = chosen;
			}
			if (dy < ans) {
				ans = dy;
				best = y;
				c = chosen;
			}
			
			if (dy - dx > 1e-9) {
				b = y;
				//printf("voltou\n");
			}
			else {
				a = x;
				//printf("avancou\n");
			}
		}
	}

	printf("%.4lf\n", ans);
	for (int i = 0; i < n; i++) {
		if (i > 0)
			printf(" ");
		printf("%.7lf ", (double) pos[c] + (double) (i - c)*best);
	}
	printf("\n");

	return 0;
}