Problema OJI 2009

[•Mitza444]

Buna am si eu o problema nu e chiar tema ci e pt olimpiada..........daca ma puteti ajuta un pik sa-mi dati cva idei.........
Mama mea este profesoară de informatică, dar îi place foarte mult să gătească. Recent am descoperit caietul ei de reţete, care arată foarte neobişnuit. Fiecare reţetă este scrisă pe un singur rând pe care sunt precizate produsele folosite, cantităţile, precum şi ordinea în care se execută operaţiile. De exemplu:
(unt 50 zahar 250 ou 4)5
ceea ce înseamnă că se amestecă 50 grame unt cu 250 grame zahăr şi cu 4 ouă timp de 5 minute. Pentru fiecare produs mama foloseşte întotdeauna aceeaşi unitate de măsură, aşa că unităţile de măsură nu mai sunt precizate. Numele produsului este scris întotdeauna cu litere mici, iar produsele şi cantităţile sunt separate prin spaţii (unul sau mai multe). Produsele care se amestecă împreună sunt încadrate între paranteze rotunde; după paranteza rotundă închisă este specificat timpul de preparare.
Evident, mama are şi reţeţe mai complicate:
(((zahar 100 ou 3)5 unt 100 nuca 200)4 (lapte 200 cacao 50 zahar 100) 3)20
Să traducem această reţetă: se amestecă 100 grame zahăr cu 3 ouă timp de cinci minute; apoi se adaugă 100 grame unt şi 200 grame nucă, amestecând totul încă 4 minute. Se amestecă 200 ml lapte cu 50 grame de cacao şi 100 grame zahăr timp de 3 minute, apoi se toarnă peste compoziţia precedentă şi se amestecă totul timp de 20 minute.
Observaţi că înainte sau după parantezele rotunde pot să apară sau nu spaţii.
Cerinţă

Dată fiind o reţetă să se determine timpul total de preparare, precum şi cantităţile necesare din fiecare produs.
Date de intrare

Fişierul de intrare reteta.in conţine pe prima linie un şir de caractere care reprezintă o reţetă.
Date de ieşire

Fişierul de ieşire reteta.out va conţine pe prima linie timpul total necesar pentru prepararea reţetei. Pe următoarele linii sunt scrise ingredientele în ordine lexicografică (ordinea din dicţionar), câte un ingredient pe o linie. Pentru fiecare ingredient este specificat numele urmat de un spaţiu apoi de cantitatea totală necesară.
Restricţii

0 < Lungimea unei reţete ≤ 1000
1 ≤ Numărul de ingrediente ≤ 100
Numele unui ingredient este scris cu maxim 20 litere mici ale alfabetului englez.
Timpii de preparare sunt numere naturale < 100
Cantităţile specificate în reţete sunt numere naturale < 1000
Pentru determinarea corectă a timpului total se acordă 30% din punctajul pe test; pentru determinarea corectă a timpului total şi afişarea corectă a ingredientelor (ordonate lexicografic) se acordă integral punctajul pe test.
Exemple
reteta.in
(((zahar 100 ou 3)5 unt 100 nuca 200)4 (lapte 200 cacao 50 zahar 100) 3)20
reteta.out
32
cacao 50
lapte 200
nuca 200
ou 3
unt 100
zahar 200

Daca ma puteti ajuta vu o rezolvare de cls a9-a - a10-a.............................

[•caen1]

Ai încercat aici? Nu dă și sursă, dar descrie soluția.

[•Mitza444]

Da am vazut numai ca problema e ca nu prea stiu cum sa implementez.....daca imi puteti da niste indicatii

[•SpiderMan]

Odata ai aici pe infoarena problema, poti incerca daca eventual vrei sa implementezi cam cat iei, sunt aceleasi teste ca si la OJI, http://infoarena.ro/problema/reteta2. Acum ca si o idee, ai putea face cam asa : pentru timpul total, ti-e clar ca trebuie sa aduni la sol fiecare numar X de dupa paranteze, si ai solutia. Adica pentru exemplu, ai asa :

Cod:

(((zahar 100 ou 3) 5 unt 100 nuca 200) 4 (lapte 200 cacao 50 zahar 100)3)20

Ai primul 5 de dupa ), apoi 4 de dupa ), 3 si 20, in total facand 32, adica exact solutia. Adica pur si simplu faci asa : daca dai de o ')', iei numarul imediat de dupa acea paranteza, si il aduni solutiei. Acum pentru punctul 2, faci cel mai usor asa : zice ca poti avea maxim 100 ingrediente, deci iti tii o structura care contine un char, fiind numele acelui ingredient, si un int, care sa fie valoarea. Cand dai de un ingredient, vezi daca il mai ai pus, daca nu il adaugi si bagi cat trebuie. Daca il mai ai, atunci la int adaugi cantitatea corespunzatoare. Cel mai usor sa bagi un element este sa iei o variabila sa zicem N, sa zicem nr. de ingrediente. Daca vrei sa adaugi la structura faci ++N si adaugi ce trebuie, iar ca sa vezi daca mai exista faci un for de la 1 -> N si vezi daca mai ai acel ingredient. Acum la final, sortezi aceasta structura dupa char si afisezi . Iti pun aici cum sa sortezi lejer cu sortul din STL si cum iti poti tine o structura lejer.

Cod:

struct vector {
    char in[MAX_N];
    int val;
} q[105];

bool operator <  (const vector& a , const vector& b) { // asta e functia de sortare
    return strcmp (a.in, b.in) < 0; // compara pentru fiecare 2 elemente la un pas ca a sa fie mai mic ca b din punct 
// de vedere lexicografic
}

sort(q + 1 , q + N + 1); // sortarea pentru N elemente, daca ai indexarea de la 1 -> N

[•Mitza444]

citirea cum imi sugerezi sa o fac sa citestesc fiecare caracter adica cam asa??
while(f.eof())
f>>c;
(char c)
sau stii ceva mai simplu??
si inca ceva imi mai poti explica putin functia aceea de sortare ca nu am inteles foarte bine(deabia am terminat a 9-a si nu reusesc nici cum sa ma prind cum mere problema asta) ,daca imi mai poti explica un pic cum e cu functia aceea si acolo la citire poate reusesc....

[•SpiderMan]

Fii atent aici : daca ai de sortat un vector, vrei sa-l sortezi normal, te gandesti LOGIC asa : ma, daca am 2 elemente, a si b, eu trebuie sa-i spun acelei FUNCTII in ce relatie trebuie sa le fie ele DUPA SORTARE. Adica mai usor, el alege la un moment dat 2 elemente si le compara (V[ i ] si V[ j ]). Daca avem functia asa :

Cod:

bool comp (int a, int b) {
    return a < b;
}

Atunci a o sa fie V[ i ] si b o sa fie V[ j ]. Acum return a < b este totuna cu :

Cod:

if (a < b) return 1;
return 0;

Ori prima, ori a doua sunt corecte. Acum, ti-am explicat si-ti mai spun inca odata : tu trebuie sa concepi acea functie LOGIC : adica daca ai un vector, sau o structura, te gandesti dupa ce sa le sortezi si cum. Un exemplu : daca avem structura st, si elementele x si y, si trebuie sa sortam crescator dupa x, si in caz de egalitate descrescator dupa y, te gandesti si zici : daca am 2 elemente , V[ i ] si V[ j ], care sunt structuri st, vedem daca V[ i ].x == V[ j ].x atunci sortam dupa y descrescator, adica folosesti semnul > intre indici, ca la BUBBLE SORT sau QSORT. Altfel sortezi cu semnul < intre xsi.

Cod:

struct st {
    int x, y;
};
st V[MAX];

bool comp (const st& a, const st& b) {
    if (a.x == b.y) return a.y > b.y;
    return a.x < b.x;
}

sort (V + 1, V + N + 1, comp);

In functia de comparare, a ia locul lui V[ i ] la un moment dat, si b lui V[ j ] tot in acel moment. Exact ce ti-am explicat mai sus, inlocuiesti pe V[ i ] = a si V[ j ] = b. El la fiecare moment de timp o sa compare si o sa vada. La BUBBLE SORT, ai cam asa : daca intre 2 elemente consecutive este o ALTA RELATIE decat cea buna, atunci se interschimba. EXACT la fel este si aici, doar NU SUNT POZITII CONSECUTIVE, CI ALESE DE FUNCTIE. Deci, de acum in colo, daca vrei sa concepi o functie, te gandesti logic cum vrei sa sortezi, adica CE RELATIE sa fie intre elemente, si exact aia o pui la comparare. Ai de grija, sa nu pui >= sau <=, ca nu are rost, cateodata e cu probleme, pentru ca daca sunt egale, adica 5 cu 5, stie el ce sa faca . Acum la partea cu citirea, nu iti recomand caracter cu caracter, desi aici nu conteaza, pe viitor e mai rapida citirea cu sir de caractere.

Cod:

char S[MAX];
fin >> S;// sau fin.getline (S, MAX); <- merge mai repede uneori

[•Mitza444]

buna am reusit sa scriu un cod si problema e aproape gata( nu stiu daca nu pica la memorie)......ce mai trebuie sa fac este sa sortez o matrice si sa grupez elemntele.....ar fi o idee buna sa folosesc functia strcmp pe linia i si i+1 si sa le schimb daca codul caracterului este mai mic decat celalt si sa fac asta pana nu se mai face nici o schimbare.............poate ar fi o idee buna nu stiu desi poate e cam complicat si dureaza mult...........daca aveti alte idei mai simple??
va pun aici codul:

Cod:

#include<cstdio>
using namespace std;
char mat[100][20];
int v[100];
int main(){
	char c;
	int t,tt=0,i=1,j=1,gasit=0,jmax=0,n,m;
	FILE * pFile;
	pFile = fopen ("reteta.in","r");
	 while (!feof(pFile)){
		fscanf(pFile,"%c",&c);
		if(c==')'){fscanf(pFile,"%d",&t);
					tt=tt+t;}
		if(c>='a' && c<='z'){
			mat[i][j]=c;j++;gasit=1;}
		if(c==' ' && gasit==1){fscanf(pFile,"%d",&v[i]);i++;gasit=0;
		if(j>jmax){jmax=j;}
		j=1;
		}
		
	}
	pFile = fopen ("reteta.out","w");
	fprintf(pFile,"%d",tt);
	fprintf (pFile,"\n");
	for(n=1;n<=i-1;n++){
		for(m=1;m<=jmax;m++){
			if(mat[n][m]!=0){fprintf(pFile,"%c",mat[n][m]);}
		}
		fprintf (pFile," ");
		fprintf(pFile,"%d",v[n]);
		fprintf (pFile,"\n");
	}
		
	return 0;
}

[•maritim]

Salut !

Pana la olimpiada mai trebuie sa inveti functii si structuri !

Tu vei avea nevoie de o Structura care sa iti pastreze pentru fiecare ingredient in parte numele (sub forma de string) si cantitatea (int). Astfel vei avea un vector destructuri (pana la 100 de elemente in total), in care vei retine cele N posibile elemente. Dupa ce ai aflat toate ingredientele si cantitatea, ele trebuiesc sortate crescator dupa nume. In acest mod vei sorta vectorul de structuri, interschimband structurile intre ele, nu doar numele sau cantinatea.

Ar trebui sa arate cam asa:

Cod:

typedef struct
{
char NumeIngr[25];
int cantitate;
} Ingredient;

Ingredient A[101] // declari vectorul ingredient

In concluzie vei sorta acest vector cu bubble sort si gata problema !

Mult succes si sper sa te ajute!

[•Mitza444]

Buna am reusit sa rezolv problema si cred ca e cat de cat bn numai ca atunci cand compileaza imi da o eroare ceva de genu return code -197....
Ma puteti ajuta ??(folosesc Mingw Developer Studio)

Cod:

#include<cstdio>
#include<string>
using namespace std;
int v[100];
int main(){
	string ing[100],sc;
	char c;
	int t,tt=0,i=0,gasit=0,jmax=0,n,m,j,man;
	FILE * pFile;
	pFile = fopen ("reteta.in","r");
	 while (!feof(pFile)){
		fscanf(pFile,"%c",&c);
		if(c==')'){fscanf(pFile,"%d",&t);
					tt=tt+t;}
		if(c>='a' && c<='z'){
			i++;
			ungetc(c,pFile);
			fscanf(pFile,"%s",&ing[i]);
		}
		if(c>='0' && c<='9'){
			ungetc(c,pFile);
			fscanf(pFile,"%d",&v[i]);
		}
	 }
		while(gasit==0){
			gasit=1;
			for(j=1;j<=i;j++){
				if(ing[j]>ing[j+1]){
					sc=ing[j];
					ing[j]=ing[j+1];
					ing[j+1]=sc;
					man=v[j];
					v[j]=v[j+1];
					v[j+1]=man;
					gasit=0;
				}
			}
		}
		for(j=1;j<=i;j++){
			if(ing[i]!="///"){
				for(m=j+1;m<=i;m++){
					if(ing[j]==ing[m]){
						ing[m]="///";
						v[j]=v[j]+v[m];
						v[m]=-1;
					}
				}
			}
		}
	pFile = fopen ("reteta.out","w");
	fprintf(pFile,"%d",tt);
	fprintf (pFile,"\n");
	for(j=1;j<=i;j++){
		if(ing[i]!="///"){
		fprintf(pFile,"%s",ing[i]);
		fprintf(pFile," ");
		fprintf(pFile,"\n");
		}
	}
	return 0;
}

[•SpiderMan]

Nu merge sa citesti un STRING cu citirea din c. Eu ti-am modificat, am citit un string s[1005], si i-am atribuit lui ing[ i ] pe s. De asemenea cu afisarea, nu poti afisa un stirng cu citirea din c, am afisat string.c_str (), care converteste un string intr-un array de char (adica string din C), dar programul nu afiseaza bine. Te descurci tu de aici :
P.S. Se pare ca am gasit greseala, tu la sfarsit parcurgeai cu indicele j, si faceai (adica afisai si verificai) cu ing[ i ] in loc de ing[ j ]. Am modificat aia si am mai modificat sa nu iti afiseze aiureli, adica trebuie neaparat ca fiecare ingredient sa inceapa CU O LITERA MICA. Teoretic merge, o sa verific si o sa mai vad.
P.S. Final : Am luat 100 puncte (http://infoarena.ro/job_detail/601931), aveai doua greseli :
1. Nu lasa niciodata limita la fix, pentru ca la tine v sa zicem era indexat de la 0->99, nu pana la 100 (v[100]), deci mai bine pui mai mult. Testul 3 avea spre exemplu 150 ingrediente (nu stiu cum de a aparut atat, dar asta e), si am pus mai mult limita (v[185]).
2. La bubble sort, aparea eroare cand j = i, adica aici : for(j=1; j<=i; j++). Cand j = i, el testeaza pe ing[j+1], care nu exista, adica care este "", si cum "" e mai mic, il interschimba, si o sa-l adauge pe prima pozitie, si astfel pierzi ultimul ingredient, care este pe pozitia j + 1. Astfel, stergi egalul de acolo, si lasi j < i, si astfel ai rezolvat problema.
 

Cod:

#include<cstdio>
#include<string>
using namespace std;
int v[185];
char s[1005];
int main() {
    string ing[185],sc;
    char c;
    int t,tt=0,i=0,gasit=0,jmax=0,n,m,j,man;
    FILE * pFile;
    pFile = fopen ("reteta2.in","r");
    while (!feof(pFile)) {
        fscanf(pFile,"%c",&c);
        if(c==')') {
            fscanf(pFile,"%d",&t);
            tt=tt+t;
        }
        if(c>='a' && c<='z') {
            i++;
            ungetc(c,pFile);
            fscanf(pFile,"%s",&s);
            ing[i]=s;
        }
        if(c>='0' && c<='9') {
            ungetc(c,pFile);
            fscanf(pFile,"%d",&v[i]);
        }
    }
    while(gasit==0) {
        gasit=1;
        for(j=1; j<i; j++) {
            if(ing[j]>ing[j+1]) {
                sc=ing[j];
                ing[j]=ing[j+1];
                ing[j+1]=sc;
                man=v[j];
                v[j]=v[j+1];
                v[j+1]=man;
                gasit=0;
            }
        }
    }
    for(j=1; j<=i; j++) {
        if(ing[i]!="///") {
            for(m=j+1; m<=i; m++) {
                if(ing[j]==ing[m]) {
                    ing[m]="///";
                    v[j]=v[j]+v[m];
                    v[m]=-1;
                }
            }
        }
    }
    pFile = fopen ("reteta2.out","w");
    fprintf(pFile,"%d",tt);
    fprintf (pFile,"\n");
    for(j=1; j<=i; j++) {
        if(ing[j]!="///") {
            fprintf(pFile,"%s",ing[j].c_str());
            fprintf(pFile," ");
            fprintf(pFile,"%d\n", v[j]);
        }
    }
    return 0;
}

[•Mitza444]

Mersi mult pentru ajutor am inteless acuma in sfasit ca nu stiam ca nu poti citi stringurile si scrie,si stiu de greseala aia cu i numai ca am corectat-o si am uitat sa salvez pt ca nu-mi mergea la faza cu stringurile....

No in orice caz ms foarte mult pentru ajutor si pentru timpu pierdut sa ma ajuti ca ma inteles ff greu