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
SOLUTIE
#include <fstream>
#include <cmath>
using namespace std;
int main()
{
ifstream cin("ksir.in");
ofstream cout("ksir.out");
long long int k,g=1,p;
cin>>k;
g=sqrt(k);
if(g*g==k) cout<<g;
else
{ p=k-g*g;
if(p<=g) cout<<p;
else cout<<g+1;
}
return 0;
}