Rezolvare completă PbInfo #1081 Numar3

Se dă un număr raţional strict pozitiv q, sub formă de fracţie zecimală.

Cerinţă

Să se determine două numere naturale a şi b astfel \( q= \frac{a}{b} \) încât iar modulul diferenţei dintre a şi b să fie minim.

Date de intrare

Fișierul de intrare numar3.in conține

  • pe prima linie două valori naturale ni şi nz. ni reprezintă numărul de cifre care formează partea întreagă a lui q iar nz reprezintă numărul de cifre care formează partea fracţionara a lui q.
  • pe a doua linie, ni cifre care reprezintă partea întreagă a lui q. Între două cifre se află câte un caracter spaţiu.
  • pe a treia linie, nz cifre care reprezintă partea zecimală a lui q. Între două cifre se află câte un caracter spaţiu.

Date de ieșire

Fișierul de ieșire numar3.out va conține:

  • pe prima linie un număr natural n1 care reprezintă numărul de cifre din care este alcătuit numărul a;
  • pe a doua linie, cifrele numărului a, fără spaţiu între ele.
  • pe a treia linie un număr natural n2 care reprezintă numărul de cifre din care este alcătuit numărul b;
  • pe a patra linie, cifrele numărului b, fără spaţiu între ele.

Restricții și precizări

  • 1≤ n1,n2 < 2000
  • 1≤ n1+n2 ≤ 2000
  • Cifrele din care este alcătuit q sunt cele din sistemul zecimal.
  • Pentru 20% dintre teste, n1+n2≤9; pentru alte 15% dintre teste, 10≤n1+n2≤16

Exemplul 1

numar3.in

1 3
0
3 7 5

numar3.out

1
3
1
8

Explicație

\( q = 0.375 = \frac {3}{8} \).
Exista şi alte perechi de valori naturale x, y astfel incat \( \frac {x} {y} = 0.375 \), dar pentru oricare altă pereche, |x-y| > |3-8| (|…| reprezintă modulul).

Exemplul 2

numar3.in

3 7
0 1 2
3 4 5 6 7 0 0

numar3.out

7
1234567
6
100000

Explicație

\( q = 12.34567 = \frac {1234567} {100000} \) .

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Numar3:

//implementare de 100 de puncte - ciprian chesca
#include <fstream>

using namespace std;

typedef unsigned long vector[2000];

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

unsigned long prim[]={2,5};


void initializare(vector v) {   
  v[0] = 0;   
}  
void atribuire(vector v, unsigned long x) {   
  v[0] = 0;   
  while (x) {   
      ++v[0];   
      v[v[0]] = x % 10;   
      x /= 10;   
  }   
}  

void inmultire(vector v, unsigned long x)   
/* v <- v*x */  
{ unsigned long i,t=0;   
  
  for (i=1;i<=v[0];i++)   
    { v[i]=v[i]*x+t;   
      t=v[i]/10;   
      v[i]=v[i]%10;   
    }   
  while (t) /* Cat timp exista transport */  
    { v[++v[0]]=t%10;   
      t/=10;   
    }   
}  


void adunare(vector a, vector b)   
/* a <- a+b */  
{ unsigned long i,t=0;   
  
  if (b[0]>a[0])   
    { for (i=a[0]+1;i<=b[0];) a[i++]=0;   
      a[0]=b[0];   
    }   
    else for (i=b[0]+1;i<=a[0];) b[i++]=0;   
  for (i=1;i<=a[0];i++)   
    { a[i]+=b[i]+t;   
      t=a[i]/10;   
      a[i]%=10;   
    }   
  if (t) a[++a[0]]=t;   
}  


void scriere(vector v)
{
unsigned long i;
for(i=v[0];i>=1;i--)
    g<<v[i];
g<<endl;
}


void shl(vector a, int p)
/* H <- H*10ACount */
{ long i;

  /* Shifteaza vectorul cu Count pozitii */
  for (i=a[0];i;i--) a[i+p]=a[i];
  /* Umple primele Count pozitii cu 0 */
  for (i=1;i<=p;) a[i++]=0;
  /* Incrementeaza numarul de cifre */
  a[0]+=p;
}


void shr(vector a, int p)
/* H <- H/10ACount */
{ unsigned long i;

  /* Shifteaza vectorul cu Count pozitii */
  for (i=p+1;i<=a[0];i++) a[i-p]=a[i];
  /* Decrementeaza numarul de cifre */
  a[0]-=p;
}

unsigned long divide(vector a, unsigned long x)
/* A <- A/X si intoarce A%X */
{ unsigned long i;
  unsigned long R=0;

  for (i=a[0];i;i--)
    { a[i]=(R=10*R+a[i])/x;
      R%=x;
    }
  while (!a[a[0]] && a[0]>1) a[0]--;
  return R;
}

unsigned long mod(vector a, unsigned long x)
/* Intoarce A%X */
{ unsigned long i;
  unsigned long R=0;

  for (i=a[0];i;i--)
    R=(10*R+a[i])%x;
  return R;
}

int main()
{
    unsigned long n,m,i;
    vector v; // numarator
    vector s; // numitor
    initializare(v);
    initializare(s);
    
    f>>n>>m;
    // citesc partea intreaga
    for(i=1;i<=n;i++)
        f>>v[n+m-i+1];
            
    
    // citesc partea fractionara
    for(i=1;i<=m;i++)
        f>>v[m-i+1];
    
    v[0]=n+m;
    if (v[n+m]==0) v[0]--;
    
    
    atribuire(s,1);
    shl(s,m);
    if (m==0) {g<<n<<"
";scriere(v);g<<1<<"
";scriere(s); return 0;}
    
    for(i=0;i<=1;i++)
        while (mod(v,prim[i])==0&&mod(s,prim[i])==0) 
                { 
                divide(v,prim[i]);
                divide(s,prim[i]);
                }
        
    g<<v[0]<<"
";scriere(v);g<<s[0]<<"
";scriere(s);   
    
f.close();
g.close();

return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email.

Rezolvarea problemei #1081 Numar3

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1081 Numar3 de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!