% 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