ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1007. Code Words

Note: the rule stated in the prob indicates a palindromic string.

----------------------
program ural1007;
const
  maxn=1000;
var
  bit:array[1..maxn+1]of boolean;
  n,l,i,j:integer;
  c:char;
function pal(s,t:integer):boolean;
  var
    i:integer;
  begin
    for i:=s to (s+t) div 2 do
      if bit[i]<>bit[s+t-i] then begin
        pal:=false;
        exit;
      end;
    pal:=true;
  end;
begin
  readln(n);
  repeat
    l:=0;
    while not eoln(input) do begin
      read(c);
      if c='1' then begin
        inc(l);bit[l]:=true;
      end
      else if c='0' then begin
        inc(l);bit[l]:=false;
      end;
    end;
    readln;
    if l=0 then continue;

    j:=0;
    if l=n then begin
      if not pal(1,l) then
        for i:=1 to l div 2 do
          if bit[i]<>bit[l+1-i] then begin
            bit[i]:=false;
            bit[l+1-i]:=false;
            break;
          end;
      for i:=1 to l do
        write(ord(bit[i]));
      writeln;
    end

    else if l=n-1 then begin
      for i:=1 to l div 2 do
        if bit[i]<>bit[l+1-i] then begin
          if pal(i,l-i) then j:=i else j:=l+2-i;
          break;
        end;
      if j=0 then j:=l div 2+1;
      for i:=1 to j-1 do
        write(ord(bit[i]));
      write(ord(bit[l+1-j]));
      for i:=j to l do
        write(ord(bit[i]));
      writeln;
    end

    else if l=n+1 then begin
      for i:=1 to l div 2 do
        if bit[i]<>bit[l+1-i] then begin
          if pal(i,l-i) then j:=l+1-i else j:=i;
          break;
        end;
      if j=0 then j:=l div 2+1;
      for i:=1 to j-1 do
        write(ord(bit[i]));
      for i:=j+1 to l do
        write(ord(bit[i]));
      writeln;
    end;
  until eof(input);
end.
Edward Bolshakov [NNTU] Re: WAed N times on Test #1! Anything strange about that test? [3] // Problem 1007. Code Words 8 Jun 2004 19:48
Maigo Akisame wrote 8 June 2004 14:40
Note: the rule stated in the prob indicates a palindromic string.
No, it is not necessarily. I had analogous illusion when wrote first version of solution. And I was really surprised when got WA at 1st test :)) Example of asymmetric string for N=5 is "11100" (1+2+3 = 6 = N+1)
There are many cases similar to this for other values of N.
program ural1007;
const
  maxn=1001;
var
  bit:array[1..maxn]of boolean;
  n,i,j,l,m:integer;
  c:char;
procedure nochange;
  var
    i:integer;
  begin
    for i:=1 to l do write(ord(bit[i]));
    writeln;
  end;
procedure clear(p:integer);
  var
    i:integer;
  begin
    for i:=1 to p-1 do write(ord(bit[i]));
    write(0);
    for i:=p+1 to l do write(ord(bit[i]));
    writeln;
  end;
procedure insert(p,b:integer);
  var
    i:integer;
  begin
    for i:=1 to p-1 do write(ord(bit[i]));
    write(b);
    for i:=p to l do write(ord(bit[i]));
    writeln;
  end;
procedure del(p:integer);
  var
    i:integer;
  begin
    for i:=1 to p-1 do write(ord(bit[i]));
    for i:=p+1 to l do write(ord(bit[i]));
    writeln;
  end;
procedure tooshort;
  var
    i,c:integer;
  begin
    bit[n]:=false;c:=0;
    for i:=n downto 1 do begin
      if bit[i] then inc(c);
      if (m+c) mod (n+1)=0 then begin insert(i,0);exit;end;
      if (m+c+i) mod (n+1)=0 then begin insert(i,1);exit;end;
    end;
  end;
procedure toolong;
  var
    i,c:integer;
  begin
    c:=0;
    for i:=n+1 downto 1 do begin
      if (m-c-ord(bit[i])*i+(n+1)*2) mod (n+1)=0 then begin del(i);exit;end;
      if bit[i] then inc(c);
    end;
  end;
begin
  readln(n);
  for i:=1 to n do begin
    repeat
      l:=0;
      while not eoln(input) do begin
        read(c);
        if c='1' then begin
          inc(l);bit[l]:=true;
        end
        else if c='0' then begin
          inc(l);bit[l]:=false;
        end;
      end;
      readln;
    until (l>n-2) and (l<n+2);

    m:=0;
    for j:=1 to n do
      if bit[j] then m:=(m+j) mod (n+1);

    if l=n then
      if m=0 then nochange else clear(m)
    else if l=n-1 then
      tooshort
    else if l=n+1 then
      toolong;
  end;
end.
your program is wrong ;
  4
  101
  your answer is 0101
  it should be 1001 ,isn't it?
         Chicken QQ:372879887
Maigo Akisame (maigoakisame@yahoo.com.cn) But my 2nd prog gives 1001 // Problem 1007. Code Words 18 Sep 2004 18:26