Aula por Arthur Lobo
Problemas interativos são problemas em que o seu código tem que interagir com o juiz para dar uma resposta correta. Geralmente o seu código deve fazer uma quantidade limitada de "perguntas" em um formato pré estabelecido e no final você tem que dar a resposta correta, que normalmente é para descobrir alguma informação escondida.
Vamos imaginar uma situação do dia a dia: Ana e seu amigo Beto estão brincando de Jogo da Forca, no qual Ana tem que adivinhar qual a palavra que João escolheu. No início do jogo, Ana sabe apenas o tamanho da palavra (a quantidade de tracinhos). Em cada rodada, Ana faz a pergunta no formato: "A palavra tem a letra [insira alguma letra aqui]?", e seu amigo irá responder , de acordo com a palavra escolhida inicialmente, se ela possui ou não a letra e, caso possua, onde ela está. Até que Ana perca (atinga o limite de perguntas) ou acerte a palavra.
Nesse exemplo, Ana faz o papel do seu código e Beto faz o papel do juiz. Ana pode fazer uma quantidade limitada de perguntas no formato pré estabelecido, assim como seu código, e no final tem que descobrir uma informação escondida, mas sem exceder a quantidade limite de perguntas. Existem muitos outros jogos do dia a dia que se assemelham com um problema interativo de informática, como o Wordle, Batalha Naval, e Cara a Cara (nos dois últimos, ambos os jogadores agem como seu código e como o juiz ao mesmo tempo).
Como é um problema interativo em informática?
O Problema da Semana 29 Intermediário é um excelente exemplo de problema interativo de informática:
Nesse problema, você é o jogador e quer achar o número secreto. Você sabe que o número secreto está entre 
e 
e tem até 25 tentativas. Para cada tentativa, a máquina vai dizer se o número secreto é 
(maior ou igual a) ou se ele é 
(menor que) sua tentativa. Depois de no máximo 25 tentativas, você deve imprimir qual o número secreto.
Nesse exemplo, você tem que utilizar uma busca binária para, em cada pergunta, reduzir sua área de busca pela metade, e depois de cerca de 20 perguntas, você saberá qual é a informação escondida (o número secreto).
Existem 2 tipos de modelos de problemas interativos:
Interação através da saída
Esse modelo é usado em sites como AtCoder e Codeforces. Nele o seu código interage com o juiz através do buffer, ou seja, da saída padrão. Para fazer as perguntas, você imprime ela em um formato pré estabelecido e depois usa o comando "cout.flush()" em C++, esse comando basicamente manda tudo que está na saída padrão para o juiz, em seguida, você lê a reação do juiz para a pergunta pela entrada padrão. Para dar a resposta, você faz a mesma coisa - imprime a resposta no formato e usa "cout.flush()".
Um exemplo de código para o problema exemplificado a cima:
Para treinar esse tipo de interativo, tente fazer o problema Find by Query, do AtCoder.
Interação através de funções
Esse é o modelo usado em Olimpíadas de Informática, como na IOI, e também na Seletiva para a IOI. Se você está se preparando para a seletiva, é de extrema importância que você se acostume com esse tipo.
Nesse modelo, o seu código vai estar dentro de uma função e ele interage com o juiz através também de funções. Para fazer uma pergunta, o seu código vai chamar uma função do juiz - o argumento (ou argumentos) dessa função será a pergunta, e o valor retornado pela função será a resposta.
No exemplo do problema da semana, ao invés de imprimir uma pergunta e ler a resposta, o problema teria uma função "string tentativa(int x)" do juiz - para fazer perguntas, seu código faria "string maior_ou_menor = tentativa(tentativa_atual)" e seguiria normalmente. Até que na hora que o número secreto for descoberto, você retorna ele com "return resposta".
O seu código não terá o "int main()", no lugar, haverá apenas a função que você deve escrever seu código dentro para retornar a resposta, além disso, alguns problemas pedem para você incluir algumas bibliotecas (além de "bits/stdc++.h"), mas isso será dito no enunciado caso seja necessário. Um exemplo de código nesse formato para o problema da semana 29:
Mas onde está a main? Onde está essa função que eu chamo para fazer a pergunta? Ambas estão na parte do código do juiz. Na hora de testar seu algoritmo, o seu código e o código do juiz serão rodados juntos, como se fossem um código só. Portanto, uma função de um dos códigos pode interagir (chamar e receber o valor retornado) com uma função do outro. A função main está no código do juiz e ela que vai ler (na entrada padrão) qual o número secreto, chamar a função "int descobrir_numero()" e comparar se o número retornado é igual ao número secreto, para então falar se seu código está certo ou não.
Você não precisa se preocupar em como o código do juiz vai funcionar, mas em geral, a estrutura dele será assim:
Como rodar o código localmente
Na página do enunciado vai ter um arquivo .zip que vem com os arquivos necessários para o problema. Ao baixá-lo e extraí-lo para alguma pasta local, você verá todos os arquivos necessários
- O arquivo com a "base" do código que você usará para resolver o problema, que geralmente vai ser "nome_do_problema.cpp". Ele já vai vir com um exemplo de interação com o código do juiz e com as bibliotecas extras que devem ser incluídas. Basta apagar essa parte de exemplo e começar a escrever seu código ali dentro. Vale ressaltar que você pode declarar variáveis e funções globais (a não ser que o enunciado diga que não pode).
- O código do juiz, que será rodado junto com o seu código, que geralmente vai ser "grader.cpp". Ele virá pronto, com a main e todas as funções que seu código vai chamar, além de chamar a função do seu código - portanto, você não deve modificar esse código.
- Além dos dois citados a cima, vão existir outros arquivos necessários para que ambos rodem juntos. Como alguns com final ".h" que são as bibliotecas incluídas no seu código, não precisa se preocupar nem modificar esses arquivos. Dependendo do problema, a entrada (que o código do juiz vai ler) pode ser através de um arquivo ou da entrada/saída padrão, se for por um arquivo, basta modificá-lo com a entrada desejada.
Depois que terminarmos o código, a maneira de testarmos a solução vai depender do sistema operacional que usamos:
Linux
Primeiramente, abrimos o terminal na pasta com os arquivos, para fazer isso, basta ir até a página da pasta desejada no gerenciador de arquivos, clicar nos 3 pontinhos lá em cima e então em "Open in terminal". Para compilar o código, devemos digitar "g++ -o nome_do_problema nome_do_problema.cpp grader.cpp" e aperte Enter (se o nome do arquivo do seu código não for o nome do problema, coloque o nome do arquivo do seu código no lugar). Para executar o código, digite "./nome_do_problema" e Enter. Se a entrada não for por arquivo, basta digitar a entrada e pronto. Clicando com a seta para cima no terminal você consegue acessar os últimos comando que usou, então não precisa ficar reescrevendo o tempo todo.
Para treinar, recomendo que tente fazer os problemas Memory e Cluedo, ambos da IOI 2010. São problemas mais fáceis que o comum na IOI, porque a de 2010 teve 4 problemas ao invés de 3.
Na pasta desses problemas, existiram mais arquivos que o normal, mas isso é porque nessa época a IOI aceitava várias linguagens de programação, então tem os graders e códigos bases para todas. Aqui você só precisa se preocupar com as ".cpp", então, se preferir, pode apagar os arquivos terminados em ".c" e ".pas", mas cuidado para não apagar os ".h" e "grader.in.1".