As Olímpiadas de Informática são um concurso de programação, como tal é importante saber programar. Não é necessário saber muito de programação para ter sucesso neste concurso, como iremos ver num artigo futuro (Eficiência vs Eficácia). Ainda assim, é preciso saber programar, por isso neste artigo discutimos as ferramentas necessárias e como aprender a programar.

O que é um programa?

Antes de mais, o que é um programa? Um programa é apenas um texto numa linguagem de programação. Há 3 linguagens de programação permitidas nas Olimpíadas: C++, Java e Pascal. Para quem está a começar, recomendamos começar por C++, porque é a linguagem com mais recursos para concursos como as Olimpíadas (existem outras razões técnicas, mas para já não são relevantes). Um programa em C++ parece-se algo como o seguinte:

#include <iostream>

using namespace std;

int main() {
  int a, b;

  cin >> a >> b;
  cout << a << " + " << b << " = " << a + b << endl;

  return 0;
}

Um programa é um conjunto de instruções para processar um conjunto de dados (conhecido como input) e devolver um resultado (conhecido como output). Estas instruções seguem um conjunto de regras definido pela linguagem de programação em que o programa está escrito, identicamente a um texto em português, que segue um conjunto de regras definido pela língua em que está escrito. O programa acima recebe dois números e devolve a soma dos dois (ou seja é uma mini calculadora). Iremos ver porquê em breve.

Ambiente de programação

Depois de escrevermos um programa, é preciso fazer com que o computador execute as suas instruções. Para tal precisamos de um outro programa que transforma o nosso programa para um formato que o computador consegue entender. Este programa chama-se um compilador, isto porque compilar um programa significa exatamente fazer o processo descrito.

Depois de compilarmos um código podemos executá-lo, o que significa passar-lhe um conjunto de dados (um input) para obter o resultado que ele devolve (o output).

Onde aprender a programar

Existem muitos recursos disponíveis online sobre programação e aprender a programar em geral. É fácil perder-se em tanta informação, especialmente porque existe muito de programação além do que é necessário para as Olimpíadas. Sendo assim, recomendamos alguns recursos de introdução à programação (ambos em inglês):

Estas referências também indicam como instalar o ambiente de programação necessário (o compilador) para começarem a programar. Se preferirem recursos em Português:

Não se assustem com facto de algumas destas notas serem de introdução a um curso universitário, é uma cadeira introdutória e não requer qualquer tipo de conhecimento prévio.

Recomendamos que leiam o resto desta secção antes de ler os artigos/livros mencionados acima.

O meu primeiro programa

A melhor maneira de aprender a programar é por consolidar a leitura dos conceitos teóricos com a sua aplicação, ou seja, programando. No próximo artigo (Problemas Introdutórios) apresentamos 4 problemas simples, com nível de dificuldade crescente, para irem aplicando os vários conceitos que aprenderam. Recomendamos que à medida que vão aprendendo mais vão resolvendo estes problema (cada problema terá uma nota indicando o que necessitam de saber).

Como exemplo, incluímos neste artigo um primeiro problema assim como o resolver. Para saberem como resolver este problema é importante que saibam os conceitos mais básicos de C++, incluindo a estrutura de um programa, váriaveis e tipos e ainda leitura e escrita de dados (que devem ser os primeiros conceitos que aprendem em qualquer um dos recursos recomendados).

O meu primeiro problema

Todos os problemas das Olimpíadas têm uma pequena história que contextualiza o problema a resolver. Além disso, a história fornece a intuição necessária para saber o que pede o problema. Por isso, uma habilidade que é muito importante trabalhar é a de interpretação do texto problema. Vejamos então o primeiro exemplo de um problema muito simples:

É o aniversário do Ricardo. Como tal, a sua família comprou-lhe um bolo com N fatias iguais para todos comerem. O Ricardo é um rapaz justo, por isso quer que cada elemento da sua família coma o mesmo número de fatias. Além disso, o Ricardo não quer dividir nenhuma das fatias, como tal cada fatia só pode ser comida por no máximo uma única pessoa. Sabendo que a família do Ricardo tem M (incluindo o Ricardo) elementos, qual o máximo número de fatias que o Ricardo pode dar a cada um para que todos comam o mesmo número de fatias?

Vamos descontruir este problema. Temos N fatias de bolo. N é um parâmetro do nosso problema, ou seja, é algo que nos será dado no input do problema e que o nosso programa deve ler. Adicionalmente, temos M pessoas que vão comer algumas dessas fatias. Finalmemente, é-nos pedido para determinar o máximo de fatias que cada um pode comer para que todos comam o mesmo número.

Não é preciso pensar muito neste problema para perceber que a resposta é exatamente N a dividir por M. E se M não for divisível por N? Então temos de arredondar por defeito, ou seja, escolher o maior número inteiro que é menor do que a divisão de N por M.

Como podemos fazer um programa para executar isto? O nosso programa vai começar por ler dois números inteiros, primeiro N e depois M. Visto que se trata de pessoas e fatias, vamos a assumir que tanto N e M são inteiros e maiores que 1 (a família do Ricardo inclui pelo menos o Ricardo e ele tem direito a pelo menos uma fatia). Finalmente só temos de imprimir a divisão arredondada por defeito dos dois números, que em C++ se faz usando o operador /.

O nosso programa final será então (o que se encontra depois dos caracteres // é ignorado e serve apenas para anotar o programa, estes pedaços de texto são conhecidos como comentários do programa):

#include <iostream>

using namespace std;

int main() {
  int N, M; // As variaveis do problema

  cin >> N >> M; // Ler os dois valores do problema
  cout << N / M << endl; // Imprimir a resposta

  return 0;
}

O programa é muito semelhante ao anterior, mas efetua uma divisão em vez de uma soma. Também devem ter reparado que depois de imprimir a resposta, o programa imprime ainda uma mudança de linha (através do endl, correspondente ao carácter \n), isto é porque todos os outputs de problemas das Olimpíadas devem acabar com uma mudança de linha (a não ser que o enunciado indique o contrário).

Nota: Nota sobre comentários

O uso de comentários é útil para além do uso pedagógico que mostramos aqui. Anotar o programa com comentários ajuda a identificar o que diferentes secções do programa fazem, especialmente em programas mais extensos.

Submeter um programa

Depois de escrevermos um programa para resolver um problema como o anterior, é útil podermos verificar se está correto. Além disso, durante as provas das Olimpíadas é necessário avaliar os vários programas para determinar quais estão corretos (equivalente a corrigir um teste ou exame). Para tal, usamos uma plataforma de submissão de programas chamada Mooshak.

Quando submetem um programa para o Mooshak, ele avalia-o em vários casos de teste, ou seja, corre diferentes inputs (que foram criados para testar o problema) e compara o output do programa com o output esperado (que corresponde ao output gerado por um programa correto). Este é um processo determinístico, ou seja, o Mooshak compara cada carácter do output do programa fornecido com cada carácter do output esperado e apenas indica que a resposta está correta se todos forem exatamente iguais. Isto significa que não devem imprimir mais nenhuma informação, por exemplo, se a resposta a um input para o problema a cima for 5 e o vosso programa devolver O Ricardo pode dar 5 fatias ou A resposta é 5, o Mooshak irá avaliar o vosso programa como errado para este caso de teste. É por isso que a questão anterior sobre usar mudanças de linha no fim do output é tão importante, para garantir que os outputs são exatamente iguais.

Nota: Registo no Mooshak

O registo na plataforma de submissão está temporariamente restrito a concorrentes inscritos nas ONI. Para te inscreveres vai ao site das ONI.

Todos os problemas nestes artigos estão presentes no Mooshak de treino das Olimpíadas. Para entrarem, basta seguirem o link seguinte, clicarem em "Registar num concurso de treino" e escolherem o concurso "Problemas Introdutórios" da lista de concursos. Escolham um nome identificativo e coloquem o vosso email. Depois de receberem um email com as vossas credenciais, podem entrar no mesmo link, clicar em login, escolher o concurso "Problemas Introdutórios" novamente e introduzir as vossas credenciais. No topo da página terão uma lista de problemas, ordenados pela ordem que aparecem aqui. Sempre que mencionarmos um problema teremos uma nota como a seguinte a identificar o problema:

Problema A: Festa do Ricardo

Este problema está disponível no Mooshak de treino como o problema A.

Experimentem submeter o programa acima para este problema (ou o vosso próprio) no Mooshak. Devem receber uma notificação a dizer "100 Accepted" e se forem ao ranking estarão listado como tendo 100 pontos (num artigo futuro iremos mencionar como funciona o sistema de pontos). Para mais informações sobre o Mooshak ir aqui. Mais um reparo final, se o vosso código não tiver a mudança de linha no fim do output como mencionado anteriormente, o Mooshak dará um erro de Presentation Error quando submeterem o vosso programa (podem ler mais sobre este e outros erros no link dado na frase anterior).

Nota final sobre problemas

No problema anterior tivemos que assumir algumas coisas sobre o input de acordo com a história do problema, nomeadamente que N e M são números inteiros, entre outras coisas. Se virem a versão deste mesmo problema no Mooshak, verão que tem algumas secções extra, que servem para resolver estas ambiguidades, nomeadamente:

  • Secção "O Problema": contém um resumo do problema dado no resto do enunciado, normalmente é importante ler o resto do enunciado para entender o resumo;
  • Secção "Input": esclarece o formato do Input e possíveis garantias que sejam dadas pelo Input;
  • Secção "Output": esclarece o formato do Output;
  • Secção "Restrições": indica os limites de todos os parâmetros do input, por exemplo, neste caso N é sempre maior ou igual a 1 e menor ou igual a 1000 e o mesmo para M;

Adicionalmente têm ainda uma (noutros problemas podem ter até várias) secção de exemplos, que servem para poderem testar o vosso programa. Cada exemplo contém um input, no formato pretendido, e o respetivo output. Podem correr o vosso programa com cada exemplo e verificar se está correto. Notem que estar correto para os exemplos não significa que o programa esteja correto, quando o submetem o Mooshak corre outros casos de teste de possíveis inputs e verifica se o programa está correto em todos, os exemplo apenas servem para vos ajudar a verificar a correção dos vossos programas.