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

Vídeo: Discussão sobre os problemas

Algumas soluções dos competidores

Squitter (por Renato Ferreira)

#include <cstdio>

typedef long long lint;

const lint P = 1000000009;

const int MAX_N = 1000010;

lint fact[2*MAX_N];
lint inv_pow2[MAX_N];

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

int main() {
	fact[0] = 1;
	for (lint i = 1; i < 2*MAX_N; i++)
		fact[i] = (i * fact[i - 1]) % P;
	lint inv2 = mpow(2, P - 2);
	lint curr = 1;
	for (lint i = 0; i < MAX_N; i++) {
		inv_pow2[i] = curr;
		curr = curr * inv2 % P;
	}
	
	lint n;
	while (scanf("%lld", &n) == 1) {
		printf("%lld\n", fact[2*n] * inv_pow2[n] % P);
	}

	return 0;
}

Expressões Regulares (por Cesar Kawakami)

import java.util.*;
import java.io.*;
import java.util.regex.*;

class Main {
    static int p;
    static String preorder;
    static StringBuilder inorder;
    static void traverse() {
	if (preorder.charAt(p) == '.') {
	    ++p; inorder.append("(?:"); traverse(); inorder.append(")(?:"); traverse(); inorder.append(")");
	} else if (preorder.charAt(p) == '*') {
	    ++p; inorder.append("(?:(?:"); traverse(); inorder.append(")*)");
	} else if (preorder.charAt(p) == '+') {
	    ++p; inorder.append("(?:(?:"); traverse(); inorder.append(")|(?:"); traverse(); inorder.append("))");
	} else if (preorder.charAt(p) == 'e') {
	    ++p;
	} else {
	    inorder.append(preorder.charAt(p)); ++p;
	}
    }
    public static void main(String[] args) throws Throwable {
	BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
	while (true) {
	    StringTokenizer st;
	    try { st = new StringTokenizer(in.readLine()); } catch (NullPointerException ex) { break; }
	    p = 0;
	    preorder = st.nextToken();
	    inorder = new StringBuilder();
	    traverse();
	    //out.printf("%s\n", inorder.toString());
	    Pattern p = Pattern.compile(inorder.toString());
	    while (true) {
		String c;
		c = st.nextToken();
		if (c.equals("$"))
		    break;
		else if (c.equals("e"))
		    c = "";
		if (p.matcher(c).matches())
		    out.printf("Y");
		else
		    out.printf("N");
	    }
	    out.printf("\n");
// 	    while (true) {
		
// 	    }
	}
	out.close();
    }
}

GCD (por Renato Ferreira)

#include <cstdio>

const int MAX_N = 505;

int gcd(int a, int b) {
	if (b == 0)
		return a;
	return gcd(b, a % b);
}

int memo[MAX_N][MAX_N];

int main() {
	int n;
	while (scanf("%d", &n) && n > 0) {
		int ans = 0;
		for (int i = 1; i < n; i++) for (int j = i + 1; j <= n; j++) {
			if (memo[i][j] == 0)
				memo[i][j] = gcd(i, j);
			ans += memo[i][j];
		}

		printf("%d\n", ans);
	}

	return 0;
}

Wesnoth (por Felipe Abella)

#include <iostream>
#include <cstdio>
#include <map>
#include <cmath>

#define MAXM 128

using namespace std;

int m0, d0, m1, d1, l0, l1;
double p0, p1;
double ret0[MAXM], ret1[MAXM];

void go(int turn, int h0, int n0, int h1, int n1, double p)
{
	if (h0 == 0 || h1 == 0 || (n0+n1 == 0)) {
		ret0[h0] += p;
		ret1[h1] += p;
		return;
	}

	if ((turn == 0 && n0) || (turn == 1 && !n1)) {
		go(1, min(m0, h0+l0), n0-1, max(h1-d0, 0), n1, p*p0);
		go(1, h0, n0-1, h1, n1, p*(1.0-p0));
	} else {
		go(0, max(h0-d1, 0), n0, min(m1, h1+l1), n1-1, p*p1);
		go(0, h0, n0, h1, n1-1, p*(1.0-p1));
	}
}

int main()
{
	int h0, n0, h1, n1;

	while (scanf("%d %d %d %lf %d %d %d %d %d %lf %d %d", &m0, &h0, &n0, &p0, &d0, &l0, &m1, &h1, &n1, &p1, &d1, &l1) > 0) {
		for (int i = 0; i <= m0; i++)
			ret0[i] = 0.0;
		for (int i = 0; i <= m1; i++)
			ret1[i] = 0.0;

		go(0, h0, n0, h1, n1, 1.0);

		int first = 1;
		for (int h = 0; h <= m0; h++) {
			if (ret0[h] < 1e-5)
				continue;
			if (!first)
				printf(" ");
			first = 0;
			printf("%d:%f", h, ret0[h]);
		}
		printf("\n");

		first = 1;
		for (int h = 0; h <= m1; h++) {
			if (ret1[h] < 1e-5)
				continue;
			if (!first)
				printf(" ");
			first = 0;
			printf("%d:%f", h, ret1[h]);
		}
		printf("\n");

		printf("\n");
	}

	return 0;
}

Long Long Nim (por Felipe Abella)

#include <iostream>
#include <cstdio>

#define MASK (1<<22)

using namespace std;

typedef long long lint;

int can[MASK+16];
int seen[MASK+16];

int main(int argc, char ** argv)
{
  int n;
  
  while (scanf("%d", &n) == 1) {
    int prevmask = 0, x;
    while (scanf("%d", &x), x)
      prevmask |= (1<<(x-1));

    for (int i = 0; i < MASK; i++)
      seen[i] = -1;

    lint result = 0;

    int mask = MASK-1, nevermind = 0;
    for (int i = 0; i <= n; i++) {
      if (!nevermind && seen[mask] != -1) {
	int j = seen[mask];

	int cyclelen = i-j;
	int nrep = (n-i)/cyclelen;

	lint many = 0;
	for (int k = j; k < i; k++)
	  many += !can[k];

	result += many * nrep;
	i += cyclelen * nrep;

	nevermind = 1;
      }
      seen[mask] = i;

      int cani = (prevmask & (~mask)) != 0;

      if (i < MASK+16)
	can[i] = cani;
      mask = ((mask<<1) | cani)&(MASK-1);
      result += !cani;
    }

    printf("%lld\n", result-1LL);
  }

  return 0;
}

Maior Progressão Aritmética (por Renato Ferreira)

#include <cstdio>
#include <algorithm>

using namespace std;

const int MAX_N = 4005;

int val[MAX_N];
int best[MAX_N][MAX_N];

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

		if (n <= 1) {
			printf("%d\n", n);
			continue;
		}

		int ans = 1;
		for (int i = n - 1; i >= 0; i--) {
			int k = i + 2;
			for (int j = i + 1; j < n; j++) {
				best[i][j] = 2;
				while (k < n && val[k] - val[j] < val[j] - val[i])
					k++;
				if (k >= n || val[k] - val[j] > val[j] - val[i])
					continue;
				best[i][j] = max(best[i][j], 1 + best[j][k]);
			}
		}

		for (int i = 0; i < n; i++) for (int j = 0; j < n; j++)
			ans = max(ans, best[i][j]);

		printf("%d\n", ans);
	}

	return 0;
}

Treediff (por Renato Ferreira)

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

using namespace std;

const int MAX_N = 50005;

typedef long long lint;

int parent[MAX_N];
vector < int > adj[MAX_N];
lint ans[MAX_N];
vector < pair < int, int > > children[MAX_N];
set < lint > elem[MAX_N];
int which_elem[MAX_N];
lint val[MAX_N];
int size[MAX_N];

void dfs(int u) {
//	printf("dfs(%d)\n", u);

	if (adj[u].empty()) {
		elem[u].insert(val[u]);
		which_elem[u] = u;
		size[u] = 1;
		return;
	}

	for (int i = 0; i < (int) adj[u].size(); i++) {
		int v = adj[u][i];
		dfs(v);
		children[u].push_back(make_pair(size[v], v));
		size[u] += size[v];
		ans[u] = min(ans[u], ans[v]);
	}

	sort(children[u].begin(), children[u].end());

	int last = adj[u].size() - 1;
	int wlast = which_elem[children[u][last].second];
	which_elem[u] = wlast;
	for (int i = 0; i < last; i++) {
		set < lint >::iterator it, a, b;
		int curr = which_elem[children[u][i].second];
		for (it = elem[curr].begin(); it != elem[curr].end(); ++it) {
//			printf("filho %d(de %d) tem valor %u\n", children[u][i].second, u, *it);

			a = elem[wlast].lower_bound(*it);
			b = elem[wlast].upper_bound(*it);
			if (a != elem[wlast].end() && *a == *it)
				ans[u] = 0;
			if (a != elem[wlast].begin()) {
				--a;
				if (a != elem[wlast].end())
					ans[u] = min(ans[u],  (*it - *a));
//				printf("diff com %u\n", *a);
			}

			if (b != elem[wlast].end()) {
				ans[u] = min(ans[u],  (*b - *it));
//				printf("diff com %u\n", *b);
			}
			elem[wlast].insert(*it);
		}
		//elem[curr].clear();
	}

//	printf("ans de %d = %u\n", u, ans[u]);
}

int main() {
	int n, nleaf;
	scanf("%d %d", &n, &nleaf);
	parent[0] = 0;
	for (int i = 1; i < n; i++) {
		scanf("%d", &parent[i]);
		parent[i]--;
		adj[parent[i]].push_back(i);
	}

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

	fill(ans, ans + MAX_N, (1LL << 31) - 1);
	dfs(0);

	for (int i = 0; i < n - nleaf; i++) {
		if (i > 0)
			printf(" ");
		printf("%d", (int) ans[i]);
	}
	printf("\n");

	return 0;
}

Throne (por Renato Ferreira)

#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long lint;

lint gcd(lint a, lint b) {
	if (b == 0)
		return a;
	return gcd(b, a % b);
}

inline lint lcm(lint a, lint b) {
	lint g = gcd(a, b);
	if (g == 0)
		g = 1;
	return a * b / g;
}

int main() {
	lint a, aa, b, bb, c, cc;
	while (scanf("%lld/%lld %lld/%lld %lld/%lld", &a, &aa, &b, &bb, &c, &cc) == 6) {
		lint l = lcm(lcm(aa, bb), cc);
		a *= l/max(aa, 1LL);
		b *= l/max(bb, 1LL);
		c *= l/max(cc, 1LL);
		aa = bb = cc = l;

		lint x = a;
		lint xx = a + b - c;
		lint g = gcd(x, xx);
		if (g == 0)
			g = 1;
		x /= g;
		xx /= g;
		if (xx == 0)
			xx = 1;
		printf("%lld/%lld\n", x, xx);
	}

	return 0;
}