Provas da Primeira Fase da Maratona de Programação

Os enunciados das provas das primeiras fases da Maratona de Programação a partir de 2006 podem ser encontrados no links a seguir:

• Aquecimento 2006
• Prova 2006
• Aquecimento 2007
• Prova 2007
• Aquecimento 2008
• Prova 2008
• Aquecimento 2009
• Prova 2009
• Aquecimento 2010
• Prova 2010
• Aquecimento 2011
• Prova 2011

 

Maratona: Mário (do Armário)

Prova 2007/Primeira Fase/Problema D

Solução:

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

int maximo (int x, int y) {
	if (x>y) return x;
	else return y;
}

int main () {
	int N, L;
	int armarios[100000];
	int melhor, i, j;
	
	scanf ("%d%d", &N, &L);
	while (N!=0 || L!=0) {
		
		for (i = 0; i < L; i++) scanf ("%d", &armarios[i]);
		
		melhor = 0;
		i = 0;
		j = 0;
		
		while (melhor < N && j < L) {
			if (armarios[j] < armarios[i] + N) {
				melhor = maximo (melhor, j-i + 1);
				j++;
			}
			else i++;
		}
		
		printf ("%d\n", N-melhor);

		scanf ("%d%d", &N, &L);
	}
	return 0;
}

Maratona: Rouba-Monte

2007/Primeira Fase/Problema B

Solução:

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

int maximo (int *v, int n) {
	int i, m = v[0];
	
	for (i = 0; i < n; i++) 
		if (v[i] > m) m = v[i];

	return m;
}

void zeraVetor (int *v, int n) {
	int i;
	for (i = 0; i < n; i++) v[i] = 0;
}

int busca (int x, int *v, int n, int jogador) {
	int i;
	
	for (i = 0; i < jogador; i++) if (v[i] == x) return i;
	for (i = jogador+1; i < n; i++) if (v[i] == x) return i;
		
	return i;
}

int main () {
	int N, J;
	int i, j, jogador, carta, m, pos;
	int baralho[13]; // cartas de 1 a 13, vetor de 0 a 12
	int montes[20]; // jogadores de 2 a 20, vetor de 0 a 18
	int topos[20]; // jogadores de 2 a 20, vetor de 0 a 18
	
	scanf ("%d%d", &N, &J);
	while (N!=0 || J!=0) {
		zeraVetor (baralho, 13);
		zeraVetor (montes, J);
		zeraVetor (topos, J);

		jogador = 0;
		
		for (i = 0; i < N; i++) {
			scanf ("%d", &carta);
			
			if (baralho[carta-1] == 1) { // Achou a carta nos descartes
				montes[jogador] += 2;
				topos[jogador] = carta;
				baralho[carta-1] = 0;
			}
			else {
				pos = busca (carta, topos, J, jogador);
				if (pos < J) { // Achou a carta no topo do monte de outro jogador
					montes[jogador] += montes[pos] + 1;
					montes[pos] = 0;
					topos[jogador] = carta;
					topos[pos] = 0;
				}
				else {
					if (topos[jogador] == carta) { // Achou a carta no topo dele mesmo
						montes[jogador] += 1;
					}
					else {
						baralho[carta-1] = 1;
						jogador = (jogador + 1) % J;
					}
				}
			}
		}
		
		m = maximo (montes, J);


		printf ("%d ", m);
		for (i = 0; i < J; i++)
			if (montes[i] == m) printf ("%d ", i+1);
		printf ("\n");
		
		scanf ("%d%d", &N, &J);
	}
	
	return 0;
}

Maratona: Histórico de Comandos

Prova 2007/Primeira Fase/Problema E

Neste problema, foram armazenados

• Um vetor armazenando o histórico de comandos.
• O maior comando presente no histórico.
• Um vetor com uma posição para cada possível comando (o tamanho do vetor é o maior comando lido do histórico).

A princípio, todas as posições do segundo vetor estão zeradas. A cada comando executado do histórico, armazena-se neste vetor a ordem em que ele foi executado.

Solução (O(N)):

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

int maximo (int x, int y) {
	if (x>y) return x;
	else return y;
}

int main () {
   int N;
   int *numeros, *comandos;
   int maior, i, total;
 
   scanf("%d", &N);
   while (N != 0){
      comandos = (int*)malloc (N*sizeof (int));
      total = 0;
 
      for (i = 0; i < N; i++) {
         scanf ("%d", &comandos[i]);
         maior = maximo (comandos[i], maior);
      }
 
      numeros = (int *)calloc (maior, sizeof(int));
 
      for (i = 0; i < N; i++){
         if (numeros[comandos[i]-1] != 0 )
            total += (i + 1) - numeros[comandos[i]-1];
         else
            total += comandos[i] + i;
 
         numeros[comandos[i]-1] = i + 1;
      }
 
      printf ("%d\n", total);
      scanf ("%d", &N);
   }
 
   return 0;
}

Maratona: Desempilhando Caixas

Prova 2007/Primeira Fase/Problema F

Neste problema, foram armazenados:

• Um vetor contendo o número de caixas presentes em cada pilha.
• A pilha em que se encontra a caixa 1.
• A altura em que a caixa 1 se encontra em sua pilha.

O algoritmo é simples: Supondo que o inventário se encontra na pilha X, percorre-se as pilhas de X para a esquerda calculando a quantidade de caixas que seriam retiradas neste sentido (o algoritmo para se um pilha não possuir caixas na mesma altura que o inventário). Em seguida, executa-se o mesmo para as pilhas da direita. A resposta é o menor valor encontrado. O algoritmo é O(N), mas a própria leitura dos dados é O(N x P).

Solução:

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

int minimo (int x, int y) {
    if (x<y) return x;
    else return y;
}

int main () {
    int N, P;
    int i, j, pilha, altura;
    int nesq, ndir, caixa;
    int *v;
    
    scanf ("%d%d", &N, &P);
    while (N!=0 || P!=0) {
        v = (int *)malloc (P*sizeof (int));
        
        for (i = 0; i < P; i++) {
            scanf ("%d", &v[i]);
            for (j = 0; j < v[i]; j++) {
                scanf ("%d", &caixa);
                if (caixa == 1) {
                    pilha = i;
                    altura = j+1;
                }
            }
        }
        
        nesq = v[pilha] - altura;    // quantas caixas estao acima do inventario
        for (i = pilha-1; i >= 0 && v[i] >= altura; i--)
            nesq += (v[i]-altura+1);        // quantas caixas seraos retirada nesta pilha
        
        ndir = v[pilha] - altura;    // quantas caixas estao acima do inventario
        for (i = pilha+1; i < P && v[i] >= altura; i++)
            ndir += (v[i]-altura+1);        // quantas caixas seraos retirada nesta pilha
        
        printf ("%d\n", minimo (nesq, ndir));
        
        free (v);
    
        scanf ("%d%d", &N, &P);
    }
    
    return 0;
}