Hakim problemləri (Həll təhlili)

Problemdə DOMjudge və $Kattis$ sistemləri tərəfindən verilən nəticələrin sayını və hansı nəticələrin olduğunu saymaq tələb olunur. Əgər nəticə $s$ DOMjudge sistemi tərəfindən $a$ dəfə və $Kattis$ sistemi tərəfindən $b$ dəfə alınmışdırsa, bu halda uyğun gələn nəticələrin sayı $s$ üçün $min(a,b)$-yə bərabərdir.

Əvvəlcə map<string, int> cnt təsviri vasitəsilə DOMjudge sistemi tərəfindən verilən hər bir nəticə $s$-nin neçə dəfə meydana gəldiyini sayırıq. Daha sonra $Kattis$ sistemi tərəfindən verilən hər bir nəticə $s$ üçün $cnt[s]$-ni bir dəfə azaldırıq (əgər cnt[s] > 0). Bu azalmaların sayı hər iki sistemdə uyğun gələn maksimum nəticələrin sayına bərabər olacaq.

Nümunə

Təqdim edilmiş nümunədə DOMjudge və $Kattis$ sistemləri tərəfindən verilən nəticələrin sayını hesablayırıq.

Dörd nəticə uyğun gəlmişdir.

Algoritmin realizasiyası

$cnt$ təsvirini elan edək ki, burada $cnt[s]$, DOMjudge sistemi tərəfindən nəticə $s$-nin neçə dəfə verildiyini saxlayacaq.

map\string, int\ cnt;

Göndərmələrin sayını $n$ oxuyuruq.

cin > n;

DOMjudge sistemi tərəfindən verilən nəticələrin sayını hesablayırıq.

for (i = 0; i < n; i++)
{
  cin > s;
  cnt[s]++;
}

$Kattis$ sisteminin nəticələrinə baxırıq.

res = 0;
for (i = 0; i < n; i++)
{
  cin > s;

Əgər nəticə $s$ DOMjudge-də mövcud olarsa (yəni cnt[s] > 0), $cnt[s]$-ni azaltmaq və $res$ sayğacını artırmaq, hər iki sistemdə uyğun gələ biləcək nəticələrin sayını artırır.

  if (cnt[s] > 0)
  {
    cnt[s]--;
    res++;
  }
}

Cavabı çap edirik.

cout << res << endl;

Java realizasiyası

import java.util.*;

public class Main
{
  static Map<String, Integer> cnt = new HashMap<String, Integer>();
  
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    int n = con.nextInt();
  
    for(int i = 1; i <= n; i++)
    {
      String s = con.next();
      if (!cnt.containsKey(s))
        cnt.put(s, 1);
      else
        cnt.put(s, cnt.get(s) + 1);
    }

    int res = 0;
    for(int i = 1; i <= n; i++)
    {
      String s = con.next();
      if (cnt.containsKey(s) && cnt.get(s) > 0)
      {
        cnt.put(s, cnt.get(s) - 1);
        res++;
      }
    }
    
    System.out.print(res);
    con.close();  
  }
}

Python realizasiyası

Göndərmələrin sayını $n$ oxuyuruq.

n = int(input())

DOMjudge sistemi tərəfindən verilən nəticələrin sayını hesablayırıq.

cnt = {}
for _ in range(n):
  s = input()
  cnt[s] = cnt.get(s, 0) + 1

$Kattis$ sisteminin nəticələrinə baxırıq.

res = 0
for _ in range(n):
  s = input()
  if cnt.get(s, 0) > 0:
    cnt[s] -= 1
    res += 1

Cavabı çap edirik.

print(res)