Nu aveti permisiuni pentru a descarca fisierul grader_eval.cpp

Cod sursa(job #1709729)

Utilizator cpitting_llamasRotaru Tanase Gherghina cpitting_llamas Data 28 mai 2016 13:39:45
Problema Consecutive Scor 0
Compilator cpp Status done
Runda ONIS 2016 - Runda - 2 - ACM ICPC Romanian Programming Contest Marime 2.71 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 find(ull low, ull high, ull sum) {
	if (sum == 0)
		return 1;
	if (sum < 0)
		return -1;
	while(low < high) {
		//std::cout << "low = " << low << " high = " << high << "\n";
		ull mid = low + (high - low) / 2;
		ull mid_sum = (mid * (mid + 1) / 2);
		//std::cout << " msum = " << mid_sum << " searched sum = " << sum << "\n";
		if (mid_sum == sum) {
			return mid;
		} else if (mid_sum < sum) {
			low = mid + 1;
		} else {
			high = mid;
		}
	}
	return -1;
}

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;

		ull lmax = N / 2 + 1;
		//for (; (lmax * (lmax + 1) / 2) <= N; lmax++);

		for (int up_idx = 0; up_idx <= lmax; ++up_idx) {
			ull part_sum = up_idx * (up_idx + 1) / 2;
			//std::cout << "testing for idx = " << up_idx << " of partsum = " << part_sum << "\n";
			int low_idx = find(0, up_idx, part_sum - N);
			if (low_idx != -1) {
				intervals.push_back(std::make_pair(low_idx, 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;
}
/*
		//std::cout << "lmax = " << lmax << "\n";
		for (int l = 1; l <= lmax; ++l) {
			int off_low = 0;
			int off_high = ;
			while(off_low < off_high) {
				int off_mid = off_low + (off_high - off_low) / 2;
				ull ttloff = off_mid * l;

				if (ttloff + (l * (l + 1) / 2) == N) {
					intervals.push_back(std::make_pair(off_mid + 1, off_mid + l));
					count++;
					break;
				} else if (ttloff + (l * (l + 1) / 2) > N) {
					off_high = off_mid;
				} else {
					off_low = off_mid + 1;
				}
			}
		}*/

		/*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*/