Cod sursa(job #2542897)

Utilizator memecoinMeme Coin memecoin Data 10 februarie 2020 18:10:13
Problema Ecuatie Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.54 kb
#include <fstream>
#include <string>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <math.h>
#include <set>
#include <map>
#include <string.h>
#include <queue>
#include <stack>

#define INF 0x3f3f3f3f

using namespace std;

#ifdef DEBUG
string name = "data";
#else
string name = "ecuatie";
#endif

ifstream fin(name + ".in");
ofstream fout(name + ".out");

void printNr(int x) {
    if (abs(x) == 1) {
        if (x == -1) {
            fout << "-";
        }
    } else {
        fout << x;
    }
}

struct Eq {
    int a,b,c,d;
    
    void print() {
        fout << "(";
        printNr(a);
        fout << "x";
        if (b > 0) {
            fout << "+";
        }
        fout << b;
        fout << ")";
        fout << "(";
        printNr(c);
        fout << "x";
        if (d > 0) {
            fout << "+";
        }
        fout << d;
        fout << ")\n";
    }

};

set<pair<pair<pair<int,int> , int> , int>> mp;

bool cmpEq(Eq x, Eq y) {
    if (x.a != y.a) {
        return x.a > y.a;
    }
    
    if (x.b != y.b) {
        return x.b > y.b;
    }
    
    if (x.c != y.c) {
        return x.c > y.c;
    }
    
    return x.d > y.d;
}

int main() {
    
    int x,y,z,k;
    
    fin >> x >> y >> z >> k;

    vector<int> divX;
    vector<int> divZ;
    
    for (int i = 1; i <= sqrt(abs(x)); ++i) {
        if (x % i == 0) {
            divX.push_back(i);
            divX.push_back(-i);
        }
    }
    
    for (int i = 1; i <= sqrt(abs(z)); ++i) {
        if (z % i == 0) {
            divZ.push_back(i);
            divZ.push_back(-i);
        }
    }
    
    divX.push_back(x);
    divZ.push_back(z);
    
    sort(divX.end(), divX.end());
    sort(divZ.begin(), divZ.end());
    divX.reserve(divX.size());
    divZ.reserve(divZ.size());
    
    vector<Eq> sol;
    
    for (auto a: divX) {
        int c = x / a;
        for (auto b: divZ) {
            int d = z / b;
            
            if (a * d + b * c == y) {
                sol.push_back({a,b,c,d});
                sol.push_back({-a,-b,-c,-d});
                sol.push_back({c,d,a,b});
                sol.push_back({-c,-d,-a,-b});
            }
        }
    }

    vector<Eq> solUniq;
    
    for (auto e: sol) {
        if (mp.count({{{e.a, e.b}, e.c},e.d}) == 0) {
            solUniq.push_back(e);
            mp.insert({{{e.a, e.b}, e.c},e.d});
        }
    }

    sort(solUniq.begin(), solUniq.end(), cmpEq);

    if (k > solUniq.size()) {
        fout << -1;
        return 0;
    }
    
    k--;
    solUniq[solUniq.size() - k - 1].print();
    
    
    return 0;
}