Desafios de Programação no Verão

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

» 14 de janeiro de 2011

Hora de início: 2011-01-14 09:14:00 -0200   Hora de término: 2011-01-14 13:14:00 -0200

Problemas

POS Competidor Resultado Pontuação A B C D E F  
1 walter erquinigo 5 (645) 99 +0 +0 +1 +8 +1 -4  
2 Daniel Ribeiro Moreira 4 (357) 97 +1 +0 +0 +1 -2 -2  
3 Atol Fortin 4 (368) 95 +1 +0 +0 +2 -11    
4 Gabriel Luís Mello Dalalio 4 (680) 93 +2 +1 +0 +2      
5 Filipe Martins 4 (742) 91 +0 +2 +0 +6 -1    
6 Guilherme Souza 4 (952) 89 +0 +6 +3 +6 -6    
7 Ricardo Hahn 3 (217) 87 +1 +0 +0        
8 Jesus Alejandro 3 (225) 85 +0 +0 +0        
9 Eduardo Ribas 3 (228) 83 +1 +1 -5 +2   -1  
10 Cesar Kawakami 3 (244) 81 +1 +0 +0 -7      
11 Felipe Abella 3 (250) 79 +1 +1 +0 -7      
12 Natan Costa Lima 3 (369) 77 +2 +1 +0        
13 daniel soncco 3 (382) 75 -2 +0 +0 +1 -4    
14 Eric Destefanis 3 (389) 73 +1 +3 +0 -6      
15 Tiago Madeira 3 (423) 71 +2 +0 +1 -8 -4    
16 Leonardo Marchetti 2 (175) 69 +2 +0   -8      
17 Thiago Sonego Goulart 2 (243) 67 +1 +0 -2 -3      
18 Adriana Libório 2 (289) 65 +1 +1          
19 Cesar Gamboa 2 (339) 63 +1 +1       -1  
20 Davi Duarte Pinheiro 2 (360) 61 +3 +0 -1        
21 Pablo Pinheiro 2 (421) 59 +3 +0          
22 Luiz Afonso 2 (472) 57 -2 +1 -1 +3      
23 Pedro Veras 1 (41) 55 +0 -1   -10      
24 Igor Ramos 1 (57) 53 +1 -1          
25 Matias Daniel Tealdi 1 (100) 51 +2 -2          
26 Douglas Santos 1 (103) 49 +1 -2          
27 Renato Ferreira 1 (108) 47 +2     -5      
28 Renato Parente 1 (132) 45 +3       -5    
29 Felipe Menezes Machado 1 (145) 43 -4 -1 +2        
30 Paulo Costa 1 (167) 41 -2 -4 +1 -1      
31 Gaston Ingaramo 1 (172) 39 -5   +1        
32 Arthur 1 (181) 37 +5 -2          
33 Leonardo Martinez 1 (182) 35 +0 -4          
34 Leonardo Inácio 1 (238) 33 +5 -3          
35 Edwin Macelo Guzman Buezo 1 (257) 31 +4            
36 Andre Hahn 1 (270) 29 +5     -5      
37 Rafael Brandão 1 (274) 27 -5 +2     -1    
44 Vinicius Ruoso 1 (341) 13 +8 -1          
44 Alex Alves da Paixão 0 (0) 13         -4    
44 Victor Jatobá 0 (0) 13   -3          
44 Phyllipe Cesar 0 (0) 13 -11     -1      
44 Caique Porto Lira 0 (0) 13 -6 -4   -1      
44 Igor R. de Assis 0 (0) 13              
44 gustavo pacianotto gouveia 0 (0) 13     -2 -2      
44 Leonardo Flores Zambaldi 0 (0) 13   -1          
44 Vinicius Flores Zambaldi 0 (0) 13 -5 -1          
44 Nicolas Gumiel 0 (0) 13 -4            
44 Victor Hugo Paredes Mora 0 (0) 13 -1 -1     -2    
44 Renan Ferraz Pires 0 (0) 13              
44 Ricardo Oliveira 0 (0) 13 -7           </div>

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);
	}
}

blog comments powered by Disqus
Licença Creative Commons
Esta obra foi licenciada com uma Licença
Creative Commons - Atribuição - Uso Não-Comercial - Obras Derivadas Proibidas 3.0 Não Adaptada.