% CCC 1997 % problem E: Long Division % % this is essentially long subtraction! Must be able to do mulitdigit (array) % subtraction and recognize if negatives are produced. UGLY! % file handling is used, the number of test cases is given % then each case is two lines, dividend and divisor. var infile : string := "div.in" var outfile : string := "div.out" var fi, fo : int var n, ndvd, ndvs, nquo : int var dvd : array 1 .. 100 of int var dvs : array 1 .. 100 of int var quo : array 1 .. 100 of int var t : array 1 .. 100 of int var offset, k, m : int var can : boolean var line : string var key : string (1) open : fi, infile, get open : fo, outfile, put get : fi, n for i : 1 .. n % get the dividend and divisor, convert to integer arrays. get : fi, line for j : 1 .. length (line) dvd (j) := strint (line (j)) end for ndvd := length (line) get : fi, line for j : 1 .. length (line) dvs (j) := strint (line (j)) end for ndvs := length (line) nquo := 0 offset := 0 loop exit when ndvs > ndvd - offset nquo := nquo + 1 quo (nquo) := 0 loop % save dividend for j : 1 .. ndvd t (j) := dvd (j) end for % do the division can := true k := ndvs m := ndvs + offset loop exit when m = 0 if k >= 1 then if dvd (m) >= dvs (k) then dvd (m) := dvd (m) - dvs (k) else dvd (m) := (dvd (m) + 10) - dvs (k) if m = 1 then can := false else dvd (m - 1) := dvd (m - 1) - 1 end if end if else if dvd (m) >= 0 then dvd (m) := dvd (m) else dvd (m) := (dvd (m) + 10) if m = 1 then can := false else dvd (m - 1) := dvd (m - 1) - 1 end if end if end if k := k - 1 m := m - 1 end loop if can then quo (nquo) := quo (nquo) + 1 else % restore dividend for j : 1 .. ndvd dvd (j) := t (j) end for end if exit when can = false end loop offset := offset + 1 end loop %print quotient, eliminating leading zeros if nquo = 0 then put : fo, "0" put "0" else k := 1 loop exit when k >= nquo or quo (k) not= 0 k := k + 1 end loop loop exit when k > nquo put : fo, quo (k) .. put quo (k) .. k := k + 1 end loop put : fo, "" put "" end if %print remainder(dividend), eliminating leading zeros k := 1 loop exit when k >= ndvd or dvd (k) not= 0 k := k + 1 end loop loop exit when k > ndvd put : fo, dvd (k) .. put dvd (k) .. k := k + 1 end loop put : fo, "" put : fo, "" put "" put "" end for close : fi close : fo