| Fişierul intrare/ieşire: | unuzero.in, unuzero.out | Sursă | ONI 2012 - clasa a 9-a |
| Autor | Gheorghe Manolache | Adăugată de |  Simoiu Robert •SpiderMan |
| Timp execuţie pe test | 0.1 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | unuzero.out | Explicaţie |
|---|---|---|
| 5 2 3 | 8 | 0000110 0001100 0001110 0011000 0011100 0110000 0110110 0111000 |
