SCUBADIV - Scuba diver

A scuba diver uses a special equipment for diving. He has a cylinder with two containers: one with oxygen and the other with nitrogen. Depending on the time he wants to stay under water and the depth of diving the scuba diver needs various amount of oxygen and nitrogen. The scuba diver has at his disposal a certain number of cylinders. Each cylinder can be described by its weight and the volume of gas it contains. In order to complete his task the scuba diver needs specific amount of oxygen and nitrogen. What is the minimal total weight of cylinders he has to take to complete the task?


The scuba diver has at his disposal 5 cylinders described below. Each description consists of: volume of oxygen, volume of nitrogen (both values are given in litres) and weight of the cylinder (given in decagrams):

3 36 120
10 25 129
5 50 250
1 45 130
4 20 119

If the scuba diver needs 5 litres of oxygen and 60 litres of nitrogen then he has to take two cylinders of total weight 249 (for example the first and the second ones or the fourth and the fifth ones).


Write a program that for each test case:

  • reads scuba diver's demand for oxygen and nitrogen, the number of accessible cylinders and their descriptions;
  • computes the minimal total weight of cylinders the scuba diver needs to complete his task;
  • outputs the result.

Note: the given set of cylinders always allows to complete the given task.


The number of test cases c is in the first line of input, then c test cases follow separated by an empty line.

In the first line of a test case there are two integers t, a separated by a single space, 1 <= t <= 21 and 1 <= a <= 79. They denote volumes of oxygen and nitrogen respectively, needed to complete the task. The second line contains one integer n, 1 <= n <= 1000, which is the number of accessible cylinders. The following n lines contain descriptions of cylinders; i-th line contains three integers ti, ai, wi separated by single spaces, (1 <= ti <= 21, 1 <= ai <= 79, 1 <= wi <= 800). These are respectively: volume of oxygen and nitrogen in the i-th cylinder and the weight of this cylinder.


For each test case your program should output one line with the minimal total weight of cylinders the scuba diver should take to complete the task.


Sample input:
5 60
3 36 120
10 25 129
5 50 250
1 45 130
4 20 119

Sample output:

hide comments
nobody550: 2019-03-03 09:45:58

A 3d knapsack problem

ankit1cool: 2018-06-22 20:13:38

Great question learnt a new thing about memoziation

s_a_k_s_h_a_m: 2018-06-15 14:24:37

good problem

Last edit: 2018-06-15 14:25:26
Sonu Sharma: 2018-06-08 17:10:46

Average , but tricky question. Advice: Assert that any of the value of o2 and n2 should not be negative.

archit4077sh: 2018-04-04 12:31:24

Last edit: 2018-05-23 20:30:53
cj23897: 2017-06-28 19:09:25

Nice question

cichipi_: 2017-06-09 21:25:55

# 3D dp using memset -> TLE...........take 3d temp array to handle it

# 2 base cases

(1) if((oxi>= ox && nitro>=nit))return 0;

(2) if(i>n)return inf; (1 indexing)

return dp[][][] = min( don't take ith , take ith )

Last edit: 2017-06-09 21:27:35
sas1905: 2017-05-26 16:19:25

3D dp+recursion ..Nice one..:)

shahzada: 2017-03-07 11:08:34


vengatesh15: 2017-02-09 10:13:27

my first 3d dp

Added by:MichaƂ Czuczman
Time limit:5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Resource:5th Polish Olympiad in Informatics, stage 2