Fişierul intrare/ieşire:intuitie.in, intuitie.outSursăONI 2009 - baraj
AutorFilip Cristian BuruianaAdăugată deandrei-alphaAndrei-Bogdan Antonescu andrei-alpha
Timp execuţie pe test1.3 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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 N50

Exemplu

intuitie.inintuitie.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content