Primeiras aulas do curso Maratona de programação: Algoritmos para sua primeira competição

Maratona de programação: Algoritmos para sua primeira competição

Começando o treinamento - Introdução

Olá, sou o Gabriel Fernandes. Boas vindas ao curso de maratona de programação. Juntos, entenderemos como treinar para essa competição usando os recursos que temos online, e quais são os assuntos que mais caem na prova.

Ao todo, resolveremos 8 problemas durante o curso, sendo um deles o problema dos Bits Trocados. Por meio desses problemas aprenderemos como usar os juízes online, sites que acessaremos para treinar para a maratona.

Desenvolveremos juntos o código para a resolução desse problema e veremos como testá-lo e algumas das dificuldades mais clássicas enfrentadas enquanto programamos para a maratona.

Quando já tivermos testado e visto que nossa solução deu certo, aprenderemos a submetê-la. Entraremos no site SPOJ Brasil, que funcionará como um juiz online, escolheremos o arquivo com nosso código e clicaremos no botão para upá-lo. Depois, só precisaremos esperar pelo veredito.

O SPOJ Brasil será um dos sites de juízes online que conheceremos durante o curso. Outros dois deles serão o CodCad, que tem vários problemas e conteúdos muito bons, e o URI, que traz problemas categorizados por assunto.

Voltaremos para o SPOJ e veremos que a solução que submetemos terá sido aceita. Então, também entenderemos sobre os vereditos que receberemos desses juízes online, como "Aceito", quando acertamos um problema, e "Resposta errada", ou "Tempo limite excedido", alguns dos erros que poderemos encontrar.

Durante o curso, veremos assuntos como ordenação por seleção (selection sort()) que programaremos num dos problemas, e a função sort() que teremos na biblioteca padrão do C++. Ela já estará implementada e nós a usaremos para ordenar uma sequência de números.

Além disso, teremos conceitos como recursão (e resolveremos problemas relacionados), busca binária e início à programação dinâmica. Aprenderemos a técnica de memoização para poder otimizar nossas recursões.

Vamos começar nossas aulas.

Começando o treinamento - Soma da sequência

Vamos começar nosso curso de maratona de programação.

Como devemos treinar para a maratona de programação ou mesmo para uma olimpíada de informática?

Vamos tentar achar problemas parecidos com os que encontraremos nas provas. Será pedida alguma solução algorítmica para um problema de teoria da computação.

Conseguimos encontrar esses problemas em sites conhecidos como juízes online. Um exemplo é o SPOJ Brasil. Esse site nos ajudará a treinar, pois apresentará uma lista com vários problemas nos quais podemos clicar para ler. Acessaremos um problema chamado "Sistema Cipoviário".

Geralmente esses exercícios serão bastante similares aos que encontraremos nas provas. Alguns deles são realmente tirados de provas de anos anteriores. Esse, por exemplo, é proveniente da Seletiva da Maratona de Programação do IME de 2007.

Então, resolver os problemas será um bom treinamento. Começaremos nosso curso resolvendo um deles. Tentaremos entender o enunciado de um problema selecionado: "Soma".

Dada uma lista de N inteiros, encontre a soma de todos eles.

Na sequência há uma descrição da entrada. A entrada de um programa será o que ele vai ler, o que receberemos usando o cin ou o scanf().

Há também a saída, ou secessão. A saída será o que o programa imprime com cout ou printf(). Isso quando estivermos programando em C ou C++.

Leremos a Entrada:

A entrada é composta de um único caso de teste. A primeira linha contém um inteiro positivo N . As N linhas seguintes contém cada uma um inteiro X representando os N números a serem somados.

Portanto, conforme havia sido dito, haverá uma lista de N inteiros, e na primeira linha da entrada o primeiro item que leremos será esse N inteiro positivo, a quantidade de números nessa lista.

Teremos primeiro a quantidade de números na lista e depois, em cada linha, todos esses números que deveremos somar.

Quanto a saída, o enunciado descreverá da seguinte forma:

Seu programa deve produzir uma única linha na saída contendo a soma de todos os N inteiros.

Depois, veremos as restrições do problema. Até então, o enunciado só tinha falado sobre variáveis. Receberemos N** números e cada número será um inteiro **X. Porém, ainda não foi dito nada a respeito do valor dessas variáveis.

As restrições servirão para especificar que o N*, ou seja, a quantidade de números que somaremos, estará entre 0 e 50 (0 ≤ *N ≤ 50).

O módulo, ou o valor absoluto do X será menor ou igual a 5000 (|X| ≤ 5000).

Já vimos como costumam ser os enunciados de problemas que encontramos nos juízes online. Será comum que sigam uma estrutura de enunciado geral, entrada, saída e especificações do problema, as restrições.

Uma outra sessão que poderá aparecer são os exemplos. Eles servirão para colaborar com nosso entendimento do problema. Nossa interpretação terá sido que primeiro leremos a quantidade de números numa lista e depois em cada linha virão os números dessa lista.

No exemplo, leremos:

Entrada
1
2
3

Saída
5

Entrada

3
1
5
3

Saída

9

Nesse exemplo aparecerá primeiro o N, o número de inteiros na lista. Serão 2. Em seguida, terão duas linhas com os números que queremos somar, 2 e 3. A saída que o juiz esperará dessa entrada será 5, a soma de 2 + 3.

O exemplo terá uma outra entrada para testar o programa com 3 valores, 1, 5 e 3, e a saída 9, resultado de 1 + 5 + 3.

Abriremos o terminal para implementar isso. Já teremos uma pasta chamada de "maratona" e entraremos nela. Digitaremos cd maratona/. Por enquanto não haverá nada nessa pasta.

Para programar, usaremos um editor de texto chamado VIM, que estará embutido no terminal e é leve. Outro editor de texto da preferência do programador poderia ser utilizado, pois esse será só um meio de escrever os códigos. Digitaremos vim SOMA.cpp. Estaremos criando um arquivo chamado "SOMA" cuja extensão é .cpp, programando em C++.

Nesse programa, precisaremos primeiramente ler o valor inteiro positivo N, ou quantos números a lista terá.

Iniciaremos programando nossa função principal, em que escreveremos todo nosso código em C++

Vamos ler o inteiro n e o declararemos. Para lê-lo, usaremos o cin lendo o valor da entrada e armazenando-o em n. Para usar o cin teremos que lembrar de dois fatores. O primeiro será usar a biblioteca que contém essa função, <iostream>. O "i" e o "o" de "iostream" virão de "input" e "output", ou entrada e saída em inglês. Essa biblioteca tratará do fluxo de entrada e saída de valores do nosso programa.

O segundo item que devemos nos atentar será o uso de namespace std. Assim não será necessário sempre escrever std:: antes do cin no código, onde a função cin estará definida dentro da biblioteca <iostream>. Fazendo essa indicação, diremos que vamos usar funções da biblioteca padrão de C++ diversas vezes, sem precisar repetir o std e os dois pontos.

#include <iostream>
using namespace std;

int main () {
    int n;
    cin >> n;
}

Nosso próximo passo será realmente ler a lista de números. Cada um dos números estará numa linha e precisaremos lê-los e somá-los de alguma forma. Para a leitura, criaremos um laço de repetição com um for() que terá um inteiro i que irá de 0 até n - 1. Outra possibilidade será colocar que ele irá de 1 até n.

Estando pronto o laço, faremos outro cin para ler o valor x que será o inteiro da sequência da nossa lista. Então esse cin lerá o valor e armazenará na variável, que declararemos na linha de cima.

Depois de ler o x, vamos somar todos os valores. Criaremos uma variável de soma que será um int e começará com um 0. Enquanto ainda não foram somados os valores, a soma será 0. A medida que os valores x serão lidos, os somaremos nessa variável soma = soma + x. Outra forma de escrever o mesmo será soma += x. Usaremos essa forma mais concisa em nosso código.

Estaremos lendo todos os valores e somando na variável soma. Então, para terminar nosso programa, imprimiremos essa soma no terminal, que de acordo com o problema, deverá ser a saída. Por isso escreveremos o cout e a soma que descobrimos.

#include <iostream>
using namespace std;

int main () {
    int n;
    cin >> n;

   int soma = 0;
   for(int i=1;i<=n;i++){
       int x;
       cin >> x;

       soma +=x

}

cout << soma;

A seguir, compilaremos nosso primeiro programa de maratona e vamos testá-lo.

Começando o treinamento - Submetendo a solução

Finalizamos nosso primeiro programa de maratona.

Agora testaremos nosso programa para saber se ele estará funcionando conforme os exemplos que o enunciado apresentou.

Vamos ocultar nosso editor de código e compilaremos o programa. No terminal, podemos digitar g++ SOMA.cpp - o SOMA.

Mas há a possibilidade de usar uma sintaxe mais reduzida com o comando make. Esse comando funcionará tanto para Linux quanto para Mac. Bastará digitarmos make SOMA.

No Windows, caso tenhamos instalado o mingw escreveremos mingw32.make no prompt.

Como estamos usando o Linux, deixaremos apenas make SOMA. Devemos lembrar que o arquivo nesse caso virá sem a extensão .cpp, apenas o nome SOMA aparecerá após o make. Rodaremos esse código e veremos que por baixo dos panos, ele executará a sintaxe que tínhamos citado, g++ SOMA.cpp - o SOMA.

Agora, se digitarmos ls no terminal, veremos os arquivos que estarão dentro da pasta "maratona", nosso programa SOMA.cpp e o arquivo compilado e acabamos de criar. Então, vamos rodá-lo.

Para isso, escreveremos ./SOMA. Vamos pegar no site em que está o enunciado o exemplo que ele nos oferece: serão 2 valores que equivalerão aos números 2 e 3. Digitaremos os mesmos números no prompt.

Teremos o resultado correto, 5:

 2
 2
 3
 5 

Veremos que o resultado estará colado ao terminal, o que parecerá estranho. Mas a única razão para isso ter acontecido é que nós não pulamos linha no código no final do programa, depois de imprimir o valor da variável. Voltaremos ao nosso editor digitando vim SOMA.cpp.

No código, só escrevemos o cout e variável soma. Colocaremos um endline depois da variável para ajeitar nossa saída.

 #include <iostream>
using namespace std;

int main () {
    int n;
    cin >> n;

   int soma = 0;
   for(int i=1;i<=n;i++){
       int x;
       cin >> x;

       soma +=x

}

cout << soma << endl;

Compilaremos novamente por meio de make SOMA no terminal e rodaremos o exemplo mais uma vez. Agora conseguiremos imprimir o 5, soma de 2+3, na linha seguinte.

Rodaremos de novo o programa SOMA e conferir o outro exemplo do site. Copiaremos o exemplo do site e colaremos no terminal.

3
1
5
3
9

A soma de 1, 5 e 3 será 9, portanto parece que o programa estará funcionando e as saídas estão batendo com as que temos no enunciado. Faremos o teste derradeiro, que será clicar no botão "Submit solution!" ao fim da página do problema e mandar a solução. O papel dele será testar se essa solução estará correta.

Teremos que logar no site e para isso será necessária uma conta no SPOJ. Precisaremos fazer um cadastro, escolhendo um username, fornecendo e-mail e senha. Vamos logar com um conta criada previamente e na página de submissão da solução desse problema teremos a opção de selecionar arquivos do computador, assim como escolher em que linguagem de programação estará nossa solução, pois o site aceitará uma grande variedade de linguagens.

Estaremos programando em C++ e há várias sugestões para submeter uma solução usando essa linguagem. Escolheremos uma com nossa versão de compilador de arquivos (C++ g++ 4.3.2).

Haverá uma área para colar nosso código, ou poderemos clicar no botão "Choose file" e escolher o arquivo que contém nosso programa. Nosso arquivo, como já foi dito, será o "SOMA.cpp" e estará na pasta "maratona".

Submeteremos o problema e com a solução submetida, o juiz on line fará testes com nosso código, da mesma forma que nós testamos colocando os valores dos exemplos no prompt, mas numa quantidade superior de casos de teste, usando por exemplo 50 números. Levará algum tempo para que os resultados sejam apresentados.

Haverá outras pessoas submetendo outras soluções para outros problemas e veremos os vereditos na nossa tela. Mais pra frente no curso entenderemos melhor as mensagens referentes a esses resultados.

O site terminará a análise e nosso resultado será aceito. De acordo com a bateria de testes efetuada pelo juiz nossa solução estará correta. Então, já conseguimos resolver um problema de maratona!

A seguir, resolveremos o problema dos Bits Trocados.

Sobre o curso Maratona de programação: Algoritmos para sua primeira competição

O curso Maratona de programação: Algoritmos para sua primeira competição possui 193 minutos de vídeos, em um total de 41 atividades. Gostou? Conheça nossos outros cursos de Computação em Programação, ou leia nossos artigos de Programação.

Matricule-se e comece a estudar com a gente hoje! Conheça outros tópicos abordados durante o curso:

Aprenda Computação acessando integralmente esse e outros cursos, comece hoje!

  • 1124 cursos

    Cursos de programação, UX, agilidade, data science, transformação digital, mobile, front-end, marketing e infra.

  • Certificado de participação

    Certificado de que assistiu o curso e finalizou as atividades

  • App para Android e iPhone/iPad

    Estude até mesmo offline através das nossas apps Android e iOS em smartphones e tablets

  • Projeto avaliado pelos instrutores

    Projeto práticos para entrega e avaliação dos professores da Alura com certificado de aprovação diferenciado

  • Acesso à Alura Start

    Cursos de introdução a tecnologia através de games, apps e ciência

  • Acesso à Alura Língua

    Reforço online de inglês e espanhol para aprimorar seu conhecimento

Premium

  • 1124 cursos

    Cursos de programação, UX, agilidade, data science, transformação digital, mobile, front-end, marketing e infra.

  • Certificado de participação

    Certificado de que assistiu o curso e finalizou as atividades

  • App para Android e iPhone/iPad

    Estude até mesmo offline através das nossas apps Android e iOS em smartphones e tablets

  • Projeto avaliado pelos instrutores

    Projeto práticos para entrega e avaliação dos professores da Alura com certificado de aprovação diferenciado

  • Acesso à Alura Start

    Cursos de introdução a tecnologia através de games, apps e ciência

  • Acesso à Alura Língua

    Reforço online de inglês e espanhol para aprimorar seu conhecimento

12X
R$75
à vista R$900
Matricule-se

Premium Plus

  • 1124 cursos

    Cursos de programação, UX, agilidade, data science, transformação digital, mobile, front-end, marketing e infra.

  • Certificado de participação

    Certificado de que assistiu o curso e finalizou as atividades

  • App para Android e iPhone/iPad

    Estude até mesmo offline através das nossas apps Android e iOS em smartphones e tablets

  • Projeto avaliado pelos instrutores

    Projeto práticos para entrega e avaliação dos professores da Alura com certificado de aprovação diferenciado

  • Acesso à Alura Start

    Cursos de introdução a tecnologia através de games, apps e ciência

  • Acesso à Alura Língua

    Reforço online de inglês e espanhol para aprimorar seu conhecimento

12X
R$100
à vista R$1.200
Matricule-se

Max

  • 1124 cursos

    Cursos de programação, UX, agilidade, data science, transformação digital, mobile, front-end, marketing e infra.

  • Certificado de participação

    Certificado de que assistiu o curso e finalizou as atividades

  • App para Android e iPhone/iPad

    Estude até mesmo offline através das nossas apps Android e iOS em smartphones e tablets

  • Projeto avaliado pelos instrutores

    Projeto práticos para entrega e avaliação dos professores da Alura com certificado de aprovação diferenciado

  • Acesso à Alura Start

    Cursos de introdução a tecnologia através de games, apps e ciência

  • Acesso à Alura Língua

    Reforço online de inglês e espanhol para aprimorar seu conhecimento

12X
R$120
à vista R$1.440
Matricule-se
Procurando planos para empresas?
Acesso por 1 ano
Estude 24h/dia onde e quando quiser
Novos cursos toda semana