Cod sursa(job #463113)

Utilizator simona.poilincaSimona Poilinca simona.poilinca Data 14 iunie 2010 16:47:14
Problema Gutui Scor 10
Compilator c Status done
Runda teme_upb Marime 2.2 kb
//Georgescu Mihai Alexandru 321CA

#include <stdio.h>
#include <stdlib.h>


int main(){

    FILE* fin = fopen("gutui.in","r");
    FILE* fout = fopen("gutui.out","w");

    int N; // nr gutui din copac
    fscanf(fin, "%d", &N);

    int H; //inaltimea maxima la care ajunge Gigel
    fscanf(fin, "%d", &H);

    int U; //cu cat se ridica crengile gutuiului
    fscanf(fin, "%d", &U);

    // vector ce va retine inaltimea fiecarei gutui
    int* inaltimi = (int*)malloc(N*sizeof(int));

    // vector ce va retine greutatea fiecarei gutui
    int* greutati = (int*)malloc(N*sizeof(int));

    int i;
    for( i=0; i<N; i++ )
    {   fscanf(fin, "%d", &inaltimi[i]);
        fscanf(fin, "%d", &greutati[i]);
    }//for

    // am terminat cu preluarea datelor din intrare din fisier
    fclose(fin);

    int cos = 0; // in cos vom pune gutuile
    int ce_se_pune_in_cos;
    int valid = 1; //valid ramane 1 cat timp Gigel are gutui la care poate ajunge ptr a le culege

    int max = 0;
    ce_se_pune_in_cos = 0; //vom pune in cos gutuia de la indicele care pastreaza cea mai mare inaltime

    while(valid)
    {   valid = 0; // de fiecare data trebuie verificat ca mai exista cel putin o gutuie la care poate ajunge
        max = 0;
        for( i=0; i<N; i++ )
            if (inaltimi[i] <= 100)
            {   if (max < inaltimi[i])
                {   max = inaltimi[i];
                    ce_se_pune_in_cos = i;
                }else if (max == inaltimi[i]){
					if ( greutati[ce_se_pune_in_cos] < greutati[i])
					{	max = inaltimi[i];
						ce_se_pune_in_cos = i;
					}//if
				}//else
			}//if

        //punem in cos gutuia scoasa
        cos = cos + greutati[ce_se_pune_in_cos];
        
        // "scoatem" din evidenta gutuia scoasa
        inaltimi[ce_se_pune_in_cos] = 0;
        greutati[ce_se_pune_in_cos] = 0;

        //ridicam crengile gutuiului
        for( i=0; i<N; i++ )
            if (inaltimi[i] != 0)
                inaltimi[i] = inaltimi[i] + U;

        //verificam ca mai sunt gutui la care Gigel poate ajunge
        for( i=0; i<N; i++ )
            if ( (inaltimi[i] != 0) && (inaltimi[i] <= H) )
                valid = 1;

    }//while

    fprintf(fout, "%d", cos);
    
    fclose(fout);

return 0;}