|
Titlul: Problema cu fotbal( e orijinala ;) ) Scris de: Cont de teste din Decembrie 14, 2009, 16:43:40 liga a 4-a de fotbal din Dardania are N serii in care joaca cate M echipe de fotbal. stiind ca in liga a 4-a cluburile au foarte putini bani ca sa se duca de la un capat la altul al tarii si ca banii in general ii obtin de la sponsori locali care nu au filiale peste tot in tara si sunt interesati in general de suprematia in zona respectiva si nu de suprematia nationala in domeniul lor de activitate, seful ligii MITICA Dardanir a venit cu idee de a pune in fiecare serie echipe cat mai apropiate unele de altele astfel incat cluburile sa nu aiba pierderi prea mari( fotbalul e o gaura fara fund totushi ) si sa poata atrage cat mai multi sponsori. Planul sau este ca suma sumelor distantelor dintre oricare doua cluburi din fiecare serie (in parte) sa fie minima.
gasiti impartirea optima a acestor cluburi se dau: N M pozitiile fiecarui club in sistemul de coordonate xOy(coordonatele de pe pozitia i+2 corespund clubului cu indicele i) se cere pe n linii diferite cate m echipe reprezentate prin indicii asa cum scrie mai sus NU STIU DACA ACEASTA PROBLEMA ESTE NEDETERMINIST POLINOMIALA SAU SE POATE REDUCE LA O PROBLEMA CLASICA PE GRAFURI PUR SI SIMPLU MI-AM PUS ACEASTA PROBLEMA IN LEGATURA CU CUM SE IMPART ECHIPELE DE FOTBAL IN SERII IN LIGILE INFERIOARE. MULTUMESC ANTICIPAT PRIMUL CARE DA REZOLVAREA OPTIMA ! Titlul: Răspuns: Problema cu fotbal( e orijinala ;) ) Scris de: Sima Cotizo din Decembrie 14, 2009, 18:06:05 Primesti deci N*M perechi de coordonate si vrei sa obtii N multimi cu cate M elemente, astfel incat suma totala a distantelor de la fiecare la fiecare element luat pt fiecare multime sa fie minim? (puteai sa sari peste "poveste" :P)
Titlul: Răspuns: Problema cu fotbal( e orijinala ;) ) Scris de: Cont de teste din Decembrie 14, 2009, 19:13:56 Primesti deci N*M perechi de coordonate si vrei sa obtii N multimi cu cate M elemente, astfel incat suma totala a distantelor de la fiecare la fiecare element luat pt fiecare multime sa fie minim? (puteai sa sari peste "poveste" :P) pai nu e chiar poveste, chiar de la fotbal mi-am pus intrebarea asta adica sa zicem ca vin in liga a 2-a din liga 1 : ceahlaul, poli iasi, otelul galati(care teoretic ar merge in seria de est a ligii a 2-a si pandurii targu jiu care e teoretic in divizia de vest si ar veni seria de est 19 echipe si cea de vest cu 17. atunci trebuie pusa fc arges de exemplu din seria a2-a in seria 1 si vom avea echilibru :ok: Dar da asa e practic trebuie sa faci N grafuri complete a cate M noduri fiecare si pentru fiecare graf faci suma distantelor si aduni la suma totala care trebuie sa fie minima dar cum faci asta : - programare dinamica sau - backtacking in caz ca e Nedeterminist Polinomiala? - greedy desi nu prea imi vine sa cred pentru ca nu mi se pare ca acopera toate solutiile Titlul: Răspuns: Problema cu fotbal( e orijinala ;) ) Scris de: Florian Marcu din Decembrie 14, 2009, 21:58:07 Primesti deci N*M perechi de coordonate si vrei sa obtii N multimi cu cate M elemente, astfel incat suma totala a distantelor de la fiecare la fiecare element luat pt fiecare multime sa fie minim? (puteai sa sari peste "poveste" :P) pai nu e chiar poveste, chiar de la fotbal mi-am pus intrebarea asta adica sa zicem ca vin in liga a 2-a din liga 1 : ceahlaul, poli iasi, otelul galati(care teoretic ar merge in seria de est a ligii a 2-a si pandurii targu jiu care e teoretic in divizia de vest si ar veni seria de est 19 echipe si cea de vest cu 17. atunci trebuie pusa fc arges de exemplu din seria a2-a in seria 1 si vom avea echilibru :ok: Dar da asa e practic trebuie sa faci N grafuri complete a cate M noduri fiecare si pentru fiecare graf faci suma distantelor si aduni la suma totala care trebuie sa fie minima dar cum faci asta : - programare dinamica sau - backtacking in caz ca e Nedeterminist Polinomiala? - greedy desi nu prea imi vine sa cred pentru ca nu mi se pare ca acopera toate solutiile Cu alte cuvinte: "Da, asta cer." :D |