2427 - Sir 10

Sursa: [1]

Cerinţa

Gigel se distrează construind şiruri crescătoare de numere din mulţimea {1,2,…,n}. La un moment dat observă că unele şiruri, de cel puţin k nr_termeni (k ≥ 3), au o proprietate mai aparte: diferența dintre doi termeni consecutivi este constantă. Iată câteva exemple de astfel de şiruri pentru n ≥ 22:

2, 3, 4

1, 5, 9, 13

7, 10, 13, 16, 19, 22

Dându-se numărul natural n ajutați-l pe Gigel să numere câte astfel de șiruri poate să construiască.

Date de intrare

Programul conține pe prima linie numărul n.

Date de ieșire

Programul va conține pe prima linie numărul cerut.

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect.", apoi pe un rând nou afișează câte astfel de șiruri poate să construiască poate să construiască Gigel.

În caz contrar, se va afișa pe ecran: "Datele nu corespund restricțiilor impuse."

Restricţii şi precizări

3 ≤ n ≤ 20000

3 ≤ nr_termeni ≤ n

Exemplul 1

Datele de intrare

N este:

3

Datele de ieșire

Datele sunt introduse corect.

1

Exemplul 2

Datele de intrare

N este:

4

Datele de ieșire

Datele sunt introduse corect.

3

Exemplul 3

Datele de intrare

N este:

5

Datele de ieșire

Datele sunt introduse corect.

7

Rezolvare

#2427
def has_valid_input(n, nr_termeni):
    if not (3 <= n <= 20000):
        print("Datele nu corespund restricțiilor impuse.")
        return False
    if not (3 <= nr_termeni <= n):
        print("Datele nu corespund restricțiilor impuse.")
        return False
    return True


def has_property(sir):
    d = sir[1] - sir[0]
    for i in range(2, len(sir)):
        if sir[i] - sir[i - 1] != d:
            return False
    return True


def backtracking(sir, pozitie):
    global nr_siruri
    if len(sir) >= nr_termeni:
        if has_property(sir):
            nr_siruri += 1
    for i in range(pozitie + 1, n + 1):
        sir.append(i)
        backtracking(sir, i)
        sir.pop()


if __name__ == '__main__':
    n = int(input("N este:"))
    nr_termeni = 3
    nr_siruri = 0

    if not has_valid_input(n, nr_termeni):
        exit()

    backtracking([], 0)
    print("Datele sunt introduse corect.")
    print(nr_siruri)

Explicatie cod:

Acest program calculează numărul de șiruri aritmetice de lungime fixă și dimensiune n, care încep cu un element oarecare și au cel puțin trei elemente și diferența constantă între oricare două elemente consecutive. Programul utilizează un algoritm de backtracking pentru a genera toate șirurile posibile, verificând dacă acestea au proprietatea cerută.

Funcția has_valid_input(n, nr_termeni) verifică dacă inputul dat este valid, adică dacă n și nr_termeni se încadrează într-un interval specificat. În caz contrar, se afișează un mesaj de eroare și se returnează False.

Funcția has_property(sir) verifică dacă un șir dat are proprietatea cerută (adică diferența dintre oricare două elemente consecutive este constantă). Dacă această proprietate este îndeplinită, funcția returnează True. Dacă nu, funcția returnează False.

Funcția backtracking(sir, pozitie) utilizează un algoritm de backtracking pentru a genera toate șirurile posibile care îndeplinesc cerințele. Aceasta primește ca argumente sir, care reprezintă șirul curent, și pozitie, care reprezintă poziția curentă în șirul n. Dacă șirul sir are cel puțin nr_termeni elemente și îndeplinește proprietatea cerută, se incrementează nr_siruri. Altfel, se explorează toate combinațiile posibile ale elementelor următoare în șirul n cu ajutorul unei bucle for. În continuare, se adaugă elementul curent în sir, se apelează recursiv funcția backtracking() pentru a explora toate posibilitățile ulterioare, se scoate ultimul element adăugat din sir și se continuă cu următoarea iterație a buclei.

În blocul if __name__ == '__main__': se citesc datele de intrare n și se inițializează variabilele nr_termeni și nr_siruri. Apoi, se verifică dacă datele introduse sunt valide, utilizând funcția has_valid_input(). Dacă inputul este valid, se apelează funcția backtracking() pentru a calcula numărul de șiruri cerute și se afișează rezultatul.