1081 - Numar 3

Cerința

Se dă un număr raţional strict pozitiv q, sub formă de fracţie zecimală. Să se determine două numere naturale a şi b astfel q=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

Exemplu 1

Intrare

1 3
0
3 7 5

Iesire

1
3
1
8

Rezolvare

<syntaxhighlight lang="python" line> from fractions import Fraction import itertools

def main():

   # Citirea datelor de intrare
   with open("numar3.in", "r") as f:
       n1, n2 = map(int, f.readline().strip().split())
       parte_intreaga = list(map(int, f.readline().strip().split()))
       parte_fractionara = list(map(int, f.readline().strip().split()))
   
   # Construirea numărului rațional q
   int_part = int(.join(map(str, parte_intreaga)))
   frac_part = int(.join(map(str, parte_fractionara)))
   total_len = len(parte_fractionara)
   q = Fraction(int_part * (10 ** total_len) + frac_part, 10 ** total_len)
   
   # Găsirea numitorilor a și b
   a, b = 0, 0
   min_diff = float('inf')
   
   for i in range(1, 2000):
       candidate_b = int(q * i)
       candidate_a = q * i
       if abs(candidate_a - candidate_b) < min_diff:
           min_diff = abs(candidate_a - candidate_b)
           a, b = int(candidate_a), i
   
   # Afișarea rezultatului
   with open("numar3.out", "w") as f:
       f.write(f"{len(str(a))}\n")
       f.write(f"{' '.join(str(a))}\n")
       f.write(f"{len(str(b))}\n")
       f.write(f"{' '.join(str(b))}\n")

if __name__ == "__main__":

   main()

</syntaxhighlight>