C/C++ Help
Forums: » Register « |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support | 
User Name:
Remember me

Go Back   Dev Articles Community ForumsProgrammingC/C++ Help

Add This Thread To:
  Del.icio.us   Digg   Google   Spurl   Blink   Furl   Simpy   Y! MyWeb 
Thread Tools Search this Thread Display Modes
Unread Dev Articles Community Forums Sponsor:
Old October 13th, 2006, 05:33 AM
costas costas is offline
Contributing User
Dev Articles Newbie (0 - 499 posts)
Join Date: Aug 2006
Posts: 407 costas User rank is Just a Lowly Private (1 - 20 Reputation Level) 
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 Balkan Olympiad In Informatics 2006) and I'm stuck in a part. Here's what the test says:
Problem: SoustaDance

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

1 1
2 2
3 4
4 3

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!!


Reply With Quote

Viewing: Dev Articles Community ForumsProgrammingC/C++ Help > "Sousta Dance" Problem

Developer Shed Advertisers and Affiliates

Thread Tools  Search this Thread 
Search this Thread:

Advanced Search
Display Modes  Rate This Thread 
Rate This Thread:

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
View Your Warnings | New Posts | Latest News | Latest Threads | Shoutbox
Forum Jump

Forums: » Register « |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support | 

Powered by: vBulletin Version 3.0.5
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.

© 2003-2018 by Developer Shed. All rights reserved. DS Cluster - Follow our Sitemap