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
Eşti în anul 2121 şi vrei să configurezi o reţea de Neuralink. Ai la dispoziţie N servere, ale căror IP-uri sunt reprezentate de permutări de lungime M (ale numerelor 0, 1 ... M-1). Vrei ca reţeaua ta să fie cât de mare, dar în acelaşi timp, te temi de potenţiale probleme de securitate: dacă un hacker află unul dintre IP-uri, îi va fi uşor să găsească un IP similar. Prin urmare, dintre cele N servere pe care le ai la dispoziţie, vrei să alegi cât de multe servere pentru reţeaua ta astfel încât să nu existe două servere cu IP-uri similare. Două IP-uri sunt similare, dacă unul dintre ele poate fi obţinut din celălalt print exact o operaţie swap (o interschimbare a oricăror două elemente). De exemplu, IP-urile (0, 1, 2) şi (1, 0, 2) sunt similare, dar (0, 1, 2) şi (1, 2, 0) nu.
Protocol de interacţiune
Concurentul trebuie să implementeze o funcţie:
(C) int solve(int N, int M, int** p);(C++) int solve(int N, int M, std::vector< std::vector<int> > p);Parametrii N şi M au semnificaţia din enunţ. p reprezintă o matrice cu N linii şi M coloane, linia i reprezentând cel de-al i-lea IP (o permutare de lungime M). Funcţia 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 permutări din cele N sunt similare cu oricare alta dintre cele N
- N ≤ 1000
Subtask 3 (36 de puncte)
- N ≤ 300
Subtask 4 (14 puncte)
- N ≤ 1000
Subtask 5 (9 puncte)
- Fără restricţii 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) şi (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).
