Runda 5

[•vlad.manea]

Runda 5 a concursului F11 se desfasoara intre 16 si 20 mai. http://www.fiicompetition.ro/f11/category/algoritmica/probleme-alg/#5 Intrebarile le puteti pune pe blogul concursului http://blog.fiicompetition.ro/2011/intrebari-algoritmica-si-programare/ sau la adresa [email protected]

[•S7012MY]

Ce se intampla cu punctele care au o una din coordonate 0?

[•vlad.manea]

Toate punctele au coordonate strict pozitive. Am clarificat și în enunț.

[•SpiderMan]

La problema "drum", afisul pentru nicio solutie este asta : No solution, adica fara '.' ( punct ) nu ?

[•spatarel]

Problema "drum":

1) Daca ambasadorul ajunge pe o planeta, alimenteaza nava, face un ciclu si revine pe planeta de pe care a alimentat, mai poate REalimenta?

2) Daca ambasadorul ajunge pe o planeta, NU alimenteaza nava, face un ciclu si revine pe planeta de pe care NU a alimentat, mai poate alimenta?

3) Daca ambasadorul poate ajunge pe Pamant cu aceeasi cantitate maxima de minerale, dar prin mai multe drumuri (cu timpi diferiti) ce timp se afiseaza? Timpul minim?

[•vlad.manea]

La problema "drum", afisul pentru nicio solutie este asta : No solution, adica fara '.' ( punct ) nu ?

Fără .

[•vlad.manea]

Problema "drum":

1) Daca ambasadorul ajunge pe o planeta, alimenteaza nava, face un ciclu si revine pe planeta de pe care a alimentat, mai poate REalimenta?

2) Daca ambasadorul ajunge pe o planeta, NU alimenteaza nava, face un ciclu si revine pe planeta de pe care NU a alimentat, mai poate alimenta?

3) Daca ambasadorul poate ajunge pe Pamant cu aceeasi cantitate maxima de minerale, dar prin mai multe drumuri (cu timpi diferiti) ce timp se afiseaza? Timpul minim?

Am trimis întrebările tale autorului problemei. Răspunsul este afirmativ la toate cele trei întrebări.

[•spatarel]

Ma surprinde raspunsul afirmativ de la prima intrebare. Asta inseamna ca nu are sens sa nu alimentezi... Sau nu-l vad eu. Asa ca intreb:

4) Are sens sa nu alimentezi, cand te afli pe o planeta?

Si o sa mai intreb:

5a) La plecare, ambasadorul porneste intotdeauna cu rezervorul la capacitate maxima?
5b) La plecare, ambasadorul porneste cu rezervorul la Min(capacitatea rezervorului, cantitatea de combustibil de pe planeta 1)?

6) Ambasadorul se poate reintoarce pe planeta 1, sa REalimenteze?

[•vlad.manea]

Am trimis autorului întrebările.

4) Are sens. Să presupunem că sunt pe o planetă A din care am două trasee posibile, unul spre planeta B şi altul spre planeta C. Din planeta B singurul drum este cel înapoi spre A. Dacă am suficient combustibil să ajung pe planeta B, să alimentez acolo şi să mă întorc, atunci are sens să alimentez doar la plecarea din A spre planeta C (teoretic am păstrat mai mult combustibil în A pentru drumurile viitoare care includ această planetă şi care nu mai trec prin B)
Cazul ar putea fi ceva de genul: am 30 combustibil, pe planeta A există 50 combustibil, pe planeta B există 100 combustibil, costul drumului A - B este 30, capacitatea maximă a rezervorului este 120. Dacă parcurg drumul A - B - A şi fac plinul în prima vizită în A, plec spre C cu 90 combustibil, dacă fac plinul la a doua vizită plec spre C cu 120 combustibil (diferenţa este dată de faptul că ajung cu prea mult combustibil în B şi nu pot să iau tot combustibilul de acolo din cauza capacităţii rezervorului)

5b) este varianta corectă

6) Nu există restricţii în acest sens, deci teoretic se poate

[•spatarel]

Eu am intrebat si mi s-a raspuns:
1) Daca ambasadorul ajunge pe o planeta, alimenteaza nava, face un ciclu si revine pe planeta de pe care a alimentat, mai poate REalimenta? - DA

Citez din enunt:
Dacă o dată ajuns pe o planetă Ambasadorul se decide să alimenteze cu combustibil, el va face de fiecare dată plinul rezervorului în limita cantității de deuteriu prezentă pe planetă și a capacității C a rezervorului.

Din cele doua, se poate deduce ca in situatia descrisa in raspunsul explicativ de la intrebarea (4) putem face urmatoarele:
Pornim cu rezervorul cu 30.
1) Alimentam in A (R: 30 + 50 = 80)
2) Mergem in B (R: 80 - 30 = 50)
3) Alimentam in B (R: 50 + 100 = 150 (120))
4) Ne intoarcem in A (R: 120 - 30 = 90)
5) REAlimentam in A (R: 90 + 50 = 140 (120))
Si putem porni spre C cu rezervorul plin (120)!

Care este interpretarea raspunsului afirmativ de la prima intrebare? Daca pot realimenta, la realimentare cu cat pot realimenta? Cu cantitatea de combustibil din datele problemei? Sau doar cu cantitatea de combustibil ramasa in urma primei alimentari?

Bleah... mi se pare mult prea complicata problema asta .

Alternativ, daca realimentarea nu se poate face decat in limita combustibilului ramas, atunci ar putea exista urmatorul scenariu:
1) Alimentam in A (R: 30 + 20 = 50) - si pastram in A 30
2) Mergem in B (R: 50 - 30 = 20)
3) Alimentam in B (R: 20 + 100 = 120)
4) Ne intoarcem in A (R: 120 - 30 = 90)
5) REAlimentam in A (R: 90 + 30 = 120) - si nu mai ramane nimic in A

Insa! Aceasta problema devine foarte... complicata, pentru ca, la fel de bine, putem presupune urmatorul scenariu:
Sa spunem ca in A avem 60 de combustibil. Atunci avem scenariul:
1) Alimentam in A (R: 30 + 20 = 50) - si pastram in A 40
2) Mergem in B (R: 50 - 30 = 20)
3) Alimentam in B (R: 20 + 100 = 120)
4) Ne intoarcem in A (R: 120 - 30 = 90)
5) REAlimentam in A (R: 90 + 30 = 120) - si pastram in A 10
Insa, in scenarii derivate acestuia, putem sa pastram 5 in A si 5 in B, sau 3 in A si 7 in B samd.; iar daca B are legaturi si cu alte planete, o revenire a mea in B, prin aceste alte planete s-ar putea sa fie posibila plastrand un pic de combustibil si acolo - la fel de bine, s-ar putea sa vreau sa revin in A si sa am nevoie de combustibil si de acolo - si chiar trebuie sa analizez toate aceste cazuri: 5/5, 3/7 etc.

Intrebare:
De ce aceasta problema pare sa fie atat de complicata? Nu inteleg eu ceva sau autorul problemei chiar vrea sa ma chinuie?

[•vlad.manea]

Adaug aici raspunsurile autorului problemei la intrebarile tale:

Care este interpretarea raspunsului afirmativ de la prima intrebare? Daca pot realimenta, la realimentare cu cat pot realimenta? Cu cantitatea de combustibil din datele problemei? Sau doar cu cantitatea de combustibil ramasa in urma primei alimentari?

În mod absolut evident se poate realimenta doar în limita cantităţii de combustibil rămase în urma alimentărilor anterioare.

Alternativ, daca realimentarea nu se poate face decat in limita combustibilului ramas, atunci ar putea exista urmatorul scenariu:
1) Alimentam in A (R: 30 + 20 = 50) - si pastram in A 30
2) Mergem in B (R: 50 - 30 = 20)
3) Alimentam in B (R: 20 + 100 = 120)
4) Ne intoarcem in A (R: 120 - 30 = 90)
5) REAlimentam in A (R: 90 + 30 = 120) - si nu mai ramane nimic in A

Insa! Aceasta problema devine foarte... complicata, pentru ca, la fel de bine, putem presupune urmatorul scenariu:
Sa spunem ca in A avem 60 de combustibil. Atunci avem scenariul:
1) Alimentam in A (R: 30 + 20 = 50) - si pastram in A 40
2) Mergem in B (R: 50 - 30 = 20)
3) Alimentam in B (R: 20 + 100 = 120)
4) Ne intoarcem in A (R: 120 - 30 = 90)
5) REAlimentam in A (R: 90 + 30 = 120) - si pastram in A 10
Insa, in scenarii derivate acestuia, putem sa pastram 5 in A si 5 in B, sau 3 in A si 7 in B samd.; iar daca B are legaturi si cu alte planete, o revenire a mea in B, prin aceste alte planete s-ar putea sa fie posibila plastrand un pic de combustibil si acolo - la fel de bine, s-ar putea sa vreau sa revin in A si sa am nevoie de combustibil si de acolo - si chiar trebuie sa analizez toate aceste cazuri: 5/5, 3/7 etc.

Cităm încă o dată din enunţ: "Dacă o dată ajuns pe o planetă Ambasadorul se decide să alimenteze cu combustibil, el va face de fiecare dată plinul rezervorului în limita cantităţii de deuteriu prezentă pe planetă şi a capacităţii C a rezervorului." Astfel, o dată decizia de a realimenta fiind luată, cantitatea de combustibil încărcată va fi de fiecare dată min(C, cantitatea de combustibil rămasă pe planetă).

Intrebare:
De ce aceasta problema pare sa fie atat de complicata? Nu inteleg eu ceva sau autorul problemei chiar vrea sa ma chinuie?

Problema doar pare să fie complicată, dar într-adevăr autorul este un individ eminamente sadic.  

[•SpiderMan]

Nu ni se poate da un "exemplu" care sa evidentieze CEL MAI CLAR raspunsul la intrebarea 4) pusa de Spatarel ? Multumim.

[•DraStiK]

As avea si eu o intrebare la problema drum:

Sa zicem ca avem o capacitate C de 100 de litrii. Eu am in rezervor 50 litrii cand ajung intr-o localitate in care exista un depozit de 60 litrii.

Decid sa realimentez. Ce se intampla? In rezervor am 100 litrii iar in depozit raman 10 litrii, sau nu ramane nimic?

[•vlad.manea]

@dragos Am trimis intrebarea ta. Voi actualiza după ce voi primi răspunsul de la autorul problemei.
@robert Explicația pentru întrebarea 4 conține și un exemplu dat de autorul problemei. Voi trimite oricum încă o dată autorului întrebarea ta.

[•vlad.manea]

Sa zicem ca avem o capacitate C de 100 de litrii. Eu am in rezervor 50 litrii cand ajung intr-o localitate in care exista un depozit de 60 litrii.
Decid sa realimentez. Ce se intampla? In rezervor am 100 litrii iar in depozit raman 10 litrii, sau nu ramane nimic?

Pe planetă rămân 10 litri.

[•vlad.manea]

Nu ni se poate da un "exemplu" care sa evidentieze CEL MAI CLAR raspunsul la intrebarea 4) pusa de Spatarel ? Multumim.

Fie următoarea configuraţie de intrare:

4 50 120 3
0 40
0 50
100 100
0 0
1 2 10 10
2 3 10 30
2 4 10 100


Se pleacă de pe planeta 1 cu 40 combustibil, se ajunge pe planeta 2 cu 30 combustibil
1. Varianta I - se alimentează pe planeta 2
Se pleacă de pe planeta 2 cu 80 combustibil, se ajunge pe planeta 3 cu 50 combustibil. Se încarcă mineralele şi se face plinul.
Se pleacă de pe planeta 3 cu 120 combustibil, se ajunge pe planeta 2 cu 90 combustibil. Nu se mai poate face plinul pentru că deja s-a epuizat combustibilul de pe planeta 2 în pasul anterior. Nu se poate pleca spre planeta 4 deoarece drumul necesită 100 combustibil. Nu există soluţie.

2. Varianta II - nu se alimentează pe planeta 2
Se pleacă de pe planeta 2 cu 30 combustibil şi se ajunge pe planeta 3 cu 0 combustibil. Se încarcă mineralele şi se face plinul.
Se pleacă de pe planeta 3 cu 100 combustibil, se ajunge pe planeta 2 cu 70 combustibil. Deoarece există încă 50 combustibil pe planetă, se poate face plinul. Se pleacă spre planeta 4 cu 120 combustibil şi se ajunge cu 20 combustibil. Soluţia este:
100 40

[•stocarul]

Nu cred că trebuie să ni se explice dacă are sens sau nu să aplicăm o anumită strategie...
E de datoria noastră să observăm dacă da sau nu.

[•spatarel]

Multumesc comisiei pentru raspunsurile primite!

Consider ca am inteles problema, dar nu am gasit o solutie buna. Astept jurizarea si solutia oficiala!

LE: Noaptea a trecut, jurizarea s-a facut, solutia oficiala s-a dezvaluit!

Propun spre analiza comisiei urmatorul test:

Cod:

7 1000 250 7
0 101
0 0
0 250
0 250
0 250
1 0
0 0
1 2 1 100
2 3 1 1
3 4 1 1
4 5 1 1
5 2 1 1
2 6 1 100
2 7 1 100

cu solutia
1 8
si drumul
1 2 3 2 6 2 5 2 7

[•a_h1926]

As dori sa propun o alta solutie la problema agendatelefonica pe care am luat 300 de puncte, care consuma memorie O( (N+M)*L), unde N este numarul de prefixe, M numarul de nume si L lungimea unui nume/prefix si timp O(N*logM*L). Unde as putea posta sursa si explicatiile?

[•Magnus]

cred ca nici macar solutiile oficiale nu sunt postate pe infoarena, dar o solutie alternativa.

[•vlad.manea]

As dori sa propun o alta solutie la problema agendatelefonica pe care am luat 300 de puncte, care consuma memorie O( (N+M)*L), unde N este numarul de prefixe, M numarul de nume si L lungimea unui nume/prefix si timp O(N*logM*L). Unde as putea posta sursa si explicatiile?

Trimite-ne un mail la [email protected] sau [email protected] si vedem