Praticando para a Olimpíada Brasileira de Informática

A Olimpíada Brasileira de Informática traz diversos desafios de lógicas. Mas como podemos resolvê-los? Veja como se preparar para os desafios

Quando eu era mais novo, na época do segundo ano do ensino médio, estava decidido a fazer um curso técnico. Na época, estava indeciso entre dois cursos técnicos: química ou informática. Acabei optando por informática e gostei muito do curso.

A parte que mais chamou minha atenção foi a parte de programação. Criar códigos, resolver problemas. Até hoje eu adoro resolver problemas com os algoritmos que aprendi!

Na época eu não sabia, mas existem alguns campeonatosde informática, como a Olimpíada Brasileira de Informática (OBI). Nessa competição, alunos do ensino fundamental, médio e que cursam o primeiro ano de um curso superior competem com desafios de lógica e programação, cada um em sua respectiva categoria.

Na OBI existem duas modalidades: a de iniciação, onde as provas são feitas no papel, e a de programação, na qual as provas são feitas no computador.

Em ambas as modalidades resolvemos problemas que envolvem lógica. A diferença é que, na modalidade de programação, a gente pode utilizar linguagens como C, Java, C++, entre outras, para criar nossa solução. Mas como será a prova? Como devemos resolver os problemas?

Só temos acesso a prova no dia da competição, mas podemos ir praticando. No site da maratona tem uma seção com alguns problemas que podemos resolver. Vamos ver como é um desses problemas!

O álbum da copa

Nos problemas de nível júnior, vamos escolher um problema de 2018 da primeira fase, o Álbum da copa.

Temos um álbum de figurinhas da copa do mundo. O álbum possui um número total de figurinhas, que é a primeira entrada no programa. Nós podemos comprar figurinhas para esse álbum - a quantidade comprada é representada na segunda entrada.

Cada figurinha que compramos representa um espaço no álbum. Esse espaço é mostrado pelas próximas entradas.

A cada nova figurinha, completamos um espaço no álbum. Logo, faltam menos figurinhas para completar o álbum. Nossa meta nesse problema é achar justamente quantas figurinhas faltam:

Entrada: 
10 ← quantidade de figurinhas no álbum 
3 ← número de figurinhas que compramos 
5 ←número da figurinha no álbum 8 3

Saida: 7 ← figurinhas que restam para completar o álbum

Podemos comprar quantas figurinhas quisermos, mas elas podem vir repetidas:

Entrada: 
5 ← quantidade de figurinhas no álbum 
6 ← número de figurinhas que compramos 
3 ←número da figurinha no álbum 
3 ← figurinha repetida 2 3 3 3

Saida: 3 ← figurinhas que restam para completar o álbum

Nesse caso compramos seis figurinhas mas quatro eram iguais, ou seja, conseguimos preencher duas figurinhas no álbum.

Como podemos começar a resolver o nosso problema?

Bem, estou utilizando a linguagem C para resolver esse problema, que é padrão nesse tipo de campeonato. Já que nosso programa terá entrada de dados, a primeira coisa que temos que fazer é incluir (include) a biblioteca padrão de entrada e saída (stdio.h):

#include <stdio.h>

Agora, temos que começar a escrever o código da solução. Todo programa em C começa a rodar a partir da função principal, a função main(). Então, vamos declará-la para conseguir executar o código:

#include <stdio.h>

int main() {

}

Essa função deve retornar um número inteiro. Por padrão, no sistema operacional, quando um programa finaliza corretamente, isso é, sem erros, é retornado (return) o valor zero:

#include <stdio.h>

int main() {

    return 0;

}

Bacana! Já temos a estrutura do projeto definida, agora vamos começar a escrever a solução.

Começando com o álbum

Nós sabemos que receberemos três informações no começo:

• A quantidade de figurinhas no álbum;
• A quantidade de figurinhas compradas e
• O número dessas figurinhas.

Já sabemos que precisa armazenar essas informações, logo, podemos falar para o C guardá-las para a gente:

#include <stdio.h>

int main() {
    int quantidadeDeFigurinhasNoAlbum;
    int numeroDeFigurinhasCompradas;

    return 0;
}

Para guardar as informações das quantidades de figurinhas, só precisamos declarar duas variáveis inteiras. Mas e para guardar o número das figurinhas que foram compradas?

Uma? Dez? Cem? Não temos como saber realmente quantas figurinhas foram compradas, então como podemos armazená-las?

O que nós podemos fazer é utilizar uma coleção que guarda as figurinhas que compramos. Essa figurinha terá, justamente, o tamanho do número de figurinhas que compramos. Mas quantas figurinhas foram compradas?

Antes de declarar essa coleção, precisamos captar o número de figurinhas compradas. Além desse número, precisamos também saber quantas figurinhas temos no álbum:

#include <stdio.h>

int main() {
    int quantidadeDeFigurinhasNoAlbum;
    int numeroDeFigurinhasCompradas;

    scanf("%d", &amp;quantidadeDeFigurinhasNoAlbum);
    scanf("%d", &amp;numeroDeFigurinhasCompradas);

    return 0;
}

Dizemos para o C que queremos escanear (scanf) valores numéricos (&d, decimal), que devem ser guardados (&) nas nossas variáveis.

Bacana! Agora nós podemos declarar a coleção com o tamanho de figurinhas compradas.

#include <stdio.h>

int main() {
    int quantidadeDeFigurinhasNoAlbum;
    int numeroDeFigurinhasCompradas;

    scanf("%d", &amp;quantidadeDeFigurinhasNoAlbum);
    scanf("%d", &amp;numeroDeFigurinhasCompradas);

    int figurinhasCompradas[numeroDeFigurinhasCompradas];

    return 0;
}

Para declarar essa coleção, que no nosso caso é um vetor, utilizamos uma sintaxe parecida com a de variáveis. Porém, passamos entre colchetes ([ ]) o tamanho do vetor. Agora, podemos ler quais foram as figurinhas que compramos.

Isto é, para um índice, que começa em 0, e enquanto esse índice for menor que o número de figurinhas compradas, vamos fazer alguma coisa. Depois disso, somamos 1 ao valor do índice, dessa forma vamos caminhando pelo vetor:

#include <stdio.h>

int main() {
    int quantidadeDeFigurinhasNoAlbum;
    int numeroDeFigurinhasCompradas;

    scanf("%d", &amp;quantidadeDeFigurinhasNoAlbum);
    scanf("%d", &amp;numeroDeFigurinhasCompradas);

    int figurinhasCompradas[numeroDeFigurinhasCompradas];
    int indice;

    for(indice = 0; indice < numeroDeFigurinhasCompradas; indice++) {
        scanf("%d", &amp;figurinhasCompradas[indice]);
    }

    return 0;
}

As figurinhas ficarão guardadas em um álbum, logo, podemos declarar um vetor para o álbum também:

#include <stdio.h>

int main() {
    int quantidadeDeFigurinhasNoAlbum;
    int numeroDeFigurinhasCompradas;

    scanf("%d", &amp;quantidadeDeFigurinhasNoAlbum);
    scanf("%d", &amp;numeroDeFigurinhasCompradas);

    int figurinhasCompradas[numeroDeFigurinhasCompradas];
    int indice;

    for(indice = 0; indice < numeroDeFigurinhasCompradas; indice++) {
        scanf("%d", &amp;figurinhasCompradas[indice]);
    }

    int album[quantidadeDeFigurinhasNoAlbum];

    return 0;
}

No começo, não existe nenhuma figurinha no álbum, logo, podemos dizer que o valor de cada posição do álbum vale 0, ou seja, nenhuma figurinha naquela posição.

#include <stdio.h>

int main() {
    // restante do código
    int indice;

    for(indice = 0; indice < numeroDeFigurinhasCompradas; indice++) {
        scanf("%d", &amp;figurinhasCompradas[indice]);
    }

    int album[quantidadeDeFigurinhasNoAlbum];

    for(indice = 0; indice < quantidadeDeFigurinhasNoAlbum; indice++) {
        album[indice] = 0;
    }

    return 0;
}

Neste caso, também usamos a variável índice e, da mesma forma que fizemos com o outro vetor, iniciamos ela com o valor zero.

Só falta agora colocar as figurinhas no álbum. Como não precisamos contar as figurinhas repetidas, podemos simplesmente passar por cada figurinha que compramos e "colá-la" no álbum, ou seja, atribuir àquela posição do álbum o valor da figurinha.

Uma característica importante é que os vetores, no C, começam na posição 0. Ou seja, se a figurinha tem o valor cinco, no vetor ela deve ocupar a posição quatro, a quinta posição no vetor. Por isso, antes de atribuir a figurinha na variável, subtraímos 1 de seu valor :

#include <stdio.h>

int main() {
     // restante do código

    for(indice = 0; indice < numeroDeFigurinhasCompradas; indice++) {
        int figurinha = figurinhasCompradas[indice];
        album[figurinha] = 1;    
    }

    return 0;
}

Com esse código, estamos atribuindo o valor 1 para cada posição no álbum, isto é, estamos "colando uma figurinha" naquela posição. Ou seja, significa que completamos mais um espaço no álbum. Podemos declarar uma variável para contar quantas figurinhas diferentes temos e, a cada atribuição no loop, incrementamos 1 nela:

#include <stdio.h>

int main() {
     // restante do código
    int figurinhasDiferentes = 0;

    for(indice = 0; indice < numeroDeFigurinhasCompradas; indice++) {
        int figurinha = figurinhasCompradas[indice] - 1;
        album[figurinha] = 1;    
        figurinhasDiferentes++;
    }

    return 0;
}

O que vai acontecer quando rodar esse último loop? Vamos incrementar o número de figurinhas diferentes para todas as figurinhas que compramos. Ou seja, até mesmo as figurinhas repetidas serão contadas!

Mas não precisamos contar as figurinhas repetidas, precisamos contar apenas as figurinhas únicas, como podemos fazer isso? Uma das formas é colocar uma condição antes de atribuir os valores nas nossas variáveis, isto é, se (if) aquela posição do álbum estiver vazia (seu valor for 0) atribuímos e incrementamos nossas variáveis:

#include <stdio.h>

int main() {
     // restante do código
    int figurinhasDiferentes = 0;

    for(indice = 0; indice < numeroDeFigurinhasCompradas; indice++) {
        int figurinha = figurinhasCompradas[indice] - 1;
        if(album[figurinha] == 0) {
            album[figurinha] = 1;    
            figurinhasDiferentes++;
        }
    }

    return 0;
}

Bacana! Aparentemente já conseguimos colar as figurinhas no álbum e contar quantas são diferentes. Sabendo quantas figurinhas são diferentes, podemos calcular quantas faltam para completar o álbum.

Agora, basta calcular a quantidade de figurinhas no álbum menos as figurinhas diferentes. Como o problema pede, vamos escrever na tela (printf) esse valor, que é um número inteiro:

#include <stdio.h>

int main() {
     // restante do código
    int figurinhasDiferentes = 0;

    for(indice = 0; indice < numeroDeFigurinhasCompradas; indice++) {
        int figurinha = figurinhasCompradas[indice] - 1;
        if(album[figurinha] == 0) {
            album[figurinha] = 1;    
            figurinhasDiferentes++;
        }
    }

    printf("%d", quantidadeDeFigurinhasNoAlbum - figurinhasDiferentes);

    return 0;
}

Como podemos saber se o nosso sistema está funcionando? Testando! No site que apresenta o desafio tem alguns testes de como o algoritmo deve funcionar. Vamos nos basear nesses testes e ver se nosso programa apresenta o resultado esperado.

Antes de executar o código, precisamos compilá-lo, isso significa que estamos passando o código para uma linguagem que a máquina entende. No meu caso, estou utilizando um Linux, porém os passos no Mac e no Windows são parecidos.

Vou utilizar o gcc para compilar o meu código, que está no arquivo album-da-copa.c, e vou falar para ele criar o programa com o nome de album-da-copa:

Nosso programa foi compilado. Podemos executá-lo utilizando o ./<nome do programa>, que no nosso caso é album-da-copa.

E como fazemos para colocar os valores de cada variável? Precisamos digitar? Digitar é uma opção, porém, na olimpíada é bacana economizar tempo para conseguir resolver mais problemas.

Pensando nisso, salvei os valores dos testes em um três arquivos de texto:

Podemos testar a aplicação executando ela e falando que a entrada de dados (<) vem de algum desses arquivos:

Legal! Nosso algoritmo passou nos testes. Mas esses testes são básicos, no site do desafio podemos submeter a solução. Basta informar a linguagem que utilizamos e o arquivo:

Quando clicamos em submeter, somos levados a tela de resultados, o ponto significa que o resultado foi correto. No final podemos ver a pontuação:

Para saber mais

Olimpíadas de programação são muito legais. Elas nos ajudam a pensar em algoritmos eficientes, que resolvam de maneira simples e rápidas os problemas. Muitos programadores gostam de participar desses tipos de competição para praticar seu código.

Para quem gostou de resolver um problema da olimpíada de programação, no site deles existem diversos outros problemas de vários níveis diferentes.

Para quem quiser ir praticando e não sabe por onde começar, na Alura Start temos diversos cursos sobre a olimpíada de programação nos quais você pode ver os problemas, ver as possíveis soluções, além de praticar a parte da programação.

Se você se interessou por esse tipo de competição, mas não pode participar porque não está estudando ou já está em anos mais avançados da faculdade, existe a Maratona de Programação, na qual cada equipe de diversas faculdades competem criando algoritmos.

Aqui na Alura existe um curso sobre a maratona de programação. Nele, você verá como se preparar para a prova, além de técnicas sobre como resolver alguns problemas.

Onde estudar faculdade de computação?

E talvez você queira entrar de cabeça em programação, em tech e em computação, né?

Faculdades são um caminho muito interessante, onde você vai poder disputar outros tipos de competição.

Recentemente a Alura juntou forças com o centro universitário FIAP. Eles espandiram o catálogo de cursos de graduação com cursos a distância também.

Espero que você venha conhecer a infraestrutura da FIAP. É incrível.

Alura + FIAP caminham cada vez mais juntas e eu espero ter você próximo da gente também!