Problema D - Fragmentos de ADN

Durante uma escavação arqueológica foram descobertos restos de animais com milhões de anos. Como em todos os organismos vivos, o seu ADN era constituído por sequências de nucleótidos. Nos organismos atuais existem quatro diferentes tipos de nucleótidos dependendo da base azotada (citosina, adenina, guanina e timina) mas nestes animais antigos que foram encontrados o número de diferentes tipos de nucleótidos pode ser outro.

Uma unidade especial foi destacada para analisar os fragmentos encontrados. Dada uma molécula de ADN de tamanho N, ou seja com N nucleótidos, o que se pretende é descobrir a quantidade K de diferentes nucleótidos existentes nessa molécula, bem como em que posições ficam os nucleótidos idênticos. Para codificar uma molécula os cientistas querem usar uma sequência de inteiros positivos a₁, a₂, ..., a_N (1 ≤ a_i ≤ K) tal que se um mesmo número aparecer em duas posições, isso significa que o mesmo nucleótido pode ser encontrado em ambas as posições.

Para examinar uma molécula, os cientistas têm disponível uma máquina que permite analisar todos os nucléotidos entre as posições i e j (inclusive), determinando o número de diferentes nucleótidos aí encontrados. Contudo, a molécula é muito frágil e não é possivel fazer mais do que P perguntas com a máquina antes que a molécula se desfaça.

O Problema

Dado o tamanho N de uma molécula, a tua tarefa é descobrir uma sequência de inteiros que codifique a molécula como atrás descrito. Para o fazer tens de usar um máximo de P operações analisar(i,j) que indicam cada uma a quantidade de diferentes nucleótidos entre as posições i e j.

Ficheiros para Download

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

Implementação

Deves submeter um único ficheiro que implementa a função resolver(N), que recebe um inteiro (N, o tamanho da molécula) e descobre uma codificação válida da molécula. Para isso deves usar o ficheiro resolver.{c,cpp,java} que descarregaste, colocando no interior da função o teu código. Podes acrescentar outras funções e declarações de variáveis, mas devem ficar todas neste ficheiro que é o único que deves submeter.

Função a implementar:

C/C++/Java:

void resolver(int N);

A tua função deve invocar a função analisar(i, j) implementada pelo avaliador, que devolve um inteiro q indicando a quantidade de diferentes nucleótidos entre as posições i e j.

Função do avaliador para fazer uma análise entre as posições i e j:

C/C++/Java:

int analisar(int i, int j);

O teu objetivo é não usar mais do que P vezes a função analisar(i, j) para descobrir como codificar a sequência. Nota que o teu programa não saberá qual o valor de P para o caso de teste em questão, mas é garantido que é possível descobrir uma codificação da sequência usando essas P análises. O programa será abortado caso a função seja invocada mais do que P vezes.

Depois de calculada a codificação, o teu programa deve invocar a função resposta(i) exatamente N vezes para descrever a codificação encontrada. Os números com que a função é chamada correspondem à codificação, da primeira posição para a última. Por exemplo, se a codificação for [1,2,1,3], deveria ser feita a sequência de chamadas resposta(1), resposta(2), resposta(1) e resposta(3).

Função do avaliador para indicar a codificação obtida:

C/C++/Java:

void resposta(int i);

O teu programa não deve ler nem escrever para os canais de entrada/saída padrão.

Exemplo

Imagina que o tamanho da sequência é 3. A função que deves implementar será chamada com resolver(3). Uma possível execução seria a seguinte (com a ordem das chamadas a ser de cima para baixo):

Estas chamadas são suficientes para codificar o ADN. A primeira chamada diz-nos que os dois primeiros nucleótidos são iguais e a segunda chamada mostra que o terceiro nucleótido é diferente dos dois anteriores. Descobrimos então que uma codificação válida é [1,1,2], sendo que a podemos indicar com as 3 chamadas à função resposta. Nota que a codificação [2,2,1] também seria válida.

Restrições

Os casos de teste deste problema estão organizados em 5 grupos com restrições adicionais diferentes:

Avaliação e Casos de Teste

Um caso de teste consiste em várias invocações da função resolver(N) para diferentes moléculas (potencialmente com tamanhos diferentes), pelo que deve inicializar quaisquer estruturas de dados que queira utilizar. A função deve codificar corretamente todas as moléculas dadas para uma pontuação ser atribuída nesse caso de teste. No máximo cada caso de teste terá 10 chamadas à função resolver.

Testes no vosso computador

É disponibilizado um avaliador exemplo em cada linguagem (avaliador.{c,cpp,java}) que pode ser utilizado para testar a vossa submissão. Este avaliador não corresponde ao utilizado pelo sistema de avaliação.

O avaliador exemplo começa por receber como input dois números: M (indicando o número de moléculas a considerar) e P (o máximo de vezes que se pode chamar a função analisar em cada molécula). Seguem-se M linhas, uma por molécula, contendo N (o tamanho) seguida de N inteiros entre 1 e N indicando uma codificação da molécula em questão.

O avaliador irá automaticamente invocar a função resolver(N) por ti implementada e indicará se a resposta foi correta. Em caso afirmativo, também indicará o número de vezes que a função analisar(i, j) foi invocada.

Disponibilizamos um ficheiro input.txt que pode ser usado para testar todas as moléculas possíveis com tamanhos entre 1 e 3 (sendo que podem acrescentar linhas se quiserem testar outros casos).

Um exemplo de teste na tua máquina seria o seguinte:

O output deve mostrar em que casos acertaram.