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

Vídeo: Discussão sobre os problemas

Algumas soluções dos competidores

Kicc Wants to Move a Mountain! (por Renato Ferreira)

#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long lint;

int main() {
	int t, x, m;
	scanf("%d %d %d", &t, &x, &m);

	int best_d = -1, best_s = -1;
	for (int i = 0; i < m; i++) {
		int d, s;
		scanf("%d %d", &d, &s);
		if (i == 0)
			best_d = d, best_s = s;
		else {
			lint dd = d;
			lint ss = s;
			lint bdd = best_d;
			lint bss = best_s;
			if (dd * bss < bdd * ss) {
				best_d = d;
				best_s = s;
			}
		}
	}

	if (m == 0) {
		printf("%d\n", t * x);
		return 0;
	}

	int steps = (best_d + best_s - 1) / best_s;
	int curr = min(steps - 1, t);
	int ans = curr;

	if (steps > 1) {
		while (curr + 1 < t) {
			curr += 2;
			ans++;
		}
	}

	lint llans = (lint) ans * (lint) x;
	printf("%lld\n", llans);

	return 0;
}

Defending Castle (por Renato Ferreira)

#include <cstdio>
#include <cmath>
#include <algorithm>

typedef long long lint;

using namespace std;

inline lint mceil(lint a, lint b) {
	return (a + b - 1) / b;
}

int main() {
	lint d, n;
	while (scanf("%lld %lld", &d, &n) && (n > 0 || d > 0)) {
		int sqr = sqrt(d);

		lint ans = 0;
		lint cnt = 0;

		lint last = 0;

		if (sqr*sqr == d)
			sqr--;

		for (lint i = 1; i <= sqr && cnt < n; i++) {
			cnt++;
			ans += mceil(d, i);
			last = mceil(d, i);
		}

		for (lint res = last - 1; res > 1 && cnt < n; res--) {
			lint a = mceil(d, res);
			lint b = mceil(d, res - 1);

			ans += res * min(b - a, n - cnt);
			cnt += b - a;
		}

		if (cnt < n)
			ans += n - cnt;

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

	return 0;
}

The Cubic End (por Felipe Abella)

#include <iostream>
#include <cstring>
#include <cstdio>

#define MAXD 16

typedef long long lint;

using namespace std;

int ndigit;
int num[MAXD];
int ret[MAXD];

int squared[MAXD];
int cubed[MAXD];

lint result;

void mult(int * d, int * s1, int *s2)
{
  for (int i = 0; i < ndigit; i++)
    d[i] = 0;

  for (int i = 0; i < ndigit; i++)
    for (int j = 0; j+i < ndigit; j++)
      d[i+j] += s1[i] * s2[j];
}

void norm(int * d)
{
  int carry = 0;
  for (int i = 0; i < ndigit; i++) {
    d[i] += carry;
    carry = d[i] / 10;
    d[i] %= 10;
  }  
}

void cube(void)
{
  mult(squared, ret, ret);
  mult(cubed, squared, ret);
  norm(cubed);
}

int go(int i)
{
  if (i) {
    cube();
    for (int j = 0; j < i; j++)
      if (cubed[j] != num[j])
	return 0;
  }

  if (i == ndigit) {
    result = 0;
    for (int j = ndigit-1; j >= 0; j--)
      result = 10LL*result + ret[j];
    
    return 1;
  }
  
  for (int d = 0; d < 10; d++) {
    ret[i] = d;
    if (go(i+1))
      return 1;
  }
  
  return 0;
}

int main(void)
{
  int ntest;

  scanf("%d", &ntest);
  
  for (int t = 0; t < ntest; t++) {
    lint _num;
    scanf("%lld", &_num);
    ndigit = 0;

    while (_num) {
      num[ndigit++] = _num%10;
      _num /= 10;
    }

    go(0);

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

  return 0;
}

Equações diofantinas (por Renato Ferreira)

#include <cstdio>
#include <utility>
#include <map>

using namespace std;

typedef long long lint;

const lint MOD = 1300031;
const int MAX_N = 2000002;

lint fat[MAX_N];
lint minv[MAX_N];
lint x, y;
int n, c, t;

void egcd(lint a, lint b) {
        if (b == 0) {
                x = 1;
                y = 0;
                return;
        }

        egcd(b, a % b);
        lint nx = y;
        lint ny = x - y*(a/b);
        x = nx;
        y = ny;
}

lint inv(lint a, lint b) {
	egcd(a, b);
	while (x < 0)
		x += b;
	return x;
}

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

	scanf("%d", &t);
	while (t--) {
		scanf("%d %d", &n, &c);

		if (minv[fat[c]] == 0)
			minv[fat[c]] = inv(fat[c], MOD);
		if (minv[fat[n - 1]] == 0)
			minv[fat[n - 1]] = inv(fat[n - 1], MOD);


		printf("%d\n", (int) ((fat[n + c - 1] * minv[fat[c]] * minv[fat[n - 1]]) % MOD));
	}

	return 0;
}

From Pythagoras to … (por Renato Ferreira)

#include <cstdio>
#include <algorithm>
#include <map>
#include <cstdlib>
#include <cmath>
#include <queue>

using namespace std;

typedef unsigned long long lint;

map < lint, int > factors;

inline void add(lint x) {
	if (!factors.count(x))
		factors[x] = 1;
	else
		factors[x]++;
}

inline lint mult(lint a, lint b, lint p) {
	lint ans = 0;
	while (b > 0) {
		if (b & 1)
			ans = (ans + a) % p;
		a = (a + a) % p;
		b /= 2ULL;
	}
	return ans;
}

lint f(lint x, int c, lint n) {
	return (mult(x, x, n) + c) % n;
}

lint gcd(lint a, lint b) {
	lint g = a % b;
	while (g != 0) {
		a = b;
		b = g;
		g = a % b;
	}
	return b;
}

lint mpow(lint a, lint b, lint p) {
	lint ans = 1;
	while (b) {
		if (b & 1)
			ans = mult(ans, a, p);
		a = mult(a, a, p);
		b /= 2ULL;
	}
	return ans;
}

bool prime(lint n) {
	if (n == 2)
		return true;
	if (n % 2 == 0)
		return false;
	if (n == 1)
		return false;
	if (n == 3)
		return true;

	lint s = 0, d = n - 1;
	while ((d & 1) == 0) {
		s++;
		d /= 2ULL;
	}
	for (int k = 0; k < 13; k++) {
		lint a = (rand() % (n - 3)) + 2;
		lint x = mpow(a, d, n);
		if (x == 1 || x == n - 1)
			continue;
		for (unsigned int r = 1; r < s; r++) {
			x = (mult(x, x, n)) % n;
			if (x == 1) {
				return false;
			}
			if (x == n - 1)
				goto END;
		}
		return false;
		END:
		;
	}
	return true;
}

void pollard(lint nn) {
	queue < lint > q; q.push(nn);
	while (!q.empty()) {
		lint n = q.front(); q.pop();
		if (prime(n)) {
			add(n);
		}
		else {
			for (int c = 1; c <= 13; c++) {
				lint x = rand() % n;
				lint y = f(x, c, n);
				//printf("x %llu y %llu\n", x, y);

				while (true) {
					//printf("n %llu\n", n);

					lint g = gcd(max(x, y) - min(x, y), n);
					if (g == n)
						break;

					if (g > 1) {
						lint n1 = g;
						lint n2 = n/g;
						if (n1 > n2)
							swap(n1, n2);

						q.push(n1);
						q.push(n2);
						goto END;
					}

					x = f(x, c, n);
					y = f(f(y, c, n), c, n);
				}
			}
			END:
			;
		}
	}
}

int main() {
	srand(1009007);
	
	int t = 1; scanf("%d", &t);
	while (t--) {
		lint n;
		long long nn;
		scanf("%lld", &nn);
		n = (lint) nn;

		if (nn < 0) {
			printf("NO\n");
			continue;
		}
		else if (nn == 0) {
			printf("YES\n");
			continue;
		}

		factors.clear();
		pollard(n);

		bool ok = true;
		map < lint, int >::iterator it;
		for (it = factors.begin(); it != factors.end(); ++it) {
			if (it->first % 4 == 3 && it->second % 2 == 1) {
				ok = false;
				//break;
			}
		}

		if (ok)
			printf("YES\n");
		else
			printf("NO\n");
	}

	return 0;
}

Board Game (por Natan Costa Lima)

#include <stdio.h>
#include <stdlib.h>

struct vert
{
	int deg, match, valid, mark, from;
	int sous[8];
};

struct graph
{
	int n;
	struct vert verts[1];
};

char zad[20][20];
int n, m;

void decode(int v)
{
	int x1, y1, x2, y2;

	y2 = v & 7;
	v >>= 3;
	x2 = v & 7;
	v >>= 3;

	y1 = v & 7;
	x1 = v >> 3;

	printf ("%d, %d    ;    %d, %d\n", x1 + 1, y1 + 1, x2 + 1, y2 + 1);
}

int encode (int x1, int y1, int x2, int y2)
{
	int code, t; 

	/* The first figure should have smaller coordinates.  */
	if (y1 > y2
			|| (y1 == y2 && x1 > x2))
	{
		t = x1; x1 = x2; x2 = t;
		t = y1; y1 = y2; y2 = t;
	}

	code = x1;
	code = (code << 3) | y1;
	code = (code << 3) | x2;
	code = (code << 3) | y2;

	return code;
}

int validpoint (int x, int y)
{
	if (x < 0 || y < 0)
		return 0;

	if (x >= n || y >= m)
		return 0;

	if (zad[y][x] == '#')
		return 0;

	return 1;
}

int validstate (int x1, int y1, int x2, int y2)
{
	if (!validpoint (x1, y1))
		return 0;
	if (!validpoint (x2, y2))
		return 0;

	/* Also forbid suicidal moves.  */
	if (x1 == x2
			&& (y1 == y2 + 1 || y2 == y1 + 1))
		return 0;
	if (y1 == y2
			&& (x1 == x2 + 1 || x2 == x1 + 1))
		return 0;

	return 1;
}

void addmove (struct graph *g, int v, int x1, int y1, int x2, int y2)
{
	int u = encode (x1, y1, x2, y2), d;
	if (!validstate (x1, y1, x2, y2))
		return;

	d = g->verts[v].deg;
	g->verts[v].sous[d] = u;
	g->verts[v].deg++;
}

void genstate (struct graph *g, int x1, int y1, int x2, int y2)
{
	int v = encode (x1, y1, x2, y2);

	if (!validstate (x1, y1, x2, y2))
		return;

	g->verts[v].valid = 1;
	g->verts[v].match = -1;

	addmove (g, v, x1 + 1, y1, x2, y2);
	addmove (g, v, x1, y1 + 1, x2, y2);
	addmove (g, v, x1 - 1, y1, x2, y2);
	addmove (g, v, x1, y1 - 1, x2, y2);
	addmove (g, v, x1, y1, x2 + 1, y2);
	addmove (g, v, x1, y1, x2, y2 + 1);
	addmove (g, v, x1, y1, x2 - 1, y2);
	addmove (g, v, x1, y1, x2, y2 - 1);
}

struct graph *read_graph(int m, int n, int *init)
{
	int nv = n << 9, y1, x1, y2, x2, ix[2], iy[2], a;
	struct graph *ret = (graph *)calloc (1, sizeof (struct graph) + nv * sizeof (struct vert));

	ret->n = nv;
	for (y1 = 0; y1 < m; y1++)
		scanf ("%s", zad[y1]);

	for (y1 = 0; y1 < m; y1++)
		for (x1 = 0; x1 < n; x1++)
		{
			for (x2 = x1 + 1; x2 < n; x2++)
				genstate (ret, x1, y1, x2, y1);

			for (y2 = y1 + 1; y2 < m; y2++)
				for (x2 = 0; x2 < n; x2++)
					genstate (ret, x1, y1, x2, y2);
		}

	a = 0;
	for (y1 = 0; y1 < m; y1++)
		for (x1 = 0; x1 < n; x1++)
			if (zad[y1][x1] == 'P')
			{
				ix[a] = x1;
				iy[a] = y1;
				a++;
			}

	if (a != 2)
		abort ();

	*init = encode (ix[0], iy[0], ix[1], iy[1]);

	return ret;
}

int explore (struct graph *g, int v, int from, int mark)
{
	int i, t;

	if (g->verts[v].mark == mark)
		return -1;

	g->verts[v].mark = mark;
	g->verts[v].from = from;

	if (g->verts[v].match == -1)
		return v;

	if (g->verts[v].match != from)
		return explore (g, g->verts[v].match, v, mark);

	for (i = 0; i < g->verts[v].deg; i++)
	{
		if (g->verts[v].sous[i] == from)
			continue;

		t = explore (g, g->verts[v].sous[i], v, mark);
		if (t != -1)
			return t;
	}

	return -1;
}

void swapmatch (struct graph *g, int t)
{
	int into = 1, last;

	while (1)
	{
		last = t;
		t = g->verts[t].from;

		if (t == -2)
			return;

		if (into)
		{
			g->verts[last].match = t;
			g->verts[t].match = last;
		}
		else
			g->verts[t].match = -1;

		into = !into;
	}
}

void imprpath (struct graph *g, int v, int mark)
{
	int t;

	if (g->verts[v].match == -1)
		g->verts[v].match = -2;

	t = explore (g, v, -2, mark);

	if (g->verts[v].match == -2)
		g->verts[v].match = -1;

	if (t == -1)
		return;
	swapmatch (g, t);
}

int main(void)
{
	int i, init_state, mark;
	struct graph *gph;

	while (1)
	{
		if (scanf ("%d%d", &m, &n) != 2)
			return 0;

		gph = read_graph (m, n, &init_state);

		if (!gph->verts[init_state].valid)
		{
			/* This happens when Alice may take
			   the other piece directly.  */
			printf ("Alice wins.\n");
			free (gph);
			continue;
		}

		mark = 1;
		for (i = 0; i < gph->n; i++)
			if (gph->verts[i].match == -1)
				imprpath(gph, i, mark++);

		if (gph->verts[init_state].match != -1)
			imprpath(gph, init_state, mark);

		if (gph->verts[init_state].match != -1)
			printf ("Alice wins.\n");
		else
			printf ("Bob wins.\n");

		free (gph);
	}
}