Difference between revisions of "Portofolii Greedy"

From Algopedia
Jump to: navigation, search
(Created page with "= Dumitrescu Elena = Algoritmii greedy sunt in general simpli si sunt folositi la probleme de optimizare, cum ar fi: sa se gaseasca cea mai buna ordine de executare a unor lu...")
(No difference)

Revision as of 07:12, 29 November 2019

Dumitrescu Elena

Algoritmii greedy sunt in general simpli si sunt folositi la probleme de optimizare, cum ar fi: sa se gaseasca cea mai buna ordine de executare a unor lucrari pe calculator, sa se gaseasca cel mai scurt drum intr-un graf etc. In cele mai multe situatii de acest fel avem: · o multime de candidati (lucrari de executat, varfuri ale grafului etc) · o functie care verifica daca o anumita multime de candidati constituie o solutie posibila, nu neaparat optima, a problemei · o functie care verifica daca o multime de candidati este fezabila, adica daca este posibil sa completam aceasta multime astfel incat sa obtinem o solutie posibila, nu neaparat optima, a problemei · o functie de selectie care indica la orice moment care este cel mai promitator dintre candidatii inca nefolositi · o functie obiectiv care da valoarea unei solutii (timpul necesar executarii tuturor lucrarilor intr-o anumita ordine, lungimea drumului pe care l-am gasit etc); aceasta este functia pe care urmarim sa o optimizam (minimizam/maximizam) Probleme semnificative: Codeforces

1 [ https://codeforces.com/contest/1220/problem/C substring game in the lesson ]


#include <iostream>
 
using namespace std;
 
int main() {
    char c, cm = 'z'+1;
    cin.get(c);
    while( c != '\n' ){
        if( c <= cm ) {
            cm = c;
            cout << "Mike \n";
        }
        else
            cout << "Ann \n";
        cin.get(c);
    }
    return 0;
}

2 [ https://codeforces.com/contest/625/problem/B war of the corporations ]


#include <iostream>
#include <cstring>
#include <algorithm>
 
using namespace std;
 
char v[100001], cv[35];
 
int main() {
    int n,nr;
    char *pt;
    cin >> v;
    cin >> cv;
    n=strlen(cv);
    nr=0;
    pt=strstr(v,cv);
    while(pt!=NULL) {
        nr++;
        pt=strstr(pt+n,cv);
    }
    cout << nr;
    return 0;
}

3 [ https://codeforces.com/contest/827/submission/64788465 substing reconstruction ]


#include <iostream>
#include <cstring>
#include <algorithm>
 
using namespace std;
 
char rez[2000001],s[2000001];
 
int main() {
	int n, k, l, len=0, p, poz; //p reprezinta cea mai din dreapta pozitie pe care am adaugat-o
	cin >> n;
	for (int i = 0; i < n; i++) {
        p=1;
		cin >> s >> k; //citim structura si nr de pozitii de pe care incepe structura
		l = strlen(s); // l reprezinta lungimea structurii
		for (int j = 0; j < k; j++) {
			cin >> poz; // citim fiecare pozitie a structurii
			for (int m = max(poz,p); m < poz + l; m++) { //pornim de la pozitia ultimului caracter pus
				rez[m] = s[m - poz];
			}
			p = poz + l - 1; //cresc p cu lungimea structurii adaugate
			if (len < p)
				len = p; //lugimea sirului final rez
 
		}
	}
	for (int i = 1; i <= len; i++) {
		if (rez[i])
			cout << rez[i];
		else
			cout << 'a'; //pe pozitiile goale punem a
	}
	return 0;
}

4 [ https://codeforces.com/contest/337/problem/A puzzles ]


#include <iostream>
 
using namespace std;
int v[51];
 
int main() {
    int n,m,i,j,aux,x;
    cin >> n >> m;
    for(i=0;i<m;i++)
        cin >> v[i];
    for(i=0;i<m;i++) {
        for(j=i+1;j<m;j++) {
            if(v[j]<v[i]) {
                aux=v[j];
                v[j]=v[i];
                v[i]=aux;
            }
        }
    }
    x=v[n-1]-v[0];
    for(i=0;i<m-n+1;i++) {
        if(x>v[n+i-1]-v[i])
            x=v[n+i-1]-v[i];
    }
    cout << x;
    return 0;
}


5 [ https://codeforces.com/contest/670/problem/A holidays]


#include <iostream>
 
using namespace std;
 
int main() {
   int n;
   cin >> n;
   cout << n/7*2+(n%7==6)<<' ';
   if (n>1)
       cout << 2+(n-2)/7*2+((n-2)%7==6);
   else
       cout << 1;
   return 0;
}

6 [ https://codeforces.com/contest/1113/problem/A sasha and his trip ]


#include <iostream>
 
using namespace std;
 
int main() {
 
   int n, v, p, o, x = 2;
   cin >> n >> v;
   p = min(n - 1, v);
   o = p + 1;
   while (o < n) {
       p = p+x;
       x++;
       o++;
   }
   cout << p;
   return 0;
}
 

7 [ https://codeforces.com/contest/1096/problem/A find divisible]


#include <iostream>
 
using namespace std;
 
int main() {
 
 int l, r, t, i ;
 cin >> t ;
 for (i = 0 ; i < t ; i++ ) {
   cin >> l >> r;
   cout << l << " " << 2*l << "\n" ;
 }
 return 0;
}
 

8 [ https://codeforces.com/contest/1096/problem/A telephone number ]


#include <iostream>
#include<cstdio>
using namespace std;
 
int v[101];
int main() {
    int caz, n, i, a, cont, j;
    char c;
    cin>>caz;
    for(i=0; i<caz; i++){
        cin>>n;
        for(j=0; j<n; j++){
            cin>>c;
            v[j]=c-'0';
        }
        cont=0;
        while(v[cont]!=8 && cont<n){
            cont++;
        }
        if(n-cont>=11)
            cout<<"YES";
        else
            cout<<"NO";
        cout<<"\n";
    }
    return 0;
}

9 [ https://codeforces.com/contest/1163/problem/A eating soup ]


#include <iostream>
 
using namespace std;
 
int main() {
    int a,b;
    cin >> a >> b;
    if( b == 0 )
      cout << 1;
    else{
      if( (a+1)/2 <= b )
        cout << a - b ;
      else
        cout << b;
    }
    return 0;
}

10 [ https://codeforces.com/contest/50/problem/A domino piling ]


#include <iostream>
#include <fstream>
using namespace std;
 
int main() {
    int n,m,n1,n2;
    cin >> n >> m;
    n1=n*(m/2)+(m%2)*n/2;
    n2=(n/2)*m+(n%2)*m/2;
    if (n1>n2)
        cout << n1;
    else
        cout << n2;
    return 0;
}

11 [ https://codeforces.com/contest/1236/problem/A stones]


#include <iostream>
 
using namespace std;
 
int main() {
    int n,a,b,c,a1,b1,c1,p1=0,p2=0;
    cin >> n;
    for(int i=0;i<n;i++) {
      cin >> a >> b >> c;
      a1=a;
      b1=b;
      c1=c;
      p1=0;
      while(a1>0&&b1>1) {
        a1--;
        b1=b1-2;
        p1++;
      }
      while(c1>1&&b1>0) {
        c1=c1-2;
        b1--;
        p1++;
      }
      p2=0;
      while(c>1&&b>0) {
        c=c-2;
        b--;
        p2++;
      }
      while(a>0&&b>1) {
        a--;
        b=b-2;
        p2++;
      }
      if(p1>p2)
        cout << 3*p1 << "\n";
      else
        cout << 3*p2 << "\n";
    }
    return 0;
}

12 [ https://codeforces.com/contest/749/problem/A bachgold problem]

#include <iostream>
 
using namespace std;
 
int main() {
    int n,d;
    cin >> n;
    if(n%2==0) {
      cout << n/2 ;
      cout << "\n";
      for(int i=0;i<n/2;i++) {
        cout << 2 << " ";
      }
    }
    else {
      cout << n/2;
      cout << "\n";
      for(int i=0;i<n/2-1;i++) {
        cout << 2  << " ";
      }
      cout << 3;
    }
    return 0;
}

PbInfo

13 [ https://www.pbinfo.ro/?pagina=probleme&id=2271&id_sursa=18424149#a_editor ProdMax ]

01.#include <iostream>
02. 
03.using namespace std;
04. 
05.int main(){
06.int n;
07.long long sol1 = 0, sol2 = 0, min1=1000001, min2=1000001, max1=-1000001, max2=-1000001, nr;
08.cin >> n;
09.for( int i = 0 ; i < n ; i++ ){
10.cin >> nr;
11.if( nr != 0 ){
12.if( nr > max2 ){
13.if( nr > max1 ){
14.max2 = max1;
15.max1 = nr;
16.}
17.else
18.max2 = nr;
19.}
20.if( nr < min2 ){
21.if( nr < min1 ){
22.min2 = min1;
23.min1 = nr;
24.}
25.else
26.min2 = nr;
27.}
28.}
29.}
30.sol1 = max1*max2;
31.sol2 = min1*min2;
32.if( sol1 > sol2 )
33.cout << sol1;
34.else
35.cout << sol2;
36.return 0;
37.}


14 [ https://www.pbinfo.ro/?pagina=probleme&id=91&id_sursa=18423955#a_editor masini]

view source
print?
01.#include <fstream>
02.#include <iostream>
03.using namespace std;
04. 
05.ifstream fin("masini.in");
06.ofstream fout("masini.out");
07.int v[1000001];
08. 
09.int main() {
10.int n,t,s=0;
11.fin>>n>>t;
12.for(int i=0; i<n; i++)
13.fin>>v[i];
14.for(int i=0; i<n-1; i++)
15.for(int j=i+1; j<n; j++)
16.if(v[i] > v[j])
17.swap(v[i], v[j]);
18.int i=0;
19.while(t>=0)
20.{
21.i++;
22.s++;
23.t=t-v[i];
24.}
25.fout<<s;
26.return 0;
27.}

15 [ https://www.pbinfo.ro/?pagina=probleme&id=92 proiecte]


01.#include <iostream>
02.#include <fstream>
03. 
04.using namespace std;
05.ifstream fin("proiecte.in");
06.ofstream fout("proiecte.out");
07.int v[1002],x[1002];
08.int main() {
09.int n,t,i,ok,aux,aux2;
10.fin>>n;
11.for(i=1;i<=n;i++){
12.fin>>t;
13.v[i]=t;
14.}
15.for(i=1;i<=n;i++){
16.x[i]=i;
17.}
18.do{
19.ok=1;
20.for(i=1;i<n;i++){
21.if(v[i]>v[i+1]){
22.aux2=x[i];
23.x[i]=x[i+1];
24.x[i+1]=aux2;
25.aux=v[i];
26.v[i]=v[i+1];
27.v[i+1]=aux;
28.ok=0;
29.}
30.}
31.}while(ok==0);
32.for(i=1;i<=n;i++){
33.fout<<x[i]<<" ";
34.}
35.return 0;
36.}

16 kMax


01.#include <iostream>
02. 
03.using namespace std;
04. 
05.int main()
06.{
07.int n,k,nr,s=0,i,v[1002],ok,aux;
08.cin>>n;
09.for(i=1;i<=n;i++){
10.cin>>nr;
11.v[i]=nr;
12.}
13.do{
14.ok=1;
15.for(i=1;i<n;i++){
16.if(v[i]>v[i+1]){
17.aux=v[i];
18.v[i]=v[i+1];
19.v[i+1]=aux;
20.ok=0;
21.}
22.}
23.}while(ok==0);
24.cin>>k;
25.for(i=1;i<=k;i++){
26.v[i]=v[i]*(-1);
27.}
28.for(i=1;i<=n;i++){
29.s=s+v[i];
30.}
31.cout<<s;
32.


17 eureni


#include <iostream>
#include <fstream>

using namespace std;

ifstream fin( "eureni.in" );
ofstream fout( "eureni.out" );

int main(){
    int s, e, n, b = 1, i = 0, cont = 0;
    fin >> s >> n >> e;
    while( n > i ){
        b = b * e;
        i ++ ;
    }
    for( i = 0 ; i <= n  ; i++ ){
        if( s / b > 0 ){
            fout << b << " " << s / b << "\n";
            cont = cont + s / b;
            s = s % b;
        }
        b = b / e;
    }
    fout << cont;
    return 0;
}

18 bomboane

#include <iostream>
#include <fstream>
using namespace std;

ifstream in("bomboane.in");
ofstream out("bomboane.out");

int minim,maxim,minpoz,maxpoz;

void Verif_Min_Max(int n, int i)
{
    if(n<minim)
    {
        minim=n;
        minpoz=i;
    }
    if(n>maxim)
    {
        maxim=n;
        maxpoz=i;
    }
}

int main()
{
    int n, medie=0,i,j;
    in>>n;
    int v[n+1];
    for(i=1; i<=n; i++)
    {
        in>>v[i];
        medie+=v[i];
    }
    if(medie%n)
        out<<-1;
    else
    {
        minim=v[1];
        maxim=v[1];
        minpoz=1;
        maxpoz=1;
        int c,mutari=0;
        int a[1001][4];
        medie/=n;
        for(j=1;; j++)
        {
            for(i=1; i<=n; i++)
            {
                Verif_Min_Max(v[i],i);
            }
            c=medie-v[minpoz];
            if(c==0)
                break;
            v[minpoz]=v[minpoz]+c;
            v[maxpoz]=v[maxpoz]-c;
            a[j][1]=maxpoz;
            a[j][2]=minpoz;
            a[j][3]=c;
            mutari++;
            minim=v[1];
            maxim=v[1];
            minpoz=1;
            maxpoz=1;
        }

        out<<mutari<<endl;
        for(i=1; i<=mutari; i++)
        {
            for(j=1; j<=3; j++)
                out<<a[i][j]<<" ";
            out<<endl;
        }
    }
}

19 plopi2

#include <iostream>
#include <fstream>

using namespace std;

ifstream fin( "plopi2.in" );
ofstream fout( "plopi2.out" );

int main(){
    int n, suma = 0, minim = 10001, a, contor = 0;
    fin >> n;
    for( int i = 0 ; i < n ; i++ ){
        fin >> a;
        if( minim >= a )
            minim = a;
        else{
            suma = suma + a - minim ;
            contor++;
        }
    }
    fout << contor << " " << suma;
    return 0;
}

20 spectacole


#include <fstream>
#include <algorithm>

using namespace std;
int n, i, aux, k;
struct spectacol
{
    int x, y;
}v[105];

bool cmp(const spectacol a, const spectacol b)
{
    return a.y < b.y;
}

int main()
{
    ifstream f("spectacole.in");
    ofstream g("spectacole.out");
    f>>n;
    for(i=1; i<=n; i++)
        f>>v[i].x>>v[i].y;
    sort(v+1, v+n+1, cmp);
    for(i=1; i<=n; i++)
        if(v[i].x>=aux)
    {
        k++;
        aux = v[i].y;
    }
    g<<k;
    return 0;
}

21 hard_ssc

#include <iostream>

using namespace std;

int n, d[100001], k, x;

void cautare( int i, int j ){
    int m = ( i + j ) / 2;
    if( d[ m - 1 ] >= x && d[ m ] < x )
        d[ m ] = x;
    else{
        if( d[m] < x )
            cautare( i, m - 1 );
        else
            cautare( m + 1 , j );
    }
}

int main(){
    int i;
    cin >> n;
    k = 0;
    d[0] = 100001;
    for (i = 1; i <= n; i++){
        cin >> x;
        if (x <= d[k])
            d[++k] = x;
        else
            cautare( 1, k );
    }
    cout << k ;
    return 0;
}

22 subsecv

#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("subsecv.in");
ofstream fout("subsecv.out");

int suma[10001];

int main() {
    int i, j, c = 0, n, x;
    fin >> n;
    for(  i = 1 ; i <= n ; i++ ) {
        fin >> x;
        suma[i] = ( x + suma[i-1] ) % n;
    }
    for(  i = 1 ; i <= n && c == 0 ; i++ ) {
        for( j = i ; j <= n && c == 0 ; j++ ) {
            if( ( suma[j] - suma[i-1] ) % n == 0 )
                c = 1;
        }
    }
    fout << i-1 << " " << j-1;
    return 0;
}