CCC '11 S4 - Blood Distribution - Olympiads Online Judge

CCC '11 S4 - Blood Distribution

Points: 15 (partial)

Time limit: 1.0s

Memory limit: 256M

Problem types

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 $1$ ~1~ 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?

Input Specification

The first line of input contains $8$ ~8~ 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 $0$ ~0~ and less than $10^7$ ~10^7~.

Output Specification

The output of your program should be a single number: the maximum number of patients that can receive blood.

Sample Input

5 5 3 1 2 11 5 12
2 4 9 2 3 9 7 3

Sample Output

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

Comments

2

Jinx commented on Oct. 24, 2021, 9:24 p.m.

Can an editorial be opened for this problem?

3

d commented on Feb. 20, 2024, 4:16 a.m.

Done. https://dmoj.ca/problem/ccc11s4/editorial

3

Nils_Emmenegger commented on Oct. 24, 2021, 11:04 p.m.

The intended solution is any maximum flow algorithm.

7

maxcruickshanks commented on Sept. 11, 2021, 9:50 p.m.

Since the data were weak, the original data ( $5$ ~5~ test cases) were grouped in a subtask worth $50$ ~50~ marks and new, stronger data ( $100$ ~100~ test cases) were added in a subtask worth another $50$ ~50~ marks.