Difference between revisions of "Problema do baile de casais"

Latest revision as of 03:25, 22 April 2009

Dificuldade única

Um organizador de um baile descobriu que as mulheres que iriam frequentar à festa eram bastante exigentes e conservadoras.

Cada uma delas só aceita dançar com um homem que seja no mínimo um ano mais velho que ela. Por exemplo, suponha Maria de 54 anos, ela só aceita dançar com João se ele no mínimo tiver 55 anos.

Para piorar sua situação o organizador descobriu que se uma mulher ficar sem par de dança, todas as outras se recusam a dançar.

Ele resolveu que precisava de um programa para verificar a lista de convidados e verificar se a festa iria ou não ser um sucesso. Sucesso representaria o fato de todas as mulheres terem par (mesmo que algum homem fique sem dançar), a fracasso significaria que alguma mulher ficou sem companheiro de dança.

Verificando a lista de convidados ele percebeu uma coisa bem interessante: todos os homens tinham sempre idades impares e as mulheres idades pares.

Faça um programa que, recebendo um número N de convidados (2<=N<=1000) e N idades I (18<=I<=100), seja capaz de informar se a festa será um sucesso (S) ou um fracasso (F).

Exemplo 1

Entrada

2
18 21

Saída

S

Exemplo 2

Entrada

2
21 22

Saída

F

Exemplo 3

Entrada

7
21 22 24 55 23 32 57

Saída

S

Possível solução: (22,23),(24,55),(32,57). O homem com idade de 21 ficará sem par, porém não há problema nisto.

Exemplo 4

Entrada

8
21 31 33 35 37 39 41 43

Saída

S

Explicação: Não há mulheres para ficarem desacompanhadas. Pela regra descrita a festa seria um sucesso.

Exemplo 5

Entrada

9
21 31 33 35 37 39 41 43 58

Saída

F

Explicação: A única mulher de 58 anos não dançará com nenhum homem da festa já que todos são mais jovens que ela.

Exemplo 6

Entrada

4
22 32 36 48

Saída

F