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

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.

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

ksir.out 3

Explicație

Al 8-lea element din şir este 3.

Rezolvare

<syntaxhighlight lang="python" line> def validate(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")

def read_input():

   with open("ksir.in", "r") as f:
       k = int(f.readline().strip())
       validate(k)
       return k

def main():

   k = read_input()

   group = 1
   count = 1
   while k > count:
       group += 1
       count += group - 1

   offset = k - count + group - 1
   result = group + offset // group

   with open("ksir.out", "w") as f:
       f.write(str(result))

if __name__ == "__main__":

   main()

</syntaxhighlight>

Explicatie

Acest cod este o soluție pentru problema "Șir k" descrisă mai sus. Este împărțit în trei funcții:

validate(k): această funcție validează intrarea k și verifică dacă k este un număr întreg și se încadrează în intervalul specificat (1 - 20.000.000.000). Dacă nu îndeplinește aceste condiții, se va genera o excepție.

read_input(): această funcție citește datele de intrare din fișierul "ksir.in", validează intrarea cu ajutorul funcției validate() și returnează valoarea k.

main(): această funcție este punctul de intrare în program și utilizează datele citite de la read_input() pentru a determina elementul k din șir. Utilizează o buclă while pentru a găsi cea mai mică grupă care conține elementul k și calculează elementul k folosind formule aritmetice simple. Apoi, scrie rezultatul în fișierul "ksir.out".

În general, codul folosește metode simple pentru a calcula elementul k din șir fără a fi nevoie să genereze efectiv șirul întreg. Validarea datelor de intrare asigură că programul funcționează corect și nu se blochează sau generează erori din cauza datelor invalide.