infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Adrian Diaconu din Martie 16, 2008, 20:30:12



Titlul: 682 Iepuri2
Scris de: Adrian Diaconu din Martie 16, 2008, 20:30:12
Aici puteţi discuta despre problema Iepuri2 (http://infoarena.ro/problema/iepuri2).


Titlul: Răspuns: 682 Iepuri2
Scris de: Florin Marius Popescu din Martie 17, 2008, 22:27:17
ce a mai nashpa olimpiada zau....... :x :x ma asteptam sa dea o problema cu grafuri (cu fluxuri cicluri APm alea alea etc) si o problema de combinatorica, dar a fost pe dos rau: combinatorica in grafuri(cum este problema iepuri la care nici nu am inteles ce vrea sa ceara) si o problema aparent banala de cum e problema NUMERE. te chinui sa faci problema numere de 100 de puncte si te trezeshti ca nu faci nimic la ea. in schimb altii care n au habar de grafuri, dinamica si alte chestii rezolva problema pt 30 de puncte si se califica la nationala:  Si stai si te gandeshti ca daca se datea grafuri si combinatorica (asa cum s-a dat in anii trecuti), calificatii  :annoyed: la nationala nici macar nu aveau habar de o rezolvare brute.  si mai bine pleci in italia la ciordit de portifele  \:D/ ca viata nu e dreapta deci ''fura, minte si sari la gat ca maine poate fii mai rau'' :ok:


Titlul: Răspuns: 682 Iepuri2
Scris de: Bogdan-Alexandru Stoica din Martie 17, 2008, 23:10:34
In primul rand, acest topic a fost creat pentru a pune intrebari STRICT despre rezolvarea problemei. Comentariile pe marginea olimpiadei judetene sunt in alta parte. In al doilea rand nu este vina nimanui ca unii nu si-au gestionat corect timpul. Daca te uiti pe rezultate (http://ssv.ploiesti.ro/oni2008/judete.php) vei vedea ca multa lume a rezolvat problema de maxim, deci nu a fost chiar atat de grea. Sunt de acord, insa, cu faptul ca a fost diferit fata de anul trecut, deoarece a imbinat programarea dinamica cu teoria grafurilor.


Titlul: Răspuns: 682 Iepuri2
Scris de: Pripoae Teodor Anton din Martie 31, 2008, 21:56:11
un iepure poate avea doi sefi directi?


Titlul: Răspuns: 682 Iepuri2
Scris de: Sima Cotizo din Martie 31, 2008, 22:19:28
Nup:

Citat
fiecare iepure are exact un sef direct (exceptandu-l pe Rila Iepurila, care este seful cel mare, seful tuturor iepurilor)


Titlul: Răspuns: 682 Iepuri2
Scris de: Sfrent Andrei din Mai 09, 2008, 07:34:22
testele 8 si 9 sunt proaste. am trimis o solutie care cicla doar in cazul in care un iepure are 2 sefi... si ce credeti? TLE... pe 8 si 9. schimbati-le si voi si reevaluati. [sper sa nu fi gresit]

CODul cu care am verificat:
Cod:
freopen("iepuri2.in","r",stdin);  
    scanf("%d%d",&n,&k); 
    int x,y,i; 
    for(i=1;i<=n-1;++i) 
    { 
        scanf("%d%d",&x,&y); 
        caract[y]++; //chestia asta inregistreaza numarul de sefi pentru y...
        la[x][++la[x][0]]=y; 
    } 
    for(rila=1;rila<=n;++rila) if(caract[rila]==0) break; 
//il determin pe rila ca fiind singurul care nu are sef
    fclose(stdin); 

//verific la infoarena daca nu cumva exista 2 sefi pentru un "epure"
for(i=1;i<=n;++i) if(caract[i] > 1) while(1); //aici o sa am un mare TLE :)


Titlul: Răspuns: 682 Iepuri2
Scris de: Gabriel Bitis din Mai 09, 2008, 07:45:06
Am verificat si eu cu o sursa care urmareste doar daca ajunge un iepure sa aiba doi sefi :
Cod:
#include <stdio.h>

int n, k, gr[105];

int main()
{
   freopen("iepuri2.in","r",stdin);
   freopen("iepuri2.out","w",stdout);

   scanf("%d %d",&n,&k);
   int i, a, b;
   for (i = 1; i < n; i++)
   {
      scanf("%d %d",&a,&b);
      gr[b]++; // incrementez numarul de sefi ai lui b
      if (gr[b] == 2) while (i); // intru in ciclu daca b are doi sefi
   }
   return 0;
}
NU am niciun TLE: http://infoarena.ro/job_detail/188586 (http://infoarena.ro/job_detail/188586).
Probabil TLE'urile tale sunt din alta cauza.

LE: n'o sa ajung la 3,4,5,... sau mai multi sefi pt ca gr[b ] creste cu 1, si nu are cum sa sara de la 1 la 3, deci daca are mai mult de 2 sefi gr[b ] tre sa fie odata 2 => intra in bucla.


Titlul: Răspuns: 682 Iepuri2
Scris de: Sfrent Andrei din Mai 09, 2008, 08:42:40
pai e o diferenta intre noi doi. tu ai pus sa fie exact 2 sefi. eu am pus mai mare ca 1. incearca... poate sunt 3,4,5,6,7,8,9... [sau poate sunt eu idiot. nu imi dau seama de ce nu merge.]


Titlul: Răspuns: 682 Iepuri2
Scris de: Bondane Cosmin din Mai 09, 2008, 09:41:46
pai e o diferenta intre noi doi. tu ai pus sa fie exact 2 sefi. eu am pus mai mare ca 1. incearca... poate sunt 3,4,5,6,7,8,9... [sau poate sunt eu idiot. nu imi dau seama de ce nu merge.]


E bun codul lui Gabi. Daca gasesti ca are 2 sefi, intra in bucla direct. Deci oricum ar avea mai multi de 2, ar intra in bucla.


Titlul: Răspuns: 682 Iepuri2
Scris de: Sfrent Andrei din Mai 09, 2008, 21:51:00
puteti pune si voi niste teste? ca nu stiu ce am gresit de iau 90 pct... WA pe testul 8... multumesc.


Titlul: Răspuns: 682 Iepuri2
Scris de: Bondane Cosmin din Mai 10, 2008, 09:30:23
puteti pune si voi niste teste? ca nu stiu ce am gresit de iau 90 pct... WA pe testul 8... multumesc.

Incearca testele oficiale.


Titlul: Răspuns: 682 Iepuri2
Scris de: Cosmin-Mihai Tutunaru din Februarie 01, 2009, 14:08:18
pai e o diferenta intre noi doi. tu ai pus sa fie exact 2 sefi. eu am pus mai mare ca 1. incearca... poate sunt 3,4,5,6,7,8,9... [sau poate sunt eu idiot. nu imi dau seama de ce nu merge.]


E bun codul lui Gabi. Daca gasesti ca are 2 sefi, intra in bucla direct. Deci oricum ar avea mai multi de 2, ar intra in bucla.
Nu se poate ca un iepure sa aiba 2 sefi....pt ca atunci nu ar mai fi un arbore....ba mai mult....stiind k se dau pe n-1 linii relatiile dintre iepuri....vom avea un graf care nu e conex (si ar ramane cel putin un iepure singur :P fara sef...si fara fii)


Titlul: Răspuns: 682 Iepuri2
Scris de: Vasile din Martie 12, 2009, 08:20:34
Ce inseamna modulo 30011?


Titlul: Răspuns: 682 Iepuri2
Scris de: Andrei Misarca din Martie 12, 2009, 08:33:31
a modulo b inseamna restul impartirii lui a la b. In cazul de fata este vorba de restul impartirii rezultatului la 30011. Citeste mai mult aici (http://en.wikipedia.org/wiki/Modular_arithmetic)


Titlul: Răspuns: 682 Iepuri2
Scris de: Sorin Rita din Februarie 19, 2012, 13:31:24
Imi poate explica si mie cineva ideea de rezolvare ? Am citit solutia oficiala si nu inteleg de ce e asa :

Observăm că putem deduce numărul de posibilităţi de a împărţi un anumit număr j de morcovi la un iepure i şi oricâţi morcovi la iepurii subordonaţi direct sau indirect dacă cunoaştem numărul de posibilităţi de a împărţi j+1, j+2, ..., j+K morcovi la fiecare fiu al său si oricâţi morcovi iepurilor ce aparţin subarborilor desemnaţi de fiecare fiu.


Titlul: Răspuns: 682 Iepuri2
Scris de: Gabriel Vanca din Februarie 20, 2014, 09:36:06
Parerea mea este ca memoria este prea la limita. Am luat 100 de puncte, dar daca declar 1-2 variabile de tip int global si nu local, iau 80-90 puncte. Cred ca ar trebui extinsa limita de memorie macar la 680 kb.


Titlul: Răspuns: 682 Iepuri2
Scris de: Andrei Coman din Martie 02, 2016, 15:03:48
 :banana: