algorithms

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

commit 9a317650c00a7199ee25f0059edec190f9a869ed
parent 0b233bc54ea3faeaa6271ad4a26bbe974dc363ef
Author: Andrew Laack <andrew@laack.co>
Date:   Wed, 11 Nov 2026 22:17:27 -0600

Trivial dp in ocaml

Diffstat:
Acomp/cut-ribbon/ex1.in | 1+
Acomp/cut-ribbon/ex2.in | 1+
Acomp/cut-ribbon/main.ml | 14++++++++++++++
Acomp/cut-ribbon/problem.txt | 58++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
4 files changed, 74 insertions(+), 0 deletions(-)

diff --git a/comp/cut-ribbon/ex1.in b/comp/cut-ribbon/ex1.in @@ -0,0 +1 @@ +5 5 3 2 diff --git a/comp/cut-ribbon/ex2.in b/comp/cut-ribbon/ex2.in @@ -0,0 +1 @@ +7 5 5 2 diff --git a/comp/cut-ribbon/main.ml b/comp/cut-ribbon/main.ml @@ -0,0 +1,14 @@ +let readInt () = Scanf.scanf " %d" (fun x -> x) in +let rec solve arr idx a b c = + if idx >= Array.length arr then + if idx > Array.length arr then -1000000000 else 0 + else + if arr.(idx) <> -1 then arr.(idx) else + let aA = 1 + solve arr (idx+a) a b c in + let aB = 1 + solve arr (idx+b) a b c in + let aC = 1 + solve arr (idx+c) a b c in + let mx = max (max aA aB) aC in + arr.(idx) <- mx; mx +in +let n = readInt () in let a = readInt () in let b = readInt () in let c = readInt () in +print_int (solve (Array.make n (-1)) 0 a b c); print_newline () diff --git a/comp/cut-ribbon/problem.txt b/comp/cut-ribbon/problem.txt @@ -0,0 +1,58 @@ +Polycarpus has a ribbon, its length is n. He wants to cut the ribbon in a way that fulfils the following two conditions: + + After the cutting each ribbon piece should have length a, b or c. + After the cutting the number of ribbon pieces should be maximum. + +Help Polycarpus and find the number of ribbon pieces after the required cutting. + +--- + +- length == n +- conditions: + - after cutting ribbons pieces should have length a,b,c + - after cutting the number of ribbon pieces should be maximum + - so basically we want as many of the shortest and one of the rest perhaps + +--- + +n,a,b,c <= 4000 + +5 5 3 2 + +n = 5 +a = 5 +b = 3 +c = 2 + +we can either not cut, or we can cut at 3 to get b and c lengths (2) + + +--- + +n=7 +a=5 +b=5 +c=2 + +7 5 5 2 + +5 + 2 = 7 + +we can cut one segment with a/b length and one with c's length: + +ans: 2 + +--- + +- idea: + - given that n <= 4000, it might be possible to just try all combinations at each step + - there are 4000-1 possible locations, and from each of these there are only at most 3 cuts of consequence we can make + - size a,b,c + - at a certain location, we only care about further cuts from that point on that fill the space up to the given location + - dp problem + +--- + +- dp formulation: + - state := (index) + - transition := as possible, cut size a,b,c