SHARE
TWEET

Untitled

a guest Jan 14th, 2020 66 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. let process_array arr =
  2.     let len = Array.length arr in
  3.     let final_state = Array.make len 0 in
  4.     let max_capacity = Array.make len 0 in
  5.     begin
  6.     for i = 0 to len - 1 do
  7.         max_capacity.(i) <- fst arr.(i);
  8.         final_state.(i) <- snd arr.(i);
  9.     done;
  10.     end;
  11.     (final_state, max_capacity)
  12.  
  13. let gcdarray arr =
  14.     let len = Array.length arr in
  15.     let div = ref arr.(0) in
  16.     let c = ref 0 in
  17.     for i = 1 to len - 1 do
  18.         while arr.(i) <> 0 do
  19.             c := !div mod arr.(i);
  20.             div := arr.(i);
  21.             arr.(i) <- !c;
  22.         done;
  23.     done; !div
  24.  
  25. let gcd_case final_state max_capacity =
  26.     let len = Array.length final_state in
  27.     let gcdarr = gcdarray (Array.copy max_capacity) in
  28.     let flag = ref 1 in
  29.     begin  
  30.     for i = 0 to len - 1 do
  31.         if (final_state.(i) <> max_capacity.(i)) && (final_state.(i) mod gcdarr <> 0) then begin flag := (-1); end;
  32.     done;
  33.     end;
  34.     !flag
  35.  
  36. let empty_full_case final_state max_capacity =
  37.     let len = Array.length final_state in
  38.     let count = ref 0 in
  39.     let flag = ref 1 in
  40.     begin
  41.     for i = 0 to len - 1 do
  42.         if (final_state.(i) = max_capacity.(i)) && (max_capacity.(i) <> 0) then (count := !count + 1;)
  43.         else if (final_state.(i) <> max_capacity.(i)) && (final_state.(i) <> 0) then (flag := 0 )
  44.         else (flag := !flag;);
  45.     done;
  46.     end;
  47.     if (!flag = 1) then !count else (-1)
  48.    
  49. let przelewanka arr =
  50.     let (final_state, max_capacity) = process_array arr in
  51.     let flag = ref 0 in
  52.     begin
  53.     let a = gcd_case final_state max_capacity in
  54.     let b = empty_full_case final_state max_capacity in
  55.     if a=(-1) then begin flag := (-1) end
  56.     else if b>=0 then begin flag := b end
  57.     else begin flag := (-2) end;
  58.     end;
  59.     if (!flag >= 0) then !flag
  60.     else if (!flag = (-1)) then (-1)
  61.     else
  62.     let len = Array.length arr in
  63.     let current_state = ref (Array.make len 0) in
  64.     let current_moves = ref 0 in
  65.     let generated_state = ref (Array.make len 0) in
  66.     let q = Queue.create () in
  67.     let distance = Hashtbl.create len in
  68.     begin
  69.     Hashtbl.add distance !current_state 0;
  70.     Queue.add !current_state q;
  71.     while Queue.is_empty q = false do
  72.         current_state := Queue.top q;
  73.         Queue.pop q;
  74.         current_moves := Hashtbl.find distance !current_state;
  75.         generated_state := Array.copy !current_state;
  76.         for i = 0 to len - 1 do
  77.                 if !current_state.(i) <> 0 then
  78.                     begin
  79.                     !generated_state.(i) <- 0;
  80.                     let x = Array.copy !generated_state in
  81.                     if Hashtbl.find_opt distance x = None then
  82.                         begin Hashtbl.add distance x (!current_moves + 1); Queue.add x q; end;
  83.                     !generated_state.(i) <- !current_state.(i);
  84.                     end;
  85.                 if !current_state.(i) <> max_capacity.(i) then
  86.                     begin
  87.                     !generated_state.(i) <- max_capacity.(i);
  88.                     let x = Array.copy !generated_state in
  89.                     if Hashtbl.find_opt distance x = None then
  90.                         begin Hashtbl.add distance x (!current_moves + 1); Queue.add x q; end;
  91.                     !generated_state.(i) <- !current_state.(i);
  92.                     end;
  93.                 for j = 0 to len - 1 do
  94.                     if (i <> j) && (!current_state.(i) <> 0) then
  95.                         begin
  96.                         !generated_state.(i) <- max 0 (!current_state.(i) - max_capacity.(j) + !current_state.(j));
  97.                         !generated_state.(j) <- min max_capacity.(j) (!current_state.(j) + !current_state.(i));
  98.                         let x = Array.copy !generated_state in
  99.                         if Hashtbl.find_opt distance x = None then
  100.                             begin Hashtbl.add distance x (!current_moves + 1); Queue.add x q; end;
  101.                         end;
  102.                         !generated_state.(i) <- !current_state.(i);
  103.                         !generated_state.(j) <- !current_state.(j);
  104.             done;
  105.         done;
  106.         if Hashtbl.find_opt distance final_state <> None then Hashtbl.find_opt distance final_state
  107.         else None;
  108.     done;
  109.     end;
  110.     match Hashtbl.find_opt distance final_state with
  111.     | Some x -> x
  112.     | _ -> (-1)
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top