Problema D - Previsão meteorológica

A Associação Nacional de Meteorologia (ANM) emprega vários engenheiros que são responsáveis por variadas tarefas. Uma das tarefas algorítmicas mais comuns é prever um valor, dado um conjunto de dados relevantes. Neste sentido, a ANM está à procura de alguém para os ajudar a desenvolver o próximo sistema de previsão de chuva, e estão a considerar-te a ti.

Em qualquer zona, a ANM tem N sensores de diferentes tipos espalhados pela região. Baseado nos dados dos sensores, o teu objetivo será prever se irá chover numa determinada região ou não, em cada dia, ao longo de T dias. Esta tarefa está divida em duas situações que deves resolver:

Parte I

Em cada um dos T dias, cada um dos N sensores prevê, baseado em certos dados que recolhe, se choverá ou não no dia seguinte. Adicionalmente, a ANM sabe que pelo menos um dos sensores dá sempre a previsão correta (o mesmo sensor todos os dias), ou seja, consegue sempre prever se choverá ou não, mas a ANM desconhece qual é.

Para cada dia irás receber a previsão de cada sensor, ou seja, ser-te-á dito que para o dia i, o sensor j tem uma previsão se irá chover ou não. Baseado nesta informação, deves fazer a tua previsão se irá chover ou não no dia i. De seguida, irás receber a observação real, ou seja, se realmente choveu ou não no dia i. O processo repete-se então para cada um dos T dias.

A ANM é muito exigente, ou seja, quer que as suas previsões sejam o mais corretas possíveis. Assim, o teu trabalho será bem sucedido se o número de previsões incorretas que fizeres for, no máximo, Q (cujo valor é dado na secção de restrições).

Para desempenhares este trabalho, deverás escrever um programa que irá receber informações como especificado nos parágrafos anteriores e fazer uma previsão. O formato deste programa está explicado abaixo, na secção "Implementação".

Parte II

A segunda parte da tua tarefa é muito semelhante à da primeira parte, mas com uma pequena diferença. Infelizmente, para algumas zonas, os sensores da ANM não são tão precisos, por isso, não há nenhum que acerta sempre na sua previsão. Ainda assim, a ANM sabe que pelo menos um dos sensores tem uma previsão correta pelo menos 99% das vezes (o mesmo sensor todos os dias), ou seja, existe um sensor que dá previsões erradas no máximo em 1% dos dias. Por exemplo, se T = 5000, o sensor erra no máximo 50 vezes. Novamente, a ANM desconhece qual sensor é.

O Problema

Dado o número de sensores N numa determinada zona, um número de dias T a prever e uma situação S (que indica a que parte do problema se refere), prever se irá chover em cada dia, ao longo dos T dias, através das previsões dos N sensores, errando no máximo Q vezes.

Ficheiros para Download

Podes começar por descarregar os ficheiros correspondentes à tua linguagem (ou um arquivo zip contendo tudo):

Nota que a implementação do avaliador a usar nos testes oficiais será diferente, mas podes esperar o mesmo comportamento. Além disso, é garantido que o avaliador demora no máximo 0.1 segundos a fornecer as previsões dos sensores.

Implementação

Deves submeter um único ficheiro que implementa duas funções:

• A função iniciar(N, T, S), que recebe um inteiro N, que representa o número de sensores, um inteiro T, que representa o número de dias a prever, e um inteiro S, que será 1 ou 2 para referir a que parte do problema este caso de teste considera.
• A função prever(previsoes, A), que recebe uma array/vetor de inteiros previsoes, que representa a previsão de cada sensor e que será 1 para representar uma previsão de chuva, e 0 caso contrário, e um inteiro A, que representa o valor real de chuva no dia anterior, ou seja, será 1 se no dia anterior choveu e 0 caso contrário. Esta função deve devolver um inteiro, 0 ou 1, que representa a tua previsão para o dia atual, baseado nas previsões dos sensores.

Nota que na primeira chamada da função prever(previsoes, A) o valor de A será -1, pois ainda não houve um dia anterior para observar. Para mais informação sobre como implementar estas funções, vê o exemplo.

Nota que a array previsoes é consistente, ou seja, ao longo de cada dia a posição i desta array refere-se à previsão do sensor i. Por exemplo, se para um caso de teste relativo à parte I acontecer que o sensor 6 for o sensor cuja previsão está sempre correta, a posição 6 da array indica sempre a previsão real.

Para isso deves usar o ficheiro resolver.{c,cpp,java,pas} que descarregaste, colocando no interior das funções o teu código. Podes acrescentar outras funções, mas devem ficar todas neste ficheiro que é o único que deves submeter.

Funções a implementar:

Nota que é importante que a função prever(previsoes, A) devolva um inteiro 0 ou 1, caso contrário a resposta será considerada incorreta.

A vossa função não deve ler nem escrever para os canais de entrada/saída padrão.

Exemplo

Imagina que há N=5 sensores e que se pretende prever se chove ou não ao longe de T=3 dias. Supõe ainda que estamos perante a situação da Parte S=1.

Uma possível execução seria a seguinte (com a ordem das chamadas a ser de cima para baixo):

Neste exemplo específico o sensor 3 estava sempre correto, tendo chovido no 1º e 3º dia. Assim, acertamos a previsão no dia 2 e 3, ou seja, apenas erramos uma previsão. Se Q for maior ou igual a 1 então esta execução teria tido sucesso.

Restrições

Os valores de Q, o número máximo de previsões erradas, são dados na secção seguinte, assim como os valores de S, a parte do problema.

Avaliação e Casos de Teste

Os casos de teste deste problema estarão agrupados em conjuntos de testes. Ao contrário dos restantes problemas, para obter pontuação é necessário acertar todos os casos de teste de um grupo de casos, nesse caso terão a pontuação completa relativa a esse grupo. Se falharem um ou mais casos de um grupo, a pontuação atribuída relativa a esse grupo será nula.

Cada grupo tem um número de pontos associado e um conjunto de restrições adicionais. Os grupos são os seguintes:

Testes no vosso computador

É disponibilizado um avaliador exemplo em cada linguagem (avaliador.{c,cpp,java,pas}) que pode ser utilizado para testar a vossa submissão. Para C/C++/Pascal está ainda disponível um ficheiro auxiliar (para C/C++ o avaliador.h e para Pascal o avaliadorlib.pas). Este avaliador não corresponde ao utilizado pelo sistema de avaliação.

Este avaliador começa por receber como input um inteiro N, um inteiro T, um inteiro S e um inteiro Q, correspondendo, respetivamente, ao número de sensores, ao número de dias, à parte do problema (1 ou 2) e ao número máximo de previsões erradas. Seguem-se T linhas, uma para cada dia j, cada uma com N inteiros 0 ou 1, separados por espaço, um para cada sensor i, sendo o i-ésimo inteiro da j-ésima linha 1 se o sensor i prevê que vai chover no dia j, e 0 caso contrário. Segue-se ainda uma linha com T inteiros 0 ou 1, separados por espaços, sendo que o j-ésimo desses inteiros é 1 se choveu no dia j, e 0 caso contrário.

O avaliador irá automaticamente invocar a função iniciar(N,T,S), por vocês implementada, uma vez, e invocará seguidamente a função prever(previsoes, A) T vezes, uma para cada dia. O avaliador indicará no final quantas previsões falharam e se a resposta é considerada correta ou não.

Disponibilizamos dois ficheiros:

• input.txt que contém o caso de exemplo referido acima.
• input_large.txt que contém um caso com N=96, T=4988, S=1 e Q=2600.

Estes dois testes serão corridos pelo Mooshak durante a Qualificação para garantir que o programa compila e funciona em testes simples, mas os testes finais que serão usados para atribuir a pontuação ao vosso programa serão diferentes.

Um exemplo de teste na tua máquina (supondo que tens os compiladores oficiais instalados) seria o seguinte: