+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- فرض کنید سامانه‌ای داریم که شامل تعدادی **تبلیغ** و وب‌سایت است که این وب‌سایت‌ها را به عنوان **جایگاهی** برای این تبلیغات در نظر می‌گیریم. هرکدام از این جایگاه‌ها و تبلیغات دارای تعدادی **برچسب** مختلف مثل «*Football*»، «*Technology*» و… هستند. هدف اصلی این سامانه این است که این تبلیغات و جایگاه‌ها را مدیریت کرده و هر تبلیغ را به جایگاه مناسبی متصل کند. نحوه‌ی پرداخت هزینه‌ی تبلیغات به‌صورت «**هزینه به ازای هر کلیک**» (*Cost Per Click*) است که به اختصار *CPC* نامیده می‌شود. هر جایگاه و هر تبلیغ یک *CPC* مورد انتظار دارند که در ادامه سوال با آن آشنا می‌شوید. شما باید برنامه‌ای برای مدیریت این سامانه بنویسید که با گرفتن لیستی از درخواست‌ها، آن‌ها را به ترتیب اجرا کرده و خروجی مربوط به آن را چاپ کند. جزئیات مربوط به این درخواست‌ها به تفکیک نوع آن‌ها در ادامه آمده است. ### برچسب <details class="yellow"> <summary> **اضافه کردن برچسب** </summary> #### `ADD-TAG -name <name>` این درخواست اضافه کردن یک برچسب با نام `<name>` است. - `<name>`: رشته‌ای با حروف الفبای انگلیسی بزرگ و کوچک و اعداد و بدون فاصله با طول حداکثر ۳۰ کاراکتر. به هر برچسب بعد از اضافه شدن یک شماره به نام `id` نسبت داده می‌شود، این شماره‌ها از ‍۱ شروع می‌شوند و به ترتیب افزایش می‌یابند. - اگر نام برچسب تکراری باشد باید `Error: Tag already exists` را چاپ کنید. - اگر خطایی رخ نداد و شماره‌ی این برچسب `<id>` بود باید `Done: Tag id is <id>` را چاپ کنید. </details> <details class="yellow"> <summary> **لیست تمام برچسب‌ها** </summary> #### `TAG-LIST` این درخواست نمایش لیست همه‌ی برچسب‌ها است. خروجی باید ابتدا کلمه‌ی `TAGs:` و سپس نام برچسب‌ها به ترتیب شماره‌ی آن‌ها با فاصله از هم باشد. مثل: #### `TAGs: <tag1> <tag2> ...` </details> ### تبلیغ <details class="blue"> <summary> **اضافه شدن یک تبلیغ** </summary> #### `<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>` را چاپ کنید. </details> <details class="blue"> <summary> **لیست تمامی تبلیغات** </summary> #### `ADS-LIST` این درخواست نمایش لیست همه‌ی تبلیغات است. خروجی باید ابتدا کلمه‌ی `ADSs:` و سپس نام تبلیغات به ترتیب شماره‌ی آن‌ها با فاصله از هم باشد. مثل: #### `ADSs: <ads1> <ads2> ...` </details> ### جایگاه <details class="green"> <summary> **اضافه شدن یک جایگاه** </summary> #### `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>` را چاپ کنید. </details> <details class="green"> <summary> **لیست تمامی جایگاه‌ها** </summary> #### `PLACE-LIST` این درخواست نمایش لیست همه‌ی جایگاه‌ها است. خروجی باید ابتدا کلمه‌ی `PLACEs:` و سپس نام تبلیغات به ترتیب شماره‌ی آن‌ها با فاصله از هم باشد. مثل: #### `PLACEs: <place1> <place2> ...` </details> ## پیشنهادها <details class="red"> <summary> **پیشنهاد تبلیغ به جایگاه** </summary> ``` 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$ نیامده است. + اگر دو تبلیغ امتیاز یکسانی داشتند، آن‌ها را به ترتیب شماره‌هایشان مرتب کنید. </details> <details class="red"> <summary> **پیشنهاد جایگاه به تبلیغ** </summary> ``` 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$ نیامده است. + اگر دو جایگاه امتیاز یکسانی داشتند، آن‌ها را به ترتیب شماره مرتب کنید. </details> <details class="red"> <summary> **متصل کردن تبلیغ به جایگاه** </summary> ``` MATCH -ads-id <adds-id> -place-id <place-id> ``` - اگر تبلیغ وجود نداشت: `Error: Ads not found` - اگر جایگاه وجود نداشت: `Error: Place not found` - در غیر این صورت: `Done: <ads-id> matched to <place-id>` توجه کنید بعد از متصل کردن، باید این تبلیغ و جایگاه را از لیست تبلیغات و جایگاه‌های موجود حذف کنید. </details> # ورودی در سطر اول ورودی، عدد صحیح $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` خطا می‌دهد. + لیست جایگاه‌ها چاپ می‌شود. + درخواست پیشنهاد تبلیغ برای جایگاهی که وجود ندارد خطا می‌دهد. + پیشنهادات تبلیغ برای جایگاه ۲ و پیشنهادات جایگاه برای تبلیغ ۲ نمایش داده می‌شود. + تبلیغ ۱ به جایگاه ۱ متصل می‌شود. + تلاش برای اتصال تبلیغی که وجود ندارد خطا می‌دهد. + تلاش برای اتصال به جایگاهی که وجود ندارد خطا می‌دهد. + تبلیغ ۲ به جایگاه ۲ متصل می‌شود.