Программа превышает ограничение по времени, что кажется невозможным - глючный код - PullRequest
Новая
       4

Программа превышает ограничение по времени, что кажется невозможным - глючный код

0 голосов
/ 03 апреля 2012

Это связано с математикой, но я публикую здесь свой код, так как, кажется, есть ошибка, которая ускользает от меня.

Вопрос :

Два робота A & B стоят на позиции 0, расположенной на бесконечно длинной прямой линии.Робот A может двигаться влево или вправо на a или b единиц, и робот B может делать то же самое, но c или d единиц.Они должны нажать кнопку, которая лежит на этой прямой линии, на расстоянии не более чем k единиц от 0.На сколько позиций p i вы можете разместить кнопку так, чтобы оба робота могли нажимать на нее (достигать ее на самом деле), независимо друг от друга.Таким образом, входные данные представляют собой 5 натуральных чисел в 1 строке: a , b , c , d , k .

Ограничения: 0 ≤ a, b, c, d, k ≤ 10 18 и количествотестовые случаи t где 1 ≤ t ≤ 1000 .

Ограничение времени: 1 сек

Например: робот A ( a = 1, b = 2), робот B ( c = 4, d = 5), диапазон: k = 1

Ответ в этом случае 3 .

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

Мое решение:

Пусть m = LCM (HCF ( a * 1094)*, b ), HCF ( c , d ))

Ответ = 2 * [ k / m ] + 1

[] обозначает наибольшую целочисленную функцию (только во избежание путаницы).

На короткой ноте (для тех, кто интересуется вопросом)все, что я сделал, это проверил, сколько кратных m существует в диапазоне k с обеих сторон, плюс позиция 0 .HCF(a,b) даст кратчайший шаг, который может сделать робот, а LCM из обоих HCF даст наименьшую общую позицию, на которой они могут стоять.Тогда найди нет.

Код (C ++): 

  1 #include <cstdio>
  3 using namespace std;
  4 typedef long long LL;
  5 
  6 inline void swap(LL *a, LL *b)
  7 {
  8     *a ^= *b;
  9     *b ^= *a;
 10     *a ^= *b;
 11 }
 12 
 13 long hcf(LL a, LL b)
 14 { return !a || !b ? a+b : hcf(b,a%b); }
 15 
 16 LL lcm(LL a, LL b)
 17 {
 18     if(a < b) swap(&a,&b);
 19     LL i=a;
 20     while(a%b) a+=i;
 21     return a;
 22 }
 23 
 24 int main()
 25 {
 26     int t; scanf("%d\n",&t);
 27     while(t--)
 28     {
 29         LL a,b,c,d,k;
 30         scanf("%lld %lld %lld %lld %lld",&a,&b,&c,&d,&k);
 31         printf("%lld\n", 1 + ((k / (lcm(hcf(a,b), hcf(c,d))) ) << 1) );
 32     }
 33     return 0;
 34 }

Я просто реализовал свой ответ.Я также выполнил свою программу через 1000 тестовых случаев, каждый из которых состоял из случайных + целых чисел в диапазоне [10 16 , 10 18 ].Я делал это несколько раз, и наихудшее потребление времени было 0,01 сек.

Теперь, когда я отправляю этот код на страницу конкурса, я получаю ошибку Time Limit Exceeded!Это невозможно, если какой-то глючный цикл не работает бесконечно для определенного ввода.Я подумал, что должен принять мнение экспертов о том, почему мой код истекает.Пожалуйста, помогите

PS: Если у вас есть лучший ответ на вопрос, добро пожаловать: -)

Редактировать : PS: Я с подозрением относился к тому, как я обрабатывал большиецелые числа в C++, поэтому я сделал преобразование в python и также отправил его, что снова привело к ошибке Time Limit Exceeded.

Ответы [ 2 ]

0 голосов
/ 03 апреля 2012

Обратите внимание, что этот код очень опасен: 

inline void swap(LL *a, LL *b)
{
   /* sometimes also written as *a^=*b^=*a^=*b;  */
    *a ^= *b;
    *b ^= *a;
    *a ^= *b;
}

Если a и b когда-либо указывают на одну и ту же память, это приведет к обнулению этой памяти.

(попробуйте поменять строку с нечетным количеством букв, используя этот своп) 

char* input = "abcde"
for(i=0, j=4; i<3; ++i, --j)
{
    swap(input+i, input+j);
}
// Result:  "ed0ba".
// With a normal-swap, 'c' would get swapped with 'c', returning "edcba"
0 голосов
/ 03 апреля 2012

Ваш код заполнен scanf звонками, которые читаются с stdin.Он будет зависать бесконечно, если не будет введен ввод.В большинстве конкурсов ваш код не читается с stdin.Что, согласно правилам, является источником информации?

...