Cod sursa(job #1709520)

Utilizator TeamFIIEUAIC ASD TeamFIIE Data 28 mai 2016 12:42:46
Problema Consecutive Scor 0
Compilator cpp Status done
Runda ONIS 2016 - Runda - 2 - ACM ICPC Romanian Programming Contest Marime 1.75 kb
#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;
unsigned long long N,T;
unsigned long long x[100000],y[100000];
unsigned long long cautbin(unsigned long long lung, unsigned long long fin,unsigned long long start)
{
    unsigned long long m,p,u,calc1,calc2;
    p=start;
    u=fin;
    while(p<=u)
    {
        m=(p+u)/2;
        calc2=m-lung;
        calc1=(m*(m+1)/2)-(calc2*(calc2+1)/2);
        if(calc1==N) return m;
        if(calc1>N)
        {
            u=m-1;
        }
        else p=m+1;
    }
    return 0;
}
int main()
{
    ifstream f("consecutive.in");
    ofstream g("consecutive.out");
    f>>T;
    unsigned long long i,lungime,rez,countt,calc,j,maximmm=0,last,first,S,h;
    for(i=1;i<=T;i++)
    {
        f>>N;
        first=(sqrt(1+8*N)-1)/2;
        last=N/2+1;
        countt=0;
        if(N%2==0)
        {
            lungime=3;
        }
        else
        {
            countt++;
            x[1]=N/2;
            y[1]=x[1]+1;
            lungime=3;
        }
        calc=(lungime)*(lungime+1)/2;
        while(calc<=N&&lungime<=first)
        {
            rez=cautbin(lungime,last,first);
            if(rez!=0)
            {
                countt++;
                y[countt]=rez;
                x[countt]=rez-lungime+1;
                last=rez-1;
            }
            lungime++;
            if(lungime%2==0)
            {
                h=lungime/2;
                if(h%2==1&&N%2==0) lungime++;
                if(h%2==0&&N%2==1) lungime++;
            }
            calc=(lungime)*(lungime+1)/2;
        }
        g<<countt<<'\n';
        for(j=1;j<=countt;j++)
        {
            g<<x[j]<<" "<<y[j]<<'\n';
        }
    }
    return 0;
}