Fişierul intrare/ieşire:maxmaxmax.in, maxmaxmax.outSursăLot Baia Mare 2013 - Baraj 1 Seniori
AutorDragos Oprica, Zoltan SzaboAdăugată deMagnvsDaniel Constantin Anghel Magnvs
Timp execuţie pe test0.06 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Maxmaxmax

Maximilian a învăţat programare dinamică la şcoală şi şi-a fixat scopul nobil de a ajunge în Lotul Naţional de Informatică şi, dacă se poate, chiar în cel restrâns. Nu demult a învăţat algoritmul ce calculează pentru un şir cu n elemente, un subşir strict descrescător de lungime maximă.
Aceasta fiind o problemă uşoară, a modificat enunţul problemei şi acum nu mai ştie să o rezolve. Problema sună în felul următor: ştiind că cele n elemente ale şirului pot avea valori din mulţimea {x, x+1, ... , y}, să se determine numărul şirurilor distincte ce admit un număr maxim de subşiruri strict descrescătoare de lungime maximă.

Cunoscând valorile n, x şi y cu semnificaţiile de mai sus, ajutaţi-l pe Maximilian să calculeze numărul de şiruri distincte modulo 1114111 ce conţin un număr maxim de subşiruri strict descrescătoare de lungime maximă.

Date de intrare

Fişierul de intrare maxmaxmax.in conţine pe prima linie cele 3 numere naturale n, x şi y separate prin spaţiu.

Date de ieşire

Fişierul de ieşire maxmaxmax.out va conţine pe prima linie un singur număr natural ce reprezintă numărul şirurilor distincte modulo 1114111.

Restricţii

  • 1 ≤ n, x, y ≤ 1 000 000 000

Exemplu

maxmaxmax.inmaxmaxmax.out
4 3 5
20

Explicaţie

Sunt 5 şiruri cu un număr maxim de 4 soluţii, ce admit subşir descrescător de lungime maximă 2:
(4 4 3 3) (4 5 3 3) (5 5 3 3) (5 5 3 4) (5 5 4 4)
Sunt alte 15 şiruri cu un număr maxim de 4 soluţii, ce admit subşir descrescător de lungime maximă 1:
(3 3 3 3) (3 3 3 4) (3 3 3 5) (3 3 4 4) (3 3 4 5) (3 3 5 5)
(3 4 4 4) (3 4 4 5) (3 4 5 5) (3 5 5 5) (4 4 4 4) (4 4 4 5)
(4 4 5 5) (4 5 5 5) (5 5 5 5)
În total 15 + 5 = 20 de soluţii.
Toate celelalte şiruri permit un număr mai mic de soluţii de lungime maximă.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content