Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- let warunek_konieczny n kubelki =
- let rec nwd a b =
- if a = 0 || b = 0 then a + b
- else nwd (min a b) ((max a b) mod (min a b))
- in
- let wspolny_dzielnik = ref 0 in
- for i = 0 to (n - 1) do
- wspolny_dzielnik := nwd !wspolny_dzielnik (fst kubelki.(i))
- done;
- let wynik = ref true in
- if !wspolny_dzielnik <> 0 then
- begin
- for i = 0 to (n - 1) do
- if (snd kubelki.(i)) mod !wspolny_dzielnik <> 0 then wynik := false;
- done
- end;
- !wynik
- let print_array x =
- let n = Array.length x in
- for i = 0 to (n - 1) do
- print_int x.(i);
- done;
- let przelewanka kubelki =
- let wynik = ref (-1) in
- let n = Array.length kubelki in
- let rozmiar_mapy = 200000 in
- if warunek_konieczny n kubelki = true then
- begin
- let koniec = Array.init n (fun i -> snd kubelki.(i)) in
- let stan_poczatkowy = Array.make n 0 in
- let q = Queue.create () in
- Queue.add stan_poczatkowy q;
- let znaleziono_wynik = ref false in
- let visited = Hashtbl.create rozmiar_mapy in
- Hashtbl.add visited stan_poczatkowy 0;
- while Queue.length q <> 0 && !znaleziono_wynik = false do
- let x = Queue.take q in
- let cur_odl = Hashtbl.find visited x in
- if x = koniec then
- begin
- znaleziono_wynik := true;
- wynik := cur_odl;
- end;
- (* Wylewanie *)
- for i = 0 to (n - 1) do
- let stan = Array.copy x in
- stan.(i) <- 0;
- if not (Hashtbl.mem visited stan) then
- begin
- Hashtbl.add visited stan (cur_odl + 1);
- Queue.add stan q;
- end
- done;
- (* Wlewanie *)
- for i = 0 to (n - 1) do
- let stan = Array.copy x in
- stan.(i) <- (fst kubelki.(i));
- if not (Hashtbl.mem visited stan) then
- begin
- Hashtbl.add visited stan (cur_odl + 1);
- Queue.add stan q;
- end
- done;
- (* Przelewanie *)
- for i = 0 to (n - 1) do
- for j = 0 to (n - 1) do
- if i <> j then
- begin
- let stan = Array.copy x in
- let zmiana = min stan.(i) ((fst kubelki.(j)) - x.(j)) in
- stan.(i) <- stan.(i) - zmiana;
- stan.(j) <- stan.(j) + zmiana;
- if not (Hashtbl.mem visited stan) then
- begin
- Hashtbl.add visited stan (cur_odl + 1);
- Queue.add stan q;
- end
- end;
- done
- done
- done
- end;
- !wynik
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement