Editorial for COCI '14 Contest 6 #2 Niko
Submitting an official solution before solving the problem yourself is a bannable offence.
Let us denote the set of players that can only play defense by , the set of players that can only play midfield positions by
, and the set of players that can only play offense by
. Let us denote the set of players that can play both defense and offense by
. Analogously, we have
and
. Finally, let us denote the set of players that can play all three lines by
.
For a given formation -
-
, it is necessary to carefully come up with a layout of the players. We will obviously place the players from sets
,
and
on the lines they can play in. The problem arises when we don't have enough defensive players and need to decide whether to take players that can play both defense and midfield positions or those that can play both defense and offense.
As it usually is with programming, we don't need to make a decision, we can try out all possible combinations and see which one is best.
- Let
be the number of players from set
we will put into defense. Then
players from that set will go into offense.
- Let
be the number of players from set
we will put into midfield positions. Then
players from that set will go into offense.
- Let
be the number of players from set
we will put into offense. Then
players from that set will go into midfield positions.
Now we are missing only players in defense,
players in midfield positions and
players in offense. Therefore, the layout is possible only if
is larger than or equal to the sum of those three numbers.
Now it is enough to try all possible combinations for numbers ,
and
and output
DA
if a layout works out, and NE
if there isn't a possible layout.
Comments