Prova de Qualificação - Olimpíadas Nacionais de Informática 2020

Bem-vindo à Prova de Qualificação das Olimpíadas Nacionais de Informática 2020. Esta prova irá decorrer desde as 12:00 do dia 23 de Abril até às 18:00 do dia 25 de Abril. Durante esse tempo poderão tentar resolver 4 problemas (enumerados de A a D) e submetê-los na plataforma Mooshak, cujas credenciais devem ter recebido por e-mail.

Cada problema vale 100 pontos, dos quais podem obter pontuações parciais por soluções que apenas resolvem parte do problema. A pontuação na qualificação será igual à soma de das vossas últimas submissões em cada problema. A pontuação oficial e final só é conhecida depois da da prova terminar.

Este ano temos algumas novidades nos problemas que vos apresentamos. Principalmente a pensar em que nunca participou antes, aqui estão algumas informações gerais:

• Como já foi dito, para verem os problemas e submeterem as vossas soluções, devem usar a plataforma Mooshak. Se nunca usaram o Mooshak têm acesso a um conjunto de instruções de como usar aqui.
• O servidor onde está a correr o Mooshak da prova é igual ao servidor que corre o mooshak da prova de treino. Isto quer dizer que devem esperar o mesmo comportamento (em termos de tempo de execução, uso de memória, etc) que nas provas de treino.
• Cada enunciado contém os nomes das variáveis relevantes ao problema a bold.
• Ao submeterem um programa no Mooshak, terão um resultado de 0 a 100, assim como informação sobre cada caso de teste (basta carregar no resultado da submissão). Esta pontuação não é a pontuação final, é apenas uma aproximação da vossa pontuação (mais informações sobre isto na secção de pré-teste). Notem que apenas a última submissão contará para a vossa pontuação final, por isso escolham bem. Adicionalmente, o Mooshak não permite submeterem o mesmo código duas vezes, por isso se quiserem resubmeter uma submissão anterior, podem adicionar um espaço no fim do programa (ou um comentário, algo que modifique o texto do código).
• Não podem usar no vosso código nenhuma diretiva que modifique as opções do compilador (ex: #pragma).
• Se forem utilizadores de Java, notem que a classe Scanner (para leitura de dados) é pouco eficiente. Como tal, disponibilizamos a classe FastScanner, cujo código está disponível aqui. Podem usar esta classe como usariam a classe Scanner e não têm de incluir o seu código na vossa submissão, o nosso compilador de java já inclui essa classe.
• O problema D é um problema interativo. Isto significa que em vez de submeterem um programa que lê da entrada padrão e escreve para a saída padrão, devem escrever um programa que implementa uma função especificada no enunciado. Se nunca resolveram um problema deste tipo, podem consultar um conjunto de instruções sobre o seu funcionamento aqui.

Se tiverem perguntas por favor utilizem o sistema de perguntas do Mooshak. Não coloquem qualquer tipo de código ou qualquer sugestão de solução, a vossa pergunta será vista por todos os concorrentes. Se não obedecerem a esta regra podem ser desqualificados.

Novidades

Partes de Problemas

Cada problema está dividido em várias partes. Cada parte está relacionada com a anterior, mas é um problema completamente diferente. Isto significa que na prática têm de resolver vários problemas relacionados num. Algumas coisas a saber sobre este assunto:

• O input de cada parte de um problema tem o mesmo formato. Todos os casos de teste começam com uma linha com um só inteiro que indica a que parte se refere esse caso de teste.
• Cada parte tem diferentes subtarefas e restrições possivelmente diferentes. Cada subtarefa indica que há um conjunto de casos de teste a valer um certo número de pontos que obedece a restrições extra (e é por isso mais fácil de resolver).
• As partes de um problema estão organizadas por ordem de dificuldade, ou seja, a Parte I é sempre mais fácil que a Parte II, que por sua vez é mais fácil que a Parte III. Isto não se aplica aos problemas, ou seja, por exemplo, o problema C não é necessariamente mais difícil que o problema A.

Pré-Testes

Contrariamente aos anos anteriores, quando submeterem um código no Mooshak da qualificação, terão como resultado um número de 0 a 100. Isto porque cada problema terá um caso de teste por subtarefa, a valer exatamente o número de pontos dessa subtarefa. Estes casos de teste não representam a vossa pontuação real, são apenas uma forma de pré-teste que vos permite avaliar se o código se está a comportar como esperado. Em particular, nenhum dos pré-testes contará para a pontuação final, esta terá um conjunto de testes distintos.

Cada pré-teste tará dimensões próximas das dimensões máximas da subtarefa correspondente, ou seja, o pré-teste de uma subtarefa onde uma váriavel de N é menor ou igual a 10⁴ será atribuído um valor de N muito próximo ou igual a 10⁴.

Nota importante: é muito importante sublinhar que a pontuação obtida nos pré-testes não influencia a vossa pontuação final. Ou seja, mesmo que tenham 100 pontos de pré-testes numa submissão de um problema, podem vir a ter 0 pontos se o vosso programa falhar todos os testes finais. Do mesmo modo, 0 pontos num pré-teste não significa que tenham 0 pontos nesse grupo de testes na classificação final.

Informação técnica

Linguagens de programação

Limites de tempo e memória

• Limite de memória global: 256MB
• Limite de memória de stack: 256MB
• Limite de tamanho de código fonte: 32KB