041 Sobo

[•domino]

Aici puteţi discuta despre problema Sobo.

[•vladcyb1]

Am citit solutia la prob asta, dar nu inteleg o kestie.
1. Daca avem un singur sobolan costul este 0, nu?
2. Daca avem 2 sobolani costul este cel mai mic pret platit pentru a intreba intr-un punct care este diferit la cei doi sobolani? (adica in punctul i la unul este 0 si la celalalte este 1)
3. Cand avem mai mult de trei sobolani de exemplu:
 a[7]; 7=111 cum functioneaza propriu zis ideea. Cum impart in multimi nevide si cum iau costurile?
Poate ca e super simplu, dar nu ma prind
   

 

[•Stilgar]

as vrea sa stiu un lucru: solutia ii tot un fel de  backtraking mai optimizat sau ii ceva dfinamica pe care io no vad?
pls help

[•bogdan2412]

Programare dinamica. Uita-te peste articolul http://info.devnet.ro/articole.php?page=art&art=25

[•Cosmin]

stilgar: sunt curios cate probleme ai facut tu pe infoarena cu "tot un fel de backtraking mai optimizat"

[•Mishu91]

Am o întrebare, cum se face împărțirea aceea în 2 mulțimi nevide, fără a mai parcurge toate submulțimile de la 0 la configurația actuală, pentru că, pentru a determina maximul, ar cam trebui să caut toate posibilitățile de împărțire.

[•0000]

Ca sa poti sa imparti in O(1) in doua multimi,poti precalcula niste vectorii. V[ i ] = ce harti de sobolani raman in calcul daca se raspunde cu 1 la intrebare despre bitul 1.

[•Pepelea_Flaviu]

Cred ca ar trebui schimbate restrictiile sau testul 4, din cate vad valorile sunt mai mari decat 1000000, iar rezultatul final nu intra in int

[•bdrzr]

Linkul pus de Bogdan nu mai este valabil. Mai stie cineva care era articolul si poate sa puna linkul bun?

[•pauldb]

http://infoarena.ro/warm-up-2004/solutii

Poti gasi solutii la multe probleme din concursurile infoarena aici: http://infoarena.ro/articole/solutii.

[•andreiulian]

până la urmă, testul 4 e corect sau nu? că e singurul la care iau WA...

[•klamathix]

Are valori mai mari decât era specificat, într-adevăr. Am înlocuit $1.000.000$ cu $11.000.000$ în enunț.