799 Fetite

[•wefgef]

Aici puteti discuta despre problema Fetite.

[•xtreme]

Aici puteti discuta despre problema Fetite.

frumoasa rezolvare , dar demonstratie ? , sau cum ati dedus ?

[•wefgef]

Sa luam un caz practic: N = 14.

Vei elimina la inceput 2, 4, 6, 8, 10, 12, 14. Vei ramane cu 1, 3, 5, 7, 9, 11, 13 - in total 7 = 14/2 elemente. Daca stim ca raspunsul pentru N = 7 este egal cu f(7), atunci f(14) va fi elementul de pe pozitia f(7) din sirul 1, 3, 5, 7, 9, 11, 13. Intr-un sir format din numerele impare in ordine crescatoare, pe pozitia x se afla elementul 2*x - 1 - se demonstreaza prin inductie. De aici rezulta f(14) = 2*f(7) - 1.

Se generalizeaza pentru N = 2*k si se rezolva analog pentru N = 2*k + 1.

[•xtreme]

Sa luam un caz practic: N = 14.

Vei elimina la inceput 2, 4, 6, 8, 10, 12, 14. Vei ramane cu 1, 3, 5, 7, 9, 11, 13 - in total 7 = 14/2 elemente. Daca stim ca raspunsul pentru N = 7 este egal cu f(7), atunci f(14) va fi elementul de pe pozitia f(7) din sirul 1, 3, 5, 7, 9, 11, 13. Intr-un sir format din numerele impare in ordine crescatoare, pe pozitia x se afla elementul 2*x - 1 - se demonstreaza prin inductie. De aici rezulta f(14) = 2*f(7) - 1.

Se generalizeaza pentru N = 2*k si se rezolva analog pentru N = 2*k + 1.

Multumesc.

[•onoffrei]

modul gasit de mine pt fetite e urmatorul.... am scris in baza 2 numarul de petale si numarul petalei care ramane ultima, dupa cateva exemple (
ex 1 : nr de petale = 5  in baza 2 :    101  -> ultima petala cu nr 1 in baza 2 :  11
ex 2 : nr de petale = 10 in baza 2 : 1010  -> ultima petala cu nr 5 in baza 2 : 101
ex 3 : nr de petale = 13 in baza 2 : 1101  -> ultima petala cu nr 11 in baza 2 : 1011
)
am observat ca in baza 2 numarul cautat are aceeasi forma ca numarul de intrare (nr de petale) doar ca este deplasat cu 1 la stanga si primul bit (bitul cu nr de ordine mai mare) ajungand la coada (bitul cu nr de ordine mai mic) exact ca in operatia ROL 1 (ROtate Left) din asembler cu diferenta ca numarul de biti asupra caeia lucreaza e egal cu numarul de biti ocupati de numarul de intrare

[•f.v.anton]

la restrictii este chiar 2⁶³? sau 2 ³⁶ ca eu am folosit long long si mi-a intrat.

[•devilkind]

long long -> 64 de biti -> [-2^63 .. 2^63]. Deci da, e 2^63.

[•danalex97]

Februarie 18, 2009, 17:37:25  onofrei •onoffrei
modul gasit de mine pt fetite e urmatorul.... am scris in baza 2 numarul de petale si numarul petalei care ramane ultima, dupa cateva exemple (
ex 1 : nr de petale = 5  in baza 2 :    101  -> ultima petala cu nr 1 in baza 2 :  11
ex 2 : nr de petale = 10 in baza 2 : 1010  -> ultima petala cu nr 5 in baza 2 : 101
ex 3 : nr de petale = 13 in baza 2 : 1101  -> ultima petala cu nr 11 in baza 2 : 1011
)
am observat ca in baza 2 numarul cautat are aceeasi forma ca numarul de intrare (nr de petale) doar ca este deplasat cu 1 la stanga si primul bit (bitul cu nr de ordine mai mare) ajungand la coada (bitul cu nr de ordine mai mic) exact ca in operatia ROL 1 (ROtate Left) din asembler cu diferenta ca numarul de biti asupra caeia lucreaza e egal cu numarul de biti ocupati de numarul de intrare

Am facut o rezolvare dupa metoda ta si vreau sa te intreb cum ai ajuns la aceasta concluzie(cum ti-a venit ideea)?
 

Editat de moderator: Foloseste tag-ul [ quote ] cand citezi pe altii.

[•miculprogramator]

S-ar putea sa scriu o mare prostie, dar am constatat ceva si nu stiu daca este adevarat ...

daca n=7

Avem 1,2,3,4,5,6,7 . Taiem: 2,4,6 in prima faza, apoi in a 2-a faza 1,3,5. Raman cu 7, adica  n.

daca n=4

Avem 1,2,3,4. Taiem: 2,4,1 si ramanem cu 3, adica n-1.

Nu stiu daca am gandit corect, explicati-mi daca e bine sau nu. 

[•klamathix]

S-ar putea sa scriu o mare prostie, dar am constatat ceva si nu stiu daca este adevarat ...

daca n=7

Avem 1,2,3,4,5,6,7 . Taiem: 2,4,6 in prima faza, apoi in a 2-a faza 1,3,5. Raman cu 7, adica  n.

daca n=4

Avem 1,2,3,4. Taiem: 2,4,1 si ramanem cu 3, adica n-1.

Nu stiu daca am gandit corect, explicati-mi daca e bine sau nu. 

Pai spune-ne ce ai gandit .

[•miculprogramator]

Am gandit ce am si scris, anume ca daca n este numar impar ultima petala este n insusi ; daca n este par ultima petala este n-1. Nu stiu daca am dreptate ... 

[•klamathix]

Am gandit ce am si scris, anume ca daca n este numar impar ultima petala este n insusi ; daca n este par ultima petala este n-1. Nu stiu daca am dreptate ...  

N-ai fost prea explicita. Nu merge nici pe exemplu, citeste solutia oficiala si incearca sa-ti demonstrezi teoriile cand lucrezi din arhiva . Si no offence, dar nu mai posta cand chestia asta iti ia mai mult timp decat sa te verifici cu exemplul din text   Just a tip , poate iti mai creste karma

[•miculprogramator]

Am citit solutia oficiala si am creat o functie care face intocmai cum am citit:

Cod:

long long N,i,r;
long fetite(long N)
{
     if (N%2==0) r=2*fetite(N/2)-1;  
        else if (N%2!=0) r=2*fetite(N/2)+1;
     return r;
}

Nu apare nimic in fisier ... 

[•pauldb]

Pentru ca nu ai conditii de oprire. Poate ar fi o idee sa inveti mai mult despre recursivitate. Acesta e un subiect tratat pe larg in manualele de la 9-10.

[•miculprogramator]

Ce conditii de oprire imi trebuie ?

LE: A iesit, multumesc Emanuel. 

[•alex_unix]

Eu am alta solutie  . Am luat un interval [i,j] (initial [1,n]) unde i este prima petala, iar j este ultima. La fiecare pas calculez i si j pana cand au aceeasi valoare, adica am ajuns la ultima petala. Nu ma pricep foarte bine la complexitati, dar cred ca e O(log n) 

[•an_drey_curent]

Am avut si eu o solutie diferita de cea oficiala, care nu o prea am vazut-o in solutiile de pana atunci. Am intrebat daca pot modifica articolul cu solutii, si am facut-o(  eram si eu mandru de mine). Oricine poate modifica articolul cu solutii, asa ca daca ai o solutie buna,diferita si vrei sa o impartasesti  nu ezita  .

[•Volkazar]

Exemplul e gresit deoarece pt n=5 zice ca ultima e 3 

[•wefgef]

Exemplul e corect.

[•Andrei-27]

Sau (n  - 2 la [log2 din n] )*2 + 1.
[ ] - partea intreaga
Plecand de la observatia ca pt numerele din
 [2 la n, 2 la(n+1)   -1] se afiseaza numerele impare din
 [ 1, 2 la n   -1].