OBI 2014 – Fase 1 – Modalidade Universitária – Editorial

Neste dia 10 de maio aconteceu a primeira fase da Olimpíada Brasileira de Informática, edição 2014 [link].

Vou postar aqui um editorial não oficial, escrito pelo maratonista Rafael Rodrigues, para os exercícios da modalidade universitária. Baixe a prova neste [link], e teste suas soluções neste [link].

Clique no link abaixo para ver o post completo.

Carteiro

Esse era um problema que precisava de uma otimização usando busca binária para ganhar todos os pontos, vejamos o programa em C++:

#include<stdio.h>
#include<stdlib.h>
#define N 45000+5
#define M 45000+5
int v[N];
int t[M];
int busca(int m, int ini, int fim)
{
    int meio=(ini+fim)/2;
    if (v[meio]==m) return meio;
    if (v[meio]<m) return busca(m,meio+1,fim);
    return busca(m,ini,meio-1);
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
        scanf("%d",&v[i]);
    for (int j=1;j<=m;j++)
        scanf("%d",&t[j]);
    int tempo=0;
    int posicao=1;
    for (int i=1;i<=m;i++)
    {
        int proxima_posicao=busca(t[i],1,n);
        tempo+=abs(proxima_posicao-posicao);
        posicao=proxima_posicao;
    }
    printf("%d\n",tempo);
    return 0;
}

O programa é bem simples e ele funciona guardando os números das casas no vetor v, além disso guarda a ordem das entregas no vetor t. Inicialmente, o tempo gasto é 0 e a posição inicial é 1.

Lembre-se que o enunciado afirma que o vetor v é ordenado crescentemente. Portanto, para cadaentrega que o carteiro deve fazer, fazemos uma busca binária do valor t[i] no vetor v, daí essa será a próxima posição que o carteiro deve ir, o que leva um tempo proxima_posicao – posicao para acontecer.

Algoritmo para estudo: [link]

Cartas

#include<stdio.h>
int v[10];
int main()
{
    for (int i=1;i<=5;i++)
    scanf("%d",&v[i]);
    bool crescente=true;
    bool decrescente=true;
    for (int i=1;i<5;i++)
        if (v[i+1]<v[i]) crescente=false;
    for (int i=1;i<5;i++)
        if (v[i+1]>v[i]) decrescente=false;

    if (crescente)
        printf("C\n");
    else if(decrescente)
        printf("D\n");
    else printf("N\n");
    return 0;
}

Se houver algum v[i]>v[i+1], então a função não é crescente.
Se houver algum v[i]<v[i+1], então a função não é decrescente.

Pacman

#include<stdio.h>
#include<algorithm>
#define N 100+5
using namespace std;
char matriz[N][N];
void analisa(char x,int *soma, int *maior)
{
    if (x=='o')
    {
        *soma+=1;
        *maior=max(*maior,*soma);
    }
    else if (x=='A')
        *soma=0;
}
int main()
{
    int n;
    scanf("%d",&n);
    for (int i=1;i<=n;i++)for (int j=1;j<=n;j++)
        scanf(" %c",&matriz[i][j]);
    int soma=0;
    int maior=0;
    for (int i=1;i<=n;i++)
    {
        if (i%2==1)
            for (int j=1;j<=n;j++)
                analisa(matriz[i][j],&soma,&maior);
        else
            for (int j=n;j>=1;j--)
                analisa(matriz[i][j],&soma,&maior);
    }
    printf("%d\n",maior);
    return 0;
}

Então para cada linha i de 1 até n, se i for ímpar então devemos percorrer da esquerda para a direita, mas se i for par, devemos percorrer da direita para esquerda.

Para cada posição (matriz[i][j]), vamos analisar o caractere dela:

  • Se for um ‘.’ não há nada a ser feito.
  • Se for um ‘o’ dizemos que temos mais uma comida(soma+=1) e testamos para ver se o número atual de comidas é maior que o máximo de antes(maior=max(soma, maior)).
  • Se for um ‘A’, ficamos com 0 de comida(soma=0).

Fechadura

Nesse problema usamos um algoritmo guloso, tente provar que esse algoritmo funciona.

#include<stdio.h>
#include<stdlib.h>
#define N 1000+5
int v[N];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
        scanf("%d",&v[i]);
    int soma=0;
    for (int i=1;i<n;i++)
    {
        soma+=abs(v[i]-m);
        v[i+1]+=m-v[i];
        v[i]=m;
    }
    printf("%d\n",soma);
    return 0;
}

O algoritmo começa fazendo os primeiros termos ficarem iguais a m, e depois vamos consertando da esquerda para a direita. Para provar que o algoritmo funciona e encontra o número mínimo de movimentos, devemos pensar que o número mais à esquerda para ser modificado, deve obrigatoriamente mudar a mesma quantidade do seu vizinho à direita. Feito isto, considere um momento em que você não modifica mais o elemento mais à esquerda. Daí, o vizinho da direita dele vira o elemento mais à esquerda em um subproblema com n-1 números. A prova do problema segue por indução.

Matriz Escada

#include<stdio.h>
#define N 500+5
#define M 500+5
int matriz[N][M];
int v[N],n,m;
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            scanf("%d",&matriz[i][j]);
    for (int i=1;i<=n;i++)
        v[i]=m+i;
    for (int i=1;i<=n;i++)
        for (int j=m;j>=1;j--)
            if (matriz[i][j]!=0)
                v[i]=j;
    bool crescente=true;
    for (int i=1;i<n;i++)
        if (v[i]>=v[i+1])
            crescente=false;
    printf(crescente?"S\n":"N\n");
    return 0;
}

O vetor v será definido da seguinte forma:
Tome na linha i, o zero mais à esquerda, daí v[i] é igual ao índice da coluna em que este zero está (Inicialmente definimos que o zero mais à esquerda está na posição m+i).

Tente mostrar que a matriz é triangular, se e somente se, o vetor v é crescente.
(Dica: Use as duas restrições dadas no enunciado do problema para definir matriz triangular e teste cada uma separadamente e lembre que, inicialmente, v[i]=m+i. Ou seja, inicialmente, v é crescente e todos valores são maiores que m)

 

É possível ver os casos de teste e as soluções oficiais divulgadas no site da OBI, neste [link].

Agradecimentos ao Rafael Rodrigues pelo editorial.
Qualquer dúvida, crítica ou sugestão, deixem um comentário abaixo.

Deixe uma resposta

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *