|
Titlul: 305 Triplete Scris de: Adrian Diaconu din Ianuarie 21, 2007, 23:56:17 Aici puteţi discuta despre problema Triplete (http://infoarena.ro/problema/triplete).
Titlul: Răspuns: 305 Triplete Scris de: Ozorchevici Ana Maria din Februarie 24, 2007, 12:38:22 va rog frumos imi puteti spune ce are atat de special ultimul test?e singurul caz care imi da incorect ](*,)
Titlul: Răspuns: 305 Triplete Scris de: Andrei Grigorean din Februarie 24, 2007, 20:47:18 Unele variabile trebuie declarate unsigned int (sunt mai mari de 2 miliarde). Ai grija de asta?
Titlul: Răspuns: 305 Triplete Scris de: Andrei Homorodean din Februarie 24, 2007, 21:03:30 Vezi ca e unsigned long int....
Titlul: Răspuns: 305 Triplete Scris de: Bogdan-Cristian Tataroiu din Februarie 24, 2007, 21:34:05 in gcc int = long int...
Titlul: Răspuns: 305 Triplete Scris de: David si Goliat din Februarie 25, 2007, 22:03:25 Exista vreo functie care returneaza in O(1) nr de biti de 1 ai unui nr ?
Titlul: Răspuns: 305 Triplete Scris de: Andrei Grigorean din Februarie 25, 2007, 22:06:19 Eu nu cunosc o astfel de functie sau macar un algoritm care sa faca asta. Poti in schmb sa faci o preprocesare si sa raspunzi in O(1).
Exista totusi posibilitatea sa afli in O(nr_de_biti_de_1) folosindu-te de operatii pe biti. Titlul: Răspuns: 305 Triplete Scris de: Lucian Boca din Februarie 26, 2007, 15:44:20 Exista vreo functie care returneaza in O(1) nr de biti de 1 ai unui nr ? Numarul de biti de 1 se numeste Hamming weight. Il poti calcula in O(log N), cu o masca pe biti, sau cu niste formule dubioase in timp (aproape :D ) O(1). Vezi http://en.wikipedia.org/wiki/Hamming_weight#Efficient_implementationTitlul: Răspuns: 305 Triplete Scris de: Savin Tiberiu din Februarie 26, 2007, 18:54:21 la problema asta daca (,) calculezi numarul de biti de 1 al unui nr in log n e prea mult. Iti trebuie o(1). Cel mai bine e cu prepocesare cum a zis si andrei grigorean.
Titlul: Răspuns: 305 Triplete Scris de: Andrei Homorodean din Mai 08, 2007, 21:32:23 Daca numeri bitii de 1 normal ajungi tot la complexitatea intiala.. E chiar absolut necesar sa faci precalculare? Nu mi se pare normal sa faci precalculare la o problema ca sa iti intre in timp. Mai ales ca daca ai lucra pe 16 biti ajungi si pe la numere de 5 cifre..
Titlul: Răspuns: 305 Triplete Scris de: Airinei Adrian din Mai 08, 2007, 21:40:53 Precalcularea o poti face in 2 linii de cod:
Cod: for(i = 1; i < N; i++) Titlul: Răspuns: 305 Triplete Scris de: Andrei Homorodean din Mai 08, 2007, 21:54:43 A, precalculare in program, gata, m-am prins, sorry :)
Later edit: wow, chestia chiar merge si e tare, merci mult :D Nu vad ce gresesc... cat va da pe testele test1 Cod: 6 10 test2 Cod: 5 9 test3 Cod: 14 20 Titlul: Răspuns: 305 Triplete Scris de: Paul-Dan Baltescu din Mai 09, 2007, 08:46:36 Nu era bun executabilul cu care am rulat:
5 7 6 [Pe testul corectat] Titlul: Răspuns: 305 Triplete Scris de: Andrei Homorodean din Mai 09, 2007, 09:02:00 si pe testul 1
Cod: 6 10 ce alte triunghiuri mai sunt inafara de urmatoarele: 2 4 6 1 2 3 2 3 4 4 5 6 1 2 6 Cred ca ti-a dat gresit(sau numeri fiecare triunghi de 3 ori...) Testul 3 e gresit ca se repeta 12 14, daca stergeti ultima muchie si puneti m 19, ar trebui sa dea 6, nu? Titlul: Răspuns: 305 Triplete Scris de: Vlasceanu Razvan din Martie 25, 2009, 00:23:04 Daca ati folosit matrice ati reusit sa aveti memorie pentru ultimul test? daca da imi spuneti si voi cum ati facut ca eu nu reusesc deloc sa intru in ultimu test prin metoda asta.
|