3381 - K Sir 1

Se dă următorul şir de numere: 1 1 2 2 1 2 3 3 3 1 2 3 4 4 4 4 1 2 3 4 5 5 5 5 5... În şir avem grupe formate după următoarea regulă: grupa g conţine numerele naturale de la 1 la g în ordine crescătoare, urmate de g-1 valori egale cu g (g=1, 2, ...).

Cerința

Scrieţi un program care citeşte o valoare k şi afişează al k-lea termen al şirului de mai sus.

Date de intrare

Fișierul de intrare ksir.in conţine pe prima linie numărul natural k.

Date de ieșire

Dacă datele sunt introduse corect, pe ecran se va afișa: "Date de intrare valide.", apoi fișierul de ieșire ksir.out va conţine o singură linie pe care va fi scris un număr natural ce reprezintă al k-lea element din şir. În cazul în care datele nu respectă restricțiile, se va afișa pe ecran: "Date de intrare invalide".

Restricții și precizări

1 ≤ k ≤ 20.000.000.000 Poziţiile termenilor din şir sunt numerotate începând cu 1.

Exemplu:

ksir.in

8

Date de intrare valide

ksir.out

3

Explicație

Al 8-lea element din şir este 3.

Rezolvare

def validare(k):
    if not isinstance(k, int):
        raise ValueError("k trebuie sa fie un numar intreg")

    if k < 1 or k > 20000000000:
        raise ValueError("k trebuie sa fie intre 1 si 20.000.000.000")

    return True


def k_sir(k):
    n, cnt = 1, 1
    while (1 * (n + 1) * (n + 1) // 4 < k):
        n += 2
        cnt += 1
    n -= 2
    k -= 1 * (n + 1) * (n + 1) // 4
    nr = 0
    while k:
        if nr != cnt:
            nr += 1
        k -= 1
    fout.write(str(nr))

    fin.close()
    fout.close()


if __name__ == "__main__":
    fin = open("ksir.in")
    fout = open("ksir.out", "w")

    k = int(fin.readline().strip())
    if validare(k):
        print("Date de intrare valide")
        k_sir(k)
    else:
        print("Date de intrare invalide")

Explicatie cod:

Funcția validare(k) primește un număr întreg k și verifică dacă acesta este un întreg și se încadrează în intervalul [1, 20.000.000.000]. Dacă k nu respectă aceste condiții, funcția aruncă o excepție de tip ValueError cu un mesaj corespunzător. În caz contrar, returnează True. Funcția k_sir(k) primește un număr întreg k și efectuează un set de operații. Folosind o buclă while, se calculează valorile n și cnt până când expresia 1 * (n + 1) * (n + 1) // 4 < k devine falsă. Apoi, se ajustează valorile n și k în funcție de formula specificată. Se parcurge o buclă while în care se scade valoarea k până când acesta devine zero, în timp ce nr este incrementat cu 1 în fiecare iterație. La final, se scrie rezultatul în fișierul de ieșire. În blocul if __name__ == "__main__":, se deschid fișierele de intrare și de ieșire (ksir.in și ksir.out). Se citește prima linie din fișierul de intrare pentru a obține valoarea k. Apoi, se verifică dacă datele de intrare sunt valide utilizând funcția validare(k). Dacă datele sunt valide, se afișează un mesaj de confirmare, se apelează funcția k_sir() și se efectuează operațiile corespunzătoare. În final, se închid fișierele de intrare și de ieșire.