Portofolii Greedy: Difference between revisions
From Algopedia
Jump to navigationJump to search
(No difference)
|
Latest revision as of 08:05, 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
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 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 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 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 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 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;
}
