algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

problem.txt (1335B)


      1 Polycarpus has a ribbon, its length is n. He wants to cut the ribbon in a way that fulfils the following two conditions:
      2 
      3     After the cutting each ribbon piece should have length a, b or c.
      4     After the cutting the number of ribbon pieces should be maximum. 
      5 
      6 Help Polycarpus and find the number of ribbon pieces after the required cutting.
      7 
      8 ---
      9 
     10 - length == n
     11 - conditions:
     12     - after cutting ribbons pieces should have length a,b,c
     13     - after cutting the number of ribbon pieces should be maximum
     14         - so basically we want as many of the shortest and one of the rest perhaps
     15 
     16 ---
     17 
     18 n,a,b,c <= 4000
     19 
     20 5 5 3 2
     21 
     22 n = 5
     23 a = 5
     24 b = 3
     25 c = 2
     26 
     27 we can either not cut, or we can cut at 3 to get b and c lengths (2)
     28 
     29 
     30 ---
     31 
     32 n=7
     33 a=5
     34 b=5
     35 c=2
     36 
     37 7 5 5 2
     38 
     39 5 + 2 = 7
     40 
     41 we can cut one segment with a/b length and one with c's length:
     42 
     43 ans: 2
     44 
     45 ---
     46 
     47 - idea:
     48     - given that n <= 4000, it might be possible to just try all combinations at each step
     49         - there are 4000-1 possible locations, and from each of these there are only at most 3 cuts of consequence we can make
     50             - size a,b,c
     51         - at a certain location, we only care about further cuts from that point on that fill the space up to the given location
     52             - dp problem
     53 
     54 ---
     55 
     56 - dp formulation:
     57     - state := (index)
     58     - transition := as possible, cut size a,b,c