Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: Mos Craciun  (Citit de 4856 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
alexandru92
Nu mai tace
*****

Karma: -191
Deconectat Deconectat

Mesaje: 496



Vezi Profilul
« : 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)
Memorat
gabitzish1
Moderatori infoarena
Nu mai tace
*****

Karma: 321
Deconectat Deconectat

Mesaje: 926



Vezi Profilul
« Răspunde #1 : Februarie 19, 2009, 20:40:44 »

Vezi problema http://infoarena.ro/problema/jocul ... e la fel. Citeste in topicul problemei, poate gasesti indicatii.
Eu cred ca am facut'o cu knapsack.
Memorat
alexandru92
Nu mai tace
*****

Karma: -191
Deconectat Deconectat

Mesaje: 496



Vezi Profilul
« Răspunde #2 : Februarie 20, 2009, 08:17:06 »

Nu mai sti in ce an a fost propusa vreau sa vad si rezolvarea oficiala
Memorat
sigrid
De-al casei
***

Karma: 61
Deconectat Deconectat

Mesaje: 129



Vezi Profilul
« Răspunde #3 : Februarie 20, 2009, 09:01:52 »

Scrie sus la sursa Smile, 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).
Memorat
alexandru92
Nu mai tace
*****

Karma: -191
Deconectat Deconectat

Mesaje: 496



Vezi Profilul
« Răspunde #4 : Februarie 20, 2009, 11:08:28 »

Am gasit  solutia   Yahoo!
Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines