Canadian Computing Competition: 2011 Stage 1, Senior #4
At the Canadian Cardiac Centre there are four types of blood available: O, A, B, and AB. Each of these types of blood has an Rh factor, which is either "positive" or "negative". There are many patients who each require unit of blood. Each patient's blood type determines the type of blood s/he may receive:
- Each Type O patient requires Type O blood.
- Each Type A patient may receive blood of Type A or Type O.
- Each Type B patient may receive blood of Type B or Type O.
- Each Type AB patient may receive blood of any type.
Patients who have Rh-negative blood can accept Rh-negative blood only, but patients with Rh-positive blood can accept either Rh-positive or Rh-negative types of blood.
We want as many patients as possible to receive a unit of blood. What is the maximum number of patients that can receive blood?
The first line of input contains integers: the number of units of blood of Type O negative, O positive, A negative, A positive, B negative, B positive, AB negative and AB positive. This is followed by a line containing eight numbers: the number of patients whose blood type is O negative, O positive, A negative, A positive, B negative, B positive, and AB negative and AB positive. Each of these integers will be at least and less than .
The output of your program should be a single number: the maximum number of patients that can receive blood.
5 5 3 1 2 11 5 12 2 4 9 2 3 9 7 3
Explanation for Sample Output
- 2 Type O- patients receive Type O- blood
- 4 Type O+ patients receive Type O+ blood
- 3 Type A- patients receive Type A- blood
- 3 Type A- patients receive Type O- blood
- 1 Type A+ patient receives Type A+ blood
- 1 Type A+ patient receives Type O+ blood
- 2 Type B- patients receive Type B- blood
- 9 Type B+ patients receive Type B+ blood
- 5 Type AB- patients receive Type AB- blood
- 3 Type AB+ patients receive Type AB+ blood
Can an editorial be opened for this problem?
The intended solution is any maximum flow algorithm.
Since the data were weak, the original data ( test cases) were grouped in a subtask worth marks and new, stronger data ( test cases) were added in a subtask worth another marks.