Cod sursa(job #1709963)

Utilizator cpitting_llamasRotaru Tanase Gherghina cpitting_llamas Data 28 mai 2016 14:36:14
Problema Consecutive Scor 0
Compilator cpp Status done
Runda ONIS 2016 - Runda - 2 - ACM ICPC Romanian Programming Contest Marime 1.88 kb
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <string>
#include <limits>
#include <vector>
#include <bitset>
#include <utility>
#include <fstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>

#define MOD 10001 // daca e nevoie de mod
#define oo 2000000000
#define ooLL (1LL<<60)
#define LSB(x) (x&(-x)) // least significat bit of
#define eps 0.00001

typedef long long ull;
typedef long double ld;

int main()
{
	std::ifstream cin("consecutive.in");
	std::ofstream cout("consecutive.out");
	int test_count;
	cin >> test_count;
	for (auto test_idx = 0; test_idx < test_count; ++test_idx) {
		ull N;
		cin >> N;
		int count = 0;
		std::vector<std::pair<int, int> > intervals;

		//for (; (lmax * (lmax + 1) / 2) <= N; lmax++);
		//ull lmax = std::min(40000, (int)(N / 2 + 1));
		//lmax = N / 2 + 1;

		for (int up_idx = N / 2 + 1; up_idx >= 2; --up_idx) {
			ull part_sum = up_idx * (up_idx + 1) / 2;

			//std::cout << "testing for idx = " << up_idx << " of partsum = " << part_sum << "\n";
			ull searched_sum = part_sum - N;
			ull sqt1 = sqrt(1 + 8 * searched_sum);
			if ((sqt1 * sqt1) == (1 + 8 * searched_sum)) {
				intervals.push_back(std::make_pair((-1 + sqt1) / 2, up_idx));
				count++;
			}
		}
		/*std::sort(intervals.begin(), intervals.end(), [](const std::pair<int, int> &x,
                                       const std::pair<int, int> &y) {
    						   			return (x.second - x.first) < (y.second - y.first);
									});*/
		cout << count << "\n";
		for (uint i = 0; i < intervals.size(); ++i) {
			cout << intervals[i].first << " " << intervals[i].second << "\n";
		}
	}

	cin.close();
	cout.close();
	return 0;
}
/*23
4987 4988
3324 3326
1993 1997
1660 1665
1422 1428
993 1002
706 719
658 672
516 534
465 485
387 411
318 347
268 302
244 281
217 258
175 224
147 203
108 177
96 170
58 152
43 147
31 144
9 141*/