Avem o tabla de sah cu N linii,fiecare linie avand A(i) patratele.
Sa se afle in cate moduri putem aseza k turnuri,astfel incat acestea sa nu se atace.
Doua turnuri se pot ataca daca sunt pe aceeasi linie sau coloana,indiferent daca intre ele se afla spatiu gol.

De la ce concurs de info e?

[Citat] Avem o tabla de sah cu N linii,_Lasati va rog dupa virgula mereu un spatiu gol_fiecare linie avand A(i) patratele.

Din pacate nu se intelege aici enuntul.
Ce este A? Ce este i?
O tabla de sah este in mod abstract o matrice 8x8.
Cele 8 linii incep toate in prima coloana.
Daca cineva are idea nesanatoasa sa faca liniile de lungimi diferite, trebuie sa imi spuna cum le imbuca. In nici un caz nu se mai poate folosi denumirea de "tabla de sah" pentru ceea ce rezulta.

Desigur ca problema nu ne spune care este relatia dintre N si k si A...

Acest tip de problema este nestructural, enervant din punct de vedere matematic, nu duce nicaieri, nu ajuta la dezvoltarea nici unei calitati umane. Da, este miza uneori pusa pe asa ceva, dar recomandarea mea este de a-i pune pe cei ce propun astfel de probleme sa si le rezolve singuri. In fata mea, drept corector, acesti autori de probleme cu capricii nu ar aduna toate punctele cu propriile rezolvari.

[Citat] De la ce concurs de info e?

http://acm.sgu.ru/problem.php?contest=0&problem=269

Scuze, mi-a trimis-o coplilul personal si m-a rugat sa o postez, eram in mare graba, am citit la volan ce a scris si am dat copy+paste.Promit sa nu mai fac, dar era tare necăjit săracul...

[Citat] [Citat] De la ce concurs de info e? http://acm.sgu.ru/problem.php?contest=0&problem=269 Scuze, mi-a trimis-o coplilul personal si m-a rugat sa o postez, eram in mare graba, am citit la volan ce a scris si am dat copy+paste.Promit sa nu mai fac, dar era tare necăjit săracul...

Deci nu este o tabla de sah ci o adunatura de linii de anumite lungimi.
Este pur si simplu o problema de cautare cu calculatorul, din punct de vedere matematic, fiecare configuratie este o problema in sine.

Care este de fapt miza pe aceste probleme?

Răspunsul este, dacă am înțeles bine problema

De antrenament ... Zice ca e important sa înțeleagă o rezolvare eficientă din punct de vedere al timpului, memoria nu e limitată.

[Citat] Răspunsul este, dacă am înțeles bine problema

Si dacă nu sunt toate liniile ocupate de turnuri?Doar k din cele n?

Atunci însumăm produse similare după toate alegerile de k linii din cele n.

[Citat] Atunci însumăm produse similare după toate alegerile de k linii din cele n.

Asta înseamnă sa rezolvam aceeași problema de combinari de n luate câte k ori, caz in care avem nevoie de mai mult timp decât ne permitem....noi ne gândeam să o rezolvam recurent, începem prin ordonarea crescătoare a lungimilor liniilor, si sa definim b(i) soluția problemei pana la linia i. In acest moment avem doua cazuri :
Dacă i>k:
Punem un turn pe linia i+1 si scoatem un turn de pe liniile precedente/ sau nu punem nimic pe linia i+1.
Dacă i<=k:
Adăugăm un turn după formula de mai sus
No, si ne-am blocat aici.

Partea de optimizare nu-mi trezește interesul. Am scris o bucățică de cod, ca să văd cum merge...