"PROFI te adoră la orice oră!" devine sloganul blogului de acum înainte pe toată durata sponsorizării pe care lanţul de Supermarket-uri Profi a decis să ne-o acorde până la încheierea studiilor în Liceul de Informatică "Tiberiu Popoviciu" din Cluj-Napoca.

Dorim să le mulţumim pe această cale domnilor de la Profi Grigorescu, Profi Mărăşti, dar în special celor de la Profi Zorilor. Pe cei din urmă îi înţelegem că, în condiţiile meteo provaidate de end-ul lunii noiembrie, nu ies afară din magazin să ne ovaţioneze la trecerea prin preajma lor. Iată, mai jos, de ce "PROFI te adoră la orice oră!"

Probleme

6. Se consideră un număr nelimitat de rucsaci de acelaşi tip, cu fiecare putându-se transporta o greutate maximă G şi n<=1000 obiecte de greutăţi g1, g2, …, gn. Să se determine numărul minim de rucsaci necesari pentru a transporta toate obiectele.

#include<iostream>
#include<fstream>
using namespace std;
int a[100],n,G;
void citire()
{int i;
ifstream f("date.in");
f>>n;
for(i=1;i<=n;i++)
    f>>a[i];
f>>G;
}

int main()
{int s=0,nr=1,i,j;
citire();
sort(a,n+a);
for(i=1;i<=n;i++)
    if(a[i]>G)
        a[i]=0;
for(i=n;i>0;i--)
{if(a[i]!=0)
    {s=a[i];
    cout<<a[i]<<" ";
    a[i]=0;
for(j=1;j<i;j++)
{    if(a[j]!=0)
    {    if(s+a[j]<=G)
        {    s=s+a[j];
            cout<<a[j]<<" ";
            a[j]=0;
        }
        else if(s+a[j]>G)
        {    nr++;
            s=0;
            cout<<endl;
            j=i;
        }
    }
}
    }
}
cout<<endl<<endl<<nr<<" ruxa";
}

Fişier

8
1 3 4 5 8 6 2 6
8

7. Se dau două şiruri de lungime N şi un număr K (N<1000 şi K<1000). Cele două şiruri au doar elementele 1 şi –1. Scopul este de a transforma primul şir în al doilea. Singura operaţie permisă este de a selecta o secvenţă de K elemente alăturate şi să le inversăm semnul la toate numerele cuprinse în această zonă. Dacă este posibil, se va afişa numărul minim de operaţii şi apoi poziţia de început a fiecărei operaţii efectuate.

#include<iostream>
#include<fstream>
using namespace std;
int n,k,v[10],a[10],b[10];

void citire()
{ifstream f("date.in");
int i;
f>>n>>k;
for(i=1;i<=n;i++)
    f>>a[i];
for(i=1;i<=n;i++)
    f>>b[i];
}

int verifica()
{int ok=1,i;
for(i=1;i<=n;i++)
    if(a[i]!=b[i])
        ok=0;
return ok;
}

void aplica(int i)
{int j;
for(j=i;j<i+k;j++)
    a[j]=-a[j];
}

int main()
{int i,j,k=0;
citire();
for(i=1;i<=n;i++)
    if(a[i]!=b[i])
    {aplica(i);
    v[k]=i;
    k++;
    if(verifica()==1)
        i=n+1;
    else i=1;
    }
cout<<k<<" operatii"<<endl;
for(i=0;i<k;i++)
    cout<<v[i]<<" ";
}

Fişier

5
2
-1 1 1 1 -1
1 1 -1 1 -1

#include<iostream>
#include<fstream>
using namespace std;
int a[10][10],n,m,sol[10][10],ax,bx,cx,ay,by,cy,oka=1,okb=2,okc=3,nr;

void citire()
{int i,j;
ifstream f("date");
f>>n>>m;
for(i=1;i<=n;i++)
    for(j=1;j<=m;j++)
        f>>a[i][j];
f>>ax>>ay>>bx>>by>>cx>>cy;
}

void fill(int i, int j, int k)
{
    if(a[i][j]==k)
    {
    a[i][j]=-k;nr++;
    if(i==bx && j==by)
        okb=1;
    if(i==cx && j==cy)
        okc=1;
    fill(i-1,j,k);
    fill(i-1,j+1,k);
    fill(i,j+1,k);
    fill(i+1,j+1,k);
    fill(i+1,j,k);
    fill(i+1,j-1,k);
    fill(i,j-1,k);
    fill(i-1,j-1,k);
    }
}

int main()
{int nra,i,j,k,nrb,nrc,minim=INT_MAX;
citire();
k=a[ax][ay];
oka=1;
okb=2;
okc=3;
fill(ax,ay,k);
nra=nr;
nr=0;
if(oka==1 && okb==2 && okc==3)
{k=a[bx][by];
fill(bx,by,k);
nrb=nr;nr=0;
if(okc==3)
    cout<<"Obiecte diferite";
fill(cx,cy,a[cx][cy]);
nrc=nr;
if(nra<=nrb && nra<=nrc)
    cout<<endl<<nra;
if(nrb<=nra && nrb<=nrc)
    cout<<endl<<nrb;
if(nrc<=nrb && nrc<=nra)
    cout<<endl<<nrc;
}

}

GREEDY. NETERMINATA. Se dau n numere întregi nenule B={b1, b2, …, bn} si m numere întregi nenule a1, a2, …, am. (m<n). Să se determine o submulţime a mulţimii B care maximizează valoarea expresiei
E=a1*x1 + a2*x2 + … + am*xm

#include<iostream>
#include<fstream>
using namespace std;
int n,m,b[100],a[100];

void citire()
{int i;
ifstream f("date");
f>>n;
for(i=1;i<=n;i++)
    f>>b[i];
f>>m;
for(i=1;i<=m;i++)
    f>>a[i];
}

int main()
{int e=0,i,j,aneg[10],bneg[10],k=0,l=0,mm;
citire();
sort(a,m+a);
sort(b,n+b);
mm=m;
for(i=1;i<=m;i++)
    if(a[i]<0)
    {aneg[k]=a[i];k++;}
for(i=1;i<=n;i++)
    if(b[i]<0)
    {bneg[l]=b[i];l++;}
for(i=1;i<k;i++)
    for(j=i+1;j<=k;j++)
        if(abs(aneg[i])>abs(aneg[j]))
            swap(aneg[i],aneg[j]);
       
for(i=1;i<l;i++)
    for(j=i+1;j<=l;j++)
        if(abs(bneg[i])>abs(bneg[j]))
            swap(bneg[i],bneg[j]);

    while(k>0)
    {    e=e+aneg[k]*bneg[l];
        k--;
        l--;
    }
    while(mm>0)
    {
        if(a[i]>0)
            {e=e+a[mm]*b[n];
    mm--;
    n--;}
            else break;
    }

cout<<e;
}

Se da un numar n si multimea {1,2,3...n}. Sa se afiseze o submultime de lungime maxima care are proprietatea ca niciun element nu se imparte la niciun altul.

#include<iostream>
#include<fstream>
using namespace std;
int n,a[100],x[100],maxi[100],ma=0;

void afisare(int x[],int n)
{int i;
for(i=1;i<=n;i++)
    cout<<x[i]<<" ";
cout<<endl;}

int verif(int i)
{int j;
for(j=1;j<i;j++)
    if(x[i]%x[j]==0)
        return 0;
return 1;}

void back(int i)
{int j;
for(j=x[i-1]+1;j<=n;j++)
{x[i]=j;
if(verif(i))
    {if(i>ma)
        {ma=i;
    for(int k=1;k<=ma;k++)
        maxi[k]=x[k];
        }
    back(i+1);
    }
   
}
}

int main()
{int i;
cin>>n;
for(i=1;i<=n;i++)
    a[i]=i;
back(1);
afisare(maxi,ma);
}

Se citeşte un şir de n numere întregi. Să se aleagă din şir un număr maxim de elemente astfel încât produsul lor să fie maxim. De exemplu, pentru n = 5 şi şirul 3, –4, 2, –5, –8 se vor alege 3, 2, –5, –8.

#include<iostream>
#include<fstream>
using namespace std;
int n,a[100];
void citire()
{int i;
ifstream f("date");
f>>n;
for(i=0;i<n;i++)
    f>>a[i];
}

void afisare(int x[],int n)
{int i;
for(i=0;i<n;i++)
    cout<<x[i]<<" ";
cout<<endl;
}

int main()
{int i,j=0,k=0,p=1,v[100],s=0,b[100],c[100],ok=0,nrneg=0;
citire();
for(i=0;i<n;i++)
    for(j=i+1;j<n;j++)
        if(abs(a[i])>abs(a[j]))
            swap(a[i],a[j]);
for(i=0;i<n;i++)
    if(a[i]<0)
        nrneg++;
if(nrneg%2==1)
    for(i=0;i<n;i++)
        if(a[i]<0)
            {a[i]=1;
            break;}
cout<<"Numerele alese"<<endl;
for(i=0;i<n;i++)
    {if(a[i]!=1)
        cout<<a[i]<<" ";
    p*=a[i];}
    cout<<endl<<"Produsul "<<p;
}

Se dă un şir de n nr. nat. Folosind un algoritm Greedy, partiţionaţi şirul în două submulţimi care au proprietatea că diferenţa dintre sumele elementelor este minimă.

#include<iostream>
#include<fstream>
using namespace std;
int n,a[100];
void citire()
{int i;
ifstream f("date");
f>>n;
for(i=0;i<n;i++)
    f>>a[i];
}

void afisare(int x[],int n)
{int i;
for(i=0;i<n;i++)
    cout<<x[i]<<" ";
cout<<endl;
}

int main()
{int i,j=0,k=0,p=0,v[100],s=0,b[100],c[100],ss=0;
citire();
sort(a,n+a);
for(i=0;i<n;i++)
    s=s+a[i];
for(i=n-1;i>=0;i--)
{    if(ss+a[i]<=s/2)
        {b[k]=a[i];
        ss=ss+b[k];
        k++;}
    else
        {v[p]=i;
        p++;}
}
for(i=0;i<p;i++)
    {c[j]=a[v[i]];
    j++;}
afisare(b,k);
cout<<"Suma "<<ss<<endl;
afisare(c,j);
cout<<"Suma "<<s-ss<<endl;
cout<<"Diferenta "<<abs(s-ss-ss);
}

Fişier

9
2 5 7 1 9 10 6 4 3

Se da un punct din interiorul unui obiect (intr-o matrice 0-1). Sa se determine numarul de valori 0 situate in imediata vecinatate a frontierei obiectului.

#include<iostream>
#include<fstream>
using namespace std;
int a[100][100],viz[100][100],n,xx,yy,nr;

void citire()
{int i,j;
ifstream f("date");
f>>n;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            f>>a[i][j];
    f>>xx>>yy;
}

void fill(int x, int y)
{
    if(x>=1 && x<=n && y>=1 && y<=n)
    if(a[x][y]==1 && viz[x][y]==0)
        {viz[x][y]=1;
        fill(x,y+1);
        fill(x,y-1);
        fill(x-1,y);
        fill(x+1,y);}
    else if(x>=1 && x<=n && y>=1 && y<=n && a[x][y]==0)
    {    if(viz[x][y]==0)
        nr++;
    viz[x][y]=2;}
}

int main()
{citire();
fill(xx,yy);
cout<<nr;
}

Fisier

5
0 1 1 0 0
0 0 0 0 1
1 1 0 0 0
0 0 0 0 1
1 1 1 0 0
3 1

Se da o fotografie color (reprezentata printr-o matrice nxm). Culorile sunt numere intregi intre 0 si 9. Sa se verifice daca exista o culoare majoritara. (care sa acopere mai mult de jumatate din suprafata matricii.)

#include<iostream>
#include<fstream>
using namespace std;
int a[100][100],n,m;

void citire()
{int i,j;
ifstream f("date");
f>>n>>m;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            f>>a[i][j];
}

int main()
{
int v[100]={0},i,j,p,k;
citire();
for(i=1;i<=n;i++)
    for(j=1;j<=m;j++)
        {p=a[i][j];
        v[p]++;}
for(k=0;k<=9;k++)
    if(v[k]>=n*m/2)
        {cout<<k<<" "<<v[k]<<endl;break;}
cout<<"Culoarea majoritara "<<k<<" apare de "<<v[k]<<" ori";
}

Fisier

5 5
1 1 1 2 1
2 2 1 1 1
4 5 5 5 1
4 2 5 6 7
1 1 1 1 1

In conditiile problemei 6, sa se verifice daca exista un obiect care sa acopere mai mult de jumatate din matrice.

#include<iostream>
#include<fstream>
using namespace std;
int a[100][100],n,m,nr;

void citire()
{int i,j;
ifstream f("date");
f>>n>>m;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            f>>a[i][j];
}

void fill(int x,int y,int k)
{
    if(x>=1 && x<=n && y>=1 && y<=m)
    if(a[x][y]==k)
        {a[x][y]=(-1)*k;
        nr++;
        fill(x,y+1,k);
        fill(x,y-1,k);
        fill(x-1,y,k);
        fill(x+1,y,k);}
}

int main()
{int i,j,k;
citire();
for(i=1;i<=n;i++)
    for(j=1;j<=m;j++)
    {k=a[i][j];
    nr=0;
    fill(i,j,k);
    if(nr>=n*m/2)
        {cout<<k<<" "<<nr;return 0;}
    }
}

Fisier

5 5
1 1 1 1 1
2 2 2 2 2
4 2 2 2 2
4 2 2 2 2
1 1 1 1 1

Sa se verifice daca 2 puncte dintr-o fotografie fac parte din acelasi obiect.

#include<fstream>
#include<iostream>
#include<iomanip>
using namespace std;
int a[100][100],n,m,i,j,is,js,iis,jjs;

void citire()
{ifstream f("date");
    f>>n>>m;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            f>>a[i][j];
    f>>is>>js>>iis>>jjs;
}

void afisare()
{for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
            cout<<setw(3)<<a[i][j];
    cout<<endl;
    }
}

void fill(int i,int j)
{
    if(a[i][j]==1)
    {
        a[i][j]=2;
        fill(i-1,j);
        fill(i-1,j+1);
        fill(i,j+1);
        fill(i+1,j+1);
        fill(i+1,j);
        fill(i+1,j-1);
        fill(i,j-1);
        fill(i-1,j-1);
    }
}

int main()
{   citire();
       fill(is,js);
    if(a[is][js]==a[iis][jjs])
        cout<<"DA"<<endl;
    else cout<<"NU"<<endl;
    afisare();
    return 0;
}

Fisier

4 4
1 0 1 1
0 0 0 1
1 1 0 1
0 0 1 0
3 1
1 4

Sa se verifice daca un obiect de culoarea c1 este vecin cu un obiect de culoarea c2. Mesaj: DA/NU

#include<fstream>
#include<iostream>
#include<iomanip>
using namespace std;
int a[100][100],n,m,c1,c2;
int dx[]={-1,0,1,0,-1,1,1,-1},dy[]={0,1,0,-1,1,1,-1,-1};

void citire()
{int i,j;
ifstream f("date");
    f>>n>>m;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            f>>a[i][j];
        f>>c1>>c2;
}

int main()
{  int ok=1,i,j,inou,jnou,k;
citire();
       for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            {if(a[i][j]==c1)
                {for(k=0;k<8;k++)
                    {inou=i+dx[k];
                    jnou=j+dy[k];
                    if(a[inou][jnou]==c2)
                        ok=0;
                }
                }
            }
if(ok==0)
    cout<<"DA";
else cout<<"NU";
}

Fisier

4 5
1 2  2 2 4
5 10 2 4 4
5 5  5 4 6
9 9  9 9 2
1 6

Fotografia alb-negru a unui obiect este reprezentata sub forma unei matrici A (nxn) cu elemente din multimea {0,1}. Doua elemente sunt vecine "in 8 directii". Sa se stabileasca daca obiectul fotografiat este compus dintr-o singura bucata sau nu si sa se afiseze un mesaj corespunzator.

#include<fstream>
#include<iostream>
#include<iomanip>
using namespace std;
int a[100][100],n;

void citire()
{int i,j;
ifstream f("fill.in");
f>>n;
for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
        f>>a[i][j];
    f.close();
}

void fill(int i,int j)
{
    if(a[i][j]==1)
    {
        a[i][j]=2;
        fill(i-1,j);
        fill(i-1,j+1);
        fill(i,j+1);
        fill(i+1,j+1);
        fill(i+1,j);
        fill(i+1,j-1);
        fill(i,j-1);
        fill(i-1,j-1);
    }
}

int main()
{int i,j;
citire();
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(a[i][j]==1)
                {fill(i,j);
                i=j=n+2;}
  
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(a[i][j]==1)
                {cout<<"Mai mult de un obiect"<<endl;
                for(i=1;i<=n;i++)
                {for(j=1;j<=n;j++)
                    cout<<setw(3)<<a[i][j];
                cout<<endl;}
                return 1;}
    cout<<"Un singur obiect";
}

Fisier

4
1 0 0 0
0 1 0 0
0 0 0 1
0 0 1 0

Pe o matrice nxm sunt codificate obiecte prin valori nr. nat. Obiectele invecinate sunt codificate prin valori diferite. Sa se afiseze dimensiunea obiectelor maximale, coordonatele unui punct din interiorul acestora si codul lor.

#include<fstream>
#include<iostream>
#include<iomanip>
using namespace std;
int a[100][100],n,m,Dmax,nrob,D;
struct obiect{
    int i,j,cod;};
obiect x[10];

void citire()
{int i,j;
ifstream f("fill.in");
f>>n>>m;
for(i=1;i<=n;i++)
    for(j=1;j<=m;j++)
        f>>a[i][j];
    f.close();
}

void fill(int i,int j,int k)
{
    if(a[i][j]==k)
    {
        a[i][j]=k*(-1);
        D++;
        fill(i-1,j,k);
        fill(i-1,j+1,k);
        fill(i,j+1,k);
        fill(i+1,j+1,k);
        fill(i+1,j,k);
        fill(i+1,j-1,k);
        fill(i,j-1,k);
        fill(i-1,j-1,k);
    }
}

int main()
{
    int i,j,k;
    citire();
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            if(a[i][j]>0){
                k=a[i][j]; // k=codul obiectului
                D=0;
                fill(i,j,k);
                if(D>Dmax)
                    {Dmax=D;
                    x[1].i=i;
                    x[1].j=j;
                    x[1].cod=k;
                    nrob=1;}
                else if(D==Dmax)
                {nrob++;
                x[nrob].i=i;
                x[nrob].j=j;
                x[nrob].cod=k;}
            }
           
    cout<<"Dimensiune maxim "<<Dmax<<endl;
    for(i=1;i<=nrob;i++)
        cout<<"obiectul codificat "<<x[i].cod<<" contine punctul ("<<x[i].i<<","<<x[i].j<<")"<<endl;
   
for(i=1;i<=n;i++)
{   for(j=1;j<=m;j++)
        cout<<setw(3)<<a[i][j];
cout<<endl;
}
return 0;
}

Fisier

5 7
1 0 0 5 0 7 0
0 1 0 5 0 0 0
0 1 0 5 0 0 20
0 0 5 0 0 0 0
0 0 0 1 1 1 1

Fiind data o matrice m x n, unde m,n apartin lui N si exista y elemente notate cu 1 si z elemente notate cu 0 iar y+z=m*n, aflati aria cea mai intinsa de elemente de 1.
Exemplu:
m=4, n=4
matricea:
0 1 1 0
0 1 1 0
1 0 0 0
0 0 1 1
Se va afisa: 4, adica regiunea care cuprinde elementele: (1,2),(1,3),(2,2),(2,3)

#include<fstream>
#include<iostream>
#include<iomanip>
using namespace std;
int a[100][100],n,m;
int size;
void fill(int i,int j,int k)
{
    if(a[i][j]==1)
    {
        a[i][j]=k; // fiecarei element din regiune ii corespunde numarul zonei
        size++;
       /*verificam daca elementele alaturate pot apartine aceiasi regiuni si daca nu au fost 
         inca marcate*/
        fill(i-1,j,k);
        fill(i+1,j,k);
        fill(i,j-1,k);
        fill(i,j+1,k);
    }
}

int main()
{
    int i,j;
    ifstream f("fill.in");
    f>>m>>n;
    for(i=1;i<=m;i++)
        for(j=1;j<=n;j++)
            f>>a[i][j];
    int max=0;
    int k=1;
    for(i=1;i<=m;i++)
        for(j=1;j<=n;j++)
            if(a[i][j]==1){
                k++; //fiecarei regiuni ii va corespunde un numar de ordine
                size=0;//numarul de elemente dintr-o regiune este initial 0
                fill(i,j,k);
                if(max<size) max=size;//calculam maximul ariilor
            }
    cout<<max<<endl;
    for(i=1;i<=m;i++)
    {
        for(j=1;j<=n;j++)
            cout<<setw(3)<<a[i][j];
    cout<<endl;
    }return 0;
}

Fisier

4 4
0 1 1 1
0 1 1 1
1 1 1 1
0 0 1 1

Se oferă un lac de nxn "bălţi" care posedă sau nu obiecte plutitoare care pot susţine o broască de masă m. Broasca este paraşutată pe un astfel de obiect plutitor căruia îi vom atribui în continuare denumirea de "nufăr". Se citeşte dintr-un fişier cu denumire fortuită n, poziţia iniţială a amfibianului, un număr întreg m şi m perechi de coordonate pe care se găsesc nuferi. Să se jenereze într-o ordine fortuită toate traseele pe care le poate parcurge amfibianul pentru a ajunge la malul lacului. Pentru olimpici (se cere doar la faza naţională): Rezolvaţi aceeaşi problemă pentru masa broaştei M=m derivat de două ori în raport cu sinusul unghiului format de razele soarelui cu suprafaţa nufărului cel mai apropiat de centrul lacului.

#include<iostream>  // Rezolvare pentru non-olimpici
#include<fstream>
#include<iomanip>
using namespace std;

int L[10][10],sol[10][10],n,m,nrsol,is,js;
int dx[]={-1,-1,1,1},dy[]={-1,1,1,-1};

void citire()
{int a,b,i;
ifstream f("broasca");
f>>n>>is>>js>>m;
for(i=1;i<=m;i++)
{f>>a>>b;L[a][b]=1;}
}

void afisare()
{int i,j;
nrsol++;
cout<<"Solutia nr "<<nrsol<<endl;
for(i=1;i<=n;i++)
{    for(j=1;j<=n;j++)
        cout<<setw(3)<<sol[i][j];
cout<<endl;}
cout<<endl;
}

void traseu(int i, int j, int pas)
{int inou,jnou,k;
for(k=0;k<4;k++)
{inou=i+dx[k];
jnou=j+dy[k];
if(inou>=1 && inou<=n && jnou>=1 && jnou<=n)
    if(sol[inou][jnou]==0 && L[inou][jnou]==1)
    {sol[inou][jnou]=pas;
    if(inou==1 || inou==n || jnou==1 || jnou==n)
        afisare();
    traseu(inou,jnou,pas+1);
    sol[inou][jnou]=0;
    }
}
}

int main()
{citire();
sol[is][js]=1;
traseu(is,js,2);
cout<<nrsol<<" Solutii";
}

Fişier

7
4 3
10
1 2
1 4
2 3
2 5
3 4
3 5
4 1
5 2
6 1
7 2

Un turist pleaca in vacanta de iarna la munte. El descopera o suprafata dreptunghiulara de teren denivelat unde vrea sa schieze. Cunoscand cotele diferitelor portiuni din acest teren si stiind in ce portiunde se afla schiorul, sa se determine toate partiile posibile pe care acesta poate cobori, pana la iesirea din teren, La un moment dat, schiorul se poate deplasa in orice portiune de teren invecinata, avand o cota strict inferioara cotei terenului pe care se afla el in momentul respectiv. Se citesc dimensiunile terenului m si n (2<=m<=100, 2<=n<=100), cotele diferitelor portiuni ale terenului (date in ordine, pe linii) si pozitia schiorului.

#include<iomanip>
#include<iostream>
#include<fstream>
using namespace std;
int n,m,L[10][10],sol[10][10],nrsol=0,is,js;
int dx[]={-1,0,1,0,-1,1,1,-1},dy[]={0,1,0,-1,1,1,-1,-1};

void citire()
{int i,j;
ifstream f("teren");
f>>m>>n;
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
f>>L[i][j];
f>>is>>js;
}


void afisare()
{int i,j;
nrsol++;
cout<<"Solutia nr "<<nrsol<<endl;
for(i=1;i<=n;i++)
{for(j=1;j<=m;j++)
cout<<setw(3)<<sol[i][j];
cout<<endl;}
cout<<endl;
}

void traseu(int i, int j, int pas)
{int inou,jnou,k;
for(k=0;k<8;k++)
{inou=i+dx[k];
jnou=j+dy[k];
if(inou>=1 && inou<=n && jnou>=1 && jnou<=m)
if(sol[inou][jnou]==0 && L[inou][jnou]<L[i][j])
{sol[inou][jnou]=pas;
 if(inou==1 || inou==n || jnou==1 || jnou==m)
 afisare();
 traseu(inou,jnou,pas+1);
 sol[inou][jnou]=0;}
}
}

int main()
{citire();
sol[is][js]=1;
traseu(is,js,2);
cout<<nrsol;
}

Fisier

5 5
20 10 7 5 6
22 8 20 60 18
12 10 30 120 12
24 6 60 100 15
2 4 4 5 6
3 2

8. ANFINISHID Se citeste o matrice nXm cu elemente numere naturale si o pozitie io, jo din matrice in care se afla un robot care se poate deplasa paralel cu liniile si coloanele matricii pe pozitii alturate.
Afisati toate drumurile pe care poate parcurge robotul matricea trecand prin fiecare pozitie de atatea ori cat este valoarea pozitiei respective.
Drumurile vor fi afisate ca perechi de coordonate.
Exemplu:
pentru datele de intrare
6 7
0 0 0 0 0 0 0
0 0 1 1 1 0 0
0 1 2 0 2 1 0
0 0 1 0 1 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
3 2
se afiseaza
3,2 3,3 4,3 3,3 2,3 2,4 2,5 3,5 4,5 3,5 3,6
3,2 3,3 4,3 3,3 2,3 2,4 2,5 3,5 3,6 3,5 4,5

#include<iomanip>
#include<iostream>
#include<fstream>
using namespace std;
int n,m,L[10][10],px[20],py[20],nrsol=0,is,js,ii=1,ff[10][10];
int dx[]={1,0,-1,0},dy[]={0,1,0,-1};

void citire()
{int i,j;
ifstream f("teren");
f>>n>>m;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
    {f>>L[i][j];
     ff[i][j]=L[i][j];}
f>>is>>js;
}

void afisare(int n)
{int i;
for(i=0;i<n-1;i++)
    cout<<px[i]<<","<<py[i]<<"  ";
nrsol++;
cout<<endl;
}

int matrice(int L[10][10])
{int i,j,ok=0;
for(i=1;i<=n;i++)
    for(j=1;j<=m;j++)
        if(L[i][j]>0)
            ok=1;
return ok;
}

void traseu(int i, int j)
{int inou,jnou,k;
for(k=0;k<4;k++)
{inou=i+dx[k];
jnou=j+dy[k];
if(inou>=1 && inou<=n && jnou>=1 && jnou<=m)
    if(L[inou][jnou]>0)
        {L[inou][jnou]--;
         px[ii]=inou;
         py[ii]=jnou;
         ii++;
         if(matrice(L)==0)
            {afisare(ii);
             for(int jj=1;jj<=ii+1;jj++)
             {px[jj]=0;
              py[jj]=0;}
             ii=1;
             L[inou][jnou]++;
            }
         else traseu(inou,jnou);
         //L[inou][jnou]++;
        }
}
}

int main()
{citire();
px[0]=is;
py[0]=js;
traseu(is,js);
cout<<endl<<"Solutii totale "<<nrsol;
}

Fisier

6 7
0 0 0 0 0 0 0
0 0 1 1 1 0 0
0 1 2 0 2 1 0
0 0 1 0 1 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
3 2

4. Pe o tabla de sah nXn sunt plasate m piese marcate prin valoarea -1, iar prin valoarea 0 sunt marcate pozitiile libere. Intr-o pozitie (i0,j0) se afla un cal, iar intr-o pozitie (i1,j1) un rege. Sa se determine toate traseele pe care calul poate sa mearga din pozitia initiala pana in cea a regelui si sa se intoaca de unde a plecat fara a trece de 2 ori prin aceeasi pozitie si mergand doar pe pozitii libere. Se citesc mai intai n si m, iar apoi m perechi reprezentand coordonatele pieselor. Ultimele se citesc coordonatele calului si ale regelui. Traseele se vor marca intr-o matrice si se for afisa si coordonatele prin care trece calul.

#include<iomanip>
#include<iostream>
#include<fstream>
using namespace std;
int n,m,L[10][10],sol[10][10],nrsol=0,calx,caly,regex,regey,ok=0;
int dx[]={-2,-1,2,1,2,1,-1,-2},dy[]={1,2,1,2,-1,-2,-2,-1};

void citire()
{int i,a,b;
ifstream f("sah");
f>>n>>m;
for(i=1;i<=m;i++)
    {f>>a>>b;
    L[a][b]=-1;}
f>>calx>>caly;
f>>regex>>regey;
}

void afisare()
{int i,j;
nrsol++;
cout<<"Solutia nr "<<nrsol<<endl;
for(i=1;i<=n;i++)
{for(j=1;j<=n;j++)
cout<<setw(3)<<L[i][j];
cout<<endl;}
cout<<endl;
}

void traseu(int i, int j, int pas)
{int inou,jnou,k;
for(k=0;k<8;k++)
{inou=i+dx[k];
jnou=j+dy[k];
if(inou>=1 && inou<=n && jnou>=1 && jnou<=n)
    if(L[inou][jnou]==1 && L[regex][regey]>0)
        afisare();
    else
        if(L[inou][jnou]==0 && L[inou][jnou]!=-1)
            {L[inou][jnou]=pas;
            traseu(inou,jnou,pas+1);
            L[inou][jnou]=0;
            }
}
}

int main()
{int i,j;
citire();
L[calx][caly]=1;
traseu(calx,caly,2);
cout<<"Sol totale "<<nrsol<<endl<<endl;
}

Fisier

5
6
1 3
3 4
2 2
1 5
5 2
4 1
1 1
4 5

7. Pe o tabla de sah nXn sunt plasate marcate prin valoarea 1, iar prin valoarea 0 sunt marcate pozitiile libere. Intr-o pozitie j0 de pe prima linie se afla un pion. Determinati toate traseele pe care poate ajunge pionul pana pe ultima linie. Traseele vor fi afisate atat in matrice cat si ca sir de pozitii.
Exemplu:
pentru datele
5
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 1 0 1 0
0 0 0 0 0
3
exista 3 solutii marcate in matrice:
0 0 0 0 0
0 0 1 0 0
0 0 2 0 0
0 1 3 1 0
0 0 4 0 0
sau
0 0 0 0 0
0 0 1 0 0
0 0 2 0 0
0 3 0 1 0
0 4 0 0 0
sau
0 0 0 0 0
0 0 1 0 0
0 0 2 0 0
0 1 0 3 0
0 0 0 4 0

#include<iomanip>
#include<iostream>
#include<fstream>
using namespace std;
int n,m,L[10][10],sol[10][10],nrsol=0,start;
int dx[]={1,1,1},dy[]={0,-1,1};

void citire()
{int i,j;
ifstream f("sah");
f>>n;
for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
        f>>L[i][j];
f>>start;
}

void afisare()
{int i,j;
nrsol++;
cout<<"Solutia nr "<<nrsol<<endl;
for(i=1;i<=n;i++)
{for(j=1;j<=n;j++)
cout<<setw(3)<<L[i][j];
cout<<endl;}
cout<<endl;
}

void traseu(int i, int j, int pas)
{int inou,jnou,k;
for(k=0;k<3;k++)
{inou=i+1;
jnou=j+dy[k];
if(inou>=1 && inou<=n && jnou>=1 && jnou<=n)
    if(jnou==j && L[inou][jnou]==0 || jnou!=j && L[inou][jnou]==1)
        {L[inou][jnou]=pas;
        if(inou==n)
            afisare();
   
    traseu(inou,jnou,pas+1);
    L[inou][jnou]=0;}
}
}
   
int main()
{int i,j;
citire();
L[1][start]=1;
traseu(1,start,2);
cout<<"Sol totale "<<nrsol<<endl<<endl;
}

Fisier

5
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 1 0 1 0
0 0 0 0 0
3

Pe o tabla de sah  n x n sunt plasate m piese marcate prin valoarea -1, iar prin valoarea 0 sunt marcate pozitiile libere. Intr-o pozitie (i0,j0) se afla un cal. Sa se determine traseul cu numar minim de pasi astfel incat calul sa manance toate piesele de pe tabla fara a trece de 2 ori prin aceeasi pozitie. Se citesc mai intai n si m, iar apoi m perechi reprezentand coordonatele pieselor. Ultimele se citesc coordonatele calului. Traseul va fi marcat intr-o matrice care se va afisa.

#include<iomanip>
#include<iostream>
#include<fstream>
using namespace std;
int n,m,L[10][10],sol[10][10],nrsol=0,x,y,z,w,drmin[10][10],mi, px[100],py[100],iz,jz;
int dx[]={-2,-1,2,1,2,1,-1,-2},dy[]={1,2,1,2,-1,-2,-2,-1};

void citire()
{int i,j;
ifstream f("sah");
f>>n>>m;
for(i=1;i<=m;i++)
    f>>px[i]>>py[i];
f>>iz>>jz;
}

void afisare()
{int i,j;
nrsol++;
cout<<"Solutia nr "<<nrsol<<endl;
for(i=1;i<=n;i++)
{for(j=1;j<=n;j++)
cout<<setw(3)<<sol[i][j];
cout<<endl;}
cout<<endl;
}

void traseu(int i, int j, int pas, int s)
{int inou,jnou,k,ii,jj,snou;
for(k=0;k<8;k++)
{inou=i+dx[k];
jnou=j+dy[k];
if(inou>=1 && inou<=n && jnou>=1 && jnou<=n)
    if(sol[inou][jnou]==0)
        {sol[inou][jnou]=pas;
        snou=s+L[inou][jnou];
        if(snou==m)
            {//afisare();
            if(pas<mi)
                {mi=pas;
                for(ii=1;ii<=n;ii++)
                    for(jj=1;jj<=n;jj++)
                        drmin[ii][jj]=sol[ii][jj];
                }
            }
        if (pas < mi)
traseu(inou,jnou,pas+1,snou);
        sol[inou][jnou]=0;
        }
}
}

int main()
{int i,j;
citire();
sol[iz][jz]=1;
for(i=1;i<=m;i++)
    L[px[i]][py[i]]=1;
mi=n*n;
traseu(iz,jz,2,0);
cout<<"Sol totale "<<nrsol<<endl;
cout<<endl<<"Drumul optim"<<endl;
for(i=1;i<=n;i++)
{for(j=1;j<=n;j++)
cout<<setw(3)<<drmin[i][j];
cout<<endl;}
cout<<endl<<mi;
cout<<endl;
for(i=1;i<=n;i++)
{for(j=1;j<=n;j++)
cout<<setw(3)<<L[i][j];
cout<<endl;}
cout<<endl;
}

Fişier

5
6
1 3
3 4
2 2
1 5
5 2
4 1
1 1

1. Un labirint dreptunghiular cu m linii si n coloane contine culoare (reprezentate prin 0) si pereti (reprezentati prin -1). Se dau coordonatele initiale ale unui soricel si coordonatele finale  in care  trebuie sa ajunga. Pe culoare se gasesc bucati de branza pt care se cunoaste greutatea in grame.
a) Sa se genereze toate solutiile., pt fiecare se afiseaza cantitatea consumata
b) Sa se afiseze solutia cea mai „consistenta”
(Soricelul se poate deplasa in 8 directii)

#include<iomanip>
#include<iostream>
#include<fstream>
using namespace std;
int n,m,L[10][10],sol[10][10],nrsol=0,x,y,z,w,dr[10][10],maxi=0;
int dx[]={-1,0,1,0,-1,1,1,-1},dy[]={0,1,0,-1,1,1,-1,-1};

void citire()
{int i,j;
ifstream f("labi");
f>>n>>m>>x>>y>>z>>w;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
f>>L[i][j];
}

void afisare()
{int i,j;
nrsol++;
cout<<"Solutia nr "<<nrsol<<endl;
for(i=1;i<=n;i++)
{for(j=1;j<=m;j++)
cout<<setw(3)<<sol[i][j];
cout<<endl;}
}

void traseu(int i, int j, int pas,int gr)
{int inou,jnou,k,ii,jj;
for(k=0;k<8;k++)
{inou=i+dx[k];
jnou=j+dy[k];
if(inou>=1 && inou<=n && jnou>=1 && jnou<=m)
if(L[inou][jnou]!=-1 && sol[inou][jnou]==0)
{sol[inou][jnou]=pas;
gr=gr+L[inou][jnou];
 if(inou==z && jnou==w)
     {
     afisare();
     cout<<gr<<endl<<endl;
     if(gr>maxi)
     {maxi=gr;
      for(ii=1;ii<=n;ii++)
         for(jj=1;jj<=m;jj++)
             dr[ii][jj]=sol[ii][jj];}
     }
 traseu(inou,jnou,pas+1,gr);
 sol[inou][jnou]=0;
 gr=gr-L[inou][jnou];
}
}
}

int main()
{int i,j;
citire();
sol[x][y]=1;
traseu(x,y,2,L[x][y]);
cout<<"Sol totale "<<nrsol<<endl;
cout<<endl<<"Drumul 8im"<<endl;
for(i=1;i<=n;i++)
{for(j=1;j<=m;j++)
cout<<setw(3)<<dr[i][j];
cout<<endl;}
cout<<endl<<maxi;
}

Fişier

5 4
3 3
5 1
 0  0  0  0
-1 -1  8 -1
 0 10  0 -1
 7 -1 25 -1

 0 14  0 -1

2. Fiind data o tabla de sah de dimensiunea nxn si un cal în coltul stânga sus al acesteia, se cere sa se afiseze toate posibilitatile de mutare a acestei piese de sah astfel încât sa treaca o singura data prin fiecare patrat al tablei. O solutie va fi afisata ca o matrice nxn în care sunt numerotate sariturile calului. Exemplu, pentru n=5, o solutie este
1 14 9 20 23
10 19 22 15 8
5 2 13 24 21
18 11 4 7 16
3 6 17 12 25

#include<iomanip>
#include<iostream>
#include<fstream>
using namespace std;
int n,L[10][10],sol[10][10],nrsol=0,x,y,z,w,dr[10][10],maxi=0;
int dx[]={-2,-1,1,2,2,1,-1,-2},dy[]={1,2,2,1,-1,-2,-2,-1};


void afisare()
{int i,j;
nrsol++;
cout<<"Solutia nr "<<nrsol<<endl;
for(i=1;i<=n;i++)
{for(j=1;j<=n;j++)
cout<<setw(3)<<sol[i][j];
cout<<endl;}
cout<<endl;
}


void traseu(int i, int j, int pas)
{int inou,jnou,k;
for(k=0;k<8;k++)
{inou=i+dx[k];
jnou=j+dy[k];
if(inou>=1 && inou<=n && jnou>=1 && jnou<=n)
if(sol[inou][jnou]==0)
{sol[inou][jnou]=pas;
 if(pas==n*n)
    afisare();
 traseu(inou,jnou,pas+1);
 sol[inou][jnou]=0;
}
}
}


int main()
{int i,j;
ifstream f("labi");
f>>n;
sol[1][1]=1;
traseu(1,1,2);
cout<<"Sol totale "<<nrsol<<endl;
}

Din fisier se citeste doar n.

Se pleaca din (x,y) si se ajunge (z,w). Sa se afiseze drumul minim.

#include<iomanip>
#include<iostream>
#include<fstream>
using namespace std;
int n,m,L[10][10],sol[10][10],nrsol=0,x,y,z,w,drmin[10][10],mi;
int dx[]={-1,0,1,0},dy[]={0,1,0,-1};

void citire()
{int i,j;
ifstream f("labi");
f>>n>>m>>x>>y>>z>>w;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
f>>L[i][j];
}

void afisare()
{int i,j;
nrsol++;
cout<<"Solutia nr "<<nrsol<<endl;
for(i=1;i<=n;i++)
{for(j=1;j<=m;j++)
cout<<setw(3)<<sol[i][j];
cout<<endl;}
cout<<endl;
}

void traseu(int i, int j, int pas)
{int inou,jnou,k,ii,jj;
for(k=0;k<4;k++)
{inou=i+dx[k];
jnou=j+dy[k];
if(inou>=1 && inou<=n && jnou>=1 && jnou<=m)
if(L[inou][jnou]==0 && sol[inou][jnou]==0)
{sol[inou][jnou]=pas;
 if(inou==z && jnou==w)
     {
     afisare();
     if(pas<mi)
     {mi=pas;
      for(ii=1;ii<=n;ii++)
         for(jj=1;jj<=m;jj++)
             drmin[ii][jj]=sol[ii][jj];}
     }
 traseu(inou,jnou,pas+1);
 sol[inou][jnou]=0;}
}
}

int main()
{int i,j;
    citire();
mi=n*m;
sol[x][y]=1;
traseu(x,y,2);
cout<<"Sol totale "<<nrsol<<endl;
cout<<endl<<"Drumul 8im"<<endl;
for(i=1;i<=n;i++)
{for(j=1;j<=m;j++)
cout<<setw(3)<<drmin[i][j];
cout<<endl;}
}

Un labirint este codificat printr-o matrice L (n x m) ale cărui culoare sunt reprezentate prin elemente egale cu 0 situate in poziţii consecutive pe aceeaşi linie sau aceeaşi coloană. 
O persoană este paraşutată în labirint în poziţia (is, js) din interiorul labirintului. Se cere afişarea tuturor traseelor de ieşire din labirint care nu trec de mai multe ori prin acelaşi loc. 
Ieşirea din labirint se află pe marginea matricei.

#include<iomanip>
#include<iostream>
#include<fstream>
using namespace std;
int n,m,L[10][10],sol[10][10],nrsol=0,is,js;
int dx[]={-1,0,1,0},dy[]={0,1,0,-1};

void citire()
{int i,j;
ifstream f("lab");
f>>n>>m>>is>>js;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
f>>L[i][j];
}


void afisare()
{int i,j;
nrsol++;
cout<<"Solutia nr "<<nrsol<<endl;
for(i=1;i<=n;i++)
{for(j=1;j<=m;j++)
cout<<setw(3)<<sol[i][j];
cout<<endl;}
cout<<endl;
}

void traseu(int i, int j, int pas)
{int inou,jnou,k;
for(k=0;k<4;k++)
{inou=i+dx[k];
jnou=j+dy[k];
if(inou>=1 && inou<=n && jnou>=1 && jnou<=m)
if(L[inou][jnou]==0 && sol[inou][jnou]==0)

{sol[inou][jnou]=pas;
 if(inou==1 || inou==n || jnou==1 || jnou==m)
 afisare();
 traseu(inou,jnou,pas+1);
 sol[inou][jnou]=0;}
}
}

int main()
{citire();
sol[is][js]=1;
traseu(is,js,2);
cout<<nrsol;
}

Fisier

5 4
3 3
0 0 0 0
1 1 0 1
0 0 0 1
0 1 0 1
0 0 0 1

1. Un instructor de schi are la dispozitie n perechi de schiuri pe care trebuie sa le distribuie la n elevi incepatori. Scrieti un program care sa distribuie cele n perechi astfel incat suma diferentelor absolute dintre inaltimea elevului si lungimea schiurilor atribuite sa fie minima.

#include<iostream>
#include<fstream>
using namespace std;
int main()
{int n,i,j,p,k=1,a[100],b[100];
cout<<"n="; cin>>n;
for(i=0;i>a[i]>>b[i];
sort(a,n+a);
sort(b,n+b);
for(i=0;i<n;i++)
cout<<a[i]<<"-"<<b[i]<<"="<<abs(a[i]-b[i])<<endl;
}

2. Avand un tablou de n nr. nat. se cere sa se aleaga din acestea cat mai multe, dar cel mult k numere prime astfel incat suma acestora sa nu depaseasca suma celor neprime.
ex: n=7, k=3 si nr: 2, 7, 4, 9, 8, 20, 11

#include<iostream>
#include<fstream>
using namespace std;
int prim(int n)
{int i,d,ok=1;
for(d=2;d<=n/2;d++)
if(n%d==0)
ok=0;
return ok;
}

int main()
{int n,m,i,j,aux,s=0,p,sp,a[100],k;
cout<<"n=";cin>>n;
cout<<"k=";cin>>k;
for(i=0;i<n;i++)
cin>>a[i];
for(i=0;i<n;i++)
if(prim(a[i])==0)
s=s+a[i];
sort(a,n+a);
i=0;p=0;sp=0;
while(p<k && sp<=s)
{if(prim(a[i]))
{sp=sp+a[i];
if(sp<=s)
{cout<<a[i]<<" ";
p++;}}
i++;
}
}

1. La un cabinet stomatologic se prezintă simultan n pacienţi. Să se determine ordinea în care medicul stomatolog va trata pacienţii astfel încât să se minimizeze timpul mediu de aşteptare dacă se cunosc duratele tratamentelor celor n pacienţi.
ex: n=3 şi t1=60, t2=10, t3=30
Pentru ordinea 1,2,3 tm=130/3, în timp ce pentru ordinea 2,3,1 tm=50/3 (timpul minim)

#include<iostream>
using namespace std;
int main()
{int n,a[100],i,j,b[100],t=0;
cout<<"n=";
cin>>n;
for(i=1;i<=n;i++)
    {cout<<i<<".";cin>>a[i];}
for(i=1;i<=n;i++)
    b[i]=a[i];
for(i=1;i<n;i++)
    for(j=i+1;j<=n;j++)
        if(b[i]>b[j])
            swap(b[i],b[j]);
cout<<"Ordinea optima"<<endl;
for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
        if(b[i]==a[j])
            {cout<<j<<".";
            cout<<b[i]<<endl;}
for(i=1;i<=n;i++)
    t=t+b[i]*(n-i);
cout<<"Timp de asteptare optimizat"<<endl;
cout<<(double)t/n;
}

2. Problema spectacolelor: Într-o sală trebuie repartizate cât mai multe spectacole. Pentru fiecare se cunoaşte ora de început şi ora de sfârşit. Spectacolele nu se pot suprapune. Să se găsească numărul maxim de spectacole şi un exemplu de repartizare a acestora.

#include<iostream>
#include<fstream>
using namespace std;
struct spectacol{
    int in,sf;
}x[100];

int main()
{int n,i,j,p,k=0;
ifstream f("dlm");
f>>n;
for(i=1;i<=n;i++)
    {f>>x[i].in;
     f>>x[i].sf;}
for(i=1;i<n;i++)
    for(j=i+1;j<=n;j++)
        if(x[i].sf>x[j].sf)
            swap(x[i],x[j]);
cout<<"Ordinea optima"<<endl;
p=x[1].sf;
for(i=2;i<=n;i++)
    if(x[i].in<p)
        {x[i].in=0;
         x[i].sf=0;}
    else p=x[i].sf;
for(i=1;i<=n;i++)
    if(x[i].in!=0 && x[i].sf!=0)
        {cout<<"["<<x[i].in<<","<<x[i].sf<<"]"<<endl;
        k++;}
cout<<k<<" spectacole";
}

Fişier text

10
1 5
2 6
1 10
2 3
4 8
5 7
4 9
3 4
10 11
7 9