002 Algoritmul lui Euclid extins

[•toni2007]

Cred ca e de la citire . Citeste direct cu readln. Eu cand am rezolvat asta am facut citirea in felul urmator:

Cod:

 
begin  
     assign(stdin,'euclid2.in');reset(stdin);  
     assign(stdout,'euclid2.out');rewrite(stdout);  
     readln(stdin,t);  
     for i:=1 to t do begin  
         readln(stdin,a,b);  
         writeln(stdout,cmmdc(a,b));  
     end;  
     close(stdin);  
     close(stdout);  
end.  

[•CezarMocan]

Eu stiam ca e in loc de stdin si stdout in Pascal sunt input si output . Si nu e nevoie sa scrii

Cod:

readln(input, a);

E de ajuns

Cod:

readln(a);

[•toni2007]

Da stiu . Doar ca atunci cand am rezolvat problema nu stiam smenul asta. Oricum nu cred ca este mai rapid asa. Cum am facut eu specifici explicit streamul de intrare, deci e posibil sa mearga mai rapid. E cam aceeasi chestie ca si cu scanf / printf vs fscanf / fprintf.

[•marcelcodrea]

Cred ca ar fi util daca ar exista si un link catre o solutie iterativa in pagina problemei.

Uite una :
http://infoarena.ro/job_detail/266684?action=view-source

[•andreirulzzz]

ce este gresit la sursa asta? nu imi dau seama deloc 
http://infoarena.ro/job_detail/272718

*am gasit greseala, functia cmmdc utiliza valori integer, le-am schimbat in longint si am luat 100 pct

[•Davide]

Unii oameni nu stiu sa faca nimic simplu? Programul meu nu foloseste algorimtul asta, si, chiar mai mult, returneaza mai mult de o valoare.

Cod:

program euclidextins;

var a,b,c,x,y,i,t:integer;

begin
     readln (a);
     readln (b);
     readln (c);
     {read}

     for x:=-c to c do
         for y:=-c to c do
             if (a*x+b*y=c) then writeln (a,'*',x,'+',b,'* ',y,'=',c);
     readln;
end.

[editat] Chiar daca se vede frumos si cum ai facut tu, data viitoare foloseste tag-ul "code"

[•bogdan2412]

Programul tau nu o sa intre in timp pentru date de intrare mari. Trimite sursa si vezi cate puncte iei. Dupa cum scrie si in explicatie, se poate extinde programul care foloseste algoritmul lui euclid sa returneze mai multe valori (sunt o infinitate de solutii ).

[•hominidu]

ba s-a stricat monitoru de evaluare sau de ce arata in continuu in asteptare? nu mai are nici un farmec infoare daca nu verifica problemle

[•mimarcel]

prima mea pb rezolvata... am primit 100 pcte dar am creat acasa un fisier cu 100000 de numere si programul a terminat executia in 0.6 secunde pt datele din acest fisier (am cronometrat). deci depaseste timpul de executie din pb si totusi... am primit punctaj maxim

[•Florian]

Dupa cum vezi in enunt, la restrictii, se precizeaza ca sunt maxim 100 de teste (T<=100). 

[•marcelcodrea]

prima mea pb rezolvata... am primit 100 pcte dar am creat acasa un fisier cu 100000 de numere si programul a terminat executia in 0.6 secunde pt datele din acest fisier (am cronometrat). deci depaseste timpul de executie din pb si totusi... am primit punctaj maxim

Daca te referi la sursa asta cred ca voiai sa scrii aici aici.
In ceea ce priveste diferenta dintre timpii de executie de acasa si cei de pe infoarena, trebuie sa stii ca evaluatorul infoarena ruleaza pe Linux unde timpii de evaluare sunt considerabil mai mici si in plus poate are o configuratie diferita de cea a PC-ului tau.

[•mimarcel]

prima mea pb rezolvata... am primit 100 pcte dar am creat acasa un fisier cu 100000 de numere si programul a terminat executia in 0.6 secunde pt datele din acest fisier (am cronometrat). deci depaseste timpul de executie din pb si totusi... am primit punctaj maxim

Daca te referi la sursa asta cred ca voiai sa scrii aici aici.
In ceea ce priveste diferenta dintre timpii de executie de acasa si cei de pe infoarena, trebuie sa stii ca evaluatorul infoarena ruleaza pe Linux unde timpii de evaluare sunt considerabil mai mici si in plus poate are o configuratie diferita de cea a PC-ului tau.

mersi pt raspuns  si scuze de greseala, dar cand am dat click pe "Lasa un comentariu" am ajuns la pagina asta de forum

[•pasarila]

Cod:

Non-zero exit status.

Conditia asta unde trebuie pusa ?

[•Florian]

Cod:

Non-zero exit status.

Conditia asta unde trebuie pusa ?

Nu e conditie. Este un doar unul din mesajele returnate de evaluator. 

[•pasarila]

Pai pentru asta eu iau 0 puncte.

[•alexandru92]

Non-zero exit status

Din cate stiu eu dupa terminare un program returneaza 0 -daca executarea s-a incheiat cu bine si diferit de 0 altfel

[•toni2007]

Omul a codat in pascal. Pascalul, din cate stiu eu, cand sunt greseli (deschide fisier inexistent pentru citire, face overflow la variabile, etc), returneaza numarul erorii ca exit code, si inchide programul. In cazul de fata, el a deschis fisierele euclid.in/euclid.out in loc de euclid2.in/euclid2.out. Aici e greseala.

[•mika17]

Salutare,
Am luat si eu 100 la aceasta problema dar tot am o nelamurire.
Daca folosesc euclid extins si inmultesc apoi cu c / cmmdc
De ce tot timpul solutiile se incadreaza in +/-2 miliarde ? pt a si b foarte mari adica, e vreun rationament matematic implicat?  Adica asa se intampla, dar nu imi dau seama de ce

si exista vreo metoda prin care sa  aflu de ex  solutiile ecuatiei ax + by = c de modul minim?

[•cristiprg]

imi zice   Solutie gresita la ecuatia 8 (30 -80 350) si rezultatul afisat ii 1 -4, de ce nu e corect ? si la mai multe face asa ...  http://infoarena.ro/job_detail/361212

[•O_Neal]

am si eu doua nelamuriri ..
prima: de ce daca c divide pe d , si NUMAI atunci exista solutii pentru ecuatie? daca .. sa presupun asa.. matematic ca exista un t pt care a*x + b*y = t ... (care este mai mic decat d, dar nu neaparat cred ).. in cazul in care exista atunci poate c nu se divide la d, dar se divide la t.. si ecuatia ar avea solutii.. astept va rog care aveti idei un argument pt chestia asta.. ca eu nu inteleg treaba asta, in rest am inteles totul ( cred ) foarte bine.. intradevar exista un d, d fiind cmmdc care sa rezolve ecuatia a*x + b*y .. bun dar de ce nu ar exista si alte valori dupa care sa ne luam? Adica nu inteleg de ce ne legam neaparat de cmmdc... daca pur si simplu exista (caci sigur exista ) alte valori diferite de d, egale cu a*x+b*y... si problema s-ar pune la acele valori care il divid pe c, in timp ce cmmdc(a,b) nu ar divide pe c, ar exista o solutie ..sper ca ma intelgeti careva.. imi transpun greu gandurile.. Problema am rezolvat-o de 100 de puncte, considerand cele spuse la indicatii ca fiind adevarate.. dar as vrea o mica demonstratie matematica, un argument ceva, sa fiu eu convins... pt ca nu sunt pe deplin convins ca cele presupuse pt rezolvare sunt adevarate..

a doua nelamurire: De ce indicatiile ne spun sa folosim algoritmul lui euclid extins, iar in exemple, se dau ca si solutii altele decat solutiile obtinut cu acest algoritm ? Eu unul am aplicat algoritmul si am obtinut solutii total diferite ( bune si ele,pt ca am luat 100, precum si alea din exemple ) insa nu inteleg.. ce algoritm s-a folosit pt determinarea solutiilor din exemple? ( presupun ca altul, ca euclid extins da pt valorile alea altceva )
multumesc anticipat.. sper sa intelegeti ce vroiam sa zic..

[•ionutz32]

1) In enunt scrie:

In cazul in care c nu se divide cu d ecuatia nu poate fi rezolvata in multimea numerelor intregi

Intotdeauna exista o infinitate de solutii.
Daca notam d=cmmdc(a,b), prod1=a/d, prod2=b/d, inseamna ca prod1,prod2 sunt intregi si avem
a*x+b*y=c
prod1*d*x+prod2*d*y=c
d*(prod1*x+prod2*y)=c
Daca d nu il divide pe c, atunci numarul c/d nu o sa fie intreg, ceea ce inseamna ca cel putin unul din numerele prod1*x si prod2*y apartine lui Q\Z, si cum prod1 si prod2 sunt din Z, inseamna ca ecuatia nu admite solutii intregi.

2) In enunt scrie:

In cazul in care exista mai multe solutii pentru o ecuatie, se poate afisa oricare solutie pentru care necunoscutele nu depasesc in valoare absoluta 2 000 000 000

Algoritmul lui Euclid extins e doar o metoda prin care poti sa afli o solutie a ecuatiei intotdeauna cand exista (in Z). Tu poti sa folosesti si un algoritm brut, dar nu o sa iei punctajul maxim.

[•O_Neal]

1) da.. asa e .. corect.. in enunt era numa specificat stii .. dar asa e totul clar si demonstrat frumos ca e adevarat...
2) pai da corect lol dar nu ti se pare putin ilogic? tocmai ca zice ca alte variante nu or sa obtine punctaj maxim, atunci de ce ar da solutiile de la alti algoritmi? chiar nu mi se pare deloc logic.. acuma noah in fine .. is exemple is corecte nu ai ce sa zici .. dar din moment ce se indica o metoda si se zice ca ar exista altele dar nu intocmai bune pt ca sa intre in timp si etc pai e logic sa dai exemple cu solutii pe metoda aia.. altfel noah.. toata chestia e ca , eu unul cel putin mi-am batut  capu destul de mult timp sa vad de ce nu imi da mie bine, ca eu luam exemplele alea drept sfante .. mi-o luat  ceva sa imi dau seama, si ceva imi spune ca nu doar eu ..

ma rog, multumesc pentru lamuriri.. 

[•SpiderMan]

1) da.. asa e .. corect.. in enunt era numa specificat stii .. dar asa e totul clar si demonstrat frumos ca e adevarat...
2) pai da corect lol dar nu ti se pare putin ilogic? tocmai ca zice ca alte variante nu or sa obtine punctaj maxim, atunci de ce ar da solutiile de la alti algoritmi? chiar nu mi se pare deloc logic.. acuma noah in fine .. is exemple is corecte nu ai ce sa zici .. dar din moment ce se indica o metoda si se zice ca ar exista altele dar nu intocmai bune pt ca sa intre in timp si etc pai e logic sa dai exemple cu solutii pe metoda aia.. altfel noah.. toata chestia e ca , eu unul cel putin mi-am batut  capu destul de mult timp sa vad de ce nu imi da mie bine, ca eu luam exemplele alea drept sfante .. mi-o luat  ceva sa imi dau seama, si ceva imi spune ca nu doar eu ..

ma rog, multumesc pentru lamuriri.. 

Eu nu cred ca solutiile le-or determinat cu algoritm, cred ca au fost puse rezolvari pe care le-au luat ei (adica ei au pus in fisierul de intrare valori care stiau rezultatul, si l-au scris in fisierul de iesire fara sa mai ruleze programul) sau au facut brute force pentru ca sunt mai multe solutii si asa sa le ia pe fiecare

[•devilkind]

eu luam exemplele alea drept sfante .. mi-o luat  ceva sa imi dau seama, si ceva imi spune ca nu doar eu ..

Nu e bine sa pui accent prea mare pe exemple. In general nici pe infoarena, nici la olimpiada, nu vei gasi exemple foarte bune. Vei primi niste exemple care sa nu te ajute in mare cu absolut nimic, decat sa intelegi cat de cat problema.

[•O_Neal]

asa e doar ca intr-un an .. la olimpiada.. o fost dat la o problema enuntu gresit si exemplu corect.. enuntul corect a ajuns destul de tarziu la elevi asa ca cei care s-au luat dupa exemplu au avut un mare avantaj.. si oricum cand faci orice problema e normal sa testezi pe exemplu dat si sa te alarmezi daca nici macar ala nu iti da bine, nu? dar da e adevarat exemplu e doar un exemplu..