Fişierul intrare/ieşire:unuzero.in, unuzero.outSursăONI 2012 - clasa a 9-a
AutorGheorghe ManolacheAdăugată deSpiderManSimoiu Robert SpiderMan
Timp execuţie pe test0.2 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Unuzero

Se consideră un şir format din N + 2 cifre binare, care conţine cel puţin o cifră 1 şi cel puţin trei cifre 0; prima şi ultima cifră a şirului sunt 0.
Numim 1-secvenţă o succesiune formată numai din cifre 1, aflate pe poziţii consecutive în acest şir, delimitată de câte o cifră 0.
Corina construieşte un astfel de şir, în care numărul de cifre 1 ale fiecărei 1-secvenţe să fie cuprins între două numere naturale date, p şi q (p ≤ q).

Cerinţă

Scrieţi un program care să determine un număr natural K, egal cu restul împărţirii la 666013 a numărului de şiruri distincte, de tipul celui construit de Corina.

Date de intrare

Fişierul de intrare unuzero.in conţine pe prima linie numărul natural N, iar pe cea de a doua linie numerele naturale p şi q (p ≤ q), separate printr-un spaţiu.

Date de ieşire

Fişierul de ieşire unuzero.out va conţine pe prima linie numărul natural K cerut.

Restricţii

  • 1 ≤ p ≤ q < N < 1 000 000.
  • Pentru 20% din teste N ≤ 25, iar pentru alte 40% din teste 25 < N ≤ 1000.

Exemplu

unuzero.inunuzero.outExplicaţie
5
2 3
8
0000110
0001100
0001110
0011000
0011100
0110000
0110110
0111000
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content