190 Telegraf

[ditzone]

Aici puteţi discuta despre problema Telegraf.

[•chibicitiberiu]

Am incercat sa rezolv problema astfel:

Citesc din fisier, numar cate tipuri caractere are textul, in functie de acest numar aflu pe cati biti trebuie scris in reprezentare binara, si am numarat in binar de la 0 la nr respectiv pe cati biti trebuie. La ultimul numar din acest sir de nr binare ii tai ultimele zerouri. Daca numarul e mai > 32 (si <36) atunci in binar va fi de forma 1000xx, asadar tai cele 3 zerouri.

Apoi aranjez sirul citit din fisier astfel incat toate valorile >0 sa fie la inceputul sirului, si zerourile la sfarsit.
Am numarat apoi cati de 0 si cati de 1 exista la fiecare caracter in reprezentarea binara. Dintre nr de 0 si nr de 1 il aleg pe cel mai mare ca fiind punct, iar pe cel mai mic fiind linie, adun nr puncte si 2x nr linii si asta e rezultatul.

Prin algoritmul asta iau 10/100, iau doar primul test, restul WA. Imi poate zice cineva daca e bun sau nu algoritmul, ce ar trebui sa schimb sau poate alt algoritm care functioneaza?

[•wefgef]

Algoritmul tau este gresit.

Aceasta este o problema destul de grea, ti-as recomanda sa o abandonezi pana cand capeti mai multa experienta.

[•chibicitiberiu]

Imi da si mie cineva un indiciu?
 

Am incercat o solutie folosind arbori binari... construiesc arborii asemanator cu cei de la coduri Huffman... dar ma asigur ca fiecare nod e cat mai greu in partea stanga, astfel incat sa se obtina costul cat mai mic.

Cu ideea asta iau doar 30 puncte...

[•pauldb]

Nu este corecta abordarea ta. Intr-adevar, trebuie sa construiesti arborele binar care corespunde solutiei optime, dar trebuie sa iei in considerare faptul ca unele muchii pot avea pondere 2. Pentru constructia arborelui este nevoie sa folosesti programare dinamica.

[•chibicitiberiu]

Nu este corecta abordarea ta. Intr-adevar, trebuie sa construiesti arborele binar care corespunde solutiei optime, dar trebuie sa iei in considerare faptul ca unele muchii pot avea pondere 2. Pentru constructia arborelui este nevoie sa folosesti programare dinamica.

Aha, o sa incerc asa
Merci de sfat