основной форум
Архив сообщений 2004-2006 года

Алгоритмы, методы, исходники


Разное >> Замечания о работе сайта

Страницы: 1
Theoremmer
новичок


Рег.: 01/19/05
Сообщений: 19
Задача 119. Magic Pairs
      #2661 - 01/19/05 11:43 PM

В задаче Magic Pairs я никак не могу понять, почему мое решение не проходит.
(Wrong answer on test 4).
Суть его такова:
в качестве искомых пар (A,B) берем пары вида: (A0*i mod N, B0*i mod N)
Потом это дело сортируем. И выводим. Вроде верно.

Но вот этот код дает WA4

type
int=int64;
var
A: array[1..10500] of int;{Здесь будут искомые пары A,B}
B: array[1..10500] of int;

procedure sort(l,r: longint);{Обычный QSORT}
var
i,j,xa,xb,ya,yb: int;
begin
i:=l; j:=r; xa:=a[(l+r) DIV 2]; xb:=b[(l+r) DIV 2];
repeat
while (a<xa)or((a=xa)and(b<xb)) do i:=i+1;
while (xa<a[j])or((a[j]=xa)and(b[j]>xb)) do j:=j-1;
if i<=j then
begin
ya:=a; a:=a[j]; a[j]:=ya;
yb:=b; b:=b[j]; b[j]:=yb;
i:=i+1; j:=j-1;
end;
until i>j;
if l<j then sort(l,j);
if i<r then sort(i,r);
end;

var
N: longint;{Используем longint, так как int64 иногда глючит с read из файла}
A0, B0: longint;
i: longint;
ans: int;
begin
read(N, A0, B0);
A[1]:=A0;
B[1]:=B0;
ans:=1; {количество таких пар}
while (A[ans]<>0)or(B[ans]<>0) do begin
A[ans+1]:=(A[ans]+A0)mod N;
B[ans+1]:=(B[ans]+B0)mod N;
inc(ans);
end;
sort(1,ans);
writeln(ans);
for i:=1 to ans do writeln(a,' ',b);
end.

Вроде искодник мой достаточно прост. Что же не так?

На всякий случай, мое обоснование того, что можно брать пары вида: (A0*i mod N, B0*i mod N)

Предположим, что для любых X,Y таких, что A0*X+B0*Y делится на N также выполняется A*X+B*Y делится на N. Рассмотрим D=НОД(A0,N) и предположим A не делится на D. Тогда возьмем X=N/D, а Y=0. Тогда первое выполняется, а второе - нет, так как A не делится на D. Противоречие.
Таким образом A делится на НОД(A0,N), а B аналогично - на НОД(B0,N)
Теперь заметим, что взяв A0/D и складывая его само с собой много раз по модулю N/D получим в конце концов 1. (так как они взаимно просты) Поэтому можем получить любой остаток, в том числе и A/D. Поэтому из условия можем вывести для любого A некоторое A*X+B*Y. Причем, такая запись почти всегда единственна... ну кроме случаев A0, 0. и 0, B0. Ну а далее легко понять, что и в этих двух случаях алгоритм работает правильно.

А вопрос вот в чем: почему Wrong Answer 4?????
Может я просто где-то наглючил в реализации, а может быть, составил неправильный алгоритм. В любом случае, я не смог найти ошибку.


Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
SergeyevАдминистратор
заслуженный
****

Рег.: 07/31/04
Сообщений: 1361
Из: Россия, Самара
Re: Задача 119. Magic Pairs [Re: Theoremmer]
      #2664 - 01/20/05 12:10 AM

У вас qsort какой-то необычный, я не уверен что он отсортирует так как надо ответы: по возрастанию первых чисел, при равенстве по возрастанию вторых.
Когда закончится обсуждение темы - я ее удалю, извините, для обсуждения раздел не тот.


Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
Theoremmer
новичок


Рег.: 01/19/05
Сообщений: 19
Re: Задача 119. Magic Pairs [Re: Sergeyev]
      #2667 - 01/20/05 01:04 AM

Не возражаю против удаления темы ПОСЛЕ обсуждения.

Алгоритм-таки правильный?

А QSORT отличается от обычного тем, что работает сразу с двумя массивами. Поэтому меняет местами и сравнивает по два.

А на форуме отображается немного не то, что на деле. Надо, наверное, сделать ["code"]
Code:
 

type
int=int64;
var
A: array[1..10500] of int;
B: array[1..10500] of int;

procedure sort(l,r: longint);
var
i,j,xa,xb,ya,yb: int;
begin
i:=l; j:=r; xa:=a[(l+r) DIV 2]; xb:=b[(l+r) DIV 2];
repeat
while (a[i]<xa)or((a[i]=xa)and(b[i]<xb)) do i:=i+1;
while (xa<a[j])or((a[j]=xa)and(b[j]>xb)) do j:=j-1;
if i<=j then
begin
ya:=a[i]; a[i]:=a[j]; a[j]:=ya;
yb:=b[i]; b[i]:=b[j]; b[j]:=yb;
i:=i+1; j:=j-1;
end;
until i>j;
if l<j then sort(l,j);
if i<r then sort(i,r);
end;

var
N: longint;
A0, B0: longint;
i: longint;
ans: int;
begin
read(N, A0, B0);
A[1]:=A0;
B[1]:=B0;
ans:=1;
while (A[ans]<>0)or(B[ans]<>0) do begin
A[ans+1]:=(A[ans]+A0)mod N;
B[ans+1]:=(B[ans]+B0)mod N;
inc(ans);
end;
sort(1,ans);
writeln(ans);
for i:=1 to ans do writeln(a[i],' ',b[i]);
end.





Вот. Теперь вроде правильно отображается.

А что необычного в моем QSORT?????


Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
SergeyevАдминистратор
заслуженный
****

Рег.: 07/31/04
Сообщений: 1361
Из: Россия, Самара
Re: Задача 119. Magic Pairs [Re: Theoremmer]
      #2673 - 01/20/05 02:18 AM

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

Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
Theoremmer
новичок


Рег.: 01/19/05
Сообщений: 19
Re: Задача 119. Magic Pairs [Re: Sergeyev]
      #2687 - 01/20/05 03:07 AM

Я брал эту сортировку из Example-ов к Turbo Pascal 7.0
А вообще-то нечто похожее можно найти здесь на Алголисте. (только на С++)

http://algolist.manual.ru/sort/quick_sort.php

А порядок сортировки обеспечивается в условиях к двум While-ам.

элемент1<элемент2 - означает
(a[1]<a[2])or((a[1]=a[2])and(b[1]<b[2]))


Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
SergeyevАдминистратор
заслуженный
****

Рег.: 07/31/04
Сообщений: 1361
Из: Россия, Самара
Re: Задача 119. Magic Pairs [Re: Theoremmer]
      #2690 - 01/20/05 04:30 AM

Что я могу сказать? За исключением сортировки все абсолютно верно. Значит все таки что-то не так в сортировке. Есть решение которое прошло все тесты (в соответствующей теме этого же раздела), сделайте так: генерируйте случайный тест, запускайте свою программу, мою программу, сравниваете результаты. И так тысячи раз
Как обнаружите несовпадение - пишите, разберемся в чем ошибка. Тема до того пусть поживет.


Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
Theoremmer
новичок


Рег.: 01/19/05
Сообщений: 19
Re: Задача 119. Magic Pairs [Re: Sergeyev]
      #2721 - 01/21/05 07:38 AM

В ответ на:

Что я могу сказать? сделайте так: генерируйте случайный тест, запускайте свою программу, мою программу, сравниваете результаты. И так тысячи раз
Как обнаружите несовпадение - пишите, разберемся в чем ошибка. Тема до того пусть поживет.



Сделал. Запустил с батника 400 раз. Долго. Надо будет совместить две проги (каждую как процедуру) и сравнивать внутри - тогда будет раз в 10 быстрее. Но пока побайтовым сравнением разницы не обнаружено... Вот так. Причем я пару раз заглядывал во входные/выходные данные: там были сложные случаи
типа такого
9581
9273 8599
Там и сортировка по обоим показателям. И даже на таких тестах - все ОК...
Я не знаю в чем бага... Надо, конечно, совместить проги и протестить на большом количестве тестов... чем и займусь.

Теперь еще два вопроса:
1. Было сказано, что вообще-то по-хорошему, здесь не место для обсуждения?
Вопрос: где следует обсуждать решение задач с acm.sgu.ru как не в теме "решение задач с acm.sgu.ru"?
2. У меня еще был вопрос по Telecasting Station (там примерно та же история с непрохождением теста) - его где задавать?


Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
Theoremmer
новичок


Рег.: 01/19/05
Сообщений: 19
Re: Задача 119. Magic Pairs [Re: Theoremmer]
      #2722 - 01/21/05 08:26 AM

Уррааа!
Я тупой..............

Короче: написал я тестовую прогу и она на 50000 тестов все проверила. Все сошлось. В унынии я таки стал искать багу вручную начиная с условия. И как всегда она сидит у меня из-за невнимательности в его прочтении! Увы в исходном коде не все "абсолютно верно"

Обратить внимание следовало на следующие ошибочные строчки

Code:
  
A[1]:=A0;
B[1]:=B0;


После замены их на правильные
Code:
  
A[1]:=A0 mod N;
B[1]:=B0 mod N;


Было получено
Accepted

Вот такие пироги.
Остался вопрос: где таки задавать подобные вопросы (по решению задач с acm.sgu.ru), после ответа на который тему можно будет закрывать и ч/з некоторое время (чтоб я ответ прочел) удалять.

Большое спасибо за поддержку: хотя она и не принесла должного эффекта, но помогла мне не забить на эту задачу и, благодаря этому, найти ошибку!


Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
SergeyevАдминистратор
заслуженный
****

Рег.: 07/31/04
Сообщений: 1361
Из: Россия, Самара
Re: Задача 119. Magic Pairs [Re: Theoremmer]
      #2723 - 01/21/05 08:51 AM

Ах ну да, в моем решении я начинал с (0,0) рассматривать решения, так что такого вопроса даже не возникало...
Если у вас вопрос по задаче которая уже разобрана - пишите в той же теме, лишнее потом удалим. Если нет такой - создавайте новую тему в этом разделе (если конечно задача с acm.sgu.ru), только называйте тему так чтобы было понятно что там не решение.


Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
Theoremmer
новичок


Рег.: 01/19/05
Сообщений: 19
Re: Задача 119. Magic Pairs [Re: Sergeyev]
      #2726 - 01/21/05 10:08 AM

Все понял. Спасибо. Тему можно закрывать.

Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
Страницы: 1



Дополнительная информация
0 зарегистрированных и 161 анонимных пользователей просматривают этот форум.

Модератор:  Илья Кантор, Sergeyev 

Распечатать тему

Права
      Вы не можете создавать новые темы
      Вы не можете отвечать на сообщения
      HTML выключен
      UBBCode включен

Рейтинг:
Просмотры темы: 16470

Rate this topic

Переход в