4th Balkan Olympiad in Informatics
Nicosia, Cyprus, 19-25 October 1997
Day 1 - Problem 1 (Compatible fishes)
If you want to create an aquarium with exotic fish you must take the advise of an expert
in order to avoid a situation in which a certain type of fish can not coexist and live
together with another fish type. The reason is the "incompatibility" among fish
Given the number of fish types and the available amount of money for spending, find the
maximum number of fish types. For this number of fish types find the maximum amount of
money that can be spent, provided that only one fish per type is used.
INPUT DATA (file INPUT.TXT) The program reads input lines from the file INPUT.TXT as
- on the first line two integers, separated by a space are given. The first number
represents the maximum available amount of money M (M<=1000) for investment and the
second one represents the different number of fish types F (F<=30) available.
- on F subsequent lines, the identification number of each fish type and the corresponding
cost separated by a space, are given.
- on subsequent lines until the end of file, the file contains pairs of fish types,
separated by space, that represent the incompatibilities among the different fish types
(those fish combinations that can not live or coexist together) the end of file is
indicated by a line that contains two zeros separated by a single space (0 0).
OUTPUT DATA (file OUTPUT.TXT) Output is written in the file OUTPUT.TXT as follows:
- on the first line, two integers separated by space, that represent the maximum number of
fish types that can live in the aquarium and the maximum amount of money that can be
spent, for this number of fish types.
- on subsequent lines, the identification numbers of the fish types that can live in the
aquarium are given.
In the case of many solutions to the problem, only one is required to be listed.
Time-limit for each test: 5 seconds. Maximal score: 30 points