|
Titlul: O problema Scris de: Bogdan-Cristian Tataroiu din Februarie 13, 2005, 08:46:01 Poate cineva sa ma ajute la urmatoarea problema: Se da un sir de n numere. Sa se partitioneze sirul in doua subsiruri astfel incat suma elementelor din cele doua subsiruri sa fie cat mai apropiate.
Titlul: O problema Scris de: VladS din Februarie 13, 2005, 09:50:28 Problema seamana cu Timus 1004 (parca) : "Pile of Stones".
Daca lungimea sirului este mica se poate face prin backtracking. Se face suma pe tot sirul, se gaseste submultimea cu suma cea mai apropiata de jumatate. Problema parca s-a dat si la bursele Agora anul trecut la runda 25 sau 26. Se chema "Fotbal". Poti sa te uiti si pe solutia oficiala de acolo. Titlul: O problema Scris de: Tiberiu-Lucian Florea din Februarie 13, 2005, 10:08:00 "O prima idee de rezolvare ar fi generarea tuturor submultimilor de cadouri, calcularea sumelor acestora si determinarea celei mai apropiate de jumatatea sumei totale a valorilor cadourilor. Dar aceasta varianta are o complexitate exponentiala, deci metoda este ineficienta.
O alta idee de rezolvare este construirea unui vector, astfel: -presupunem ca n este numarul total de cadouri si Cadou[] este un vector care contine valorile cadourilor; -S[0] = 0; -S[j] = i, pentru i apartine {1, ..., n}, inseamna ca ultima valoare adaugata pentru a obtine un total j este Cadou; -S[j]=n+1, daca subtotalul nu poate fi obtinut. In variabila suma se va calcula suma totala a valorii cadourilor. Fie Cadou[] un tablou cu valorile tuturor cadourilor; atunci cadoul i va fi adaugat la subtotalul lui j pentru a obtine o noua valoare j+ Cadou. S[j]<i (un cadou nu poate fi adaugat la subtotal decat cel mult o data si vom adauga cadourile in ordine crescatoare). Ne intereseaza sa gasim cea mai apropiata valoare de mijloc, aceasta va fi una dintre sume." Doina Hrinciuc - Logofatu - "Probleme rezolvate si algoritmi" Titlul: O problema Scris de: Tiberiu-Lucian Florea din Februarie 13, 2005, 10:09:24 Da la Timus poti sa faci back. 8)
Titlul: O problema Scris de: Bogdan-Cristian Tataroiu din Februarie 13, 2005, 10:50:13 Mersi. Mi-am dat deja seama cum se facea.
Titlul: O problema Scris de: Duta Vlad din Februarie 13, 2005, 18:56:15 interesant, shi cand te gandesti k problema inca e valabila la .campion :lol:
Titlul: O problema Scris de: Cosmin Negruseri din Februarie 14, 2005, 03:49:41 :) v-a placut fotbal de la ginfo?
Titlul: O problema Scris de: Vlad Berteanu din Februarie 14, 2005, 09:24:19 Faceti voi back pt n=20000. :D Nu mai cereti mey solutii la .campion in timpul rundei. Asa am incercat si yo la o runda, si am luat 0 pe un algoritm aprope perfect (citirea era gresita). Deci poarta ghinion. :wink:
Titlul: O problema Scris de: Bogdan-Cristian Tataroiu din Februarie 16, 2005, 14:37:48 Scuzati-ma. Cand am facut acel post nu shtiam ca e la campion. Am gasit-o altundeva. De problemele de la campion m-am apucat mai tarziu (in timpul saptamanii eram foarte ocupat sa invat pt teste la scoala)
Mersi pt ajutor. |