Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | pswap.in, pswap.out | Sursă | OSEPI Baraj Seniori 2 |
| Autor | Bogdan Pop | Adăugată de |  Matteo Verzotti •Matteoalexandru |
| Timp execuţie pe test | 2.5 sec | Limită de memorie | 524288 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Pswap
Esti in anul 2121 si vrei să configurezi o retea de Neuralink. Ai la dispozitie N servere, ale căror IP-uri sunt reprezentate de permutări de lungime M (ale numerelor 0, 1 ... M − 1). Vrei ca reteaua ta să fie cât de mare, dar ı̂n acelasi timp, te temi de potentiale probleme de securitate: dacă un hacker află unul dintre IP-uri, ı̂i va fi usor să găsească un IP similar. Prin urmare, dintre cele N servere pe care le ai la dispozitie, vrei să alegi cât de multe servere pentru reteaua ta astfel ı̂ncât să nu existe două servere cu IP-uri similare. Două IP-uri sunt similare, dacă unul dintre ele poate fi obtinut din celălalt print exact o operatie swap (o interschimbare a oricăror două elemente). De exemplu, IP-urile (0, 1, 2) si (1, 0, 2) sunt similare, dar (0, 1, 2) si (1, 2, 0) nu.
Protocol de interactiune
Concurentul trebuie să implementeze o functie:
(C) int solve(int N, int M, int** p);(C++) int solve(int N, int M, std::vector< std::vector<int> > p);Parametrii N si M au semnificatia din enunt. p reprezintă o matrice cu N linii si M coloane, linia i reprezentând cel de-al i-lea IP (o permutare de lungime M ). Functia va ı̂ntoarce numărul maxim de IP-uri nesimilare. Concurentul trebuie să nu implementeze funcţia main.
Din cauza limitărilor impuse de Infoarena şi pentru a reproduce condiţiile din concurs, recomandăm să foloseşti template-urile de aici.
Restricţii
- 1 ≤ N ≤ 2500
- 1 ≤ M ≤ 5000
- Oricare ar fi 0 ≤ i < n, p[i] este o permutare a numerelor de la 0 la M - 1
- Oricare ar fi 0 ≤ i, j < n, p[i] si p[j] sunt distincte
Subtask 1 (11 puncte)
- N, M ≤ 20
Subtask 2 (30 de puncte)
- Cel mult 20 de permutari din cele N sunt similare cu oricare alta din cele N
- N ≤ 1000
Subtask 3 (36 de puncte)
- N ≤ 300
Subtask 4 (14 puncte)
- N ≤ 1000
Subtask 5 (9 puncte)
- Fara restrictii suplimentare.
Exemplu
| pswap.in | pswap.out |
|---|---|
| 3 3 0 1 2 2 1 0 1 0 2 | 2 |
| 5 5 0 1 2 3 4 1 0 2 3 4 0 1 2 4 3 0 4 2 3 1 4 1 2 3 0 | 4 |
| 6 3 0 1 2 0 2 1 1 0 2 1 2 0 2 1 0 2 0 1 | 3 |
Explicaţie
Pentru primul exemplu, alegem serverele cu IP-urile (2, 1, 0) si (1, 0, 2). Nu putem alege serverul (0, 1, 2), deoarece IP-ul său este similar cu ale celorlalte 2. Pentru cel de-al doilea exemplu, putem alege toate IP-urile ı̂n afară de primul. Pentru cel de-al treilea exemplu, putem selecta IP-urile (0, 1, 2), (1, 2, 0), (2, 0, 1).
