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/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 e única que é permitida nas IOI (existem outras razões técnicas, mas para já não são tão relevantes). Um programa em C++ parece-se algo como o seguinte:

// Exemplo de programa que lê dois números inteiros e imprime a sua soma
#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, bem como uma explicação de 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 de um 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 elementos (incluindo o Ricardo), 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 (as linhas que começam com `\\`) é ú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 acima 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á restrito a concorrentes inscritos nas ONI, que recebem credenciais de acesso quando a sua inscrição for aceite. 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 Login e escolherem o concurso "Guia de Iniciação" da lista de concursos. 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

O enunciado estará sempre também disponível no Mooshak, mas para facilitar a leitura deste guia incluimos uma ligação também aqui. 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.