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