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

Bem-vindo à Prova de Qualificação das Olimpíadas Nacionais de Informática 2021. Esta prova irá decorrer desde as 12:00 do dia 30 de Abril até às 18:00 do dia 2 de Maio. 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.

Os melhores concorrentes da fase de qualificação, até um máximo de 30, participarão na final nacional. Iremos aceitar um máximo de 20 alunos do 12º ano e um máximo de 25 alunos do 11º e 12º, promovendo a participação de alunos que ainda tenham mais anos de ONIs pela frente.

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.

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. O mesmo se aplica ao Discord, não devem discutir nada sobre a prova até estar terminada (depois das 18:00 de dia 2).

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 pode ter ou não o mesmo formato, isto está especificado em cada enunciado. 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 terá 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