O João
trabalha num laboratório de microbiologia e está a preparar uma
experiência muito importante. A experiência consiste em analisar
uma placa que contém N bactérias em linha. O João sabe que
na sua placa há K tipos de bactérias diferentes, cada uma
com um nome mais complicado que a anterior, por isso para
simplificar vamos distingui-las pela sua cor.
Uma propriedade importante das bactérias que está a estudar é que têm tendencia a agrupar-se, ou seja, as bactérias da mesma cor estão todas juntas. Formalmente isto significa que todas as bactérias da mesma cor estão em posições seguidas. A figura seguinte mostra um exemplo de uma placa com N = 8 e K = 3.
Naturalmente, as bactérias não são visiveis a olho nu, o que significa que o João não faz ideia das cores das bactérias, apenas sabe o número total de bactérias N, mas é muito importante para a sua experiência que ele saiba quantos tipos de bactérias há (ou seja o valor K)!
Para descobrir o pretendido o João desenvolveu um método que lhe permite escolher quaisquer duas bactérias e determinar se têm a mesma cor ou não. Infelizmente este método demora muito tempo, por isso, o João precisa de uma estratégia para descobrir quantos tipos de bactérias existem na sua placa usando o seu método de comparação de bactérias no máximo Q vezes e por isso precisa da tua ajuda.
Dado o número de bactérias N na placa do João e um número máximo de comparações Q, descobrir quantos tipos de bactérias diferentes existem usando apenas o seu método de determinar se duas bactérias têm a mesma cor no máximo Q vezes.
Podes começar por descarregar os ficheiros correspondentes à tua linguagem (ou um arquivo zip contendo tudo):
| Linguagem | Ficheiro a implementar | Ficheiro com avaliador exemplo | Ficheiros auxiliares | Input para avaliador exemplo |
| C | resolver.c | avaliador.c | avaliador.h | input.txt |
| C++ | resolver.cpp | avaliador.cpp | ||
| Java | resolver.java | avaliador.java | ------ | |
| Pascal | resolver.pas | avaliador.pas | avaliadorlib.pas |
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 é possível efetuar 100.000 comparações em menos de 0.1 segundos.
Deves submeter um único ficheiro que implementa a
função resolver(N, Q), que recebe um inteiro N,
que representa o número total de bactérias e um
inteiro Q, que representa o número máximo de comparações
que podes fazer. Para isso deves usar o
ficheiro resolver.{c,cpp,java,pas} que descarregaste,
colocando no interior da função o teu código. Podes acrescentar
outras funções, mas devem ficar todas neste ficheiro que é o
único que deves submeter.
A função deverá retornar o valor de K, ou seja, o número total de tipos de bactérias diferentes.
Função a implementar:
| C/C++/Java: | int resolver(int N, int Q); |
| Pascal: | function resolver(N : Longint, Q : Longint): Longint; |
A tua função deve invocar a seguinte função:
comparar(p1, p2) implementada pelo avaliador, que
recebe dois inteiros que representam indíces de posições de
bactérias (devem ser entre 1 e N) e retorna um inteiro,
'1' se têm a mesma cor ou '0' caso contrário.
Nota que é importante que tanto p1 como p2 sejam entre 1 e N. Também é importante notar que se excederes as Q comparações o programa será interrompido e a resposta será considerada incorreta.
Funções do avaliador:
| C/C++/Java: | int comparar(int p1, int p2); |
| Pascal: | function comparar(p1 : Longint, p2 : Longint): Longint; |
avaliador.comparar(p1, p2).
A vossa função não deve ler nem escrever para os canais de entrada/saída padrão.
Imagina que estás a placa do João tem N = 8 bactérias e
tens Q = 8 perguntas disponíveis. A
função resolver que deves implementar será chamada
como resolver(8, 8).
Uma possível execução seria a seguinte (com a ordem das chamadas a ser de cima para baixo):
| Invocação | Resultado | Descrição |
| comparar(1, 3) | 1 | A primeira e terceira bactéria têm a mesma cor. |
| comparar(3, 4) | 0 | A terceira e quarta bactéria NÃO têm a mesma cor. |
| comparar(4, 7) | 1 | A quarta e sétima bactéria têm a mesma cor. |
| comparar(7, 8) | 0 | A sétima e oitava bactéria NÃO têm a mesma cor. |
| retornar 3 | Há 3 tipos de bactérias diferentes |
Para este exemplo a placa tinha o seguinte aspeto:
| 1 ≤ N ≤ 100 000 | Número de bactérias. | 1 ≤ K ≤ 100 | Número de tipos de bactérias. |
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:
| Grupo | Número de Pontos | Restrições adicionais |
|---|---|---|
| 1 | 5 | N ≤ 2 000, K ≤ 2, Q = 2 000 |
| 2 | 20 | N ≤ 2 000, Q = 2 000 |
| 3 | 25 | Q = 50 000 |
| 4 | 25 | Q = 3 000 |
| 5 | 25 | Q = 1 500 |
É 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 e um inteiro Q correspondendo, respetivamente, ao número de bactérias e ao número máximo de comparações possíveis. Segue-se uma linha com N inteiros entre 1 e N, separados por espaços, que representam as cores das bactérias na placa do João.
O avaliador irá automaticamente invocar a
função resolver(N,Q) por vocês implementada e
indicará se a resposta foi correta. Em caso afirmativo, também
indicará o número de comparações que foram efetuadas.
Disponibilizamos um ficheiro input.txt que contém um caso de teste exemplo.
Um exemplo de teste na tua máquina (supondo que tens os compiladores oficiais instalados) seria o seguinte:
| Linguagem | Compilar | Executar com o exemplo |
| C | gcc -Wall avaliador.c resolver.c | ./a.out < input.txt |
| C++ | g++ -Wall avaliador.cpp resolver.cpp | ./a.out < input.txt |
| Java | javac avaliador.java resolver.java | java avaliador < input.txt |
| Pascal | fpc avaliador.pas | ./avaliador < input.txt |