Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: 748 Toys  (Citit de 3519 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
DITzoneC
Nu mai tace
*****

Karma: 301
Deconectat Deconectat

Mesaje: 962



Vezi Profilul
« : Iunie 15, 2008, 13:00:35 »

Aici puteţi discuta despre problema Toys.
Memorat
anna_bozianu
De-al casei
***

Karma: 5
Deconectat Deconectat

Mesaje: 111



Vezi Profilul
« Răspunde #1 : Iulie 27, 2008, 11:43:08 »

Va rog sa imi clarificati si mie cateva nelamuriri legate de enuntul problemei toys.

1. Care este considerat momentul 0?
     a ) momentul in care primim configuratia.
     b ) momentul in care s-a luat prima jucarie din camera luand in consideratie atat copii care duc o jucarie cat si pe cei care au dus deja o jucarie
     c) momentul in care a luat jucaria copilul care cara o jucarie si este cel mai aproape de camera in momentul primirii configuratiei.


2. Cate jucarii sunt in sufragerie la momentul primirii configuratiei?
    a ) M jucarii
    b ) M-N jucarii deoarece fiecare copil a luat deja cate o jucarie pe care a dus-o sau urmeaza sa o duca in camera.
    c ) M-K unde K= numarul de copii care se indreapta spre camera cu o jucarie in mana.

3. ( stupid question ) Gigel cara jucarii ?
Memorat
stef2n
Nu mai tace
*****

Karma: 218
Deconectat Deconectat

Mesaje: 641



Vezi Profilul
« Răspunde #2 : Iulie 27, 2008, 12:07:21 »

Imi cer scuze ca nu am timp sa recitesc problema si sa te lamuresc, dar stiu ca si eu am avut ceva neclaritati la momentul ei si o precizare a lui ditzone m-a lamurit: http://forum.portal.edu.ro/index.php?showtopic=62740&view=findpost&p=529784
Memorat

Exista 10 categorii de oameni: cei care inteleg sistemul binar si cei care nu il inteleg.
anna_bozianu
De-al casei
***

Karma: 5
Deconectat Deconectat

Mesaje: 111



Vezi Profilul
« Răspunde #3 : Iulie 28, 2008, 17:29:55 »

Am inteles ca problema se reduce la determinarea unui element dintr-un sir atunci cand este cunoscuta poz = pozitia sa dupa sortare. Exista pentru aceasta problema un algoritm liniar?
Eu pierd un singur test ( testul 9 ) pe care obtin TLE. Am incercat in trei moduri.
 I. Sortez sirul (heap-sort)
 II. Construiesc un maxheap din primele poz elemente pe care il updatez daca e cazul cu celelalte.
      (aici am incercat sa folosesc si minheap in cazul in care poz > n/2 )
 III. Consider val = prima valoare din sir. Mut in alt sir elementele strict mai mari, pastrez in sir elementele strict mai mici contorizand cate am mai mari si cate am mai mici. Pe cele egale le ignor dar stiu ca egale=toate-mici-mari.
      Dupa ce fac parcurgerea am trei variante.
      a) poz<=mici Atunci reiau rationamentul pe sirul celor mici.
      b) mici < poz <= mici + egale Atunci problema e rezolvata
      c) poz > mici + egale. Atunci reiau rationamentul pe sirul celor mari micsorand poz cu mici + egale.


Exista ceva mai eficient. Daca da pls, teach me.  Pray

P.S. 10x Stefan.
Memorat
stef2n
Nu mai tace
*****

Karma: 218
Deconectat Deconectat

Mesaje: 641



Vezi Profilul
« Răspunde #4 : Iulie 28, 2008, 19:09:01 »

Cea mai buna rezolvare este cu statistici de ordine (vezi Cormen): pe cazul mediu este liniar, pe cel mai defavorabil tot N * log N (dar un algoritm randomizat nu prea atinge cazul asta). Pe scurt, te folosesti de functia de partitionare de la quicksort.
Memorat

Exista 10 categorii de oameni: cei care inteleg sistemul binar si cei care nu il inteleg.
pauldb
Nu mai tace
*****

Karma: 821
Deconectat Deconectat

Mesaje: 1.901



Vezi Profilul
« Răspunde #5 : Iulie 28, 2008, 21:00:02 »

Exista si functia in STL pentru asta: nth_element().
Memorat

Am zis Mr. Green
anna_bozianu
De-al casei
***

Karma: 5
Deconectat Deconectat

Mesaje: 111



Vezi Profilul
« Răspunde #6 : Iulie 29, 2008, 00:49:42 »

Am incercat si cu functia nth_element(). Din pacate testul 9 tot TLE da.
Memorat
alex_unix
Strain
*

Karma: 22
Deconectat Deconectat

Mesaje: 46



Vezi Profilul
« Răspunde #7 : Noiembrie 03, 2012, 16:09:02 »

Deci avem 5 copii si 100 de jucarii ramase in camera lui Gigel. Holul ce trebuie parcurs are lungimea 101. Copii sunt asa :

1 : d = 84 si t = 1, inseamna ca va lasa jucaria in camera in 101 - 84 timp, si se va intoarce sa ia una noua dupa ce parcurge holul inapoi, adica 17 + 101 = 118
2 : d = 56 si t = 1, deci lasa jucaria in camera in 101 - 56 si apoi se intoarce in sufragerie. 45 + 101 = 146
3 : d = 43, t = 0, ia alta jucarie din sufragerie in 43
4 : d = 65, t = 0, ia alta jucarie din sufragerie in 65
5 : d = 2, t = 1, ajunge in camera in 99 si se intoarce in 101 => 200

M-am gandit ca solutia reprezinta timpul in care este adusa a 100-a jucarie. Fiecare aduce pe rand cate o jucarie, in ordinea distantei calculate anterior. Cum 100 % 5 e 0, am dedus ca cel numerotat cu 5 va aduce ultima jucarie (adica ultimul in ordinea distantelor). Fiecare a carat 20 de jucarii, deci el va parcurge de 19 ori holul dus-intors si o data dus.
200 + 20 * 202 - 101 (drumul de intoarcere dupa ultima jucarie nu il mai pun) = 4139  sad
Va rog frumos, poate cineva sa imi dea un hint unde gresesc ?  Confused

L.E. Data viitoare ma dau cu capu' de un perete inainte sa pun o intrebare pe forum  Brick wall . Enuntul este formulat destul de clar, nu am fost eu atent Embarassed
Doar in cazul in care cineva va mai avea neclaritatile mele : copilul 1 duce ultima jucarie in camera in 185 + 20 * 202 - 101 = 4124
« Ultima modificare: Noiembrie 04, 2012, 22:30:34 de către Petenchea Alexandru » Memorat
lucky1992
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 3



Vezi Profilul
« Răspunde #8 : Decembrie 22, 2012, 22:22:26 »

Buna seara! Poate sa-mi spuna si mie cineva de ce nu imi intra in timp la testele 8 si 9. Am folosit atat nth_element cat si implentarea manuala si tot nu intra in timp. Va multumesc!
Memorat
visanr
Nu mai tace
*****

Karma: 168
Deconectat Deconectat

Mesaje: 213



Vezi Profilul
« Răspunde #9 : Decembrie 23, 2012, 01:02:56 »

Incearca sa lucrezi cat mai mult cu int, din cate vad ai long long cam peste tot si asta incetineste foarte mult.
Memorat
lucky1992
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 3



Vezi Profilul
« Răspunde #10 : Decembrie 23, 2012, 16:28:14 »

Am inlocuit cat se putea long long cu int, iar pt. inmultirea cu nr.mari faceam unde trebuia cast la long long. Imi trece testul 8, dar la 9 tot nu imi intra in timp. S-ar putea sa fie din cauza functiei nth_element ?
Memorat
visanr
Nu mai tace
*****

Karma: 168
Deconectat Deconectat

Mesaje: 213



Vezi Profilul
« Răspunde #11 : Decembrie 23, 2012, 18:58:52 »

Nu e din cauza functiei nth_element, asa fac si eu. Eu pun long long la variabila unde tin raspunsul, in rest am int.
Memorat
lucky1992
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 3



Vezi Profilul
« Răspunde #12 : Decembrie 24, 2012, 12:29:59 »

Asa am facut si eu printre primele variante: aveam o singura variabila de tip long long in care puneam raspunsul. Din pacat imi dadea 30 pct.( dar totusi imi intra in timp la testul 9  Smile  ). Apoi cand faceam X,Y,Z si V long long ( sau le lasam int si faceam cast la long long ) imi treceau toate testele mai putin 9. Deja sunt confuz pt. ca algoritmul eu cred ca il gandesc corect, insa ma cam bat tipurile de date folosite  Brick wall.
Memorat
marius135
Echipa infoarena
Client obisnuit
*****

Karma: 19
Deconectat Deconectat

Mesaje: 56



Vezi Profilul
« Răspunde #13 : Noiembrie 07, 2013, 16:53:44 »

  Am marit un pic limita de timp sper sa nu mai fie probleme cu testele 8-9.
Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

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