Cod sursa(job #435061)

Utilizator octavian.moraruOctavian Moraru octavian.moraru Data 6 aprilie 2010 20:48:35
Problema Gutui Scor 10
Compilator cpp Status done
Runda teme_upb Marime 3.91 kb
#include <iostream>

using namespace std;

struct Gutuie
{
    int inaltime;
    int greutate;
    bool ales;
};

bool myCompare( Gutuie g1, Gutuie g2 )
{
    if (g1.greutate == g2.greutate)
        return g1.inaltime > g2.inaltime;
    return g1.greutate > g2.greutate;
};

int main()
{
    //cout << "Hello world!" << endl;
    /*
    int A[] = {1, 4, 2, 8, 5, 7};
    const int N = sizeof(A) / sizeof(int);
    sort(A, A + N);
    for(int i = 0 ; i < N; i++)
        cout << A[i] << " ";
    */
    int n,h,u;
    FILE *fin = fopen("gutui.in","r");
    FILE *fout = fopen("gutui.out","w");
    Gutuie* g;

    fscanf(fin,"%d %d %d",&n,&h,&u);

    g = (Gutuie *)malloc(sizeof(Gutuie) *n);

    for (int i = 0 ; i < n ; i++)
    {
        fscanf(fin,"%d %d",&g[i].inaltime,&g[i].greutate);
        g[i].ales = false;
    }

    sort(g, g + n, myCompare);

    for (int i = 0 ; i < n ; i++)
        cout << g[i].inaltime << ' ' << g[i].greutate << '\n';

    cout << '\n';

    int total  = 0;
    int u_curent = 0;
    int prim = 0;
    int rezervat = 0;
    int maxh = 0;
    int k = 0;
    bool continua = true;
    bool alestot = false;
    while (continua)
    {
        continua = false;
        alestot = true;
        rezervat = 0;
        maxh = 0;
        for (int i = 0 ; i < n ; i++)
        {
            if(g[i].ales || g[i].inaltime + u_curent > h)
            {
                //gutuia a depasit inaltimea maxima
                //nu mai poate fi culeasa
                //sau a fost deja aleasa
                //g[i].ales = true;
                continue;
            }
            //if(!g[i].ales && alestot)
            if(!g[i].ales)
            {
                //salvam indexul primei gutui care poate fi culeasa
                //in caz ca toate gutuile pot fi culese
                //TODO: in acest caz trebuie culeasa cea mai inalta gutuie?

                if(g[i].inaltime > maxh)
                {
                    prim = i;
                    maxh = g[i].inaltime;
                }
                if(alestot) //prima gutuie care se poate culege
                {
                    rezervat = (h - (g[i].inaltime + u_curent))/u - 1;
                    k = i;
                    //rezervat gutui se pot culege pana se culege aceasta gutuie
                    alestot = false;
                    continue;
                }

                //continue;
            }
            //if(!g[i].ales && (g[i].inaltime + u_curent + u > h || g[i].inaltime + u_curent + rezervat > h))
            if(g[k].inaltime <= g[i].inaltime && (g[i].inaltime + u_curent + u  > h || rezervat <= 0))
            {
                //gutuia nu poate fi aleasa la urmatoarea iteratie dupa culegere gutuilor rezervate
                g[i].ales = true;
                total += g[i].greutate;
                u_curent += u;
                continua = true;
                cout << g[i].greutate << ' ' << g[i].inaltime << '\n';
                break;
            }
            else
                rezervat--;
            /*if(g[i].inaltime + u_curent < h)
            {
                //gutuia poate fi culeasa
                //cate gutui pot culege pana sa culeg aceasta gutuie?
                k = (h - g[i].inaltime)/u;
                //adica k * u cm
                k *= u;
                rezervat += k;
                //if(!k) //daca poate fi culeasa la urmatoarea iteratie
                  //  continue;

            }*/
        }
        if(!continua && !alestot)
        {
            //daca toate gutuile se pot culege ulterior
            g[prim].ales = true;
            total += g[prim].greutate;
            u_curent += u;
            cout << g[prim].greutate << ' ' << g[prim].inaltime << '\n';
            continua = true;
        }

    }

    fprintf(fout,"%d",total);
    fclose(fin);
    fclose(fout);

    return 0;
}