Question

3 probleme rezolvate cu structura alternativa ( enuntul problemei , analiza problemei si algoritmul in C/C++ . VA ROG AJUTATI-MA !!!

Answer 1

#include <iostream>#include <fstream>
using namespace std;
ifstream f("drum.in");ofstream g("drum.out");
int n, m, k, i, j, P[10000][10000];
struct planeta{    struct    {        int x;        int y;    } P1;    struct ppapa    {        int x;        int y;    } P2[100];    int nr;} leg[10000];
int lumina(int a, int b, int l){    for(i=0 ; i<l-1 ; i++)        if(leg[i].P1.x==a && leg[i].P1.y==b)        {            leg[i].nr++;            return i;        }    return 0;}
void citire(){    f>>n>>m>>k;    for(i=0 ; i<k ; i++)    {        int a,b;        f>>a>>b;        j=lumina(a,b,i);        if(j!=0)        {            leg[j].P1.x= a;            leg[j].P1.y= b;            f>>leg[j].P2[leg[j].nr].x>>leg[j].P2[leg[j].nr].y;        }        else        {            leg[i].P1.x=a;            leg[i].P1.y=b;            f>>leg[i].P2[leg[j].nr].x>>leg[i].P2[leg[j].nr].y;        }
        /*        leg[i+k].x1=leg[i].x2;        leg[i+k].y1=leg[i].y2;        leg[i+k].x2=leg[i].x1;        leg[i+k].y2=leg[i].y1;        */    }}
int numar;
void calea_spre_lumina(int i){    for(j=0 ; j<leg[i].nr ; j++)    {        int spre;        spre=lumina(leg[i].P2[j].x, leg[i].P2[j].y, k);
        if(leg[i].P2[j].x==n)            numar++;        else if(spre!=0)            calea_spre_lumina(spre);    }}

int main(){    citire();    calea_spre_lumina(1);    cout<<numar;}CERINTA: DanBarbilian 2018 cls X-a


#include <iostream>#include <iostream>#include<math.h>
using namespace std;
//sa se efectueze plata sumei cu monede de tipul a0, a1, a2,... stiind ca exista //suficiente monede de fiecare tip
int x[100],n,s=0, S=0;
void tiparire(int k){    int i;    for(i=1; i<=k; i++)        cout<<x[i]<<" ";    s=s-x[k];    cout<<endl;}
void init(int k){    if(k==1)        x[k]=0;    else x[k]=-1;}
int solutie(int k){    if (s==S)        return 1;    else return 0;}
int valid (int k){    if (s+x[k]<=S)    {
        s=s+x[k];        return 1;    }    return 0;}
void BT(){    int k=1;    init(k);
    while(k>0)        if((x[k]<9-s) &&( s<S) && (k<=n))        {            x[k]++;            if(valid(k)==1)                if(solutie(k)==1)                    tiparire(k);                else                {                    k++;                    x[k]=-1;
                }        }        else        {            k--;            s=s-x[k];        }}
int main(){    cin>>n>>S;    BT();    cout<<k<<" "<<s; }CERINTA: DanBarbilian 2018 cls X-a

#include <iostream>#include <fstream>
using namespace std;
ifstream f("ferma.in");ofstream g("ferma.out");
int di[4] = {1,0,-1,0};int dj[4] = {0,1,0,-1};
int Gradina[401][401],Map[401][401],m,n,nr_cerinta; // m= nr linii, n= nr coloaneint nr_zona,i_next,j_next,i,j;int d[100]; // numarul de parcele pentru fiecare zonaint x=1; // x= numarul de variabile unice din matrice +1int culturi[100],rezerva[100]; // acesti doi vectori vor fii identici
bool OK(int  i, int j){    if(i<1 || j<1 || i>m || j>n)        return false;    if(Map[i][j]!=0)        return false;    return true;}
bool sir(char c) // salvez intr-un vector, toate valorile care apar, dar numai o data (functioneaza impreuna cu if(sir(c)) de la Read{    int a;    for(a=1; a<=x; a++)        if(culturi[a]==c)            return false;    return true;}
void Read(){    f>>nr_cerinta;    f>>m>>n;    for(int i=1; i<=m; i++)        for(int j=1; j<=n; j++)        {            char c;            f>>c;            if(sir(c))            {                culturi[x]=c;                rezerva[x]=c; //vectorii culturi si rezerva sunt identici, pentru ca vectorul culturi mi se modifica fara motiv la un moment dat                x++;            }            Gradina[i][j]= (int) c; //bag valorile din fisier in matrice        }}
void algFill(int i, int j){    Map[i][j]=nr_zona;    d[nr_zona]++;    for(int a=0 ; a<4 ; a++)    {        i_next=i+di[a];        j_next=j+dj[a];        if(OK(i_next,j_next)&&Gradina[i_next][j_next]==Gradina[i][j])            algFill(i_next,j_next);    }}
int Rezolva() // calculez aria maxima din matrice{    int maxim=0;    for(i=1; i<=m; i++)        for(j=1; j<=n; j++)        {            nr_zona++;            algFill(i,j);            if(maxim<d[nr_zona])                maxim=d[nr_zona];        }    return maxim;}
int main(){    int l,c,leguma,a,Coloana,Linie,Litera;    int maxim1,maxim2=0;
    Read();
    maxim1=Rezolva(); // calculez maximul pentru matricea nemodificata
    if(nr_cerinta==2) // treubuie sa modific 1 elem din matrice a.i. sa obtin o arie mai mare    {    for(l=1; l<=m; l++)        for(c=1; c<=n; c++)        {            leguma=Gradina[l][c]; // copiez in leguma, codul aflat pe pozitia [l][c] pentru ca urmeaza sa modific matricea            for(a=1;a<x;a++)                {                    culturi[a]=rezerva[a]; // culturi mi se modifica fara motiv, asa ca am fost nevoit sa fac asta                    Gradina[l][c]=culturi[a]; // inlocuiesc poizita [l][c], pe rand, cu toate valorile posibile                    maxim2=Rezolva(); // testez daca in urma modificarii aria maxima e alta                    if(maxim2>maxim1)                    {                        maxim1=maxim2;                        Coloana=c;                        Linie=l;                        Litera=culturi[a]; // salvez toate datele referitoare la parcela modificata (coloana,linia, si litera cu care am inlocuit-o)                    }                }            Gradina[l][c]=leguma; // readuc matricea la forma initiala        }        cout<<Linie<<" "<<Coloana<<"\n"<< (char) Litera;    }    if(nr_cerinta==1)        cout<<maxim1; // daca dau cout<<Rezolva(), nu imi afiseaza 11 (cum ar trebui), imi afiseaza 119 (iar eu nici nu am atatea elemente in matrice
}CERINTA: Algoritmul lui Fill