Siruri 2-3-monotone
Fie N (N ≤ 1000) un numar natural. Numim sir 2-3-monoton de lungine N un sir S1, S2, S3, … Sn format din N elemente ale multimii {1, 2, … N} care verifica urmatoarele doua relatii:
Si < Si+2, oricare ar fi 1 ≤ i ≤ N-2
Si < Si+3, oricare ar fi 1 ≤ i ≤ N-3
Cerinta
Fie X numarul de siruri 2-3-monotone de lungime N. Calculati restul impartirii lui X la 1.000.000 (1 milion).
Date de intrare
Fișier: ul sir23.in va contine pe prima linie numarul intreg N.
Date de iesire
Pe prima linie a fisierului sir23.out se va scrie numarul cautat.
Exemple
sir23.in sir23.out
2 4
3 9
5 88
ma chinui de doua ore sa gasesc relatia de recurenta.am observat cateva cazuri elementare si ca nu pot exista mai mult de 2 termeni consecutivi egali,dar e prea putin. aceasta problema ma depaseste
solutie?
http://www.infoarena.ro/problema/sir23
Problema are destule comentarii care te pot duce lejer la solutie. Solutia optima e O(N) cea implementata de mine e O(N^2) iar cea care nu obtine 100p e O(N^3). Mai chinuie-te la ea… 2 ore nici mie nu mi-a fost suficient. Daca nu iese si nu iese… o sa-ti dau PM cu solutia in C/C++. Dar nu-mi place ca abandonezi prea rpd. Eu nu cred ca te depaseste esti tu mai imprastiat… fara suparare dar asha imi lasi impresia cand renunti dupa 2 ore.