4007 - Partitie AB 1

Cerința

Se dau trei numere naturale n a b, 1 ≤ a < b < n. Să se determine o modalitate de a-l scrie pe n ca sumă de termeni egali cu a sau b în care numărul de termeni egali cu a este minim.

Date de intrare

Programul citește de la tastatură numerele n a b.

Date de ieșire

Programul va afișa pe ecran un șir de numere ordonate crescător, reprezentând termenii ceruți.

Restricții si precizări:

• 1 ≤ n ≤ 1.000.000
• 1 ≤ a < b ≤ 1000

• pentru toate datele de test n poate fi scris ca sumă de termeni egali cu a și b.

Exemplu:

Intrare

44 3 5

Iesire

3 3 3 5 5 5 5 5 5 5

Rezolvare:

<syntaxhighlight lang="python"> def gaseste_valori(n, a, b):

   p, q = -1, -1

   for i in range(0, n + 1):
       if (n - i * a) % b == 0:
           p = i
           break

   q = (n - p * a) // b

   return p, q

def afiseaza_valori(p, q, a, b):

   for i in range(1, p + 1):
       print(a, end=" ")

   for i in range(1, q + 1):
       print(b, end=" ")

   print()

if __name__ == "__main__":

   n, a, b = map(int, input().split())

   p, q = gaseste_valori(n, a, b)

   afiseaza_valori(p, q, a, b)

</syntaxhighlight>