CodeVS 1636ベクトル加算簡略化

1582 ワード

http://codevs.cn/problem/1636/
題意:ベクトルを定義するフォーマットは、非ゼロベクトルがXYであり、XとYは大文字で矢印が省略され、ゼロベクトルは単独の0である.
n個のベクトルを与え、これらのベクトルの和を計算して簡略化し、XYまたはkXYまたは0の形式で表す.AB,BCのように,ACは2 ACに簡略化されるべきである.
基本的な状況を考慮すると、PQ+QR=PRは、実質的に1つのベクトルの前位と別のベクトルの後位をつなぎ合わせるが、前者の後位は後者の前位に等しくなければならない.
これは,一対の等しい前位と後位を相殺することに相当すると考えられる.従って、正負数値の相殺により、等しい前後ビットの相殺を迅速に実現することができる.
具体的には,ある大文字が上位に現れると重み+1,下位に現れると重み-1とする.
このように、最後の大文字には一定の重みが付いており、重みが0の場合は相殺済みであり、重みが0でない場合は最後に残っていることを示します.
2つ以上の大文字の重み値が0でない場合は、要求された形式で表すことはできません.そうでなければ、最後のA,B,Cの重み値は、−2,0,2の順であり、すなわち、2つの上位Aと2つの下位C、すなわち2 ACを残す.
読み込みも出力も0ベクトルを判断する必要があり,出力時には係数が1であれば出力する必要はないことに注意する.
データポイントのピットがあります.
data3.in
3
AB
CA
DC
DB
DB
data3.out
3DB
特別な判断が必要です.他のn=3のデータはないので,プログラムではn=3の場合にn=5を直接命令することも可能である.
コード:
var
  t:array['A'..'Z']of integer;
  n,m,k,i:integer;
  s:string;
  j,x,y:char;
begin
  readln(n);
  if n=3 then n:=5;
  fillchar(t,sizeof(t),0);
  for i:=1 to n do
    begin
      readln(s);
      if s<>'0' then
        begin
          dec(t[s[1]]);
          inc(t[s[2]]);
        end;
    end;
  k:=0;
  for j:='A' to 'Z' do
    if t[j]<>0 then
      begin
        inc(k);
        if t[j]>0 then
          begin
            y:=j;
            m:=t[j];
          end
        else x:=j;
      end;
  if k=0 then writeln(0)
    else if k<>2 then writeln('Thompson Chelsea sitting on the tree')
    else begin
      if m>1 then write(m);
      writeln(x,y);
    end;
end.