http://acm.pku.edu.cn/JudgeOnline/problem?id=1117
Код:
program PKU1117;
{$I-, s-, q-, r-}
const maxn = 12;
maxm = 200000;
type integer = longint;
var w, a, b: array[0..maxn] of integer;
c: array[0..maxm] of integer;
n, l, ans: integer;
procedure prepare;
var tmp: integer;
begin
read(n);
l := 0; tmp := n;
while n > 0 do begin
l := l + 1;
w[l] := n mod 10;
n := n div 10;
end; n := tmp;
end;
var s1, st: string;
procedure addans;
var tmp, i: integer;
begin
tmp := 0;
for i := l downto 1 do tmp := tmp * 10 + a[i];
str(tmp, st); str(n - tmp, s1);
if length(s1) < length(st) then begin
ans := ans + 1;
c[ans] := tmp;
end;
end;
procedure search(k, r, tmp: integer);
begin
if k = 0 then begin
if (r = 0) and (tmp = 0) then addans;
exit;
end;
if r = 1 then begin
tmp := tmp + w[k] - b[k];
if tmp < 0 then exit;
if (tmp > 0) and (tmp <= 10) then begin
a[k] := tmp - 1; b[k - 1] := tmp - 1;
search(k - 1, 1, 10);
search(k - 1, 0, 10);
end;
if tmp < 10 then begin
a[k] := tmp; b[k - 1] := tmp;
search(k - 1, 1, 0);
search(k - 1, 0, 0);
end;
end else begin
tmp := tmp + w[k];
a[k] := tmp shr 1; b[k] := a[k];
search(k - 1, r, (tmp and 1) * 10);
end;
end;
var temp: integer;
procedure sort(l, r: integer);
var i, j, mid: integer;
begin
i := l; j := r; mid := c[(l + r) shr 1];
while i <= j do begin
while c[i] < mid do i := i + 1;
while c[j] > mid do j := j - 1;
if i <= j then begin
temp := c[i]; c[i] := c[j]; c[j] := temp;
i := i + 1; j := j - 1;
end;
end;
if i < r then sort(i, r);
if l < j then sort(l, j);
end;
procedure main;
var i, j: integer;
begin
b[l] := 0; ans := 0;
c[0] := -1;
search(l, 1, 0);
sort(1, ans);
j := ans; ans := 0;
for i := 1 to j do if c[i] > c[ans] then begin
ans := ans + 1;
c[ans] := c[i];
end;
writeln(ans);
for i := 1 to ans do begin
str(c[i], s1);
str(n - c[i], st);
while length(st) < length(s1) - 1 do st := '0' + st;
writeln(s1, ' + ', st, ' = ', n);
end;
end;
begin
prepare;
main;
end.