| Fişierul intrare/ieşire: | tenis.in, tenis.out | Sursă | ad-hoc |
| Autor | Ciprian Oprisa | Adăugată de |  Ciprian Oprisa •cypry |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 16384 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Tenis
N elevi participă la o tabără de tenis, unde fiecare pereche de elevi joacă exact un meci pe durata taberei. În total se joacă N*(N-1)/2 meciuri, fiecare terminându-se cu victoria unuia dintre participanţi. La finalul taberei, fiecare jucător primeşte o diplomă de jucător profesionist (înainte de primirea diplomei este considerat amator), în cadrul ceremoniei de premiere.
După ce s-au decernat K diplome, vom avea K jucători profesionişti şi N-K amatori. Vom nota cu PK numărul total de meciuri pierdute de profesionişti în faţa amatorilor, la momentul K.
Organizatorii doresc să decerneze diplomele într-o anumită ordine, astfel încât valoarea maximă a lui PK, 0 < K < N să fie cât mai mică. Determinaţi această valoare minimă.
Date de intrare
Fişierul de intrare tenis.in conţine pe prima linie numărul de teste T. Fiecare test va fi format dintr-o linie ce conţine patru întregi N, A, B şi M. N reprezintă numărul elevilor, iar A, B şi M ne ajută să generăm şirul xi după următoarea regulă: x0 = 1, iar xi+1 = (A * xi + B) mod M (operatorul mod semnifică restul împărţirii).
Se ştie că meciurile s-au desfăşurat în ordinea (1, 2); (1, 3); ... (1, N); (2, 3); ... (2, N); ... (N-1, N). Numerotarea meciurilor începe de la 1. În meciul cu numărul i ( i ≥ 1 ) câştigă primul jucător (cel cu identificatorul mai mic) dacă xi este impar, respectiv al doilea jucător daca xi este par.
Date de ieşire
Fişierul de ieşire tenis.out conţine T linii, câte una pentru fiecare test din fişierul de intrare. Pentru fiecare test se va scrie în fişier valoarea minimă (a numărului maxim de meciuri pierdute de profesionişti în faţa amatorilor) determinată.
Restricţii
- 2 ≤ N ≤ 3000
- 2 ≤ A, B, M ≤ 100000
- 1 ≤ T ≤ 30
Exemplu
| tenis.in | tenis.out |
|---|---|
| 2 2 7 4 9 5 9 8 15 | 0 3 |
Explicaţie
În primul test avem doar 2 jucători, deci un singur meci. x1 = (7 * 1 + 4) mod 9 = 2, care este par, deci al doilea jucător câştigă. Dacă ordinea de decernare a diplomelor este 2, 1, la nici un moment de timp nu vom avea profesionişti învinşi de amatori, deci rezultatul este 0.
