| Fişierul intrare/ieşire: | intuitie.in, intuitie.out | Sursă | ONI 2009 - baraj |
| Autor | Filip Cristian Buruiana | Adăugată de |  Andrei-Bogdan Antonescu •andrei-alpha |
| Timp execuţie pe test | 0.65 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Intuitie
Înaintea barajului la Olimpiada Naţională de Informatică, G., încercând să intuiască subiectele, scrie pe o foaie de hârtie toate permutările cu N elemente. La un moment, observă că unele numere din permutare, situate între poziţiile 2 şi N-1, sunt strict mai mari decât elementele vecine (situate pe poziţii adiacente), în timp ce altele sunt strict mai mici. G. denumeşte elementele mai mari maxime locale, iar elementele mai mici minime locale. De exemplu, permutarea p = (4 1 2 8 5 6 7 3) are două minime locale, 1 şi 5, şi două maxime locale, 8 şi 7.
G. se gândeşte să scrie toate permutările cu N elemente care să aibă P maxime locale şi Q minime locale. Deoarece numărul permutărilor este foarte mare, G. abandonează problema. A doua zi, la olimpiadă, apare chiar problema la care se gândise G.
Cerinta
Să se determine câte permutări cu N elemente au P maxime locale şi Q minime locale.
Date de intrare
Prima şi singura linie a fişierului de intrare intuitie.in conţine trei numere naturale, N, P şi Q, cu semnificaţia din enunţ.
Date de ieşire
Pe prima linie a fişierului de ieşire intuitie.out se va afişa numărul de permutări cu N elemente care au P maxime locale şi Q minime locale, modulo 999017.
Restricţii
- 3 ≤ N ≤ 500
- 0 ≤ P, Q ≤ N-2
- P + Q ≤ N-2
- 50% din teste au N ≤ 50
Exemplu
| intuitie.in | intuitie.out |
|---|---|
| 4 1 0 | 6 |
Explicaţie
Permutările cerute sunt (1 2 4 3), (1 3 4 2), (1 4 3 2), (2 3 4 1), (2 4 3 1), (3 4 2 1). Maximul local apare îngroşat.
