Cod sursa(job #1709132)

Utilizator TeamFIIGUAIC Parjoala TeamFIIG Data 28 mai 2016 11:00:33
Problema Consecutive Scor 0
Compilator cpp Status done
Runda ONIS 2016 - Runda - 2 - ACM ICPC Romanian Programming Contest Marime 1.41 kb
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<cstdio>
#include <cmath>
#include<algorithm>

using namespace std;
struct solutie
{
	int st, dr;
};
vector <long long> s;
vector <solutie> sol;
void Sume()
{
	long long maxi = pow(2, 31);
	long long suma = 0;
	int i;
	s.push_back(0);
	for (i = 1; suma<=maxi; ++i)
	{
		
		suma = suma + i;
		
		s.push_back(suma);
	}
}
int CautBin(int n)
{
	int st, dr, m;
	st = 1;
	dr = n;
	while (st <= dr)
	{
		m = (st + dr) / 2;
		if (s[m] == n) return m;
		else if (s[m] < n) st = m + 1;
		else if (s[m] > n) dr = m - 1;
	}
	return m;
}
bool Comp(solutie x, solutie y)
{
	return (x.dr - x.st) < (y.dr - y.st);
}
int main()
{
	freopen("consecutive.in", "r", stdin);
	freopen("consecutive.out", "w", stdout);
	Sume();
	int test,n;
	scanf("%d", &test);
	for (int t = 1; t <= test; t++)
	{
		sol.clear();
		scanf("%d", &n);
		int p = CautBin(n);
		int x,y;
		x = 1;
		y = p;
		int suma = s[p];
		solutie solve;
		while (y-x+1 >1)
		{
			if (suma == n)
			{
				solve.st = x;
				solve.dr = y;
				sol.push_back(solve);
			}
			if (suma >= n)
			{
				suma -= x;
				x++;
			}
			if (suma < n)
			{
				y++;
				suma += y;
			}

		}
		sort(sol.begin(), sol.end(), Comp);
		printf("%d\n", sol.size() );
		for (int j = 0; j < sol.size(); j++)
			printf("%d %d\n", sol[j].st, sol[j].dr);
		

	}
	
}