Question

Gigel este un cântăreț începător. El știe deja să cânte n melodii, și pentru fiecare melodie se cunoaște durata, exprimată în minute și secunde. Gigel va participa la o emisiune de televiziune, unde va putea cânta timp de T secunde. El vrea să cânte cât mai multe melodii, pentru a-și demonstra talentul deosebit.

Ajutați-l să aleagă piesele pentru emisiune, și vă va răsplăti cu un autograf.

Date de intrare
Fişierul de intrare concert.in conţine pe prima linie numerele n T. Fiecare dintre următoarele n linii conține durata unei melodii, în formatul m:s, unde m și s pot avea una sau două cifre.

Date de ieşire
Fişierul de ieşire concert.out va conţine pe prima linie numărul M, reprezentând numărul maxim de melodii care pot fi alese. Următoarea linie va conține M numere între 1 și n, reprezentând numărul de ordine al melodiilor alese, așa cum sunt ele date în fișierul de intrare.

Restricţii şi precizări
1 ≤ n ≤ 100
1 ≤ T ≤ 1000
0 ≤ m ≤ 10
0 ≤ s ≤ 59

Exemplu
concert.in

7 450
2:30
1:45
2:10
03:00
01:15
02:05
2:05
concert.out

4
2 5 6 7
#403

Answer 1

Am ordonat melodiile in functie de timpul crescator si le-am inclus pe toate cate se puteau in cele T secunde.

#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
//structura cu numar inregistrare melodie si durata ei in secunde
struct muzica{
int inregistrare,durata;
} melodie[100];
//functie care transforma sir caractere in secunde
int timp_secunde(char* timp){
int numar,i,este_minut=1,secunde=0;
//functie care imparte sir in functie de delimitator, :
char *text=strtok(timp,":");

while(text!=NULL){
numar=0;
//formam numarul
for(i=0;i<strlen(text);i++){
numar=10*numar+(text[i]-'0');
}
//initializat semnalizat ca minute, inmultim cu 60 sa devina secunde
if(este_minut>0){
numar=numar*60;
//acum o sa intalnim minute, nu secunde
este_minut=0;
}
//adunam la secunde
secunde=secunde+numar;
//cand este null, aplicam token la sirul propriu zis
text=strtok(NULL,":");
}
return secunde;
}
//metoda sortarii prin selectie pentru duratele fiecarei melodii
void sorteaza_durata(muzica melodie[],int n){
int i,j,min,temp;
for(i=1;i<=n-1;i++){
min=i;
for(j=i+1;j<=n;j++){
if(melodie[j].durata<melodie[min].durata){
min=j;
}
}
if(min!=i){
melodie[temp]=melodie[i];
melodie[i]=melodie[min];
melodie[min]=melodie[temp];
}
}
}
//pentru testare, afisare a componentelor melodiei durata si inregistrare
void afiseaza_lista(muzica melodie[],int n){
int i;
for(i=1;i<=n;i++){
cout<<melodie[i].inregistrare<<" "<<melodie[i].durata<<endl;
}
}
int main(){
int T,M,n,i,indice_melodie[10],nr_melodii=0;
char timp[100];
ifstream fic("concert.in");
ofstream foc("concert.out");
fic>>n>>T;
//arunca prima linie din stream
fic.getline(timp,100);
//citeste fiecare melodie cu durata si inregistrare
for(i=1;i<=n;i++){
fic.getline(timp,100);
melodie[i].inregistrare=i;
melodie[i].durata=timp_secunde(timp);
}
// afiseaza_lista(melodie,n);
//sorteaza crescator melodiile dupa durata
sorteaza_durata(melodie,n);
// afiseaza_lista(melodie,n);

while(1){
nr_melodii++;
T=T-melodie[nr_melodii].durata;
//cat timp durata nu este depasita, executa loop
//daca timpul a fost depasit, iesi din loopul de melodii
if(T<0){
nr_melodii--;
break;

}
indice_melodie[nr_melodii]=melodie[nr_melodii].inregistrare;
}
foc<<nr_melodii<<endl;
for(i=1;i<=nr_melodii;i++){
foc<<indice_melodie[i]<<" ";
}
return 0;
}

Answer 2

#include<fstream>
#include<algorithm>
using namespace std;
ifstream f("concert.in");
ofstream g("concert.out");
int n,T,nr,s[101];
struct art {int t,ord;} x[101];
int cmp(art A, art B) {return A.t<=B.t;}
int main()
{   f>>n>>T;
    int i;
    for(i=1;i<=n;i++)
    {   char v[7];
        f>>v;
        int j=0,a=0,b=0;
        while(v[j]!=':') a=a*10+v[j++]-'0';
        a*=60; j++;
        while(v[j]!='\0') b=b*10+v[j++]-'0';
        a+=b;
        x[i].t=a; x[i].ord=i;
    }
    sort(x+1,x+n+1,cmp);
    i=1;
    while(i<=n and x[i].t<=T) {s[++nr]=x[i].ord; T-=x[i].t; ++i;}
    g<<nr<<'\n';
    for(i=1;i<=nr;i++) g<<s[i]<<' ';
    g.close(); return 0;
}