Theoremmer
новичок
Рег.: 01/19/05
Сообщений: 19
|
|
В задаче 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
Из: Россия, Самара
|
|
У вас qsort какой-то необычный, я не уверен что он отсортирует так как надо ответы: по возрастанию первых чисел, при равенстве по возрастанию вторых. Когда закончится обсуждение темы - я ее удалю, извините, для обсуждения раздел не тот.
|
Theoremmer
новичок
Рег.: 01/19/05
Сообщений: 19
|
|
Не возражаю против удаления темы ПОСЛЕ обсуждения. 
Алгоритм-таки правильный?
А 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
Из: Россия, Самара
|
|
Что-то я не могу понять логику вашей сортировки... Вы это сами придемали? Я не могу понять почему она сортирует массив именно как в условии задачи - по первым числам, при их равенстве по вторым. Попробуйте сделать по простому, должно прокатить.
|
Theoremmer
новичок
Рег.: 01/19/05
Сообщений: 19
|
|
Я брал эту сортировку из 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
Из: Россия, Самара
|
|
Что я могу сказать? За исключением сортировки все абсолютно верно. Значит все таки что-то не так в сортировке. Есть решение которое прошло все тесты (в соответствующей теме этого же раздела), сделайте так: генерируйте случайный тест, запускайте свою программу, мою программу, сравниваете результаты. И так тысячи раз  Как обнаружите несовпадение - пишите, разберемся в чем ошибка. Тема до того пусть поживет.
|
Theoremmer
новичок
Рег.: 01/19/05
Сообщений: 19
|
|
В ответ на:
Что я могу сказать? сделайте так: генерируйте случайный тест, запускайте свою программу, мою программу, сравниваете результаты. И так тысячи раз  Как обнаружите несовпадение - пишите, разберемся в чем ошибка. Тема до того пусть поживет.
Сделал. Запустил с батника 400 раз. Долго. Надо будет совместить две проги (каждую как процедуру) и сравнивать внутри - тогда будет раз в 10 быстрее. Но пока побайтовым сравнением разницы не обнаружено... Вот так. Причем я пару раз заглядывал во входные/выходные данные: там были сложные случаи типа такого 9581 9273 8599 Там и сортировка по обоим показателям. И даже на таких тестах - все ОК... Я не знаю в чем бага... Надо, конечно, совместить проги и протестить на большом количестве тестов... чем и займусь.
Теперь еще два вопроса: 1. Было сказано, что вообще-то по-хорошему, здесь не место для обсуждения? Вопрос: где следует обсуждать решение задач с acm.sgu.ru как не в теме "решение задач с acm.sgu.ru"? 2. У меня еще был вопрос по Telecasting Station (там примерно та же история с непрохождением теста) - его где задавать?
|
Theoremmer
новичок
Рег.: 01/19/05
Сообщений: 19
|
|
Уррааа! Я тупой..............
Короче: написал я тестовую прогу и она на 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
Из: Россия, Самара
|
|
Ах ну да, в моем решении я начинал с (0,0) рассматривать решения, так что такого вопроса даже не возникало... Если у вас вопрос по задаче которая уже разобрана - пишите в той же теме, лишнее потом удалим. Если нет такой - создавайте новую тему в этом разделе (если конечно задача с acm.sgu.ru), только называйте тему так чтобы было понятно что там не решение.
|
Theoremmer
новичок
Рег.: 01/19/05
Сообщений: 19
|
|
Все понял. Спасибо. Тему можно закрывать.
|