ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1007. Кодовые слова

WAed N times on Test #1! Anything strange about that test?
Послано Maigo Akisame 8 июн 2004 14:40
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.
Re: WAed N times on Test #1! Anything strange about that test?
Послано Edward Bolshakov [NNTU] 8 июн 2004 19:48
Maigo Akisame писал(a) 8 июня 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.
A new prog. Still WA on test #1. What magic could that test have?
Послано Maigo Akisame 11 июн 2004 13:47
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.
Re: A new prog. Still WA on test #1. What magic could that test have?
Послано lee zhuojian 13 сен 2004 12:00
your program is wrong ;
  4
  101
  your answer is 0101
  it should be 1001 ,isn't it?
         Chicken QQ:372879887
But my 2nd prog gives 1001
Послано Maigo Akisame (maigoakisame@yahoo.com.cn) 18 сен 2004 18:26