1356 - N Sir

Cerința

Fie n un număr natural. Să se determine toate șirurile a de k numere naturale nu neapărat distincte: 1 ≤ a1, a2,...,ak ≤ n, astfel încât: 1) 1 = 1/a1+ 1/a2+...+ 1/ak 2) n = a1 + a2 +...+ ak

Date de intrare

Fișierul de intrare nsir.in conține pe prima linie numărul n.

Date de ieșire

Fișierul de ieșire nsir.out va conține pe fiecare linie câte un șir determinat, în ordine lexicografică. Dacă nu poate fi generat un astfel de șir, atunci se va scrie valoarea 0 pe prima linie a fișierului de ieșire.

Restricții și precizări

5 ≤ n ≤ 75 se admite că cerința 1) este satisfăcută dacă: | 1/a1 + 1/a2 + … + 1/ak – 1 |<10-5 ==Exemplu==: nsir.in

33 nsir.out

3 3 9 9 9 3 5 5 5 15

Explicație

Se observă că 1) 1 = 1/3+1/3+1/9+1/9+1/9 și 33 = 3+3+9+9+9 2) 1 = 1/3+1/5+1/5+1/5+1/15 și 33 = 3+5+5+5+15

Rezolvare

def backtracking(n, k, target_sum, current_sum, current_sequence, result):

   if k == 0:
       if current_sum == target_sum:
           result.append(list(current_sequence))
       return
   for i in range(1, min(n, target_sum - current_sum) + 1):
       current_sequence.append(i)
       backtracking(n, k - 1, target_sum, current_sum + i, current_sequence, result)
       current_sequence.pop()


def find_sequences(n):

   result = []
   for k in range(2, n + 1):
       backtracking(n, k, n, 0, [], result)
   return result


if __name__ == "__main__":

   # Citim numărul n din fișierul de intrare
   with open("nsir.in", "r") as f:
       n = int(f.readline().strip())
   # Găsim și afișăm șirurile în fișierul de ieșire
   sequences = find_sequences(n)
   with open("nsir.out", "w") as g:
       if not sequences:
           g.write("0\n")
       else:
           for sequence in sequences:
               g.write(" ".join(map(str, sequence)) + "\n")

python nsir.py