Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | sandokan.in, sandokan.out | Sursă | preONI 2008, Runda finala |
| Autor | Adrian Airinei | Adăugată de |  Airinei Adrian •astronomy |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 5120 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Sandokan
Sandokan a ales un numar natural K si a gasit pe canapea un sir cu N numere naturale distincte. El se joaca cu acest sir de numere si aplica succesiv asupra sirului urmatoarea operatie: alege K elemente distincte din sir si le elimina pe toate mai putin elementul care are valoarea maxima (dintre cele alese). Daca la un moment dat sirul are un element sau strict mai putin decat K elemente se opreste si scrie acest sir pe o foaie magica, altfel aplica in continuare operatii pe sirul rezultat. Ne este greu sa aflam ce sir a scris Sandokan pe foaie magica, de aceea vrem doar sa aflam numarul total de posibiltati distincte de a scrie un sir pe foaia magica. Fiindca pot fi destul de multe posibilitati, vrem sa stim doar restul impartirii acestui numar la 2 000 003.
Date de intrare
Fisierul de intrare sandokan.in contine pe prima linie numerele N si K, avand semnificatia din enunt. Pe linia urmatoare urmeaza cele N numere naturale distincte.
Date de iesire
Pe prima linie a fisierului de iesire sandokan.out se afla numarul total de posibilitati distincte de a scrie un sir pe foaia magica modulo 2 000 003.
Restrictii
- 1 ≤ K ≤ N ≤ 5000
- Doua posibilitati de a scrie un sir sunt distincte daca exista macar un numar care apare intr-un sir si nu apare in celalalt
Exemplu
| sandokan.in | sandokan.out |
|---|---|
| 3 3 1 2 3 | 1 |
