infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva educationala => Subiect creat de: Andrei Grigorean din Februarie 26, 2008, 11:06:29


Titlul: 000 Algoritmul lui Euclid
Scris de: Andrei Grigorean din Februarie 26, 2008, 11:06:29
Aici puteti discuta despre problema Algoritmul lui Euclid (http://infoarena.ro/problema/euclid2).

Titlul: Răspuns: 000 Algoritmul lui Euclid
Scris de: Andrei Grigorean din Martie 04, 2008, 15:26:11
Din pacate ia 100 de puncte si o solutie (http://infoarena.ro/job_detail/148546?action=view-source) in O(sqrt(A)).

Titlul: Răspuns: 000 Algoritmul lui Euclid
Scris de: Adrian Diaconu din Martie 04, 2008, 18:29:33
Cel mai bine era sa se dea mai multe teste in fisier. (ca la euclid3)

Titlul: Răspuns: 000 Algoritmul lui Euclid
Scris de: Filip Cristian Buruiana din Martie 10, 2008, 16:13:58
Datorita ineficientei testelor, la aceasta problema s-au schimbat atat enuntul, cat si testele folosite pentru evaluare. In consecinta, s-a facut o reevaluare a tuturor surselor trimise pana in prezent. Ne cerem scuze pentru eventualele neplaceri.

Titlul: Răspuns: 000 Algoritmul lui Euclid
Scris de: Mazilu Victor din Martie 21, 2008, 23:41:20
Ceva fooarte ciudat...  cum se face ca sursa asta :
Citat
#include <stdio.h>   
 
int T, A, B;   
 
int gcd(int a, int b)   
{   
    if (!b) return a;   
    return gcd(b, a % b);   
}   
 
int main(void)   
{   
    freopen("euclid2.in", "r", stdin);   
    freopen("euclid2.out", "w", stdout);   
 
    scanf("%d", &T);   
    for (; T; --T)   
    {   
        scanf("%d %d", &A, &B);   
        printf("%d\n", gcd(A, B));   
    }           
 
    return 0;   
} 

     - care este a lui Buruiana Filip, ia 100 de puncte, pe cand sursa mea-->
Citat
#include<iostream.h>   
#include<fstream.h>   
 
int t,a,b;   
 
  int cmmdc(int a, int b)   
  {   
       if(!b) return a;   
       return cmmdc(b,a%b);   
  }   
 
 
  int main()   
 {   
  ifstream f("euclid2.in");   
  ofstream g("euclid2.out");   
 f>>t;   
 for(t;t;--t)   
  {f>>a>>b;   
  g<<cmmdc(a,b)<<endl;   
  }   
  return (0);   
  } 
- care este absolut identic cu a lui Buruiana, ia numai 40 de puncte, dandu-mi TLE pe ultimele teste ???

Titlul: Răspuns: 000 Algoritmul lui Euclid
Scris de: Andrei Grigorean din Martie 22, 2008, 00:07:46
Am facut si eu o sursa cu streamuri, am luat tot 40 :). Nu e vina ta, se pare ca merg stremurile prea prost.

Titlul: Răspuns: 000 Algoritmul lui Euclid
Scris de: Stefan-Alexandru Filip din Martie 23, 2008, 14:09:22
Din contra, streamurile merg mai repede. Lui victor ii ia foarte mult afisarea pentru ca foloseste 'endl'. Acesta din urma goleste bufferul dupa fiecare numar afisat. In locul lui ar trebui folosit '\n'. Lui wefgef cred ca ii merge incet pentru ca foloseste obiectele 'cin' si 'cout', care probabil nu sunt optimizate pentru citirea si respectiv scrierea in fisiere (posibil sa aibe un buffer mai mic sau deloc).

Titlul: Răspuns: 000 Algoritmul lui Euclid
Scris de: Andrei Grigorean din Martie 23, 2008, 14:30:36
Mersi Prostule :). O sa incerc din nou, sa vad cum merge.

Titlul: Răspuns: 000 Algoritmul lui Euclid
Scris de: Herpesius din Aprilie 04, 2008, 17:58:31
La nationala pot folosi streamuri (in sensul efectivităţii).. adică ce e mai rapid .. un freopen sau un stream ?

Titlul: Răspuns: 000 Algoritmul lui Euclid
Scris de: Bogdan-Alexandru Stoica din Aprilie 04, 2008, 18:12:35
poti sa folosesti. teoretic merge mai repede cu streamuri.

Citat din mesajul lui: Filip Stefan A. din Martie 23, 2008, 14:09:22
Din contra, streamurile merg mai repede. Lui victor ii ia foarte mult afisarea pentru ca foloseste 'endl'. Acesta din urma goleste bufferul dupa fiecare numar afisat. In locul lui ar trebui folosit '\n'. Lui wefgef cred ca ii merge incet pentru ca foloseste obiectele 'cin' si 'cout', care probabil nu sunt optimizate pentru citirea si respectiv scrierea in fisiere (posibil sa aibe un buffer mai mic sau deloc).

uite-te peste sursele de care vorbeste Filip ca sa te lamuresti :)

Titlul: Răspuns: 000 Algoritmul lui Euclid
Scris de: Herpesius din Aprilie 04, 2008, 18:21:39
Păi, ca să mă asigur ,am făcut aceiaşi problemă atât cu streamuri , cât şi cu citirea standard din C.

cu streamuri (http://infoarena.ro/job_detail/171656)
fără streamuri (http://infoarena.ro/job_detail/171659)

Observ că la citirea standard este folosită mult mai puţina memorie.. (diferenţă de peste 100KB faţă de citirea cu streamuri) , ar trebui să mă îngrijoreze asta la unul dintre subiectele de la naţională?


L.E.: îmi place citirea standard din C , la faza:
Cod:
char c;
while(scanf("%c",&c)!=EOF)
   { fă-Å£i treaba }

Titlul: Răspuns: 000 Algoritmul lui Euclid
Scris de: Tataranu Vlad din Aprilie 04, 2008, 20:46:57
Citat din mesajul lui: lezr rEbyTer din Aprilie 04, 2008, 17:58:31
La nationala pot folosi streamuri (in sensul efectivităţii).. adică ce e mai rapid .. un freopen sau un stream ?
In sensul efectivitatii (http://dexonline.ro/search.php?cuv=efectiv) streamurile sunt mai dubioase, compilatorul le aduce dintr-un univers paralel si asta dureaza mult timp.
Ai aici (http://infoarena.ro/forum/index.php?topic=2949.msg24392#msg24392) un experiment legat de efectivitate, in caz ca vrei sa studiezi mai indeaproape subiectul.

PS: Pe versiuni de gcc mai vechi parca mergeau mai incet streamurile, nu?

Titlul: Răspuns: 000 Algoritmul lui Euclid
Scris de: Herpesius din Aprilie 04, 2008, 21:32:45
Citat
PS: Pe versiuni de gcc mai vechi parca mergeau mai incet streamurile, nu?

Da.

Este prea efectiv sa folosesc cuvantul "efectiv" . Vroiam să spun eficient . Dar doar vroiam #-o .

Titlul: Răspuns: 000 Algoritmul lui Euclid
Scris de: Simoiu Robert din Aprilie 02, 2010, 18:23:39
Imi explica si mie de ce la problema alg. lui euclid, la comentarii este link catre alg. lui euclid extins ? Merci.
[LE] Vad ca s-a rezolvat. Good job  :ok:

Titlul: Răspuns: 000 Algoritmul lui Euclid
Scris de: Daniel Alexandru Radu din Septembrie 08, 2010, 03:20:21
Citat
Pentru a imbunatati timpul de rulare putem folosi algoritmul lui Euclid prin scaderi, ceea ce duce la obtinerea a 60 de puncte

cum se face ca am luat 100 cu euclid?
nu ca m-ar deranja

Titlul: Răspuns: 000 Algoritmul lui Euclid
Scris de: Paul-Dan Baltescu din Septembrie 08, 2010, 05:40:38
Pentru ca ai implementat prin impartiri. Citeste si tu ce citezi si apoi posteaza.

Titlul: Răspuns: 000 Algoritmul lui Euclid
Scris de: Stochitoiu Radu din Decembrie 03, 2010, 20:23:48
nu inteleg de ce iau punctaj atat de mic ... nu pot sa pricep ... am modificat sursa de cateva ori dar degeaba :| imi puteti da o indicatie? ma puteti ajuta va rog?

Cod:
#include<iostream.h>
#include<fstream.h>
int t,i,a,r,b;
int main()
{
	fstream f("euclid2.in",ios::in);
	fstream g("euclid2.out",ios::out);
f>>t;
if(t<=100000&&t>=1)
for(i=1;i<=t;i++)
{
	f>>a>>b;
	while(b!=0){
		r=a%b;
		a=b;
		b=r;}
	g<<a<<endl;
}
f.close();g.close();
return 0;
}

Editat de admin: Foloseste tagul "code" cand postezi surse.

Titlul: Răspuns: 000 Algoritmul lui Euclid
Scris de: Mihai Calancea din Decembrie 03, 2010, 20:38:39
De la endl ti se trage. Inlocuieste-l cu "\n".

Titlul: Răspuns: 000 Algoritmul lui Euclid
Scris de: Balan Radu Cosmin din Decembrie 06, 2010, 03:02:30
Eu zic asa:
-Schimba <fstream.h> in <fstream> si scrie dupa using namespace std;.
-Declara variabilele tale ca fiind locale si nu globale.

Titlul: Răspuns: 000 Algoritmul lui Euclid
Scris de: Pripoae Teodor Anton din Decembrie 06, 2010, 08:36:20
Citat din mesajul lui: Balan Radu Cosmin din Decembrie 06, 2010, 03:02:30
Eu zic asa:
-Schimba <fstream.h> in <fstream> si scrie dupa using namespace std;.
-Declara variabilele tale ca fiind locale si nu globale.


N-are nicio legatura ca a inclus "fstream.h" in loc de "fstream", pe infoarena e gcc 4.2. Abia din 4.3 e "fstream.h" deprecated. Iar legat de variabile, crede-ma ca n-are nicio importanta daca sunt locale sau globale, la cate are. Compilatorul isi face oricum niste optimizari.

Problema e de la endl. Endl goleste buffer-ul de scriere de fiecare data, pe cand afisarea "\n" nu. E ca si cum ai face fflush de fiecare data.

Titlul: Răspuns: 000 Algoritmul lui Euclid
Scris de: Junc Raul Cosmin din Februarie 27, 2011, 21:02:38
Imi poate zice si mie ce ii gresit la codul asta?

int cmmdc(int a, int b)
{
   if(!b) return a;
   return cmmdc(b, a % b);
}

Iar apelul e aici.
   f >> n;
   for(i = 0; i < n; i ++)
   {
      f >> a >> b;
      g << cmmdc(a, b) << endl;
   }
Imi da doar 30 de pc... si zice ca am depasit timpul. De ce?

Titlul: Răspuns: 000 Algoritmul lui Euclid
Scris de: Macarescu Sebastian din Februarie 27, 2011, 21:09:05
Incearca sa inlocuiesti endl cu '\n'. Citeste mai sus de ce nu e indicat endl.

Titlul: Răspuns: 000 Algoritmul lui Euclid
Scris de: Petrean Vlad din Octombrie 12, 2012, 12:55:35
E prea smecher tipul asta :yahoo: :yahoo: :rotfl:

Titlul: TLE
Scris de: Galatanu Tiberiu din Octombrie 22, 2012, 18:34:56
Imi ziceti si mie cum as putea optimiza programul cami da TLE pe ultimele 2 teste.

Cod:
var f,g:text;
    a,b,t,i:longint;
    v1,v2:array[1..1000] of longint;
begin
  assign(f,'euclid2.in');
  assign(g,'euclid2.out');
  settextbuf(f,v1);
  settextbuf(g,v2);
  reset(f);
  rewrite(g);
  readln(f,t);
  for i:=1 to t do
    begin
      readln(f,a,b);
      while a<>b do
        if a>b then
          dec(a,b)
        else
          dec(b,a);
      writeln(g,a);
    end;
  close(f);
  close(g);
end.

Titlul: Răspuns: 000 Algoritmul lui Euclid
Scris de: George Marcus din Octombrie 22, 2012, 19:02:29
In pagina problemei zice clar ca metoda cu scaderi nu intra in timp.

Titlul: Răspuns: 000 Algoritmul lui Euclid
Scris de: Galatanu Tiberiu din Octombrie 22, 2012, 19:57:00
Citat
In pagina problemei zice clar ca metoda cu scaderi nu intra in timp.
Mersi. Nu vazusem unde scrie chestia asta :mrgreen:. Acum am refacut problema si am luat 100.

Titlul: Răspuns: 000 Algoritmul lui Euclid
Scris de: Oprea George Alexandru din Iunie 06, 2013, 22:47:04
nu inteleg ce este gresit la programul asta :@  ](*,)

#include<iostream>
using namespace std;
int main(){
   int i,a,b;
   cin>>a,b;
   if(a>=b){
      for(i=b;i!=0;i--)
         if(a%i==0&&b%i==0){
            cout<<i;
            break;
         }
   }
   else
      if(a<=b){
         for(i=a;i!=0;i--)
         if(a%i==0&&b%i==0){
            cout<<i;
            break;
         }
      }
}
 :angry:

Titlul: Răspuns: 000 Algoritmul lui Euclid
Scris de: Daniel Alexandru Radu din Iunie 07, 2013, 08:28:38
Nu poti citi
Cod:
cin >> a,b;
daca vrei sa le citesti dintr-un singur input poti folosi
Cod:
cin >> a >> b;

Aici ai mai multe detalii
http://www.cplusplus.com/reference/iostream/cin/?kw=cin (http://www.cplusplus.com/reference/iostream/cin/?kw=cin)

Titlul: Răspuns: 000 Algoritmul lui Euclid
Scris de: Maxim Valentin-Constantin din August 23, 2013, 01:35:07
Citat din mesajul lui: Mihai Calancea din Decembrie 03, 2010, 20:38:39
De la endl ti se trage. Inlocuieste-l cu "\n".
Esti zeu fratele meu  :winner1:, poftimn si tu, ambele cu fstream, ambele acelasi format, un singur cuvant ce am inlocuit  #-o.
30 puncte, "endl": http://www.infoarena.ro/job_detail/988519?action=view-source (http://www.infoarena.ro/job_detail/988519?action=view-source) ( randul 53 )
100 puncte, '\n': http://www.infoarena.ro/job_detail/988520?action=view-source (http://www.infoarena.ro/job_detail/988520?action=view-source) ( randul 53 )

Titlul: Răspuns: 000 Algoritmul lui Euclid
Scris de: Hale Georgian-Dorin din Februarie 27, 2014, 16:44:17
Poate cineva sa ma ajute si pe mine ? Imi tot spune ca nu se creaza fisierul .out la testare dar numele e scris corect... Sau o fi altceva???

#include <iostream>
#include <fstream>


using namespace std;

int main()
{
    short int T,a,b,i,d=1,aux,j;
    fstream f("euclid2.in");
    fstream g("euclid2.out");
    f>>T;
    for (i=1;i<=T;i++)
    {
        f>>a>>b;
        if (b>a)
        {
            aux=a;
            a=b;
            b=aux;
        }
        for (j=2;j<=a/2;j++)
        {
            if (a%j==0 and b%j==0)
            {
                d=j;
            }
        }
        g<<d<<"\n";
        d=1;
    }
    f.close(),g.close();
    return 0;
}

Titlul: Răspuns: 000 Algoritmul lui Euclid
Scris de: Dandelion din Februarie 27, 2014, 20:24:45
pune:

fstream f("euclid2.in",ios::in);
fstream g("euclid2.out",ios::out);

sau

ifstream f("euclid2.in");
ofstream g("euclid2.out");

Titlul: Răspuns: 000 Algoritmul lui Euclid
Scris de: Valentin Valeanu din Iunie 22, 2014, 12:41:07
program euclid2;
var
f1,f2:text;
n,m,k,i:longint;
begin
assign (f1,'euclid2.in');
reset(f1);
readln (f1,m);
assign (f2,'euclid2.out');
rewrite (f2);
for i:=1 to m do begin
readln (f1,n,k);
while (n<>0) and (k<>0) do
if n>k then n:=n mod k else k:=k mod n;
if n=0 then writeln (f2,k) else
writeln (f2,n);
end;
close (f1);
close (f2);
end.
de ce 60 de puncte. ](*,)

Titlul: Răspuns: 000 Algoritmul lui Euclid
Scris de: George Marcus din Iunie 22, 2014, 19:10:13
Timpul de executie e prea mare pe ultimul test. Incearca cu integer in loc de longint.

Titlul: Răspuns: 000 Algoritmul lui Euclid
Scris de: Valentin Valeanu din Iunie 23, 2014, 12:36:27
cu integer merge 30 de puncte,o sa-l scriu mai bine in c++. :)

Titlul: Răspuns: 000 Algoritmul lui Euclid
Scris de: Petru Titarca din Ianuarie 06, 2015, 17:13:02
NU STIU DE CE IAU DOAR 100 PUNCTE :fighting:

Titlul: Răspuns: 000 Algoritmul lui Euclid
Scris de: bieltz vlad din Ianuarie 19, 2015, 21:08:33
Citat din mesajul lui: Petru Titarca din Ianuarie 06, 2015, 17:13:02
NU STIU DE CE IAU DOAR 100 PUNCTE :fighting:

nu stiu de ce esti asa modest

Titlul: Răspuns: 000 Algoritmul lui Euclid
Scris de: Radu Catalin-Gabriel din Februarie 11, 2015, 20:59:39
Salut! Mie mi se afiseaza decat prima pereche. Ce trebuie sa fac ca sa afisez rezultatul la toate perechile?

Titlul: Răspuns: 000 Algoritmul lui Euclid
Scris de: Ursu Daniel din Februarie 28, 2015, 15:57:18
De ce am doar 60 puncte? Am folosit algoritmul pentru scor maxim. In plus, am încercat și soluțiile celorlalți și tot 60 puncte primesc.

Titlul: Răspuns: 000 Algoritmul lui Euclid
Scris de: Butnaru George din Martie 01, 2015, 15:48:47
Nai cum sa scoti 100 in pascal,inainte era posibil acum nu,succes,invata c++.

Titlul: Răspuns: 000 Algoritmul lui Euclid
Scris de: Madalina Marin din Ianuarie 13, 2016, 21:09:52
Iau 30p pe algoritm, schimb endl cu "\n" si  iau 100. Care e faza?:))

Titlul: Răspuns: 000 Algoritmul lui Euclid
Scris de: Valeriu Motroi din Ianuarie 13, 2016, 21:22:17
endl face flush la output după fiecare afișare; asta face ca programul tău să ruleze mai lent.
Este recomandat să folosești '\n';
O soluție bună este #define endl '\n' .

Titlul: Răspuns: 000 Algoritmul lui Euclid
Scris de: Octavian Florin Staicu din Iunie 05, 2016, 01:28:49
Buna ziua! Recent am inceput sa ma joc cu java, si observ ca imi da 30p cu memory limit exeeded, desi in c acelasi algoritm ocupa f putin. Imi puteti explica de ce?
cod:
import java.io.*;
public class Main {
 
    public static int cmmdc( int a, int b ){
        if( b==0 )
            return a;
        else
            return cmmdc( b, a%b );
    }
    public static void main(String[] args) throws IOException{
        int n, i, a, b, d;
        StreamTokenizer fin = new StreamTokenizer( new BufferedReader( new FileReader ( "euclid2.in" ) ) );
        PrintWriter fout = new PrintWriter(new BufferedWriter( new FileWriter ( "euclid2.out" ) ) );
        fin.nextToken(); n = (int) fin.nval;
        for( i=0; i<n; i++ ){
            fin.nextToken(); a = (int) fin.nval;
            fin.nextToken(); b =(int) fin.nval;
            d = cmmdc( a, b );
            fout.println( d );
        }
        fout.close();
    }
}

Titlul: Răspuns: 000 Algoritmul lui Euclid
Scris de: Florin Gabriel Haja din Iunie 05, 2016, 22:03:25
Mai întâi, încearcă să-l faci iterativ. Gândește-te că aloci mai multă memorie pe stivă la fiecare apel de funcție (mai ales dacă ai funcție recursivă).

Deci transformă funcția ta în ceva de genul:
Cod:
public static int cmmdc(int a, int b){
    int r;
    while (b){
        r = a%b;
        a = b;
        b = r;
    }
    return a;
}

Titlul: Răspuns: 000 Algoritmul lui Euclid
Scris de: Florian MOGA din Iunie 26, 2016, 10:38:08
Chiar si iterativ iese din memorie in Java.. Folosesc BufferedReader/Writer.

Titlul: Algoritmul lui Euclid
Scris de: Agafitei Razvan din Martie 10, 2017, 16:00:50
Ce evaluator aveti?Daca pun '\n' dupa valoare imi da 0.Daca nu iau 100. :fighting:

Titlul: Răspuns: 000 Algoritmul lui Euclid
Scris de: Mihai Calancea din Martie 10, 2017, 16:08:28
Pai tu cum ai scrie evaluatorul astfel incat sa primeasca (spre exemplu) ca output sirul "543678431" si sa se prinda ca tu voiai sa afisezi 3 raspunsuri egale cu 543, 67, respectiv 8431?  :)

Titlul: Răspuns: 000 Algoritmul lui Euclid
Scris de: Moisin Andrei din Martie 25, 2017, 14:53:55
Am trimis o solutie buna pentru evaluare si am primit doar 30 de puncte, testele incorecte fiind cu limita de timp depasita. Problema este ca am trimis aceasi sursa a doua oara cu diferenta ca in aceea am scris intr-un for ++i in loc de i++ si am primit 100 de puncte. Eu nu stiu sa fie mai eficient varianta cu ++i in for si nu prea inteleg cum s-a facut aceasta departajare.

Titlul: Răspuns: 000 Algoritmul lui Euclid
Scris de: Nicolae Filat din Aprilie 24, 2017, 20:18:48
     Nu inteleg de ce primesc doar 30 p pe sursa mea:http://www.infoarena.ro/job_detail/1973390?action=view-source

     Imi da TED la toate


     Ma ajuta cineva? :)  :D

      Mersi

Titlul: Răspuns: 000 Algoritmul lui Euclid
Scris de: Alexandru Valeanu din Aprilie 24, 2017, 21:26:44
Inlocuieste endl-ul cu '\n'.

Titlul: Răspuns: 000 Algoritmul lui Euclid
Scris de: daniel babaian din Mai 08, 2017, 11:57:52
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("euclid2.in");
ofstream g("euclid2.out");
int main()
{
int a,b,c,d;
f>>c;
while (c>=1)
{
   f>>a>>b;
   while (a>0 && b>0){
   if (a>b) a=a%b;
   if (b>a) b=b%a;}

   c=c-1;
   if (a==0) d=b;
   if (b==0) d=a;
   g<<d<<'\n';a=0;b=0;
   
   }   
   


return 0;   
}dc nu imi merge nu inteleg?

Titlul: Răspuns: 000 Algoritmul lui Euclid
Scris de: Burcea Bogdan Madalin din Mai 08, 2017, 17:24:02
Pune

Cod:

while (a>0 && b>0){
if (a>b) a=a%b;
else b=b%a;}


In loc de

Cod:

while (a>0 && b>0){
if (a>b) a=a%b;
if (b>a) b=b%a;}



Al doilea cod nu merge fiindca nu considera cazul cand a si b sunt egale sau cazul cand valoarea lui a se schimba in primul if si conditia din al doilea if va fi adevarata in cadrul aceleiasi iteratie a while-ului  :)

Titlul: Răspuns: 000 Algoritmul lui Euclid
Scris de: Rablau Claudiu-Ionut din Martie 09, 2018, 19:46:15
imi poate spune cineva de ce imi da memory limit exceeded pt acest algoritm https://infoarena.ro/job_detail/2157648?action=view-source

Titlul: Răspuns: 000 Algoritmul lui Euclid
Scris de: Vlad Alexandru din Martie 12, 2018, 18:07:13
Nu inteleg de ce imi tot da 0 puncte.

#include <fstream>

using namespace std;

int main()
{
    ifstream fin ("euclid2.in");
    ofstream fout ("euclid2.out");

    int T, a, b, i, rest, aj_b;
    fin>>T;
    for (i = 1; i <= T; ++i)
    {
        fin >> a >> b;
        aj_b = b;

        while (b != 0)
        {
            rest = a % b;
            a = b;
            b = rest;
        }
        fout << a << "\n";
    }
    return 0;
}

Titlul: Răspuns: 000 Algoritmul lui Euclid
Scris de: Nicola Victor Teodor din Iunie 02, 2018, 08:17:25
ESTE ATAT DE GREA!!!!!!!!!! ](*,)
incat am facut-o din primalol \:D/

Titlul: Răspuns: 000 Algoritmul lui Euclid
Scris de: Radu Stancu din Iulie 22, 2018, 11:59:59
Am incercat sa rezolv problema asta folosind Java https://www.infoarena.ro/job_detail/2223945 , https://www.infoarena.ro/job_detail/2223960. Primesc cv TLEs + 1  - 2 MLEs. Din ce imi dau seama citirea + scirerea in fisier este eficienta in abordarea mea (amandoua folosesc buffered reader / writer behind the curtains). Cat despre MLEs, in afara de marimea bufferului de 32KB si de marimea la standard libraries, memoria suplimentara ar tb sa fie O(1). Se pot mari limitele de timp / memorie pt sursele in Java ?

Titlul: Răspuns: 000 Algoritmul lui Euclid
Scris de: Sallai Tamas din Octombrie 07, 2018, 21:08:11
Pentru asta am primit 0 puncte:)) :aha:

#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("euclid2.in");
ofstream fout("euclid2.out");

int euclid(int x, int y)
{
    if(!y)
        return x;
    return(y, y%x);

}

int main()
{
    int x, nr1, nr2;
    fin >> x;
    for(int i = 1; i <= x; i++)
    {
        fin >> nr1 >> nr2;
        fout << euclid(nr1, nr2) << "\n";
    }
    return 0;
}


Titlul: Răspuns: 000 Algoritmul lui Euclid
Scris de: Dinica Andrei Cristian din Octombrie 21, 2018, 19:03:45
#include <iostream>
#include <fstream>

using namespace std;
ifstream f ("euclid2.in");
ofstream g ("euclid2.out");
int cmmdc(int a, int b)
{
    if(b==0) return a;
    else cmmdc(b, a%b);
}
int main()
{ int t, a, b;
f>>t;
for(int i=0;i<t;i++)
{
    f>>a>>b;
    g<<cmmdc(a,b)<<endl;
}

    return 0;
}
De ce nu primesc punctajul complet?

Titlul: Răspuns: 000 Algoritmul lui Euclid
Scris de: Lambda din Decembrie 13, 2018, 15:07:54
Ar trebui mărită limita de memorie pâna la 4650kb pentru ca o sursă minimală scrisă în Java să treacă testele :)


Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines