2321 - HappyNY2018

Alba ca Zapada

şi cei n pitici locuiau încă în căsuţa lor din pădure. Piticilor le făcuse cadou Moş Crăciun câte un număr şi fiecare pitic s-a hotărât să scrie numărul primit ca sumă de m numere naturale.

Cerinţa

Dându-se cele n numere naturale primite de pitici, să se afle, pentru fiecare pitic, cele m numere a căror sumă este egală cu numărul primit de pitic, astfel încât cel mai mic dintre numerele din sumă să fie maxim posibil, iar diferenţa dintre cel mai mare număr din sumă şi cel mai mic să fie minimă.

Date de intrare

Programul citește de la tastatură numerele n şi m, iar apoi de pe a doua linie n numere naturale, separate prin spații, reprezentând numerele primite de pitici.

Date de ieșire

Programul va afișa pe ecran, pe primele n linii, câte m numere, reprezentând numerele cerute pentru fiecare pitic, în ordine crescătoare.

Restricţii şi precizări

• 1 ⩽ n ⩽ 2017
• 2 ⩽ m ⩽ 2018
• cele n numere citite vor fi mai mici decât 1.000.000

Exemplu 1

Intrare

1 2
5

Iesire

Datele de intrare corespund restrictiilor impuse
2 3

Exemplu 2

Intrare

3000 3000
3000

Iesire

Datele de intrare nu corespund restrictiilor impuse

Explicatie

Avem un pitic care a primit numărul 5 şi trebuie să-l scrie ca sumă de două numere naturale : 2+3=5. Cel mai mic dintre cele două numere este maxim (2).

Rezolvare

def find_numbers(n, m):
    # Funcția găsește m numere a căror sumă este egală cu n,
    # astfel încât cel mai mic număr să fie maxim posibil și diferența dintre
    # cel mai mare număr și cel mai mic să fie minimă.

    # Calculăm cât de mari pot fi numerele
    q, r = divmod(n, m)
    # Primele r numere vor fi cu 1 mai mari decât restul
    return [q + 1] * r + [q] * (m - r)


def main():
    n, m = map(int, input().strip().split())
    numbers = list(map(int, input().strip().split()))

    # Verificăm dacă numerele respectă restricțiile
    if not (1 <= n <= 2017) or not (2 <= m <= 2018) or any(number >= 1000000 for number in numbers):
        print("Datele de intrare nu corespund restrictiilor impuse")
        return

    print("Datele de intrare corespund restrictiilor impuse")

    # Pentru fiecare număr, găsim m numere a căror sumă este egală cu numărul
    for number in numbers:
        print(' '.join(map(str, sorted(find_numbers(number, m)))))


if __name__ == "__main__":
    main()