Cod sursa(job #2542796)

Utilizator memecoinMeme Coin memecoin Data 10 februarie 2020 16:41:37
Problema Ecuatie Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.65 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";
    }
    
    void flip() {
        a *= -1;
        b *= -1;
        c *= -1;
        d *= -1;
    }
    
    void swap() {
        int t;
        t = a;
        a = c;
        c = t;
        t = b;
        b = d;
        d = t;
    }
};

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

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);
        }
    }
    
    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) {
                if (mp.count({{{abs(a), abs(b)}, abs(c)}, abs(d)}) == 0) {
                    sol.push_back({c,d,a,b});
                    mp.insert({{{{abs(a), abs(b)}, abs(c)}, abs(d)}});
                }
            }
        }
    }
    
    k--;
    
    if (k < sol.size()) {
        sol[k].flip();
        sol[k].print();
        return 0;
    }
    
    if (k < 2 * sol.size()) {
        k -= sol.size();
        sol[sol.size() - k - 1].flip();
        sol[sol.size() - k - 1].swap();
        sol[sol.size() - k - 1].print();
        return 0;
    }
    
    if (k < 3 * sol.size()) {
        k -= 2 * sol.size();
        sol[k].swap();
        sol[k].print();
        return 0;
    }
    
    k -= 3 * sol.size();
    
    sol[sol.size() - k - 1].print();
    
    return 0;
}