Registration System

Registration System
Codeforces medium

تحتاج خدمة بريد إلكتروني جديدة إلى نظام تسجيل. يرسل المستخدمون \(n\) طلبًا، واحدًا بعد الآخر، ويحتوي كل طلب على اسم.

  • إذا لم يكن الاسم موجودًا في قاعدة البيانات، يضيفه النظام ويرد بـ OK.
  • إذا كان الاسم موجودًا في قاعدة البيانات، يكوّن النظام اسمًا جديدًا بإضافة أصغر عدد \(i \ge 1\) بحيث لا يكون name\(i\) موجودًا في قاعدة البيانات (name1، name2، …). ثم يضيف الاسم الجديد إلى قاعدة البيانات ويرد به.

القيود:

  • \(1 \le n \le 10^5\)
  • كل اسم غير فارغ، وطوله لا يزيد عن \(32\) حرفًا، ويتكوّن من حروف لاتينية صغيرة فقط.

الإدخال:

  • السطر الأول: عدد صحيح \(n\) — عدد الطلبات.
  • الأسطر الـ \(n\) التالية: اسم واحد في كل سطر.

المخرجات:

  • \(n\) سطرًا — رد النظام على كل طلب.

مثال:

الإدخال:

6
first
first
second
second
third
third

المخرجات:

OK
first1
OK
second1
OK
third1
الحل

نحتفظ بخريطة map<string, int> تخزّن لكل اسم عدد المرات التي طُلب فيها حتى الآن.

  • إذا كان عدد مرات الاسم \(0\)، فالاسم جديد، ونطبع OK.
  • إذا كان العدد \(c > 0\)، فالأسماء name، name1، …، name\((c-1)\) مستخدمة، لذلك نطبع name\(c\).

في الحالتين نزيد بعد ذلك عدد مرات الاسم بمقدار \(1\).

هذا صحيح لأن كل اسم مطلوب يتكوّن من حروف فقط. الاسم المولَّد مثل first1 يحتوي على رقم، فلا يمكن لأحد أن يطلبه، والطريقة الوحيدة لدخوله قاعدة البيانات هي عدّاد الاسم first.

إذا لم يكن الاسم موجودًا في الخريطة، فإن count[name] تنشئه بالقيمة \(0\). الدالة to_string تحوّل عددًا إلى string، والعملية + تصل نصّين.

كل طلب يُجري \(O(\log n)\) عملية على الخريطة، لذا يعمل الحل كله في زمن \(O(n \log n)\) (بإهمال طول الأسماء).

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    int n;
    cin >> n;

    // name -> how many times this name was requested before
    map<string, int> count;

    for (int i = 0; i < n; i++) {
        string name;
        cin >> name;

        if (count[name] == 0) {
            cout << "OK\n";
        } else {
            cout << name + to_string(count[name]) << "\n";
        }
        count[name]++;
    }
}