October 13th, 2006, 04:33 AM
Join Date: Aug 2006
Time spent in forums: 3 Days 3 h 25 m 24 sec
Reputation Power: 13
"Sousta Dance" Problem
Hi to all,
I'm working on a "project"(not really a project, but a task from the B
nformatics 2006) and I'm stuck in a part. Here's what the test says:
Sousta is a popular Cypriot folk dance where men and women gracefully dance together in couples in rows across from each other to express the joy of life and love. In order to make up a folk group in Larnaka they gather N men dancers and N women dancers. They ask them to select their partner. Usually men ask the most beautiful woman, whereas women the most handsome man. The chief choreographer asks each male dancer to rank in order of preference all the female dancers (1st choice, 2nd choice and so on…). He also asks female dancers to do the same for their partners. Subsequently, he tries to do the pairings by giving priority to the satisfaction of the preferences of male dancers. However, he understands that he cannot always satisfy them all. Thus, he devises a compromising solution where a person (male or female) may not be paired to his/her 1st choice, however, for all the couples (mi,wj) and (mp,wk) of his compromising solution, at least one of two following conditions hold:
a) mi prefers wj more than wk, or
b) wk prefers mp more than mi.
Luckily, for the given preferences of both male and female dancers only one such pairing solution exists.
Your program should read the standard input. The first line of the input contains an integer N ( ) representing the number of couples. Each of the next N lines contains N integers in the range [1,N]. These lines, containing N elements each, form a matrix, the columns of which depict the preferences of women for men (see example below). Each of the next N lines contains N integers in the range [1,N], which depict the preferences of men for women. For these N lines each column represents the female’s number (i.e. column 1 represents female 1, etc.) and the values represent the preferences for that particular female.
Your program should write on the standard output N lines. Each ith line of these N lines contains the pair of the ith man and the woman selected for him by the algorithm.
2 1 2 1
1 2 1 2
3 4 4 3
4 3 3 4
1 3 4 2
4 1 2 3
4 2 3 1
4 2 1 3
The ones in blue are the 1st woman's preferences -- they go the same way for the others
The ones in read are the 1st man's preferences -- they go the same way for the others
So, man number one has the first woman as his first preference, the second woman as his third preference, the third woman as his fourth preference and the fourth woman as his second preference.
Well, from all what I've done so far is: I've read both the males' and females' preferences. I've checked them so they're not the same! Now, I can't find I way to check the two conditions(they are in bold). If you can, I'd like from you not to write the whole code and write it for me but tell me how(in real life I know -- you know if they put me and not the computer I could do it) to do it in code!!
Thanks in advance!!