| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 2048 MB | 57 | 5 | 5 | 8.772% |
Particija skupa $\{1, 2, \dots , N\}$ (za neki zadani prirodni broj $N$) je bilo koja kolekcija nepraznih skupova takvih da se svaki broj od $1$ do $N$ pojavljuje u točno jednom od tih skupova. Na primjer, jednu particiju skupa $\{1, 2, 3, 4, 5\}$ čine skupovi $\{1, 3\}$, $\{2, 4\}$ i $\{5\}$. Jedan način na koji možemo zadati particiju je koristeći niz brojeva $x_1, x_2, \dots , x_N$ ($1 ≤ x_i ≤ N$) tako da proglasimo da se $i$ i $j$ nalaze u istom skupu particije ako i samo ako vrijedi da je $x_i = x_j$. Particiju iz prethodnog primjera mogli smo zadati nizom $1, 2, 1, 2, 3$, ali također i nizom poput $5, 1, 5, 1, 4$.
Patricija je djevojka koja u svom vlasništvu ima dvije particije skupa $\{1, 2, \dots , N\}$. Prva od tih particija zadana je nizom $a_1, a_2, \dots , a_N$, a druga nizom $b_1, b_2, \dots , b_N$. Patriciju zanima odgovor na sljedeće pitanje: koji je najmanji broj skupova koji tvore particiju skupa $\{1, 2, \dots , N\}$, ako na raspolaganju ima skupove navedenih dviju particija.
U ovisnosti o zadanom broju $k ∈ \{0, 1, 2\}$ potrebno je napraviti sljedeće.
Napomenimo da kada je $k = 1$ ili $k = 2$, nova vrijednost promijenjenog broja mora biti između $1$ i $N$.
Pomozite Patriciji te napravite program koji rješava $T$ ovakvih test primjera.
U prvom su retku brojevi $T$ i $k$, redom broj test primjera te parametar koji određuje vrstu zadatka.
Slijede opisi $T$ test primjera.
Svaki test primjer započinje prirodnim brojem $N$, veličinom particije.
U sljedeća dva retka nalaze se nizovi $a_1, \dots , a_N$ te $b_1, \dots , b_N$ koji određuju particije.
Za svaki od $T$ test primjera u zasebni redak ispišite odgovor na traženo pitanje.
U svim podzadacima vrijedi $1 ≤ T ≤ 200\, 000$, $0 ≤ k ≤ 2$, te $1 ≤ a_i , b_i ≤ N$ za sve $i = 1, 2, \dots , N$. Vrijedi da je suma vrijednosti $N$ po svim test primjerima najviše $200\, 000$.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 7 | $k = 0$, $N ≤ 8$, suma vrijednosti $2^N$ po svim test primjerima je $≤ 10^5$. |
| 2 | 23 | $k = 0$ |
| 3 | 15 | $k = 1$, $N ≤ 1000$, suma vrijednosti $N^2$ po svim test primjerima je $≤ 10^6$. |
| 4 | 16 | $k = 1$ |
| 5 | 19 | $k = 2$, $N ≤ 1000$, suma vrijednosti $N^2$ po svim test primjerima je $≤ 10^6$. |
| 6 | 20 | $k = 2$ |
2 0 4 1 1 2 3 1 2 3 3 7 1 1 1 1 2 3 4 1 2 3 4 4 4 4
2 4
3 1 4 1 1 2 3 1 2 3 3 4 1 1 1 1 1 2 3 3 7 1 1 1 1 2 3 4 1 2 3 4 4 4 4
2 1 2
3 2 4 1 1 2 3 1 2 3 3 4 1 1 1 3 1 2 3 3 7 1 1 1 2 3 4 5 1 2 3 4 4 4 4
3 3 4
Pojašnjenje prvog probnog primjera:
Za prvi test primjer: Prvi niz određuje particiju na skupove $\{1, 2\}$, $\{3\}$ i $\{4\}$, a drugi na skupove $\{1\}$, $\{2\}$ i $\{3, 4\}$. Koristeći te skupove možemo napraviti particiju na dva skupa $\{1, 2\}$ i $\{3, 4\}$.
Za drugi test primjer: Prvi niz određuje particiju na skupove $\{1, 2, 3, 4\}$, $\{5\}$, $\{6\}$ i $\{7\}$, a drugi na skupove $\{1\}$, $\{2\}$, $\{3\}$ i $\{4, 5, 6, 7\}$. Bilo koja od tih particija ujedno je i optimalna.