Cod sursa(job #1834222)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 24 decembrie 2016 06:13:04
Problema Ecuatie Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.99 kb
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;

vector<ll> all_divs(const ll x){
	vector<ll> rez;
	for(ll i = 1; i*i <= max(x, -x); ++i){
		if(x%i) continue;
		rez.push_back(i);
		rez.push_back(-i);
		rez.push_back(x/i);
		rez.push_back(-x/i); }
	sort(begin(rez), end(rez));
	rez.erase(unique(begin(rez), end(rez)), end(rez));
	return rez; }

struct a_solution{
	ll p1, q1, p2, q2;
	a_solution(const ld x, const ld y, const ld z, const ld p):
		p1(round(x)), q1(round(y)), p2(round(z)), q2(round(p)){}
	bool operator<(const a_solution& rhs)const{
		return p1 < rhs.p1 || (p1 == rhs.p1 && q1 < rhs.q1); }
	bool operator==(const a_solution& rhs)const{
		return p1 == rhs.p1 && q1 == rhs.q1 && p2 == rhs.p2 && q2 == rhs.q2; } };

void print_paren(ostream& lhs, const ll p, const ll q){
	lhs << '(';
	if(p == 1);
	else if(p == -1) lhs << '-';
	else lhs << p;
	lhs << 'x';
	if(q >= 0) lhs << '+';
	lhs << q;
	lhs << ')'; }

ostream& operator<<(ostream& lhs, const a_solution& rhs){
	print_paren(lhs, rhs.p1, rhs.q1);
	print_paren(lhs, rhs.p2, rhs.q2);
	return lhs; }

bool whole(ld x){
	return x == round(x); }
	
void add_solution_if_possible(const ld a, const ld b, const ld c,
		const ld p1, const ld p2, vector<a_solution>& sols){
	const static ld delta = (b * b) - (ld)4 * a * c;
	const static ld sqdelta = sqrt(delta);
	
	const ld q10 = (b + sqdelta) / ((ld)2 * p2),
		q11 = (b - sqdelta) / ((ld)2 * p2),
		q20 = c / q10, q21 = c / q11;

	if(whole(q10) && whole(q20)) sols.emplace_back(p1, q10, p2, q20);
	if(whole(q11) && whole(q11)) sols.emplace_back(p1, q11, p2, q21); }

int main(){
	ifstream f("ecuatie.in");
	ofstream g("ecuatie.out");
	ll a, b, c;
	f >> a >> b >> c;

	vector<ll> divs = all_divs(a);
	vector<a_solution> sols;

	for(const auto x : divs){
		add_solution_if_possible(a, b, c, x, a/x, sols); }

	sort(begin(sols), end(sols));
	sols.erase(unique(begin(sols), end(sols)), end(sols));

	ll k;
	f >> k;

	if(k-1 >= sols.size()) g << -1;
	else g << sols[k-1] << endl;
	return 0; }