Andrei este manager la o firmă foarte importantă, la care se lucrează în ture. Aceste ture durează un număr constant de minute (1017 minute), fiecare tură începând la minutul 1. După o tură, Andrei, fiind foarte obosit, doarme până la începutul următoarei ture.
El este foarte ocupat cu o mulțime de ședințe (S ședințe mai exact). Acestea sunt trecute în agenda lui astfel: Minutul de început Durata Minutele necesare pentru pregătire – în minutele de pregătire nu trebuie să îl deranjeze nimeni).
Agenda este foarte dezordonată, iar şedinţele nu sunt notate în ordine cronologică, şi, în plus, acestea se pot suprapune. Ca un bun manager, Andrei doreşte să participe la cât mai multe şedinţe într-o tură cu condiţia să nu se desfăşoare în acelaşi timp. Deoarece nu poate renunța la nicio ședință, el va amâna pentru turele viitoare unele dintre ședințele care se suprapun, păstrând în agendă aceleași informații despre fiecare (început, durată, timp necesar pentru pregătire).
Cerința
a) Afișați numărul minim de ture în care Andrei poate participa la toate şedinţele.
b) Știind că în prima tură, Andrei poate să ajungă la toate şedinţele (nu se desfăşoară două sau mai multe şedinţe la un moment dat), determinați minutul în care se poate programa începutul pregătirii unei noi şedinţe de durată D şi timp de pregătire P, astfel încât să nu se suprapună cu o alta (dacă există mai multe soluţii se va afişa cea cu momentul de început minim).
Date de intrare
Pe prima linie a fişierului de intrare manager.in se găseşte litera a, însemnând că se cere rezolvare cerinţei a), sau b, semnificând faptul că se cere rezolvarea cerinţei b). Pe linia a doua se găseşte un număr S reprezentând numărul de şedinţe, iar pe următoarele S linii se găsesc câte trei numere x y z separate prin câte un spaţiu, astfel: x – minutul la care începe şedinţa de pe linia curentă, y – durata şedinţei iar z – timpul necesar pentru pregătirea şedinţei, în care Andrei nu trebuie să fie deranjat de nimeni. Doar pentru cerinţa b), pe
ultima linie, adică linia S+3, se vor afla 2 numere D P separate printr-un spaţiu, având semnificaţiile din enunţ.
Date de ieșire
Fișierul de ieșire manager.out va conține pe prima linie un singur număr reprezentând răspunsul la cerinţa a sau b dată pe prima linie în fişierul manager.in.
Restricții și precizări
1 ≤ D P x y z ≤ 10171 ≤ S ≤ 100.000x-z>0
Exemplul 1
manager.in
a 7 5 8 1 1 3 0 2 4 0 5 9 3 2 7 0 6 10 1 5 1 0
manager.out
6
Explicație
În prima tură se pot desfășura ședințele 2, 7 sau ședințele 2, 6. Toate celelalte ședințe conțin minutul 5 deci vor trebui sa se desfășoare în ture separate astfel: În cea de a doua tură ședința 1, în a treia ședința 3, în cea de-a patra ședința 4, într-a cincea ședința 5, iar într-a șasea ședința 6 sau 7 în funcție de cea aleasă pentru tura 1. În total sunt 6 ture.
Exemplul 2
manager.in
b 6 5 3 2 20 6 3 48 10 4 10 5 0 30 3 1 55 3 3 7 1
manager.out
33
Explicație
Pregătirea noii ședință poate începe de la minutul 33, între ședințele 5 și 3.
Cum e corect?
cout < "As la info";
cout << "As la info";
cout >> "As la info";
Felicitări! Poți mai mult?
Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.
Greșit, dar nu-i bai!
Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.
Rezolvare
Iată rezolvarea de 100 de puncte pentru problema Manager:
// manager - solutie oficiala - 100 pct
#include <fstream>
#include <algorithm>
#define MAX 100005
using namespace std;
ifstream fin("manager.in");
ofstream fout("manager.out");
struct struct_A{long long int minut; bool esteInc;};
struct struct_B{long long int inc, sf;};
bool test_A(struct_A a, struct_A b)
{
if(a.minut != b.minut)
return a.minut<b.minut;
else
if(a.esteInc!=b.esteInc)
return a.esteInc;
else
return false;
}
void citeste_A(struct_A sedinta[], long long int &nrSedinte)
{
long long inc,durata,timpPregatire;
fin >> nrSedinte;
for(int i=1;i<=nrSedinte;i++)
{
fin >> inc >> durata >> timpPregatire;
sedinta[i*2-1].minut = inc - timpPregatire; sedinta[i*2-1].esteInc = true;
sedinta[i*2].minut = inc + durata - 1; sedinta[i*2].esteInc = false;
}
}
void rezolva_A()
{
struct_A sedinta[MAX * 2];
long long int nrSedinte,nrTure,nrMaxTure;
nrTure = nrMaxTure = 0;
citeste_A(sedinta,nrSedinte);
sort(sedinta+1,sedinta+nrSedinte*2+1,test_A);
for(int i=1;i<=nrSedinte*2;i++)
if(sedinta[i].esteInc)
{
nrTure++;
if(nrTure>nrMaxTure)
nrMaxTure = nrTure;
}
else
nrTure--;
fout<<nrMaxTure;
}
bool test_B(struct_B a, struct_B b)
{
if(a.inc != b.inc)
return a.inc < b.inc;
else
return a.sf < b.sf;
}
void citeste_B(struct_B sedinta[],long long int &nrSedinte,long long int &timpSedinta)
{
long long int aux, durata, inc, timpPregatire;
fin>>nrSedinte;
for(int i=1;i<=nrSedinte;i++)
{
fin >> inc >> durata >> timpPregatire;
sedinta[i].inc = inc - timpPregatire;
sedinta[i].sf = inc + durata - 1;
}
fin>>timpSedinta; fin>>aux;
timpSedinta+=aux;
}
void rezolva_B()
{
long long int nrSedinte, ultimulSf = 0, timpSedinta;
struct_B sedinta[MAX];
citeste_B(sedinta,nrSedinte,timpSedinta);
sort(sedinta+1,sedinta+nrSedinte+1,test_B);
for(int i=1;i<=nrSedinte;i++)
if(sedinta[i].inc - ultimulSf - 1>=timpSedinta)
{
fout<<ultimulSf + 1;
return;
}
else
if(sedinta[i].sf > ultimulSf) ultimulSf = sedinta[i].sf;
fout << ultimulSf + 1;
}
int main()
{
char cerinta;
fin>>cerinta;
if(cerinta == 'a')
rezolva_A();
else
rezolva_B();
return 0;
}
Atenție
Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa 
.
Rezolvarea problemei #1427 Manager
Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1427 Manager de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.
Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!