ac1085.pas

来自「这是在网络上搜集到的在东京大学的ACM上面解决的一些题目的源码」· PAS 代码 · 共 67 行

program tju1085;
const
  maxn=80;
var
  nonzero,next:array[1..maxn]of byte;
  t,u,l,i,j,k,start:word;
  s:string;
function bigger(a,b,c,d:byte):boolean;
  var
    t,i:shortint;
  begin
    t:=(b-a)-(d-c);
    if t>0 then
      for i:=1 to t do begin
        if s[a]>'0' then begin bigger:=true;exit;end;
        inc(a);
      end
    else if t<0 then
      for i:=1 to -t do begin
        if s[c]>'0' then begin bigger:=false;exit;end;
        inc(c);
      end;
    repeat
      if s[a]>s[c] then begin
        bigger:=true;exit;
      end
      else if s[a]<s[c] then begin
        bigger:=false;exit;
      end;
      inc(a);inc(c);
    until a>b;
    bigger:=false;
  end;
begin
  readln(t);
  for u:=1 to t do begin
    readln(s);l:=length(s);
    nonzero[l]:=l;
    for i:=l-1 downto 1 do
      if s[i]='0' then nonzero[i]:=nonzero[i+1] else nonzero[i]:=i;
    if nonzero[1]=l then begin writeln(s);continue;end;

    for k:=l downto 1 do begin
      if s[k]='0' then continue;next[k]:=l+1;
      for i:=k-1 downto 1 do begin
        if nonzero[i]=k then begin next[i]:=l+1;continue;end;
        next[i]:=0;
        start:=nonzero[i]+l+1-k;if start>k then start:=k;
        for j:=start downto i+1 do
          if (next[j]>0) and bigger(j,next[j]-1,i,j-1) then begin
            next[i]:=j;break;
          end;
      end;
      if next[1]>0 then begin
        i:=1;
        repeat
          for j:=i to next[i]-1 do write(s[j]);
          i:=next[i];
          if i>l then begin writeln;break;end;
          write(',');
        until false;
        break;
      end;
    end;
  end;
end.