ahmedarifhasan Ответов: 2

Тест-кейс, где этот код терпит неудачу?


Страница Конкурса | CodeChef[^]
Хотя код выглядит огромным, но идея довольно проста.

Никто не знает, но в саду шеф-повара живут N лягушек.

Теперь они сидят на оси Х и хотят поговорить друг с другом. Одна лягушка может послать сообщение другой, если расстояние между ними меньше или равно К.

Шеф-повар знает все P пар лягушек, которые хотят отправлять сообщения. Помогите ему определить, могут они или нет!

Примечание : более 1 лягушки могут находиться в одной и той же точке на оси X.


Ввод
Первая строка содержит три целых числа N, K и P.
Вторая строка содержит N целых чисел через пробел A1, A2, ..., AN, обозначающих x-координаты лягушек".
Каждая из следующих P строк содержит два целых числа A и B, обозначающих количество лягушек в соответствии с входными данными.


Выход
Для каждой пары выведите "да" без скобок, если лягушки могут говорить, и "нет", если они не могут.



Ограничения
1 ≤ N, P ≤ 10^5
0 ≤ Ai, K ≤ 10^9
1 ≤ A, B ≤ N




##Извините, если код не эффективен, я любитель в программировании, и я улучшу iA.

Что я уже пробовал:

#include<stdio.h>
#include<stdlib.h>

int main()
{
   long int counter, d, w, flag, temp, q, y, t, N, K, P, *e, *f, A, B, i, j;

   scanf("%ld%ld%ld",&N,&K,&P);
   e=(long int*)malloc(N*sizeof(long int));
   f=(long int*)malloc(N*sizeof(long int));
  
   counter=0; //so that the array is sorted only once i.e for i=0
  
   for(i = 0; i < N; i++ )
   { 
       scanf("%ld", e+i ); 
       *( f + i )  =  *( e + i );   
   }   
   for( t = 0; t < P; t++ )
   {
      scanf( "%ld%ld",&A, &B ); 

      w= *( f + A - 1 );  //contains the coordinate of x at Ath position
      q= *( f + B - 1 );  //contains the coordinate of x at Bth position
    
      if( abs( w - q ) <= K )
          printf("Yes\n");
      else
      {
          d = ( w < q ) ? w : q;  //d contains greater of the two coordinates
          if( counter == 0 )
          {
              for( i = 0; i < n; i++ ) //sorting only for c=0
              {
                  for( j = 0; j < n-1; j++ )
                  {
                      if( *( e + j ) >  *( e + j + 1 )   )
                      {
                          temp = *( e + j );
                          *( e + j ) = *( e + j + 1 );
                          *( e + j + 1 ) = temp;
                      }
                  }
              }
          }

          for( i = 0; i < N; i++ )
          { 
              if( *( e + i )  ==  d   )
                  break;
          }

          flag=0;
          while(1)
          {
              if( ( *(e+i+1) - *(e+i) ) > K )
              { 
                  flag=1;
                  break;
              }

              if( i == N-1 || (*( e + i + 1 )) == q )
              {
                  break;
              }
              i++;
          }

          if( flag == 0 )
              printf("Yes\n");
          else
             printf("No\n");
          counter++;
      }
   }
   return 0;
}

Richard MacCutchan

В чем вопрос (кроме того, кто пишет такой ужасный код)?

Richard MacCutchan

Я бы попытался помочь, если бы вы объяснили свою проблему, но так как вы этого не сделали, я не смог догадаться, в чем она заключалась. И этот код практически невозможно понять, со всеми этими однобуквенными именами переменных, которые ничего не значат.

Rick York

Нет, этот вопрос не упоминается выше. На самом деле, в вашем посте вообще нет никаких вопросов. Существует формулировка проблемы, которую вы пытаетесь решить, и ваша попытка решения. Итак, еще раз, в чем заключается ваш вопрос? Позвольте мне быть упреждающим в одном-если вы спрашиваете: "почему это не работает?" Я не знаю. Запустите отладчик и выясните это. Это то, что вы должны сделать, и вы не можете ожидать, что кто-то другой поймет это за вас. И еще одна вещь: когда большинство переменных названы одной буквой, любому гораздо труднее понять, что происходит.

Rick York

Еще один комментарий - Мне легче следовать ему, когда я использую нотацию индекса массива вместо разыменования указателей. Например, во внутренней части вашего цикла получение значений может быть записано следующим образом :

scanf( "%ld", &e[i] );
f[i] = e[i];

а первые задания w и q можно записать в виде :

w = f[A-1];
q = f[B-1];

Я думаю, что это гораздо более интуитивно и легко.

Rick York

Я заметил еще одну вещь - у вас есть scanf, который ищет два целых числа и передает ему строку формата "%ld%ld". Правильно ли это работает? У меня такое чувство, что этого не произойдет, потому что что будет разграничивать ценности? Я бы поставил пробел или запятую между ними в этой строке формата - "%ld %d". Я спрашиваю, потому что уже очень давно не писал консольной программы, которая запрашивала бы ввод.

2 Ответов

Рейтинг:
2

OriginalGriff

Попробуй n = -2 ...

И сделай себе одолжение! Прекратите использовать односимвольные имена для переменных: это легко ввести, но также легко ошибиться, и это делает код трудным для чтения - особенно когда он недокументирован, и мы понятия не имеем, что он должен делать...


ahmedarifhasan

я выложил выше ограничения

Rick York

Для имен переменных не существует ограничений. Просто потому, что определение проблемы использует однобуквенные имена, не означает, что вы должны это делать.

Рейтинг:
12

Patrice T

Цитата:
Тест-кейс, где этот код терпит неудачу?
Это ближе всего к вопросу. Мы понятия не имеем, в чем ваша проблема.

Предполагая, что вы не понимаете, почему ваш код терпит неудачу, есть 1 инструмент, который может вам помочь, это отладчик, он покажет вам, что делает ваш код вместе со значениями переменных.

Существует инструмент, который позволяет вам видеть, что делает ваш код, его имя отладчик Это также отличный инструмент обучения, потому что он показывает вам реальность, и вы можете увидеть, какие ожидания соответствуют реальности.
Когда вы не понимаете, что делает ваш код или почему он делает то, что он делает, ответ таков: отладчик.
Используйте отладчик, чтобы увидеть, что делает ваш код. Просто установите точку останова и посмотрите, как работает ваш код, отладчик позволит вам выполнять строки 1 на 1 и проверять переменные по мере их выполнения.

Отладчик - Википедия, свободная энциклопедия[^]

Освоение отладки в Visual Studio 2010 - руководство для начинающих[^]
Базовая отладка с помощью Visual Studio 2010 - YouTube[^]
Отладчик здесь, чтобы показать вам, что делает ваш код, и ваша задача-сравнить с тем, что он должен делать.
В отладчике нет никакой магии, он не находит ошибок, он просто помогает вам. Когда код не делает того, что ожидается, вы близки к ошибке.
Цитата:
Извините, если код не эффективен, я любитель программирования и буду улучшать iA.

Просто улучшение:
вы сортируете массив внутри цикла, но вы знаете, что никогда не будете сортировать его снова, поэтому вы помещаете код, чтобы предотвратить сортировку снова. почему бы вам не отсортировать массив перед входом в цикл?

CodeChef constests всегда требует умных решений, а прямой прямой код никогда не является решением.
Вам нужно знать, находится ли лягушка в данной позиции или нет, вам действительно не нужно сортировать массив позиций.
Что делать, если у вас есть массив позиций с 0 для пустых и 1, Если есть лягушка, просто чтение элемента массива говорит вам, есть ли лягушка, и вы можете заполнить массив без сортировки позиций.