Dona Fernanda resolveu casar-se com Carlos, o padre porém disse que os noivos não poderiam escolher a data de casamento devido a grande quantidade de solicitações na igreja. Vários noivos também estavam ansiosos para saber quando poderiam se casar naquela linda igreja, para dizer a cada casal o dia exato em que eles poderiam se casar o padre solicitou que eles fornecessem de 1 até 5 dias no mês de sua preferência e desenvolveu um algoritmo que ajudaria a resolver este impasse de forma aleatória e justa agora e no futuro, ele definiu:

  • T - quantidade de casamentos na fila
  • M - mês do casamento
  • N - quantidade de dias do mês disponível
  • Vx - Valor do dia na posição X (V1, V2, V3…)

ENTRADA VÁLIDA

TN
V1 V2 V3 … Vx
M

Cada linha corresponde a uma entrada do casal, então se T for igual 10, existiriam 10 casais para casar na igreja em determinado mês, e por consequência, haveriam 10 linhas de entrada informando os dias preferidos do casal.

POR EXEMPLO

5
5 2 7 5 8 14
5 2 4 14 8 15
1 4
0
3 2 7 9
2

RESTRIÇÕES

T > 0 && T <= 20

M > 0 && M <= 12

N > 0 && N <= 5

V > 0 && V < 32

  • O dia a ser escolhido deve ser o menor do grupo
  • Caso um casal tenha selecionado um dia já escolhido por outro ele ficará com o próximo dia possível, se houver (por exemplo, A = 4 = { 1, 3, 4, 6 } se os dias 1, 3 e 4 já tiverem sido escolhidos, o casal poderá tentar o próximo item, o quarto número, o dia 6), mas precisa ser sempre o menor número do grupo.
  • Em caso de não haver outro dia disponível para o casal deverá ser escrito:
    • “O casal número N só pode casar no próximo mês pois já tem um casal nos dias selecionados”
  • Em caso de violação de restrição deverá ser escrito
    • “Padre, foi encontrado uma inconsistência nos dados.”

RESPOSTA VÁLIDA / SAÍDA VÁLIDA

Padre, são 5 Casamentos em Fevereiro
O casal número 1 ficou de casar no dia 2 de Fevereiro
O casal número 2 ficou de casar no dia 4 de Fevereiro
O casal número 3 só pode casar no próximo mês pois já tem um casal nos dias selecionados
Padre, foi encontrado uma inconsistência nos dados.
O casal número 5 ficou de casar no dia 7 de Fevereiro

EXPLICAÇÃO DA SAÍDA

“Padre, são 5 casamentos em Fevereiro”

é o número T de casamentos de entrada e o mês M da entrada

“O casal número 1 ficou de casar no dia 2 de Fevereiro”

é o primeiro casal que tem os dias N = {2, 7, 5, 8, 14} disponíveis e o menor possível é o dia 2 de Fevereiro

“O casal número 2 ficou de casar no dia 4 de Fevereiro”

é o segundo casal que tem os dias N = {2, 4, 14, 8, 15} disponíveise o menor possível é o dia 4 de Fevereiro

“O casal número 3 só pode casar no próximo mês pois já tem um casal nos dias selecionados”

é o terceiro casal que tem os dias N = {4} disponíveis mas como já existia um casal com o dia 4, não é possível realizar o casamento

“Padre, foi encontrado uma inconsistência nos dados do casal 4.  :(“

é a mensagem de erro em caso de violação de restrição

“O casal número 5 ficou de casar no dia 7 de Fevereiro”

é o quinto casal que tem os dias N = {2 7 9} disponíveis e o menor possível é o dia 7 de Fevereiro

MAIS TESTES PARA VALIDAÇÃO

Gerador de testes aleatórios válidos

bash$ ( T=$(( (RANDOM % 20) + 1 )); echo $T; \
for i in `seq 1 $T`; \
do N=$(( (RANDOM % 5) + 1 )) ; echo -n "$N "; \
for x in `seq 1 $N`; do V=$(( (RANDOM % 31) + 1)); echo -n "$V "; done; \
echo; done; echo $(( (RANDOM % 12) +1 )) )

Teste #01

5
5 21 26 4 1 15
5 19 11 7 16 17
1 28
4 29 6 21 25
1 115

Teste #02

3
3 28 26 7
2 29 16
3 8 14 15
4

Teste #03

5
3 17 31 16
1 15
1 7
4 31 30 12 1
2 20 27
3

Teste #04

18
1 21
3 23 24 5
5 15 11 19 28 8
5 11 9 16 16 5
1 4
1 4
4 4 8 7 26
4 23 12 11 28
1 7
2 28 27
3 27 13 31
3 30 29 11
5 2 5 10 20 14
5 4 16 5 17 25
2 3 20
2 17 2
5 19 21 2 24 25
5 16 8 18 23 28
5

Teste #05

11
5 7 19 30 2 22
3 8 23 30
5 25 4 16 17 31
3 18 31 14
3 6 3 19
2 20 1
2 27 22
2 16 19
4 9 28 18 21
2 10 20
2 29 9
7

Quer ver a minha versão com entradas e saídas funcionando?? http://pastebin.com/VvbxBZWD

Conseguiu resolver? Poste suas respostas nos comentários! Quer saber a solução? Entre em contato comigo ou procure na lista de Shell-Script a thread “Desafio Shell-Script #001 do Mulato” ;-)