682 Iepuri2

[•DITzoneC]

Aici puteţi discuta despre problema Iepuri2.

[•florin_marius90]

ce a mai nashpa olimpiada zau....... 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  la nationala nici macar nu aveau habar de o rezolvare brute.  si mai bine pleci in italia la ciordit de portifele  ca viata nu e dreapta deci ''fura, minte si sari la gat ca maine poate fii mai rau''

[•fireatmyself]

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 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.

[•toni2007]

un iepure poate avea doi sefi directi?

[•sima_cotizo]

Nup:

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

[•andreisfrent]

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 :)

[•gabitzish1]

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.
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.

[•andreisfrent]

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.]

[•cos_min]

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.

[•andreisfrent]

puteti pune si voi niste teste? ca nu stiu ce am gresit de iau 90 pct... WA pe testul 8... multumesc.

[•cos_min]

puteti pune si voi niste teste? ca nu stiu ce am gresit de iau 90 pct... WA pe testul 8... multumesc.

Incearca testele oficiale.

[•stocarul]

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 fara sef...si fara fii)

[•LowArmour]

Ce inseamna modulo 30011?

[•Mishu91]

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

[•soriyn]

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.

[•gabrielv]

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.

[•andreicoman]