Problema B
Case antes que seja coisa de ricos...
Este exercı́cios debruça-se sobre um problema algorı́tmico clássico, o problema dos casamentos
estáveis. Mais uma vez espera-se que defina uma resolução, eventualmente recursiva, concisa e
elegante.
Problem
Foi contratado por uma agência casamenteira que pretende ter uma solução informática que ajude
em trazer felicidade a almas solitárias num paı́s que tanto precisa. Como tal a solução deverá
conseguir propor a cada cliente a sua alma gêmea...”até que a morte os separe”.
Os dados do problemas são os seguintes: Considere um conjunto de n homens e um conjunto
de n mulheres desejosos em quebrar a maldição da solidão.
Neste exercı́cios vamos propor que os homens e as mulheres se identificam por um número
entre 1 e n.
Assim a agência forneceu a cada um deles a lista dos ou das pretendentes assim como um
descriptivo de cada um. A seguir, pediu a cada um dos senhores e a cada uma das senhoras que
fornecesse a lista das suas preferências:
• Cada homem lista todas as mulheres por ordem decrescente das suas preferências para casamento.
• Cada mulher lista todas os homens por ordem decrescente das suas preferências para casamento.
A solução deverá ser capaz de encontrar e propor um conjunto de casamentos tais que estes
sejam todos estáveis.
Os casamentos são instáveis se existe um homem e uma mulher que se preferem mais entre eles
do que aos seus atribuı́dos esposos.
Input
Na primeira linha encontra-se o valor inteiro n, número total de homens e de mulheres.
Nas n linhas seguintes encontram-se as listas de preferências dos solteiros: n valores inteiros
por linha. Por exemplo se na primeira desta linha encontramos 2 1 3, isto significa que o homem
no . 1 prefere a segunda mulher, depois a primeira e depois a terceira.
De forma semelhante, nas n linhas restantes são apresentadas, linha a linha (da primeira mulher
à última mulher) as preferências de cada uma delas.
Output
O resultado consiste em n linhas.
Na primeira linha encontra-se um valor n1 que corresponde ao idenficador da mulher com quem
o primeiro homem se deve casar.
Na segunda linha encontra-se um valor n2 que corresponde ao idenficador da mulher com quem
o segundo homem se deve casar.
etc.
Constraints
n ∈ {1 . . . 100}
1
Sample Input
4
1
3
4
3
2
4
1
2
3
4
2
2
1
1
3
3
2
1
3
1
3
2
2
1
4
2
1
4
4
3
4
4
Sample Output
1
3
4
2
2