Cod sursa(job #1709233)

Utilizator UPB_ShiftMyBitsUPB Mirea Avram Boaca UPB_ShiftMyBits Data 28 mai 2016 11:23:23
Problema Consecutive Scor 100
Compilator cpp Status done
Runda ONIS 2016 - Runda - 2 - ACM ICPC Romanian Programming Contest Marime 1.61 kb
#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
#include <cmath>
using namespace std;

ifstream fin("consecutive.in");
ofstream fout("consecutive.out");

void solve(long long n) {
    long long k = 0, p = 1;
    vector<pair<long long, long long>> sol;
    for (long long x = 2; x * (x + 1) <= 2 * n; ++x) {
        p = (x * (x + 1)) / 2;
        if ((n - p) % x == 0) {
            k = (n - p) / x;
            sol.emplace_back(k + 1, k + x);
        }
    }

    fout << sol.size() << '\n';
    for (const auto& p : sol) {
        fout << p.first << ' ' << p.second << '\n';
    }
}

typedef long long ll;

vector<pair<long long, long long>> brute(long long N) {
    vector<pair<ll, ll>> sol;
    for (ll x = 1; x <= N; ++x) {
        ll y = x + 1;
        ll sum = x + y;

        while (sum < N) {
            y++;
            sum += y;
        }

        if (sum == N) {
            sol.emplace_back(x, y);
        }
    }

    reverse(sol.begin(), sol.end());
    return sol;
}

void print_vector(const vector<pair<ll, ll>>& v) {
    fout << v.size() << '\n';
    for (const auto& p : v) {
        fout << p.first << ' ' << p.second << '\n';
    }
}

int main() {
    int T;

    fin >> T;
    while (T--) {
        long long N;
        fin >> N;
        solve(N);
    }

    /*
    for (int i = 1; i <= 100000; ++i) {
        int N = rand();
        if (brute(N) != solve(N)) {
            cerr << "Wrong " << i << '\n';
            print_vector(brute(N));
            print_vector(solve(N));
            return 1;
        } else {
//            fout << "Right " << i << '\n';
        }
    }
    */
    return 0;
}