Podudarajuće Permutacije

View as PDF

Submit solution


Points: 1
Time limit: 0.5s
Memory limit: 64M

Author:
Problem type

Kao u svim neinventivnim zadacima iz programiranja Darko je za rodjendan i Novu godinu dobio dva niza A i B dužine N (standardno sjajni pokloni). Sada, iz nekog razloga ga interesuje ako bi permutovao elemente tih nizova (što znači da u svakom nizu održi iste elemenate, samo im promeni raspored), na koliko mesta najviše se ova dva niza mogu preklapati (za koliko različitih i može da važi A_i=B_i posle permutacije).

Opis ulaza

  • U prvom redu se nalazi broj N ( 1 \leq N \leq 10^5) koji označava dimezije nizova
  • U drugom redu se nalazi niz A_i (1\leq A_i \leq 10^5)
  • U trećem redu se nalazi niz B_i (1\leq B_i \leq 10^5)

Opis izlaza

U prvom redu ispisati najveći mogući broj preklapanja izmedju ovih permutovanih nizova.

Primer ulaza

10
1 2 1 3 4 2 1 2 3 2
2 1 3 1 7 2 3 1 2 2

Primer izlaza

9

Objašnjenje primera

Ako Darko niz A permutuje tako da dobije [1, 2, 3, 2, 3, 4, 1, 2, 1, 2], a niz B tako da dobije [1, 2, 3, 2, 3, 7, 1, 2, 1, 2] ova dva niza se preklapaju na 9 mesta. Kako brojeve 4 i 7 nikako ne mogu biti jednaki nečemu iz drugog niza, vidimo da je 9 ujedno i najbolje rešenje.


Comments

There are no comments at the moment.