As aulas
de físico-química são um excelente momento para aprender sobre
como funciona o nosso mundo. Infelizmente, o Rafael, que costuma
ser um aluno muito atento, tem passado mais tempo a resolver
problemas de programação do que a prestar atenção às aulas.
Agora ele tem um grande problema, visto que tem uma experiência para fazer como trabalho de casa, mas ele não sabe como! O Rafael conseguiu obter algumas notas de uns colegas e do que percebeu do enunciado o trabalho é o seguinte:
A professora preparou N tubos de ensaio, colocados em linha, contendo uma solução aquosa de mefite. Mefite é uma substância que é inerte e reage muito pouco. Em I dos tubos, porém, a professora colocou pontite, uma substância mais rara e muito reativa. O objetivo do trabalho de casa é identificar quais os tubos de ensaio contêm pontite.
Para tal o Rafael lembrou-se que na sala há um frasco com várias tiras de catracite, uma substância que reage muito com pontite, mas não reage com mefite. Assim, ele decidiu fazer o seguinte: pegar em T tiras; mergulhar cada tira num conjunto de tubos de ensaio; esperar uma hora. Depois de uma hora, as tiras que estiveram em contacto com pelo menos um tubo de ensaio com pontite reagem e mudam de cor, enquanto que as restantes ficam na mesma.
A tua tarefa será ajudar o Rafael, escolhendo em que tubos de ensaio mergulhar cada tira e depois usar o resultado das reações após uma hora para determinar quais contêm pontite.
Na primeira parte do trabalho de casa do Rafael, ele sabe que I = 1, ou seja, há apenas um tubo de ensaio com pontite.
Na segunda parte do trabalho de casa do Rafael, ele sabe que I = 2, ou seja, há exatamente dois tubo de ensaio com pontite.
Dado um número de tubos de ensaio N, sendo que I deles contêm pontite, descobrir quais os tubos com pontite usando T tiras.
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 | ------ |
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 menos de 0.1 segundos a descobrir o resultado das reações.
Deves submeter um único ficheiro que implementa as funções:
escolher(N, I, T, tiras), que recebe um
inteiro N, que representa o número de tubos de ensaio,
um inteiro I que representa o número de tubos com
pontite, um inteiro T que representa o número de tiras
e uma array bidimensional (T
por N) tiras que será preenchida com os tubos de
ensaio em que mergulhar cada tira;
decidir(tiras), que recebe um um array (de
dimensão T) tiras que contém o resultado das
reações para cada tira;
Para isso deves usar o ficheiro resolver.{c,cpp,java} 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:
| C/C++: | void escolher(int N, int I, int T, int tiras[MAXT][MAXN]); |
| Java: | void escolher(int N, int I, int T, int[][] tiras); |
| C/C++: | int decidir(int tiras[MAXT]); |
| Java: | int decidir(int[] tiras); |
escolher tem dimensão T
por N e a array tiras da
função decidir tem dimensão T.
O teu objetivo é descobrir quais os tubos que contêm
pontite. Para tal, na função escolher deves
preencher para cada tira, quais os tubos de ensaio para a
mergulhar. Usem o valor 0 para representar um tubo de ensaio não
mergulhado e 1 para representar um tubo de ensaio
mergulhado. Por exemplo, se tiras[0][4] = 1, então
vamos mergulhar a tira 0 no tubo de ensaio
4. Se tiras[4][3] = 0, então não mergulhamos a tira
4 no tubo de ensaio 3. NOTA: tanto as tiras como os tubos
de ensaio começam no índice 0 e vão até T - 1 e N
- 1, respetivamente.
Podem mergulhar cada tira nos tubos de ensaio que quiserem, mas não podem preencher a array tiras em posições fora de T por N.
A array tiras da função decidir
contém o resultado da reação para a experiência detalhada pelo
resultado da função escolher. Uma posição
nesta array é 0 se a tira correspondente não reagiu e 1
se reagiu. Por exemplo, se tiras[3] = 1, então a
tira número 3 foi mergulhada em pelo menos um tubo de ensaio com
pontite. NOTA: também as tiras começam no índice 0 e vão
até T - 1.
A vossa resposta é o valor devolvido pela função decidir. Para devolverem a resposta temos dois casos:
A vossa função não deve ler nem escrever para os canais de entrada/saída padrão.
Imagina que há N = 6 tubos de ensaio, apenas I = 1
com pontite e o Rafael recolheu T = 3 tiras. A
função escolher que deves implementar será chamada
como escolher(6, 1, 3, {}).
Suponhamos que queremos mergulhar a primeira tira nos tubos 0, 1, 2, a segunda tira no tubo 3 e a terceira nos tubos 4 e 5. Então preenchemos a array tiras com os seguintes valores:
tiras[0] = {111000};
tiras[1] = {000100};
tiras[2] = {000011};
Se apenas o tubo número 3 contivesse pontite, então a
função decidir que deves implementar seria chamada
como decidir({010}), pois apenas a tira 1 foi
mergulhada no tubo de ensaio 3. Para devolver a resposta correta
neste caso, devolveríamos 3 na função decidir.
| 1 ≤ N ≤ 1 000 | Número de tubos de ensaio. | 1 ≤ I ≤ 2 | Número de tubos com pontite. | 1 ≤ T ≤ N | Número de tiras. |
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 = 10, T = 10, I = 1 |
| 2 | 10 | N = 1000, T = 520, I = 1 |
| 3 | 10 | N = 1000, T = 50, I = 1 |
| 4 | 20 | N = 1000, T = 15, I = 1 |
| 5 | 5 | N = 1000, T = 999, I = 2 |
| 6 | 20 | N = 1000, T = 450, I = 2 |
| 7 | 30 | N = 1000, T = 120, I = 2 |
É disponibilizado um avaliador exemplo em cada linguagem (avaliador.{c,cpp,java}) que pode ser utilizado para testar a vossa submissão. Para C/C++ está ainda disponível um ficheiro auxiliar avaliador.h. 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 I e um inteiro T correspondendo, respetivamente, ao número de tubos de ensaio, ao número de tubos com pontite e ao número de tiras. Segue-se uma linha com I inteiros distintos, que correspondem aos tubos com pontite.
O avaliador irá automaticamente invocar a
função escolher(N, I, T, {}) por vocês
implementada. Quando esta função retornar, o avaliador chama a
função decidir({}) por vocês implementada,
colocando na array tiras o resultado das
reações. O avaliador finalmente compara o valor retornado pela
função decidir e indica se está correto. Caso não
esteja, o avaliador imprime ainda a resposta dada pelo programa.
Disponibilizamos um ficheiro input.txt que contém o caso de exemplo referido a cima.
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 -lm | ./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 |