Question

#3381 PBinfo
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.

Answer 1

Solutia oficiala:

#include <fstream>

#include <cmath>

using namespace std;

ifstream fin("ksir.in");

ofstream fout("ksir.out");

unsigned long long k,g,p,s,d;

int main()

{

   fin>>k;

   //g=sqrt(k);

   s=0;

   d=k;

   while(s+1<d)

   {

       g=(s+d)/2;

       if(g*g==k)

           break;

       else if(g*g<k)

           s=g;

       else

           d=g;

   }

   if(g*g>k)

       g--;

   if(g*g==k)

       fout<<g;

   else

   {

       p=k-g*g;

       if(p<g+1)

           fout<<p;

       else

           fout<<g+1;

   }

}