محدودیت زمان: ۱ ثانیه
محدودیت حافظه: ۲۵۶ مگابایت

فرض کنید سامانه‌ای داریم که شامل تعدادی تبلیغ و وب‌سایت است که این وب‌سایت‌ها را به عنوان جایگاهی برای این تبلیغات در نظر می‌گیریم. هرکدام از این جایگاه‌ها و تبلیغات دارای تعدادی برچسب مختلف مثل «Football»، «Technology» و… هستند. هدف اصلی این سامانه این است که این تبلیغات و جایگاه‌ها را مدیریت کرده و هر تبلیغ را به جایگاه مناسبی متصل کند.

نحوه‌ی پرداخت هزینه‌ی تبلیغات به‌صورت «هزینه به ازای هر کلیک» (Cost Per Click) است که به اختصار CPC نامیده می‌شود. هر جایگاه و هر تبلیغ یک CPC مورد انتظار دارند که در ادامه سوال با آن آشنا می‌شوید.

شما باید برنامه‌ای برای مدیریت این سامانه بنویسید که با گرفتن لیستی از درخواست‌ها، آن‌ها را به ترتیب اجرا کرده و خروجی مربوط به آن را چاپ کند. جزئیات مربوط به این درخواست‌ها به تفکیک نوع آن‌ها در ادامه آمده است.

برچسب

اضافه کردن برچسب

`ADD-TAG -name <name>`

این درخواست اضافه کردن یک برچسب با نام <name> است.

<name>: رشته‌ای با حروف الفبای انگلیسی بزرگ و کوچک و اعداد و بدون فاصله با طول حداکثر ۳۰ کاراکتر.

به هر برچسب بعد از اضافه شدن یک شماره به نام id نسبت داده می‌شود، این شماره‌ها از ‍۱ شروع می‌شوند و به ترتیب افزایش می‌یابند.

اگر نام برچسب تکراری باشد باید Error: Tag already exists را چاپ کنید.
اگر خطایی رخ نداد و شماره‌ی این برچسب <id> بود باید Done: Tag id is <id> را چاپ کنید.

لیست تمام برچسب‌ها

`TAG-LIST`

این درخواست نمایش لیست همه‌ی برچسب‌ها است. خروجی باید ابتدا کلمه‌ی TAGs: و سپس نام برچسب‌ها به ترتیب شماره‌ی آن‌ها با فاصله از هم باشد. مثل:

`TAGs: <tag1> <tag2> ...`

تبلیغ

اضافه شدن یک تبلیغ

`<ADD-ADS -name <name> -cpc <cpc> -tags <tag1> <tag2> ...`

این درخواست اضافه کردن یک تبلیغ با نام <name>، با مقدار CPC مورد انتظار <cpc>، لیست برچسب‌های مربوط به این تبلیغ <tag1>، <tag2> و... است.

<name>: رشته‌ای با حروف الفبای انگلیسی بزرگ و کوچک و اعداد و بدون فاصله با طول حداکثر ۳۰ کاراکتر.
<cpc>: یک عدد صحیح نامنفی حداکثر ۱۰۰۰ است.
<tag1> <tag2> ...: لیستی از نام موضوعات.

به هر تبلیغ بعد از اضافه شدن یک شماره به نام id نسبت داده می‌شود، این شماره‌ها از ‍۱ شروع می‌شوند و به ترتیب افزایش می‌یابند.

اگر تبلیغ تکراری باشد: Error: Ad already exists
اگر موضوعی وجود نداشته باشد: Error: Tag not found
اگر خطایی رخ نداد و شماره‌ی این تبلیغ <id> بود باید Done: Ads id is <id> را چاپ کنید.

لیست تمامی تبلیغات

`ADS-LIST`

این درخواست نمایش لیست همه‌ی تبلیغات است. خروجی باید ابتدا کلمه‌ی ADSs: و سپس نام تبلیغات به ترتیب شماره‌ی آن‌ها با فاصله از هم باشد. مثل:

`ADSs: <ads1> <ads2> ...`

جایگاه

اضافه شدن یک جایگاه

`ADD-PLACE -name <name> -cpc <cpc> -tags <tag1> <tag2> ...`

این درخواست اضافه کردن یک جایگاه با نام <name>، با مقدار CPC مورد انتظار <cpc>، لیست برچسب‌های مربوط به این جایگاه <tag1>، <tag2> و... است.

<name>: رشته‌ای با حروف الفبای انگلیسی بزرگ و کوچک و اعداد و بدون فاصله با طول حداکثر ۳۰ کاراکتر.
<cpc>: یک عدد صحیح نامنفی حداکثر ۱۰۰۰ است.
<tag1> <tag2> ...: لیستی از نام موضوعات.

به هر جایگاه بعد از اضافه شدن یک شماره به نام id نسبت داده می‌شود، این شماره‌ها از ‍۱ شروع می‌شوند و به ترتیب افزایش می‌یابند.

اگر جایگاه تکراری باشد: Error: Place already exists
اگر موضوعی وجود نداشته باشد: Error: Tag not found
اگر خطایی رخ نداد و شماره‌ی این سایت <id> بود باید Done: Place id is <id> را چاپ کنید.

لیست تمامی جایگاه‌ها

`PLACE-LIST`

این درخواست نمایش لیست همه‌ی جایگاه‌ها است. خروجی باید ابتدا کلمه‌ی PLACEs: و سپس نام تبلیغات به ترتیب شماره‌ی آن‌ها با فاصله از هم باشد. مثل:

`PLACEs: <place1> <place2> ...`

پیشنهادها

پیشنهاد تبلیغ به جایگاه

SUGGEST-ADS -id <id>

این درخواست لیست تمام تبلیغات به ترتیب مناسب بودن برای جایگاه <id> است.

اگر جایگاه وجود نداشت: Error: Place not found
در غیر این صورت ابتدا عبارت SUGGEST-ADS: و سپس شماره‌ی همه‌ی تبلیغات را در یک سطر و با فاصله از هم به ترتیب مناسب بودن چاپ کنید.

مناسب بودن تبلیغ شماره‌ی $i$ برای جایگاه شماره‌ی $j$ از فرمول زیر محاسبه می‌شود و هر چه این عدد بیشتر باشد، تبلیغ مناسب‌تری است.

$\frac{1}{\max{1, cpc_i - cpc_j}} \times (\text{Number of Matched Tags} - \text{Number of Unmatched Tags})$

منظور از $cpc_i$ مقدار مورد انتظار CPC برای تبلیغ شماره‌ی $i$ است.
منظور از $cpc_j$ مقدار مورد انتظار CPC برای جایگاه شماره‌ی $j$ است.
منظور از Number of Matched Tags تعداد برچسب‌های مشترک بین تبلیغ شماره‌ی $i$ و جایگاه شماره‌ی $j$ است.
منظور از Number of Unmatched Tags تعداد برچسب‌هایی از تبلیغ شماره $i$ است که در لیست برچسب‌های جایگاه شماره $j$ نیامده است.
اگر دو تبلیغ امتیاز یکسانی داشتند، آن‌ها را به ترتیب شماره‌هایشان مرتب کنید.

پیشنهاد جایگاه به تبلیغ

SUGGEST-PLACE -id <id>

این درخواست لیست تمام جایگاه‌ها به ترتیب مناسب بودن برای تبلیغ <id> است.

اگر تبلیغ وجود نداشت: Error: Ads not found
در غیر این صورت ابتدا عبارت SUGGEST-PLACE: و سپس شماره‌ی همه‌ی جایگاه‌ها را در یک سطر و با فاصله از هم به ترتیب مناسب بودن چاپ کنید.

مناسب بودن جایگاه شماره‌ی $i$ برای تبلیغ شماره‌ی $j$ از فرمول زیر محاسبه می‌شود و هر چه این عدد بیشتر باشد، تبلیغ مناسب‌تری است.

$\frac{1}{\max{1, cpc_i - cpc_j}} \times (\text{Number of Matched Tags} - \text{Number of Unmatched Tags})$

منظور از $cpc_i$ مقدار مورد انتظار CPC برای جایگاه شماره‌ی $i$ است.
منظور از $cpc_j$ مقدار مورد انتظار CPC برای تبلیغ شماره‌ی $j$ است.
منظور از Number of Matched Tags تعداد برچسب‌های مشترک بین جایگاه شماره‌ی $i$ و تبلیغ شماره‌ی $j$ است.
منظور از Number of Unmatched Tags تعداد برچسب‌هایی از جایگاه شماره‌ی $i$ است که در لیست برچسب‌های تبلیغ $j$ نیامده است.
اگر دو جایگاه امتیاز یکسانی داشتند، آن‌ها را به ترتیب شماره مرتب کنید.

متصل کردن تبلیغ به جایگاه

MATCH -ads-id <adds-id> -place-id <place-id>

اگر تبلیغ وجود نداشت: Error: Ads not found
اگر جایگاه وجود نداشت: Error: Place not found
در غیر این صورت: Done: <ads-id> matched to <place-id>

توجه کنید بعد از متصل کردن، باید این تبلیغ و جایگاه را از لیست تبلیغات و جایگاه‌های موجود حذف کنید.

ورودی

در سطر اول ورودی، عدد صحیح $n$ که تعداد درخواست‌ها را نشان می‌دهد آمده است. $1 \leq n \leq 100$

در $n$ سطر بعدی، در هر سطر یکی از درخواست‌ها داده می‌شود.

خروجی

خروجی هر درخواست را به ترتیب چاپ کنید.

مثال

ورودی نمونه ۱

21
ADD-TAG -name Football
ADD-TAG -name Technology
ADD-TAG -name Sports
ADD-TAG -name Football
TAG-LIST
ADD-ADS -name Tv -cpc 500 -tags Football
ADD-ADS -name Ps -cpc 700 -tags Technology Football
ADD-ADS -name Tv -cpc 600 -tags Technology
ADS-LIST
ADD-PLACE -name Ineternet -cpc 600 -tags Football
ADD-PLACE -name Street -cpc 500 -tags Technology
ADD-PLACE -name School -cpc 800 -tags Sports
ADD-PLACE -name Ineternet -cpc 700 -tags Sports
PLACE-LIST
SUGGEST-ADS -id 3
SUGGEST-ADS -id 2
SUGGEST-PLACE -id 2
MATCH -ads-id 1 -place-id 1
MATCH -ads-id 3 -place-id 2
MATCH -ads-id 2 -place-id 4
MATCH -ads-id 2 -place-id 2

خروجی نمونه ۱

Done: Tag id is 1
Done: Tag id is 2
Done: Tag id is 3
Error: Tag already exists
TAGs: Football Technology Sports
Done: Ads id is 1
Done: Ads id is 2
Error: Ad already exists
ADSs: Tv Ps
Done: Place id is 1
Done: Place id is 2
Done: Place id is 3
Error: Place already exists
PLACEs: Ineternet Street School
SUGGEST-ADS: 1 2
SUGGEST-ADS: 2 1
SUGGEST-PLACE: 1 2 3
Done: 1 matched to 1
Error: Ads not found
Error: Place not found
Done: 2 matched to 2

چهار برچسب اضافه می‌شود و تلاش برای اضافه کردن برچسب تکراری Football خطا می‌دهد.
لیست برچسب‌ها چاپ می‌شود.
دو تبلیغ اضافه می‌شود و تلاش برای اضافه کردن تبلیغ تکراری Tv خطا می‌دهد.
لیست تبلیغات چاپ می‌شود.
سه جایگاه اضافه می‌شود و تلاش برای اضافه کردن جایگاه تکراری Ineternet خطا می‌دهد.
لیست جایگاه‌ها چاپ می‌شود.
درخواست پیشنهاد تبلیغ برای جایگاهی که وجود ندارد خطا می‌دهد.
پیشنهادات تبلیغ برای جایگاه ۲ و پیشنهادات جایگاه برای تبلیغ ۲ نمایش داده می‌شود.
تبلیغ ۱ به جایگاه ۱ متصل می‌شود.
تلاش برای اتصال تبلیغی که وجود ندارد خطا می‌دهد.
تلاش برای اتصال به جایگاهی که وجود ندارد خطا می‌دهد.
تبلیغ ۲ به جایگاه ۲ متصل می‌شود.

ارسال پاسخ برای این سؤال