Titlul: Mos Craciun Scris de: alexandru din Februarie 19, 2009, 20:21:49 Problema este urmatoarea:
Olimpiada de informatica, faza zonala Timisoara, 27.01.2006 CLASA 10 PROBLEMA 1. MOŞ CRĂCIUN Ionel si Ancuţa, doi fraţi, au primit de la Mos Craciun un sac cu cadouri. Deoarece Mos Craciun a fost grabit, a dat drumul sacului prin hornul casei si nu a imparţit cadourile. Parinţii, aflaţi in dilema, au hotarat sa imparta cadourile celor doi copii astfel incat valoarea totala a cadourilor pentru fiecare copil sa fie cat mai apropiata. Ei cunosc numarul de obiecte si valoarea fiecarui obiect. Obiectele primite pentru cei doi copii sunt in valoare de S mii lei dar este posibil ca acestea sa nu poata fi imparţite astfel incat valoarea obiectelor primite de fiecare sa fie egala cu valoarea obiectelor primite de celalalt. Presupunand ca V1 este valoarea totala a obiectelor primite de un copil si V2 valoarea totala a obiectelor primite de al doilea copil, sa se calculeze valorile V1 si V2 astfel incat sa se minimizeze valoarea absoluta a diferentei V1-V2, stiind ca nici unul din obiecte nu poate fi imparţit. Date de intrare: Prima linie a fisierului text in.txt conţine numarul n al obiectelor care trebuiesc imparţite intre cei doi copii (1<=n<=100). Linia urmatoare conţine n intregi pozitivi, reprezentand valorile obiectelor in mii lei,fiecare valoare fiind <=300. Exemplu: Date de intrare: fisierul 'in.txt' contine: 7 280 70 110 80 90 70 270 Date de iesire: fisierul text 'out.txt' va contine sumele V1 si V2. Pentru fisierul de date considerat, iesirea va fi: 480 490 Eu m-am gandit sa fac urmatorul lucru. Suma maxima posibila pe care o pot avea fiecare , este logic S/2, memorat in varibila s. Sortez descrescator vectorul si i-au pe cel mai mare numar <=s, scad din s numarul acesta si caut pe urmatorul si tot asa. Daca s==0 afisez S/2 S/2 , altfel afisez S/2-s si S/2+s. Daca nu ma insel am folosit un Greedy euristic, nu stiu daca da mereu varianta corecta (cel putin nu stiu sa o demostrez). Aveti voi alte idei, sau evaluatorul de la aceasta problema?(sau o idee cum sa demonstrez ca varianta de rezolvare propusa de mine este corecta) Pentru exmplul de mai sus , programul meu face ceva de genu: s=485 vectorul : 280 270 110 90 80 70 70 485-280-110-90=5. Afiseaza s-5 si s+5 (adica 480 490) Titlul: Răspuns: Mos Craciun Scris de: Gabriel Bitis din Februarie 19, 2009, 20:40:44 Vezi problema http://infoarena.ro/problema/jocul (http://infoarena.ro/problema/jocul) ... e la fel. Citeste in topicul problemei, poate gasesti indicatii.
Eu cred ca am facut'o cu knapsack. Titlul: Răspuns: Mos Craciun Scris de: alexandru din Februarie 20, 2009, 08:17:06 Nu mai sti in ce an a fost propusa vreau sa vad si rezolvarea oficiala
Titlul: Răspuns: Mos Craciun Scris de: Maria Stanciu din Februarie 20, 2009, 09:01:52 Scrie sus la sursa :), problema a fost propusa la Grigore Moisil By Net 2006. Din cate vad solutiile nu exista pe Infoarena, dar ele au fost publicate intr-un numar din Gazeta de Informatica (http://infoarena.ro/forum/index.php?topic=961.0).
Titlul: Răspuns: Mos Craciun Scris de: alexandru din Februarie 20, 2009, 11:08:28 Am gasit solutia :yahoo:
|