Advertisement
Guest User

Untitled

a guest
Jan 21st, 2020
158
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
OCaml 2.43 KB | None | 0 0
  1. let warunek_konieczny n kubelki =
  2.   let rec nwd a b =
  3.     if a = 0 || b = 0 then a + b
  4.     else nwd (min a b) ((max a b) mod (min a b))
  5.   in
  6.   let wspolny_dzielnik = ref 0 in
  7.   for i = 0 to (n - 1) do
  8.     wspolny_dzielnik := nwd !wspolny_dzielnik (fst kubelki.(i))
  9.   done;
  10.   let wynik = ref true in
  11.   if !wspolny_dzielnik <> 0 then
  12.   begin
  13.     for i = 0 to (n - 1) do
  14.         if (snd kubelki.(i)) mod !wspolny_dzielnik <> 0 then wynik := false;
  15.     done
  16.   end;
  17.   !wynik
  18.  
  19. let print_array x =
  20.   let n = Array.length x in
  21.   for i = 0 to (n - 1) do
  22.   print_int x.(i);
  23.   done;
  24.  
  25. let przelewanka kubelki =
  26.   let wynik = ref (-1) in
  27.   let n = Array.length kubelki in
  28.   let rozmiar_mapy = 200000 in
  29.   if warunek_konieczny n kubelki = true then
  30.   begin
  31.     let koniec = Array.init n (fun i -> snd kubelki.(i)) in
  32.     let stan_poczatkowy = Array.make n 0 in
  33.     let q = Queue.create () in
  34.     Queue.add stan_poczatkowy q;
  35.     let znaleziono_wynik = ref false in
  36.     let visited = Hashtbl.create rozmiar_mapy in
  37.     Hashtbl.add visited stan_poczatkowy 0;
  38.     while Queue.length q <> 0 && !znaleziono_wynik = false do
  39.       let x = Queue.take q in
  40.       let cur_odl = Hashtbl.find visited x in
  41.       if x = koniec then
  42.       begin
  43.         znaleziono_wynik := true;
  44.         wynik := cur_odl;
  45.       end;
  46.       (* Wylewanie *)
  47.       for i = 0 to (n - 1) do
  48.         let stan = Array.copy x in
  49.         stan.(i) <- 0;
  50.         if not (Hashtbl.mem visited stan) then
  51.         begin
  52.           Hashtbl.add visited stan (cur_odl + 1);
  53.           Queue.add stan q;
  54.         end
  55.       done;
  56.       (* Wlewanie *)
  57.       for i = 0 to (n - 1) do
  58.         let stan = Array.copy x in
  59.         stan.(i) <- (fst kubelki.(i));
  60.         if not (Hashtbl.mem visited stan) then
  61.         begin
  62.           Hashtbl.add visited stan (cur_odl + 1);
  63.           Queue.add stan q;
  64.         end
  65.       done;
  66.       (* Przelewanie *)
  67.       for i = 0 to (n - 1) do
  68.         for j = 0 to (n - 1) do
  69.           if i <> j then
  70.           begin
  71.             let stan = Array.copy x in
  72.             let zmiana = min stan.(i) ((fst kubelki.(j)) - x.(j)) in
  73.             stan.(i) <- stan.(i) - zmiana;
  74.             stan.(j) <- stan.(j) + zmiana;
  75.             if not (Hashtbl.mem visited stan) then
  76.             begin
  77.               Hashtbl.add visited stan (cur_odl + 1);
  78.               Queue.add stan q;
  79.             end
  80.           end;
  81.         done
  82.       done
  83.     done
  84.   end;
  85.   !wynik
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement