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 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")

</syntaxhighlight>