Commits

Vadim Shender committed 1da63e0

Initial commit

Comments (0)

Files changed (25)

+syntax: glob
+*.cm[ioxa]
+*.o
+*~
+*.omc
+.omakedb*

00002.PRIME1/OMakefile

+../omake/OMakefile

00002.PRIME1/prime1.ml

+(* https://www.spoj.pl/problems/PRIME1/ *)
+
+let (|>) x y = y x
+
+let max_s = 31622
+
+let is_prime_t n =
+  let sn = n |> float_of_int |> sqrt |> int_of_float in
+  let rec ip_aux m =
+    if      m >  sn      then true
+    else if n mod m == 0 then false
+    else                      ip_aux (m + 2)
+  in
+  n != 1 && (n == 2 || n mod 2 > 0 && ip_aux 3)
+
+let is_prime =
+  let primes =
+    let rec calc_primes n accu =
+      if      n > max_s    then List.rev accu
+      else if is_prime_t n then calc_primes (n + 2) (n :: accu)
+      else                      calc_primes (n + 2) accu
+    in calc_primes 9 [7; 5; 3; 2]
+  in
+  function n ->
+    let sn = n |> float_of_int |> sqrt |> int_of_float in
+    let rec ip_aux = function
+        []          -> true
+      | p :: primes ->
+          if      p > sn      then true
+          else if n mod p > 0 then ip_aux primes
+          else                     false
+    in n != 1 && ip_aux primes
+
+let solve n m =
+  for i = n to m do
+    if is_prime i then
+      Printf.printf "%d\n" i
+  done ;
+  print_newline ()
+
+let main () =
+  let t = Scanf.scanf "%d\n" (fun t -> t) in
+  for i = 1 to t do
+    let n, m = Scanf.scanf "%d %d\n" (fun n m -> n, m) in
+    solve n m
+  done
+
+let () = main ()
+../common/OMakefile
+(* https://www.spoj.pl/problems/ONP/ *)
+
+
+let id x = x
+let (|>) x y = y x
+
+
+type tree =
+  Leaf of char
+| Node of char * tree * tree
+
+let parse expr =
+  let len = String.length expr in
+
+  let rec parse_a i =
+    match expr.[i] with
+      '('    ->
+        let tree, i = parse_d (i + 1) in
+        tree, i + 1
+    | letter ->
+        Leaf letter, i + 1
+
+  and parse_m' left i =
+    if i < len && (expr.[i] == '*' || expr.[i] == '/') then
+      let right, i' = parse_a (i + 1) in
+      parse_m' (Node (expr.[i], left, right)) i'
+    else
+      left, i
+  and parse_m i = let left, i = parse_a i in parse_m' left i
+
+  and parse_t' left i =
+    if i < len && (expr.[i] == '+' || expr.[i] == '-') then
+      let right, i' = parse_m (i + 1) in
+      parse_t' (Node (expr.[i], left, right)) i'
+    else
+      left, i
+  and parse_t i = let left, i = parse_m i in parse_t' left i
+
+  and parse_d' left i =
+    if i < len && expr.[i] == '^' then
+      let right, i' = parse_t (i + 1) in
+      parse_d' (Node (expr.[i], left, right)) i'
+    else
+      left, i
+  and parse_d i = let left, i = parse_t i in parse_d' left i
+
+  in fst (parse_d 0)
+
+let print tree =
+  let rec print_aux = function
+      Node (op, l, r) -> print_aux l; print_aux r; print_char op
+    | Leaf letter     -> print_char letter
+  in print_aux tree; print_newline ()
+
+
+let main () =
+  let t = Scanf.scanf "%d\n" id in
+  for i = 1 to t do
+    let expr = Scanf.scanf "%s\n" id in
+    expr |> parse |> print
+  done
+
+let () = main ()

00005.PALIN/OMakefile

+../common/OMakefile
+(* https://www.spoj.pl/problems/PALIN/ *)
+
+let (|>) x y = y x
+let id x = x
+
+
+let solve x =
+  let x = String.copy x in
+
+  let n  = String.length x in
+  let n2 = n / 2 in
+
+  let rec pass1 i is_le =
+    (* Make palindrome. *)
+    if i >= n2 then is_le
+    else
+      let is_le = x.[i] <= x.[n - i - 1] in
+      x.[n - i - 1] <- x.[i] ;
+      pass1 (i + 1) is_le
+  in
+
+  let rec pass2 i =
+    (* Fix the palindrome, obtained on first pass, if it's less or equal then
+       the source number. *)
+    if i == -1 then
+      (* The whole string proceeded. *)
+      if x.[0] == '0' then begin
+        (* 1 + string[:-1] + 1 *)
+        x.[n - 1] <- '1' ; String.concat "" ["1"; x]
+      end
+      else
+        x
+
+    else begin
+      x.[i] <- if x.[i] == '9' then '0'
+               else                 x.[i] |> Char.code |> ((+) 1) |> Char.chr ;
+
+      x.[n - i - 1] <- x.[i] ;
+
+      if x.[i] == '0' then pass2 (i - 1)
+      else                 x
+    end
+  in
+
+  if pass1 0 false then
+    pass2 (if n mod 2 == 0 then n2 - 1 else n2)
+  else
+    x
+
+
+let main () =
+  let t = Scanf.scanf "%d\n" id in
+  for i = 1 to t do
+    let k = Scanf.scanf "%s\n" id in
+    let x = solve k in
+    Printf.printf "%s\n" x
+  done
+
+let () = main ()

00006.ARITH/OMakefile

+../common/OMakefile
+(* https://www.spoj.pl/problems/ARITH/ *)
+
+open Num
+
+
+let id x = x
+
+
+let print_prefixed_with_spaces n str =
+  let len = String.length str in
+  for i = 1 to n - len do print_char ' ' done ;
+  print_endline str
+
+let print_dashes n m =
+  print_prefixed_with_spaces n (String.make m '-')
+
+let print_pm opstr op left right =
+  let res = string_of_num (op (num_of_string left) (num_of_string right)) in
+
+  let right = String.concat "" [opstr; right] in
+  let right_len = String.length right in
+  let len = max (max (String.length left) right_len) (String.length res)
+  in
+  print_prefixed_with_spaces len left ;
+  print_prefixed_with_spaces len right ;
+  print_dashes len (max right_len (String.length res));
+  print_prefixed_with_spaces len res
+
+let print_m opstr left right =
+  let res = string_of_num (( */ ) (num_of_string left) (num_of_string right)) in
+  let right = String.concat "" [opstr; right] in
+  let left_len = String.length left
+  and right_len = String.length right
+  and res_len = String.length res in
+  let len = max (max left_len right_len) (String.length res)
+  in
+  print_prefixed_with_spaces len left ;
+  print_prefixed_with_spaces len right ;
+
+  if right_len > 2 then begin
+    for i = 0 to right_len - 2 do
+      let intr =
+        string_of_num
+          (( */ )
+              (num_of_string left)
+              (num_of_string (String.make 1 right.[right_len - i - 1])))
+      in
+      if i == 0 then
+        print_dashes len (max right_len (String.length intr)) ;
+      print_prefixed_with_spaces
+        len (String.concat "" [intr; (String.make i ' ')])
+    done ;
+    print_dashes len res_len
+  end
+  else
+    print_dashes len len ;
+  print_prefixed_with_spaces len res
+
+let print_expr left op right =
+  match op with
+    "+" -> print_pm op (+/) left right
+  | "-" -> print_pm op (-/) left right
+  | "*" -> print_m op left right
+  | _   -> invalid_arg "impossible case"
+
+let main () =
+  let t = Scanf.scanf "%d\n" id in
+  for i = 1 to t do
+    let expr = Scanf.scanf "%s\n" id in
+    let re = Str.regexp "\\([0-9]+\\)\\([-+*]\\)\\([0-9]+\\)" in
+    let _ = Str.string_match re expr 0 in
+    print_expr
+      (Str.matched_group 1 expr)
+      (Str.matched_group 2 expr)
+      (Str.matched_group 3 expr) ;
+    print_newline ()
+  done
+
+let () = main ()

00010.CMEXPR/OMakefile

+../common/OMakefile

00010.CMEXPR/cmexpr.ml

+(* https://www.spoj.pl/problems/CMEXPR/ *)
+
+
+let id x = x
+let (|>) x y = y x
+
+
+type tree =
+  Leaf of char
+| Node of char * tree * tree
+
+let parse expr =
+  let len = String.length expr in
+
+  let rec parse_a i =
+    match expr.[i] with
+      '('    ->
+        let tree, i = parse_t (i + 1) in
+        tree, i + 1
+    | letter ->
+        Leaf letter, i + 1
+
+  and parse_m' left i =
+    if i < len && (expr.[i] == '*' || expr.[i] == '/') then
+      let right, i' = parse_a (i + 1) in
+      parse_m' (Node (expr.[i], left, right)) i'
+    else
+      left, i
+  and parse_m i = let left, i = parse_a i in parse_m' left i
+
+  and parse_t' left i =
+    if i < len && (expr.[i] == '+' || expr.[i] == '-') then
+      let right, i' = parse_m (i + 1) in
+      parse_t' (Node (expr.[i], left, right)) i'
+    else
+      left, i
+  and parse_t i = let left, i = parse_m i in parse_t' left i
+
+  in fst (parse_t 0)
+
+let print tree =
+  let op_prio = function
+      '+' | '-' -> 1
+    | _         -> 2
+  in
+  let op_assoc = function
+      '+' | '*' -> true
+    | _         -> false
+  in
+
+  let need_par op prio assoc is_left =
+    let prio' = op_prio op in
+    prio' < prio || (prio' == prio && not assoc && not is_left)
+  in
+
+  let rec print_aux prio assoc left = function
+      Node (op, l, r) ->
+        let npar = need_par op prio assoc left in
+        if npar then print_char '(' ;
+        print_aux (op_prio op) (op_assoc op) true l ;
+        print_char op ;
+        print_aux (op_prio op) (op_assoc op) false r ;
+        if npar then print_char ')'
+    | Leaf letter ->
+        print_char letter
+  in print_aux 0 true true tree ; print_newline ()
+
+
+let main () =
+  let t = Scanf.scanf "%d\n" id in
+  for i = 1 to t do
+    let expr = Scanf.scanf "%s\n" id in
+    expr |> parse |> print
+  done
+
+let () = main ()

00011.FCTRL/OMakefile

+../common/OMakefile
+(* https://www.spoj.pl/problems/FCTRL/ *)
+
+open Nativeint
+
+let (+/) = add
+let (|>) x y = y x
+let id x = x
+
+
+let rec z_aux accu n x =
+  if      n < x then accu
+  else if x > 200000000 then accu +/ of_int (n / x)
+  else                       z_aux (accu +/ of_int (n / x)) n (x * 5)
+
+let z n = z_aux zero n 5
+
+
+let main () =
+  let t = Scanf.scanf "%d\n" id in
+  for i = 1 to t do
+    let n = Scanf.scanf "%d\n" id in
+    n |> z |> to_string |> print_endline
+  done
+
+let () = main ()

00017.CRYPTO1/OMakefile

+../common/OMakefile

00017.CRYPTO1/crypto1.ml

+(* https://www.spoj.pl/problems/CRYPTO1/ *)
+
+open Num
+
+let (|>) x y = y x
+
+
+let p = num_of_string "4000000007"
+let k = (p -/ (num_of_int 3)) // (num_of_int 4)
+
+let limit = num_of_string "1924992000"
+
+let zero = num_of_int 0
+let one  = num_of_int 1
+
+
+let expt_mod a n p =
+  let rec em_aux accu a p n =
+    if n == zero then accu
+    else              em_aux (mod_num (accu */ a) p) a p (n -/ one)
+  in em_aux one a p n
+
+let solve enct =
+  let q = expt_mod enct (k +/ one) p in
+  if q </ limit then q
+  else               p -/ q
+
+
+let main () =
+  let enct = Scanf.scanf "%s\n" (fun x -> x) |> num_of_string in
+  let dect = solve enct in
+  Printf.printf "%s\n" (string_of_num dect)
+
+let () = main ()
+../common/OMakefile
+(* https://www.spoj.pl/problems/PIR/
+   http://www.cs.berkeley.edu/~wkahan/VtetLang.pdf *)
+
+
+open Num
+
+let sqr = square_num
+
+let vol u u' v v' w w' =
+  let li = num_of_int 4 */ sqr u */ sqr v */ sqr w -/
+           sqr u */ sqr (sqr v +/ sqr w -/ sqr u') -/
+           sqr v */ sqr (sqr w +/ sqr u -/ sqr v') -/
+           sqr w */ sqr (sqr u +/ sqr v -/ sqr w') +/
+           (sqr v +/ sqr w -/ sqr u') */
+           (sqr w +/ sqr u -/ sqr v') */
+           (sqr u +/ sqr v -/ sqr w')
+  in
+  sqrt (float_of_num li) /. 12.
+
+let main () =
+  let n = Scanf.scanf "%d\n" (fun x -> x) in
+  for i = 1 to n do
+    let u, v, w, w', v', u' =
+      Scanf.scanf
+        "%d %d %d %d %d %d\n"
+        (fun a b c d e f ->
+          num_of_int a, num_of_int b, num_of_int c,
+          num_of_int d, num_of_int e, num_of_int f)
+    in
+    Printf.printf "%.4f\n" (vol u u' v v' w w')
+  done
+
+let () = main ()

00024.FCTRL2/OMakefile

+../common/OMakefile

00024.FCTRL2/fctrl2.ml

+(* http://www.spoj.pl/problems/FCTRL2/ *)
+
+open Num
+
+let id x = x
+let (|>) x y = y x
+
+
+let rec fact = function
+    0 -> num_of_int 1
+  | n -> num_of_int n */ fact (n - 1)
+
+let main () =
+  let t = Scanf.scanf "%d\n" id in
+  for i = 1 to t do
+    Scanf.scanf "%d\n" id |> fact |> string_of_num |> print_endline
+  done
+
+let () = main ()
+../common/OMakefile
+(* http://www.spoj.pl/problems/TRIP/ *)
+
+let (|>) x y = y x
+let id x = x
+
+
+let str_reverse s =
+  let n  = String.length s in
+  let s' = String.make n ' ' in
+  for i = 0 to n - 1 do s'.[i] <- s.[n - i - 1] done ;
+  s'
+
+
+module CharOrderedType = struct
+  type t = Char.t
+  let compare = compare
+end
+
+module CharMap = Map.Make(CharOrderedType)
+
+type prefix_tree =
+  Empty
+| Node of prefix_tree CharMap.t
+
+let rec merge_trees a b =
+  match a, b with
+    Empty,   _       -> b
+  | _,       Empty   -> a
+  | Node a', Node b' ->
+      Node (CharMap.fold
+              (fun char subtree tree ->
+                CharMap.add
+                  char
+                  (if CharMap.mem char tree then
+                      merge_trees subtree (CharMap.find char tree)
+                   else
+                      subtree)
+                  tree)
+              a' b')
+
+
+(* F[i][j] = F[i-1][j-1] + 1              if a[i] == b[j]
+   F[i][j] = max(F[i-1][j], F[i][j-1])    otherwise *)
+let f_calc a b n m =
+  let f = Array.make_matrix (n + 1) (m + 1) 0 in
+
+  for i = 1 to n do
+    for j = 1 to m do
+      if a.[i - 1] == b.[j - 1] then
+        f.(i).(j) <- f.(i - 1).(j - 1) + 1
+      else
+        f.(i).(j) <- max f.(i - 1).(j) f.(i).(j - 1)
+    done
+  done ;
+
+  f
+
+let gen_tree f a b n m =
+  let cache = Array.make_matrix (n + 1) (m + 1) Empty in
+
+  for i = 1 to n do
+    for j = 1 to m do
+      cache.(i).(j) <-
+        if a.[i - 1] == b.[j - 1] then
+          (* Node (CharMap.singleton a.[i - 1] cache.(i - 1).(j - 1) *)
+          Node (CharMap.add a.[i - 1] cache.(i - 1).(j - 1) CharMap.empty)
+        else
+          merge_trees
+            (if f.(i).(j) == f.(i - 1).(j) then cache.(i - 1).(j) else Empty)
+            (if f.(i).(j) == f.(i).(j - 1) then cache.(i).(j - 1) else Empty)
+    done
+  done ;
+
+  cache.(n).(m)
+
+let print_solutions f n m tree =
+  let str = String.make f.(n).(m) ' ' in
+  let rec ps_aux i = function
+      Empty   -> print_endline str
+    | Node m  ->
+      CharMap.iter
+        (fun key subtree ->
+          str.[i] <- key ;
+          ps_aux (i + 1) subtree)
+        m
+  in ps_aux 0 tree
+
+let solve a b =
+  let n = String.length a
+  and m = String.length b
+
+  and a = str_reverse a
+  and b = str_reverse b in
+
+  let f = f_calc a b n m in
+  gen_tree f a b n m |> print_solutions f n m
+
+let main () =
+  Gc.set { (Gc.get ()) with Gc.minor_heap_size=16777216 } ;
+
+  let t = Scanf.scanf "%d\n" id in
+  for i = 1 to t do
+    let a = Scanf.scanf "%s\n" id
+    and b = Scanf.scanf "%s\n" id in
+    solve a b ;
+    print_newline ()
+  done
+
+let () = main ()
+.PHONY: all clean
+
+
+.SUBDIRS: $(glob [0-9][0-9][0-9][0-9][0-9].*)
+
+clean:
+    rm -rf *~ \#* *.omc
+open build/OCaml
+
+#
+# The command-line variables are defined *after* the
+# standard configuration has been loaded.
+#
+DefineCommandVars()
+
+#
+# Include the OMakefile in this directory.
+#
+.SUBDIRS: .
+SPOJ problems solved in OCaml
+.PHONY: all clean
+
+
+USE_OCAMLFIND = true
+OCAMLPACKS[] =
+    num
+    str
+
+NATIVE_ENABLED = true
+
+
+.DEFAULT: all
+
+TARGET = $(removesuffix $(glob *.ml))
+
+all: $(OCamlProgram $(TARGET),$(TARGET))
+
+
+clean:
+    rm -rf *~ \#* *.o *.cm[iox] *.omc *.opt $(TARGET)