Блог пользователя bardakov_a_a

Автор bardakov_a_a, 12 лет назад, По-русски

Дамы и Господа! Нужна ваша помощь. Вот задача из самого первого соревнования codeforces http://codeforces.net/contest/1/problem/B?locale=ru

Помогите найти ошибку в логике. Валится на 7 тесте

program Project2;

{$APPTYPE CONSOLE}

var
  n: Integer;
  i: Integer;
  tmp: String;


function Selection(tmp: String): Boolean;
var i,j: Integer;
begin
  Selection:=True;
  if tmp[1]='R' then
  begin
    Delete(tmp, 1, 2);
    if Pos('C', tmp)<>0 then
        Selection:=False;
  end;
end;

function Power(a, n: Integer): Int64;
begin
  if n=0 then Power:=1
  else if odd(n) then Power:=Power(a*a, n div 2)*a
       else Power:=Power(a*a, n div 2);
end;

procedure ToTwoView(tmp: String);
var i, j: Integer;
  k: Integer;
  st: String;
  sum: Int64;
begin
  sum:=0;
  j:=Length(tmp);
  for i := j downto 1 do
    if tmp[i] In ['0'..'9'] then
      st:= tmp[i] + st
    else break;
  for j := i downto 1 do
    sum:=sum + (Ord(tmp[j])-Ord('A')+1)*Power(26,i-j);
  WriteLn('R',st,'C',sum);
end;

procedure ToOneView(tmp: String);
var st, st2: String;
  i,j,k: Integer;
  p, code: Integer;
begin
  i:=Pos('C', tmp);
  st:='';
  k:=Length(tmp);
  for j := 1 to i do
    if tmp[j] In ['0'..'9'] then
      st:=st+tmp[j];
  for j := i to k do
    if tmp[j] In ['0'..'9'] then
      st2:=st2+tmp[j];
  Val(st2, p, code);
  st2:='';
  while p>0 do
  begin
    i:= p mod 26;
    if i=0 then i:=26;
    st2:=st2+Chr(Ord('A')-1+i);
    p:=p-i;
    p:=p div 26;
  end;
  k:=Length(st2);
  for i := k downto 1 do
    Write(st2[i]);
  Write(st);
  WriteLn;
end;

begin
  ReadLn(n);
  for i := 1 to n do
  begin
    ReadLn(tmp);
    case Selection(tmp) of
      true: ToTwoView(tmp);
      false: ToOneView(tmp);
    end;
  end;
end.

Думаю, функция selection при каких-то значениях не верно определяет, но конкретного примера пока не нашел.

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Вам, видимо, помогут здесь, но никто не поможет на реальном соревновании.
А что Вы сами сделали для того, чтобы найти ошибку? Написали генератор тестов, второе (переборное) решение, чекер (при необходимости), что-то еще пытались сделать?

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Так я и не прошу на реальных соревнованиях, это же тренировка) Пробовал чекер тестов, но проблема в том, что мне приходится или самому рассчитывать значения и вроде верно. В протоколе тестов на этом сайте валится на 7м тесте при n=100000; Возможно, вы сможете увидеть протокол http://codeforces.net/contest/1/my Все тесты не выводятся и поэтому не пойму где ошибка..... В протоколе указано wrong answer 998th words differ — expected: 'R954870C320947', found: 'BBHMT'...На этом сообщении я и предположил, что функция selection работает при каких-то значениях не верно...Но так и не смог это доказать.

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Действительно, Selection содержит ошибку. RC23 распознается как формат R[number]C[number], хотя на самом деле это формат [column][row].

      Ещё есть баг в функции Power (несоответствие заявленных и реальных типов: в умножениях типа a*a результат имеет тип Integer, а не Int64), но в этой задаче, скорее всего, этот баг неактуален.

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится

        Простите, вы не правы по поводу RC23. Я запустил и все верно распозналось и вывелся верный ответ: R23C471. C Power согласен, но ошибка там не столь существенна

        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Прошу прощения, действительно, на том тесте работает.

          Но не работает на тесте чуть сложнее: RCC23.

          Почему так получилось: при взгляде на эту функцию сразу видно, что она неправильная, так как она делает вывод лишь по наличию букв R и C в каких-то фиксированных частях строки. А конкретный тест мне удалось подобрать только со второго раза.

          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            я исправил на это, вроде верно...но продолжает валиться...я просто не понимаю...

            function Selection(tmp: String): Boolean;
            var i,j: Integer;
            begin
              if tmp[1]='R' then
              begin
                Delete(tmp, 1, 1);
                i:=Pos('C', tmp);
                Delete(tmp, i, 1);
                j:=Length(tmp);
                for i := 1 to j do
                  if tmp[i] In ['0'..'9'] then
                  begin
                    Selection:=False;
                  end else begin
                    Selection:=True;
                    break;
                  end;
              end else
                Selection := True;
            end;
            
            • »
              »
              »
              »
              »
              »
              »
              12 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              Я бы сказал, что критерий проще — два символа подряд, первый из которых — цифра, а второй — буква ("C"). По крайней мере функция будет состоять из одного цикла с двумя проверками внутри.

              А то дерево ифов, которое есть сейчас, понять не так-то просто, логично, что в нём может быть ошибка. Например, может ли j оказаться нулём, в случае чего значение Selection вообще не определено.

              • »
                »
                »
                »
                »
                »
                »
                »
                12 лет назад, # ^ |
                  Проголосовать: нравится +5 Проголосовать: не нравится

                Блин, вы правы, вот в этом наверное и кроется ошибка, я почему-то не учел, что при наличии 'R' символа 'C' может не оказаться)

    • »
      »
      »
      12 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

      Дело не в этой задаче.

      Просто Вы недавно появились на CF, и все Ваши записи в блоге и комментарии делаются на тему "подскажите идею" или "найдите ошибку (с приложением исходника)". Если первое еще можно неопытностью оправдать, то со вторым — только в самостоятельной работе над поиском ошибок может быть смысл.

      Ну мне так кажется ... :)

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится +17 Проголосовать: не нравится

        Прежде чем сюда сделать пост я не менее 5 часов сижу над задачей. Но если я не понимаю, так может народ поможет, объяснит, что к чему. В своем творении трудно искать ошибки, часто даже дебагер не помогает...Ну я стараюсь)