% CCC 1997 % problem B: Nasty Numbers % % a nasty number has a pair of factors that when subtracted % equals a pair of factors that add together % observation: thinking of 36 % the pairs are: % 1, 36 % 2, 18 % 3, 12 % etc. as the 1st factor increases the diff AND sum decrease % therfore starting at 1, find the difference and then look % for the sum DOWN the list! % they only get smaller so they are easy to find. (no arrays needed) % file handling is used, the number of numbers is given % then the numbers themselves function nasty (x : int) : boolean var f1, f2 : int var s : real := sqrt (x) var diff : int f1 := 1 loop exit when f1 > s % find the next factor loop exit when f1 > s or x mod f1 = 0 f1 := f1 + 1 end loop if f1 < s then diff := (x div f1) - f1 f2 := f1 + 1 % find pairs after the first pair with a sum >= diff % (stop if the sum is less than the diff) loop loop exit when f2 > s or x mod f2 = 0 f2 := f2 + 1 end loop exit when f2 > s or (x div f2) + f2 <= diff f2 := f2 + 1 end loop % if you found it great if f2 < s and x div f2 + f2 = diff then result true end if end if % otherwise keep going f1 := f1 + 1 end loop % if you never find any pairs: false result false end nasty var infile : string := "nasty.in" var outfile : string := "nasty.out" var fi, fo : int var n, x : int open : fi, infile, get open : fo, outfile, put get : fi, n for i : 1 .. n get : fi, x if nasty (x) then put : fo, x, " is nasty" put x, " is nasty" else put : fo, x, " is not nasty" put x, " is not nasty" end if end for close : fi close : fo