1208 Ferma2

[•wefgef]

Aici puteţi discuta despre problema Ferma2.

[•blue_phoenix]

Salut!

Eu am facut problema asta in doua moduri (facut adica da raspunsul corect, dar ia tle pe 7 teste din 10, in ambele moduri)
Am notat cu l1 numarul de laturi de tip 1 vandute pana acum (catete verticale), l2 numarul de laturi de tip 2 (catete orizontale)
si l3 numarul de laturi de tip trei (ipotenuze)
Primul e brut:
  fac doua foruri in care fixez l1 si l2 (l3 se deduce, este k-l1-l2). am trei functii:
      suma1(l1,l2,l3), suma2(l1,l2,l3) si suma3(l1,l2,l3) care calc. valoare parcelei de tip 1 (respectiv 2, 3), stiind ca am vandut deja l2 si l3 laturi de tipul l2 si resp l3; sursa e aici http://infoarena.ro/job_detail/636657?action=view-source
A doua solutie am incercat sa o fac o parcurgere in latime; mie mi s-a parut o solutie mai buna ca prima, dar, desi tot doar trei teste intra in timp, ea ia chiar mai mult

initial am in coada nodul (0,0,0,0) cu semnif ca la sf zilei 0, am vandut 0 laturi l1, 0 laturi l2 si castigul este 0 (pe l3 nu e nevoie sa-l tin, se deduce, este (ziua-l-l2))
expandarea nodului (ziua,l1,l2,castig) duce la adaugarea in coada a inca trei noduri:
       (ziua+1,l1,l2,castig+suma3(l1,l2,ziua-l1-l2+1)) daca vand latura 3,
       (ziua+1,l1+1,l2,castig+suma1(l1+1,l2,ziua-l1-l2)) daca vand latura 1,
       (ziua+1,l1,l2+1,castig+suma2(l1,l2+1,ziua-l1-l2)) daca vand latura 2. expandez pana la generatia k, inclusiv.
din tot ce am pus vreodata in coada aleg maximul, dpdv al castigului.
mi s-a parut o sol mai buna ca prima, pt ca chem functiile de suma de mai putine ori decat in primul caz...
sursa e aici: http://infoarena.ro/job_detail/637095?action=view-source
Imi poate spune cineva, pe scrut, care era ideea? sumele pe bucati oricum trebuiesc calculate,nu? si ele iau mult timp...

[•dushmi]

Ambele solutii alea tale au complexitate cam n^3 daca nu ma insel( din aceasta cauza nu intra in timp)...

Ideea corecta de rezolvare pleaca de la o observatie: "Daca vindem intr-o zi un teren, atunci Ion ramane tot cu un triunghi dreptunghic isoscel, dar cu catetele mai mici cu 1." Astfel dupa k zile el ramane cu un triunghi dreptughic isoscel cu catetele de lungime n - k, care, pentru ca profitul sa fie maxim, trebuie sa aiba valoare minima. De fapt problema se reduce la aflarea unui triunghi dreptunghic isoscel de cateta n - k pentru care suma este minima( care merge cu o dinamica).