The Dining Diplomats
Diplomats from several countries are together for a summit. The banquet on the last day of the summit
is to be served at a big round table. The organisers need to _nalise a seating a
angement for the
diplomats.
Some pairs of diplomats are known to be friendly to each other, and some other pairs are known to be
foes of each other. Some diplomats are indi_erent to all the other diplomats. The organisers would like
to design a seating chart so that no two foes are seated next to each other, unless at least one of them is
also seated next to a friend, and the other is seated next to a friend or an indi_erent diplomat.
Write a C++ program that given the facts about friends, foes and indi_erent diplomats, generates a
seating a
angement, if any, that satis_es the above condition. If no such seating a
angement exists,
theprogram should output a suitable message.
Input
The input will have several lines of input. Each line may have two names and one integer (1 for friend,
and 0 for foe), or just one name for diplomats that are indi_erent to all the others. The string of
characters containing the name may contain non-letters; they should not be included in the name. Some
of the letters in the name may be in upper case. These, except the _rst letter, should be converted to
lower case. Names and numbers may be separated by one or more blank spaces (' '), and/or tab
characters ('nt'). On each line, there may be one or more blank spaces (' '), and/or tab characters ('nt')
efore the end of line character
('nn').
For example, consider the following input:
Jo4e Ma,ry 1
ElizaBet5h June 1
Joe John 0
Joe, JuNe 0
John JUne 1
Margaret
The above input indicates that there are 6 diplomats attending the summit: Joe, Mary, Elizabeth, June,
John, and Margaret. The friend pairs are Joe and Mary, Elizabeth and June and John and June. The foe
pairs are Joe and John, and Joe and June. Margaret is indi_erent to all the others.
You may assume that only those diplomats whose names are included in the input _le will be at the
summit.
If a pair of diplomats, say A and B, appear in the input, but do not appear as either a pair of friends, or
a pair of foes, you may assume that they are indi_erent to each other.
You may assume that the input _le is not contradictory, i.e., if two diplomats are listed as friends, then
they will not be listed as foes, nor will either of them be listed as being indi_erent. Similarly, if two
diplomats
are listed as foes, they will not be listed as friends, nor will either of them be listed as being indi_erent.
If diplomat A is listed as a friend (respectively, foe) of diplomat B, then this implies that B is a friend
(respectively, foe) of A.
Output
Your program should _rst output the names of all the diplomats at the summit in alphabetical order.
Then, your program should output a possible seating a
angement, if one exists. If no seating
a
angement is possible, then your program should print a suitable message.
For the above input, your program could output:
Diplomats: Elizabeth, Joe, John, June, Margaret, Mary.
Seating A
angement: Joe, Mary, Elizabeth, June, John, Margaret.
Note that, since the banquet is at a round table, Margaret is seated next to Joe.
Note that for a given input, there may be several possible seating a
angements. For example, for
the above input, another possible seating a
angement is:
Joe, John, June, Mary, Elizabeth, Margaret
In this case the two foes Joe and John are seated next to each other, but John has a friend in June also
seated next to him, and Joe has Margaret, an indi_erent diplomat, seated next to him.
If multiple seating a
angements exist, your program can output any one of these possible seating ar-
angements.
Programming Guidelines
1. You may assume that each name contains no more than 20 characters, and that, there are no more
than 50 diplomats attending the summit.
2. You may assume that the input is co
ect, i.e., you do not need to check for the validity of the input.
3. Your program should be well-structured using appropriate functions.
4. Your program should be well-commented using pre/post conditions for each function, and asser-
tions/comments as suitable.
5. Each function should not be any more than 60 lines (including pre/post and comments).
6. Your program should not use any magic numbers.
7. Your program should not use any li
aries other than iostream.
8. You program should not use any
eak, goto or continue statements.
9. Any function that needs to return a value should have exactly one return statement at the end of the
function.
10. If a function has a non-void return type, then it should not have any parameters passed by
eference.
11. Your program should be e_cient, i.e., not perform any unnecessary operations.