Суддівські проблеми (Розбір)

У задачі необхідно підрахувати, які і скільки результатів суддівства були видані системами DOMjudge та $Kattis$. Якщо результат $s$ був отриманий системою DOMjudge~a разів, а системою Kattis~b разів, то кількість однакових результатів $s$ дорівнює $min(a,b)$.

Спочатку за допомогою відображення map<string, int> cnt підрахуємо кількість появ кожного результату $s$, виданого системою DOMjudge. Потім для кожного результату $s$, виданого системою $Kattis$, зменшуємо значення $cnt[s]$ на одиницю (якщо cnt[s] > 0). Кількість таких зменшень і буде рівна максимальній кількості результатів, які співпали в обох системах.

Приклад

Підрахуємо кількість результатів, виданих системами DOMjudge та $Kattis$ в наведеному прикладі.

Співпали $4$ результати.

Реалізація алгоритму

Оголосимо відображення $cnt$, в якому $cnt[s]$ буде зберігати кількість разів, коли результат $s$ був виданий системою DOMjudge.

map<string, int> cnt;

Читаємо кількість посилок $n$.

cin >> n;

Підраховуємо кількість результатів, виданих системою DOMjudge.

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

Обробляємо результати системи $Kattis$.

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

Якщо результат $s$ зустрічався у DOMjudge (тобто cnt[s] > 0), зменшуємо $cnt[s]$ на одиницю і збільшуємо лічильник $res$ — кількість результатів, які могли б бути однаковими в обох системах.

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

Виводимо відповідь.

cout << res << endl;

Java реалізація

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 реалізація

Читаємо кількість посилок $n$.

n = int(input())

Підраховуємо кількість результатів, виданих системою DOMjudge.

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

Обробляємо результати системи $Kattis$.

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

Виводимо відповідь.

print(res)