Get Time

   Problem Statement  

 Problem Statement for KeyDungeonDiv1

Problem Statement

    You are exploring a dungeon. In the dungeon you found some locked doors. Each locked door has some red and some green keyholes (zero or more of each kind). In order to open a door, you must insert fitting keys into all its keyholes simultaneously. All the keys used to open a door break in the process of opening it and you have to throw them away. However, each door hides a small chamber that contains some new keys for you. Once you open the door, you may take all of those keys and possibly use them to open new doors. (Of course, it only makes sense to open each door at most once. If you open the same door again, there will be no new keys for you.)

There are three kinds of keys: red, green, and white ones. Each red key fits into any red keyhole. Each green key fits into any green keyhole. Each white key fits into any keyhole (both red and green ones).

You are given int[]s doorR, doorG, roomR, roomG, and roomW. These five int[]s all have the same length. For each valid i, the values at index i describe one of the doors you found: the door has doorR[i] red and doorG[i] green keyholes, and upon opening it you gain new keys: roomR[i] red ones, roomG[i] green ones, and roomW[i] white ones.

You are also given the int[] keys with three elements: keys[0] is the number of red keys, keys[1] the number of green keys, and keys[2] the number of white keys you have at the beginning.

Your goal is to have as many keys as possible at the moment when you decide to stop opening doors. (The colors of the keys do not matter.) You are allowed to open the doors in any order you like, and to choose the keys used to open each of the doors. You are also allowed to stop opening doors whenever you are satisfied with your current number of keys. Compute and return the maximal total number of keys you can have at the end.


Parameters:int[], int[], int[], int[], int[], int[]
Method signature:int maxKeys(int[] doorR, int[] doorG, int[] roomR, int[] roomG, int[] roomW, int[] keys)
(be sure your method is public)


-doorR, doorG, roomR, roomG and roomW will each contain between 1 and 12 elements, inclusive.
-doorR, doorG, roomR, roomG and roomW will contain the same number of elements.
-Each element of doorR, doorG, roomR, roomG and roomW will be between 0 and 10, inclusive.
-keys will contain exactly 3 elements.
-Each element of keys will be between 0 and 10, inclusive.


{1, 2, 3}
{0, 4, 9}
{0, 0, 10}
{0, 8, 9}
{1, 0, 8}
{3, 1, 2}
Returns: 8
First you have 3 red keys, 1 green key, 2 white keys. You can end with 8 keys as follows:
  • First, you open door 0 using 1 red key. From the opened chamber you gain 1 white key, so currently you have 2 red keys, 1 green key, and 3 white keys.
  • Second, you open door 1 using 2 red keys, 1 green key, and 3 white keys (all of them into green locks). Immediately after opening the door you have no keys: all the ones you had were just used and thus they broke. However, the chamber you just opened contains 8 green keys.
You can't end with more than 8 keys, so you should return 8.
{1, 1, 1, 2}
{0, 2, 3, 1}
{2, 1, 0, 4}
{1, 3, 3, 1}
{1, 0, 2, 1}
{0, 4, 0}
Returns: 4
You have only green keys, while each door has at least 1 red keyhole. So you cannot open any of the doors.
{2, 0, 4}
{3, 0, 4}
{0, 0, 9}
{0, 0, 9}
{8, 5, 9}
{0, 0, 0}
Returns: 27
Initially you have no key at all, but door 1 also has no key hole. Therefore, you can start by opening door 1.
{5, 3, 0, 0}
{0, 1, 2, 1}
{0, 9, 2, 4}
{2, 9, 2, 0}
{0, 9, 1, 1}
{1, 1, 0}
Returns: 32
Returns: 16

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       Single Round Match 588 Round 1 - Division I, Level Two