Imprimă pagina - 799 Fetite

Titlul: 799 Fetite
Scris de: Andrei Grigorean din Februarie 15, 2009, 13:30:53

Aici puteti discuta despre problema Fetite (http://infoarena.ro/problema/fetite).

Titlul: Răspuns: 799 Fetite
Scris de: speedzeal din Februarie 16, 2009, 20:45:22

Citat din mesajul lui: Andrei Grigorean din Februarie 15, 2009, 13:30:53

Aici puteti discuta despre problema Fetite (http://infoarena.ro/problema/fetite).

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

Titlul: Răspuns: 799 Fetite
Scris de: Andrei Grigorean din Februarie 16, 2009, 22:10:40

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.

Titlul: Răspuns: 799 Fetite
Scris de: speedzeal din Februarie 17, 2009, 19:21:20

Citat din mesajul lui: Andrei Grigorean din Februarie 16, 2009, 22:10:40

Multumesc.

Titlul: Răspuns: 799 Fetite
Scris de: onofrei din Februarie 18, 2009, 17:37:25

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

Titlul: Răspuns: 799 Fetite
Scris de: Flavius Anton din Februarie 20, 2009, 10:52:21

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

Titlul: Răspuns: 799 Fetite
Scris de: Savin Tiberiu din Februarie 20, 2009, 10:57:56

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

Titlul: Răspuns: 799 Fetite
Scris de: Dan H Alexandru din Martie 24, 2009, 19:43:37

Citat

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)?
:-k

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

Titlul: Răspuns: 799 Fetite
Scris de: A Cosmina - vechi din Iulie 23, 2009, 19:04:42

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. :-k

Titlul: Răspuns: 799 Fetite
Scris de: Mihai Calancea din Iulie 23, 2009, 22:02:48

Citat din mesajul lui: ALbulescu Cosmina din Iulie 23, 2009, 19:04:42

Pai spune-ne ce ai gandit .

Titlul: Răspuns: 799 Fetite
Scris de: A Cosmina - vechi din Iulie 23, 2009, 22:07:19

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 ... :?

Titlul: Răspuns: 799 Fetite
Scris de: Mihai Calancea din Iulie 23, 2009, 22:13:57

Citat din mesajul lui: ALbulescu Cosmina din Iulie 23, 2009, 22:07:19

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 :D

Titlul: Răspuns: 799 Fetite
Scris de: A Cosmina - vechi din Iulie 27, 2009, 22:17:51

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 ... ???

Titlul: Răspuns: 799 Fetite
Scris de: Paul-Dan Baltescu din Iulie 27, 2009, 22:55:04

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.

Titlul: Răspuns: 799 Fetite
Scris de: A Cosmina - vechi din Iulie 27, 2009, 22:57:18

Ce conditii de oprire imi trebuie ? :sad:

LE: A iesit, multumesc Emanuel. :peacefingers:

Titlul: Răspuns: 799 Fetite
Scris de: Petenchea Alexandru din Aprilie 13, 2012, 14:41:13

Eu am alta solutie :P . 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) :D

Titlul: Răspuns: 799 Fetite
Scris de: andreycurent din Aprilie 13, 2012, 18:42:33

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( :oops: 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 :ok: nu ezita :wink:.

Titlul: Răspuns: 799 Fetite
Scris de: Serban Rares din Iunie 11, 2016, 10:57:30

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

Titlul: Răspuns: 799 Fetite
Scris de: Andrei Grigorean din Iunie 12, 2016, 07:49:28

Exemplul e corect.

Titlul: Răspuns: 799 Fetite
Scris de: Arhire Andrei din Iulie 19, 2018, 23:29:18

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].

infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Andrei Grigorean din Februarie 15, 2009, 13:30:53