Cod sursa(job #113054)

Utilizator floringh06Florin Ghesu floringh06 Data 8 decembrie 2007 16:43:57
Problema Ecuatie Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.85 kb
#include <cstdio>
#include <cstring>
#include <cmath>
#include <fstream>

using namespace std;

#define FIN "ecuatie.in"
#define FOUT "ecuatie.out"

int A, B, C, K;

typedef struct 
{
        int p1, p2;
        int q1, q2;
} solution;

solution S[10000];
int Nsol;

    void swap (int i, int j)
    {
         solution x;
         x = S[i]; S[i] = S[j]; S[j] = x;
    }

    int part (int st, int dr)
    {
        int i, j, s = 1;
        i = st; j = dr;
        while (i < j)
        {
              if (S[i].p1 > S[j].p1)
              {
                 swap (i, j);
                 s = 1 - s;
              }
              if (S[i].p1 == S[j].p1 && S[i].q1 > S[j].q1)
              {
                 swap (i, j);
                 s = 1 - s;
              }
              if (s) ++i; else --j;
        }
        return i;
    }
                 

    void sort (int st, int dr)
    {
         if (st < dr)
         {
                int p = part (st, dr);
                sort (st, p - 1);
                sort (p + 1, dr);
         }
    }

    int EQ (int i, int j)
    {
        if (S[i].p1 != S[j].p1) return 0;
        if (S[i].q1 != S[j].q1) return 0;
        if (S[i].p2 != S[j].p2) return 0;
        if (S[i].q2 != S[j].q2) return 0;
        return 1;
    }

    void solve ( void )
    {
         int i, j;
         double x1, x2, delta;
         delta = (double)sqrt(B*B - 4*A*C);
         x1 = (double)((-B - delta)/(2*A));
         x2 = (double)((-B + delta)/(2*A));
         for (i = 1; i <= (int)sqrt(A); ++i)
             if (A % i == 0)
             {
                   ++Nsol;
                   S[Nsol].p1 = i; S[Nsol].q1 = (int) -x1*i; S[Nsol].p2 = (int)A/i; S[Nsol].q2 = (int)-x2*(A/i);
                   ++Nsol;
                   S[Nsol].p1 = i; S[Nsol].q1 = (int) -x2*i; S[Nsol].p2 = (int)A/i; S[Nsol].q2 = (int)-x1*(A/i);
                   i = -i;
                   ++Nsol;
                   S[Nsol].p1 = i; S[Nsol].q1 = (int) -x1*i; S[Nsol].p2 = (int)A/i; S[Nsol].q2 = (int)-x2*(A/i);
                   ++Nsol;
                   S[Nsol].p1 = i; S[Nsol].q1 = (int) -x2*i; S[Nsol].p2 = (int)A/i; S[Nsol].q2 = (int)-x1*(A/i);
                   i = -i;
             }
         i = A;
         if (A % i == 0)
             {
                   ++Nsol;
                   S[Nsol].p1 = i; S[Nsol].q1 = (int) -x1*i; S[Nsol].p2 = (int)A/i; S[Nsol].q2 = (int)-x2*(A/i);
                   ++Nsol;
                   S[Nsol].p1 = i; S[Nsol].q1 = (int) -x2*i; S[Nsol].p2 = (int)A/i; S[Nsol].q2 = (int)-x1*(A/i);
                   i = -i;
                   ++Nsol;
                   S[Nsol].p1 = i; S[Nsol].q1 = (int) -x1*i; S[Nsol].p2 = (int)A/i; S[Nsol].q2 = (int)-x2*(A/i);
                   ++Nsol;
                   S[Nsol].p1 = i; S[Nsol].q1 = (int) -x2*i; S[Nsol].p2 = (int)A/i; S[Nsol].q2 = (int)-x1*(A/i);
                   i = -i;
             }
         sort (1, Nsol);
         K--;
         for (i = 1; i <= Nsol; ++i)
         {
             if (!K) break;
             if (!EQ(i, i - 1)) K--;
         }
         if (S[i].p1 != 1 && S[i].p1 != -1) printf ("(%d", S[i].p1); 
            else if (S[i].p1 == -1) printf ("(-");
                 else printf ("(");
         if (S[i].q1 < 0) printf ("x-"); else printf ("x+");
         printf ("%d)", abs(S[i].q1));
         if (S[i].p2 != 1 && S[i].p2 != -1) printf ("(%d", S[i].p2); 
            else if (S[i].p2 == -1) printf ("(-");
                 else printf ("(");
         if (S[i].q2 < 0) printf ("x-"); else printf ("x+");
         printf ("%d)", abs(S[i].q2));
    }      

    int main ()
    {
        freopen (FIN, "r", stdin);
        freopen (FOUT, "w", stdout);
        
        scanf ("%d %d %d %d", &A, &B, &C, &K);
        
        solve ();
        
        return 0;
    }