| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 2048 MB | 0 | 0 | 0 | 0.000% |
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.