Fişierul intrare/ieşire: | negustori.in, negustori.out | Sursă | Summer Challenge 2009, Runda 3 |
Autor | Din Folclor | Adăugată de | |
Timp execuţie pe test | 0.125 sec | Limită de memorie | 20480 kbytes |
Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Negustori
Sunteţi santinela unei bresle de negustori. Astăzi dimineaţă, n negustori (numerotaţi de la 1 la n) s-au aşezat în linie pentru a intra pe aleea comercială a oraşului. De-alungul aleii există n locaţii unde negustorii îşi pot parca căruţele pentru a-şi vinde ulterior bunurile. Începând cu negustorul numărul 1, fiecare negustor, unul după celălalt, intră pe alee cu căruţa proprie, se îndreaptă către locaţia repartizată iar dacă este liberă o ocupă. Altfel, negustorul îşi continuă drumul spre următorul loc liber pe care îl ocupă. Dacă toate următoarele locaţii sunt ocupate, acesta părăseşte oraşul fără a-şi vinde bunurile.
Negustorii nu îşi pot întoarce căruţele datorită îngustimii aleii. Sarcina dvs ca santinelă este să repartizaţi negustorii în locaţiile de pe alee. Negustorii locali sunt privilegiaţi în sensul că sunt repartizaţi în locaţia favorită, în timp ce negustorii străini vor trebui să accepte orice locaţie le desemnaţi.
Fiind date locaţiile preferate ale negustorilor locali, trebuie să decideţi dacă există o repartizare a negustorilor străini în locaţii de pe alee astfel încât fiecare negustor (deopotrivă local şi străin) să îşi găsească un loc liber. În caz că există o astfel de repartizare, trebuie să găsiţi numărul de repartizări valide modulo un număr întreg dat M.
Să considerăm un exemplu. Să presupunem că există patru negustori. Primii trei sunt negustori locali cu poziţia favorită 2, 1, respectiv 1. Ultimul negustor este străin. Fiecare negustor îşi găseşte un loc liber în fiecare din următoarele patru cazuri: (2, 1, 1, 1), (2, 1, 1, 2), (2, 1, 1, 3), (2, 1, 1, 4), unde, de exemplu, (2, 1, 1, 3) înseamnă că primul negustor are repartizată poziţia 2, ... , iar ultimul negustor poziţia 3. Acest exemplu arată că negustori locali diferiţi pot avea locaţii favorite identice, că unui negustor străin i se poate repartizata o locaţie dorită de un negustor local şi că locaţia finală a unui negustor local poate fi îndepărtată de locaţia favorită.
Date de intrare
Fişierul de intrare negustori.in conţine pe prima linie trei numere întregi n, m, M, separate prin spaţiu, unde m reprezintă numărul negustorilor locali din toţi cei n negustori. Pe următoarea linie se vor găsi m perechi de numere a1, b1, ..., am, bm, cu 1 ≤ ai, bi ≤ n şi toţi ai diferiţi, unde ai este poziţia celui de al i-lea negustor local în coadă iar bi locaţia sa preferată. Dacă nu există negustori locali, această linie va fi goală.
Date de ieşire
În fişierul de ieşire negustori.out se va scrie o singură linie, conţinând, fie NO dacă este imposibil ca fiecare negustor să primească o locaţie liberă, fie YES urmat de numărul total de repartizări modulo M (separate printr-un spaţiu).
Restricţii
- 1 ≤ n ≤ 300
- 0 ≤ m ≤ n
- 2 ≤ M ≤ 109
Exemplu
negustori.in | negustori.out |
---|---|
4 3 10 1 2 2 1 3 1 | YES 4 |
Explicaţie
Este exemplul din enunţ.