| ssmax |
|
La o şcoală de informatică bine cotată se organizează un concurs de programare. Una dintre problemele de concurs este cea a generării tuturor subşirurilor de lungime maximă pentru un şir cu n elemente. Autorul problemei a hotărât să genereze teste, folosind numai elemente întregi dintr-un interval dat [a,b], iar numărul de soluţii să crească gradat de la un test la altul. Pentru acest motiv el este dornic să afle cazul cel mai nefavorabil existent pentru un interval dat: adică să găsească elemente pentru şir din intervalul [a,b], astfel încât să se obţină un număr maxim de subşiruri de lungime maximă (cu alte cuvinte: niciun alt şir cu elemente din intervalul dat să nu conţină mai multe soluţii de lungime maximă). De exemplu, pentru n=4, cu elementele intervalului [3,5] putem construi printre altele şirurile a=(a1,a2,a3,a4)=(4,3,4,5) sau b=(b1,b2,b3,b4)=(4,3,5,5). Observăm că şirul a conţine un singur şir crescător de lungime maximă (a2,a3,a4)=(3,4,5), pe când şirul b conţine patru subşiruri crescătoare de lungime maximă, chiar dacă ele sunt de lungime mai mică: (b1,b3)=(4,5), (b1,b4)=(4,5), (b2,b3)=(3,5), (b2,b4)=(3,5). Cerinţă Scrieţi un program care să determine pentru n, a şi b date numărul maxim de subşiruri de lungime maximă ce poate avea un şir de lungime n având toate elementele din intervalul [a,b].Date de intrare Fişierul de intrare ssmax.in conţine pe prima linie trei numere naturale n, a şi b separate prin câte un spaţiu, cu semnificaţiile de mai sus. Date de ieşire Fişierul de ieşire ssmax.out va conţine o singură linie pe care va fi scris un numărul maxim de subşiruri ce se pot construi pentru datele de intrare modulo 666013.Restricţii
Exemplu
|