•alexandru92
|
|
« : 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)
|