2011 Canadian Computing Competition, Stage 1

Problem S4: Blood Distribution

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 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.
  • The Type AB patients may receive blood of any type.

Patients who have Rh-negative blood can accept Rh-negative blood only, but patients with Rhpositive 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 Format

The first line of input contains 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 and less than 107.

Output Format

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

33

Explanation

  • 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 0- blood
  • 1 Type A+ patients receive Type A+ blood
  • 1 Type A+ patients receive Type O+ blood
  • 2 Type B- patients receive Type B- blood
  • 9 Type B+ patients receive Type B+ blood
  • 5 Type AB- patient receives Type AB- blood
  • 3 Type AB+ patients receive Type AB+ blood

Note: At least 30% of the test cases for this problem will have at most 1000 units of each type of blood.

All Submissions
Best Solutions


Point Value: 7
Time Limit: 2.00s
Memory Limit: 16M
Added: Mar 01, 2011

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

I'm getting wa on two cases and I've looked through my code, and I can't see what's wrong with it, could someone help?

You only have one case WA now, so gj on finding your other error. You're overestimating the number of treated patients. Unfortunately this problem is kind of tedious to debug, so I can't quite pinpoint where your error is, but hopefully that should be enough to go off of. :-)

I tried condensing the code down to a for loop in the hopes that it would be easier to debug for me, but I still have the same problem. Is this a problem with my algorithm and not just a typo?

Okay, I see your error. Carefully re-read the section on which patients can receive which types of blood.

I tried putting in a fix, but now case 1 is getting wa. This is frustrating :/