[(Fm+n,Fm+n-1)=( FmFn+Fm-1Fn+FmFn-1 , FmFn+Fm-1Fn-1)]

Scuze. Am aruncat o vorba fara nicio explicatie. Eu ma gandeam la ceva recursiv pe metoda urmatoare:

(F_m+n,F_m+n-1)=( F_mF_n+F_m-1F_n+F_mF_n-1 , F_mF_n+F_m-1F_n-1)

De aici

(F_2k,F_2k-1)=( F_k²+2F_kF_k-1 , F_k²+F_k-1²)

 si

(F_2k+1,F_2k)=( F_2k+F_2k-1,F_2k)

Astfel se obtine ceva similar cu ce spunea Vlad. La fiecare pas, n se injumatateste si se aplica operatii de inmultire si adunare care duc la complexitate L²  ( unde L este numarul de cifre n/log n ). Sumand aceste complexitati mie imi da ceva de genul  O ( n^1,7 ) .

Complexitatea la care te gandesti e ceva de forma O( n^a )  unde a e prin apropiere de 1,7 ?

Prima restrictie este : •   6<=N<=200; ( 200 nu 20 )

Rezultate prima zi.

Vlad Alexandru Gavrila 249p (Locul 23)
Andrei Purice 192p (Locul 55)
Adrian Budau 170p (Locul 79)
Gheorghe Mihai Dan 100p (Locul 182)

Rezultatele complete le adresa http://sc2.ioi2011.net:8070/scoreboard/ ( accesibila dealtfel si de pe site-ul oficial)

Sunt 17 punctaje maxime dupa prima zi.

Din socotelile mele cel mai bine stau China si Croatia ( cate 3 punctaje maxime ) iar Romania este in top 10.

L.E. Am incurcat socotelile

@ Catalin

Incearca sa rezolvi un caz cu valori mici.

Ia de exemplu:  S=1000  A=2 B=3 ( 3A+2 = 8 ,  3B+1 = 10 )

Pe zile ar trebui sa obtii sumele:

1000 , 1008, 336, 112 , 120, 40, 48, 16, 24, 8, 18, 6, 2, 12, 4 , 12, 4, 12, 4, 12,4, 12, 4, 12...

Observa ca macar o data la doua zile suma se imparte prin 3, ca dupa cateva zile se ajunge la sume destul de mici si ca secventa de sume "12 , 4"  incepe sa se repete incepand din prima zi cand s-a obtinut 12.

Ideea e simularea operatiilor folosind "numere mari" pana ajungi la "numere mici" si apoi marcarea sumelor mici ( de ordinul de marime un pic peste numerele 3A+2 si 3B+1 ) cu zilele in care se obtin prima data. Sumele care se repeta nu depasesc ordinul zecilor de mii.

Daca nu stii inca operatii cu numere mari ar fi bine sa incepi prin a le invata inainte de a incerca sa rezolvi problema.

 

Nu stiu cat de mult am voie sa spun. Nu stiam problema dinnainte. Insa pot spune ca solutia este formula care implica doar 6 puncte din figura (4 pentru calcul si inca 2 pentru verificare) si o ecuatie de grad 2 in complex. Daca nu spun prea mult: punct fix pentru o transformare omografica. Daca am spus deja prea mult se poate sterge postul

@ Usurelu Daniel

Am cautat printre sursele trimise recent la problema si nu am gasit niciuna trimisa de tine. Da un nr de Job al sursei tale daca vrei sa primesti sfaturi.

Felicit pe cei care au avut ideea infiintarii grupei Open. Am intrebare pentru Andrei Parvu si/sau Tiberiu Savin "marm" de la TractoMarm de la ce vine ? De la Marmura sau se la Marmota ?  


L.E. Sau poate de la Marmureanu - cel care ne tot ameninta cu un cutremur.