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

در بازی گل یا پوچ سه نفر با هم، هم‌تیمی می‌شوند. هر کدام دو دست دارند. دست چپ را با $L$ و دست راست را با $R$ نشان می‌دهیم. پس در مجموع شش دست در بازی هست. در یک دست گل و پنج دست دیگر پوچ است.

بازیکن‌ها را با اعداد ۱ تا ۳ شماره‌گذاری می‌کنیم. در ابتدا گل در دست $x$ بازیکن شماره‌ی $s$ است که مقدار $x$ برابر $L$ یا $R$ است. بازی شروع می‌شود و در حین بازی، بازیکنان $n$ حرکت انجام می‌دهند. حرکت‌ها یکی از حالت‌های زیر را دارد:

خالی بازی $k$🔗

در این حرکت بازیکن شمار‌ه‌ی $k$ محتوای دو دستش را جابه‌جا می‌کند. ($k = 1, 2, 3$)

جابه‌جایی $k$ و $k+1$🔗

در این حرکت بازیکن شماره‌ی $k$ محتوای دست $x$ خودش را با محتوای دست $y$ بازیکن $k+1$ جابه‌جا می‌کند. ($k = 1, 2$ و $x, y \in \{L, R\}$)

مشتی‌ علی گزارش این $n$ حرکت را به ترتیب به شما می‌دهد. شما باید شماره‌ی بازیکنی که گل در دست آن است و اسم دست آن بازیکن را نشان می‌دهد.

ورودی🔗

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

در سطر دوم ورودی، عدد $s$ و کاراکتر $x$ داده می‌شود. $s \in \{1, 2, 3\}, \quad x \in \{L, R\}$

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

حرکت نوع اول به صورت $1\ k$ است. که یعنی بازیکن $k$ام محتوای دو دستش را عوض می‌کند.

$k \in \{1, 2, 3\}$

حرکت نوع دوم به صورت $2\ k\ x\ y$ که یعنی بازیکن $k$ام محتوای دست $x$ را به دست $y$ بازیکن $k+1$ام می‌دهد.

$k \in \{1, 2\}, \quad x, y \in \{L, R\}$

خروجی🔗

در یک سطر، عدد $f$ و کاراکتر $y$ را چاپ کنید که شماره‌ی بازیکن و دستی که گل در آن است را نشان می‌دهد.

مثال‌ها🔗

ورودی نمونه ۱🔗

5
2 L
2 2 R L
2 1 L L
1 1
1 2
1 3

خروجی نمونه ۱🔗

1 R

ورودی نمونه ۲🔗

2
3 R
1 1
2 1 R R

خروجی نمونه ۲🔗

3 R

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

باقر و علی می‌خواهند باهم دارت بازی کنند. تصویر دارت به صورت شکل زیر است:

در بازی دارت، قوانین امتیازدهی به این صورت است:

تخته دارت به ۲۰ بخش مساوی تقسیم شده که هر بخش عددی بین ۱ تا ۲۰ را نشان می‌دهد.

در مرکز تخته دارت یک بخش کوچک به نام «بولس‌آی» (Bullseye) وجود دارد که از دو بخش تشکیل شده است. حلقه‌ی مرکزی کوچک‌تر، دایره‌ای با شعاع ۱ سانتی‌متر با ۵۰ امتیاز و حلقه‌ی مرکزی بزرگ‌تر، دایره‌ای با شعاع ۲ سانتی‌متر و ۲۵ امتیاز دارد.

اگر دارت به هر بخش از تخته بخورد، امتیاز همان بخش به بازیکن تعلق می‌گیرد (یک برابر). در اطراف هر عدد، دو حلقه وجود دارد: حلقه خارجی (حلقه سه‌برابر): اگر دارت به این حلقه برخورد کند، امتیاز آن بخش سه برابر می‌شود. اندازه‌ی این بخش ۱ سانتی‌متر است.

حلقه داخلی (حلقه دو‌برابر): اگر دارت به این حلقه برخورد کند، امتیاز آن بخش دو برابر می‌شود. اندازه‌ی این بخش ۱ سانتی‌متر است.

تخته بیرونی (خارج از بخش‌های امتیازی): دارت به تخته نخورده و امتیازی ندارد.

اندازه‌ی شعاع دایره‌ی خارجی (با حلقه سه‌برابر) ۱۰ سانتی‌متر و اندازه‌ی شعاع دایره‌ی داخلی (با حلقه دوبرابر) ۶ سانتی‌متر است.

آن‌ها دچار خطای ارزیابی هستند و اکنون پرتاب‌های خودشان را روی صفحه انجام داده‌اند و سپس می‌خواهند ترتیب اعداد ۱ تا ۲۰ را طوری تغییر دهند که امتیاز باقر خیلی بیشتر از امتیاز علی شود. آن‌ها نمی‌توانند امتیاز بولس‌آی را تغییر دهند.

حال می‌دانیم باقر $n$ پرتاب کرده و علی $m$ پرتاب می‌خواهیم بدانیم در بین تمام عددگذاری‌های مختلف در کدام حالت اختلاف امتیاز باقر از علی بیشتر است.

پرتاب‌های باقر و علی را به صورت $r$ و $\theta$ می‌دهیم یعنی در چه شعاع و زاویه‌ای دارت پرتاب شده است. مقدار $r$ برحسب سانتی‌متر و نشان دهنده‌ی فاصله از مرکز دارت است. همچنین $\theta$ زاویه‌ی نقطه‌ی پرتاب شده از محور $x$ها را نشان می‌دهد. برای مثال ناحیه‌ی شماره‌ی ۱۳ در شکل، زاویه‌ی ۹ تا ۲۷ درجه است.

تضمین می‌شود هیچ‌وقت پرتابی به ناحیه‌ی مرزی نمی‌خورد.

ورودی🔗

در سطر اول ورودی، دو عدد صحیح و مثبت $n$ و $m$ داده می‌شود.

$1 \leq n, m \leq 100$

در $n+m$ سطر بعدی در هر سطر دو عدد $r$ و $\theta$ داده می‌شود که $n$ پرتاب اول برای باقر و $m$ تای بعدی برای علی است.

تضمین می‌شود هیچ‌وقت پرتابی به ناحیه‌ی مرزی نمی‌خورد.

خروجی🔗

یک عدد صحیح برابر بیشترین اختلاف امتیازی که می‌تواند باقر از علی پیدا کند.

مثال‌ها🔗

ورودی نمونه ۱🔗

3 1
5.285 61.600
1.697 76.563
1.820 226.466
0.820 324.470

خروجی نمونه ۱🔗

40

در این حالت، باقر ۳ دارت و علی ۱ دارت پرتاب کرده‌اند. باقر پرتاب دوم و سومش به بولس‌آی ۲۵ امتیازی و پرتاب علی به بولس‌آی ۵۰ امتیازی برخورد کرده است. پرتاب اول باقر در حلقه‌ی داخلی (دو برابر) خورده است. بنابراین اگر امتیازها را طوری تغییر دهیم که ۲۰ امتیاز روی آن قطعه قرار بگیرد، اختلاف امتیاز باقر و علی بیشینه و برابر است با: $2 \times 20 + 25 + 25 - 50 = 40$

ورودی نمونه ۲🔗

2 2
1.790 119.791
9.260 178.282
0.850 166.297
9.538 31.585

خروجی نمونه ۲🔗

32

در این حالت، باقر و علی هر کدام ۲ دارت پرتاب کرده‌اند. پرتاب اول باقر به بولس‌ای ۲۵ امتیازی و پرتاب اول علی به بولس‌آی ۵۰ امتیازی برخورد کرده است. پرتاب‌های دوم باقر و علی هر دو به حلقه‌های بیرونی (سه برابر) خورده است ولی در دو ناحیه‌ی مختلف. اگر اعداد ۱ تا ۲۰ را طوری قرار دهیم که ناحیه‌ی باقر ۲۰ امتیاز و ناحیه‌ی علی ۱ امتیاز داشته باشد، اختلاف امتیاز باقر و علی بیشینه و برابر است با:

$25 + 3 \times 20 - 50 - 3 \times 1 = 32$

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

در یک شرکت $n$ برنامه‌نویس مشغول به کار هستند. هر کدام از این $n$ نفر در برخی از زمینه‌های Front-end، Back-end یا Product Mangement تخصص دارد.

تخصص‌های هر شخص را با یک رشته شامل حروف B، F و P به صورت مرتب‌شده الفبایی به ما داده شده است.

می‌خواهیم با داشتن این تخصص‌ها، حداکثر تعدادی تیم کامل را تشکیل دهیم. منظور از یک تیم کامل تیمی است که در آن برای هر کدام از این سه زمینه حداقل یک متخصص وجود داشته باشد. هر شخص باید دقیقاً یک سمت را داشته باشد و نمی‌تواند بخاطر تخصصش در دو زمینه نیاز تیم را در هر دو زمینه برطرف کند. توجه کنید باید در این تیم‌بندی هر شخص در حداکثر یک تیم آمده باشد.

حال از شما می‌خواهیم برنامه‌ای بنویسید که این بیشترین تعداد تیم را محاسبه کند.

ورودی🔗

در سطر اول ورودی، عدد صحیح و مثبت $t$ آمده که تعداد تست‌ها را نشان می‌دهد.

$1 \leq t \leq 10 \,000$

در سطر اول هر تست، عدد صحیح و مثبت $n$ داده می‌شود که تعداد برنامه‌نویس‌ها را نشان می‌دهد.

$1 \leq n \leq 100$

در $n$ سطر بعدی در هر سطر یک رشته داده می‌شود که رشته‌ی سطر $i$ام تخصص برنامه‌نویس $i$ام را نشان می‌دهد.

خروجی🔗

در تنها سطر خروجی، یک عدد صحیح برابر بیشترین تعداد تیم کامل را چاپ کنید.

مثال‌ها🔗

ورودی نمونه ۱🔗

3
5
B F P BFP BF
6
BF BP FP B BFP P
2
B BFP

خروجی نمونه ۱🔗

1
2
0

در نمونه‌ی اول تیم‌بندی می‌تواند به صورت زیر باشد: $\{B, F, P\}$

در نمونه‌ی دوم تیم‌بندی می‌تواند به صورت زیر باشد: $\{BF, BP, FP\} \quad \{B, BFP, P\}$

در نمونه‌ی سوم سه نفری وجود ندارد که بتوانند تیم تشکیل بدهند.

کد شما باید روی PostgreSQL قابل اجرا باشد.

جزئیات پایگاه‌داده🔗

دیتابیسی که در این سوال به آن می‌پردازیم، متشکل از اطلاعات تعدادی کاربر، شرکت و محصولات شرکت‌ها خواهد بود.

داده‌های اولیه را از این لینک دانلود کنید.

psql -U postgres -f /path/to/initial.sql

مطلوبات🔗

کوئری‌هایی بنویسید که خروجی‌های مطلوب زیر را به‌دست آورد (توجه کنید که هر کوئری نمره‌ای جداگانه دارد و اگر کوئری قسمتی را نتوانستید بنویسید، کوئری‌هایی که حل کردید را بفرستید و کوئری آن قسمت را خالی بگذارید):

1. آیدی، نام کوچک،‌ فامیلی و نام‌ کاربری تمام کاربرانی که نام کوچک (first_name) آن‌ها با حرف s و فامیلی (last_name) آن‌ها با حرف e تمام می‌شود. کوچک یا بزرگ بودن حروف مهم نیست و رکوردها باید براساس آیدی به صورت صعودی مرتب شوند.

2. نام شرکت و مجموعه‌ای از محصولاتی که متعلق به آن شرکت هستند. رکوردها براساس تعداد محصولات شرکت به صورت نزولی مرتب می‌شوند، در صورت برابر بودن تعداد محصولات دو شرکت، ترتیب صعودی آیدی آن‌ها اولویت دارد.

3. در این کوئری باید آدرس شرکتی که کاربر در آن حضور دارد و نام‌ کاربری او را برگردانید. در صورتی که کاربر در شرکتی حضور نداشت یا شرکتی که کاربر در آن حضور دارد، آدرسی نداشت، آدرسی را که در جدول کاربران برای کاربر مشخص‌ شده است، برگردانید. خروجی باید به ترتیب صعودی آیدی کاربران مرتب شده باشد. ترتیب قرار گیری آدرس در ستون user_address به صورت روبرو است: Country, City, Zip Code

4. در این کوئری از شما می‌خواهیم با جست‌و‌جو در جدول محصولات، یک جدول با فیلدها‌ی زیر‌ را برگردانید:

• نام، قیمت و کتگوری محصول
• نام و شهرِ شرکت محصول
• در انتها یک فیلد که در آن اگر قیمت محصول از میانگین قیمت کل محصولات بیش‌تر بود، expensive و اگر قیمت آن از میانگین کل محصولات کم‌تر بود not expensive قرار می‌گیرد.
• خروجی باید براساس آیدی محصول مرتب شده باشد.

فایل نهایی🔗

پس از پیاده‌سازی کوئری‌ها، آن را در فایل queries.sql، وارد کرده و سپس این فایل را آپلود کنید. کد شما باید به صورت زیر باشد:

-- Section1
   Your first query here
-- Section2
   Your second query here
-- Section3
   Your third query here
-- Section4
   Your fourth query here

برای این سوال، نسخه‌ی دات‌نت شما باید ۷ باشد.

شما به قبل سال 2000 برگشته‌اید، زمانی که فناوری دیتابیس‌ها به تازگی در حال ظهور است و مهندسان در تلاشند تا راه‌حل‌های نوآورانه‌ای برای جستجوی اطلاعات پیدا کنند. بسیاری از آن‌ها از ایده‌های جدید شگفت‌زده شده و دنیای فناوری اطلاعات در آستانه‌ی تغییرات شگرفی است.

شما که از آینده خبر دارید، تصمیم گرفته‌اید سیستم ابتدایی Full-Text Search را پیاده‌سازی کنید. با این اختراع، شما نه تنها دنیای جستجو را متحول می‌کنید بلکه تاریخ را نیز تحت تأثیر قرار خواهید داد و این اختراع را به نام خود ثبت خواهید کرد.

جزئیات پروژه🔗

پروژه‌ی اولیه را از این لینک دانلود کنید. ساختار فایل‌های پروژه به‌صورت زیر است:

└── SearchEngine
    ├── Document.cs
    ├── Index.cs
    ├── Program.cs
    ├── Query.cs
    └── SearchEngine.csproj

شما باید سه کلاس Document، Index و Query را مطابق با مواردی که در ادامه مطرح می‌شود، کامل کنید.

کلاس Document🔗

اولین کلاسی که باید تکمیل کنید کلاس Document است. این کلاس بدنه اصلی داکیومنت‌های شما را برای اندیس مشخص می‌کند و باید شامل ویژگی‌های(property) زیر باشد:

کلاس Query🔗

این کلاس شامل ویژگی‌های کوئری است که قصد دارید طبق این ویژگی‌ها داکیومنت‌هایی را از درون اندیس بازیابی کنید. این کلاس شامل ویژگی‌های زیر می‌شود:

کلاس Index🔗

این کلاس اصلی‌ترین کلاسی است که باید پیاده‌سازی کنید. این کلاس شامل داکیومنت‌ها و اندیس‌ها می‌شود. اندیس‌های این کلاس در واقعا اندیس‌های معکوس (Inverted index) به هر داکیومنت هستند.

Index.cs

namespace SearchEngine;

public class Index
{
    private List<Document> documents = new();
    private Dictionary<string, HashSet<long>> textIndex = new();
    private SortedDictionary<DateOnly, HashSet<long>> dateIndex = new();

    public Index() { }

    public Index(string filePath)
    {
        throw new NotImplementedException();
    }

    public void IndexDocument(Document document)
    {
        throw new NotImplementedException();
    }

    public void SaveIndexToFile(string filePath)
    {
        throw new NotImplementedException();
    }

    public List<Document> Search(Query query)
    {
        throw new NotImplementedException();
    }
}

همان‌طور که می‌بینید، دو اندیس textIndex و dateIndex وجود دارند که نحوه ساخت این اندیس‌ها در ادامه آورده شده است. مطابق این فایل، شما در این کلاس باید یک کانستراکتور و سه متد که در ادامه جزئیات آن‌ها ذکر می‌شود را پیاده‌سازی نمایید:

کانستراکتور Index: این کانستراکتور فایلی که در مسیر ورودی دریافت کرده را به صورت متن خوانده و اندیس‌های گفته شده را باید به درستی مقداردهی کند.

متد saveIndexToFile: این متد یک مسیر را دریافت و کل کلاس Index را با تمام مقادیرش به صورت متن در این مسیر ذخیره می‌کند.

متد indexDocument: این متد یک داکیومنت را دریافت می‌کند و اندیس‌های گفته شده را به صورت زیر ایجاد می‌کند:

• برای ساخت textIndex باید ویژگی text هر داکیومنت براساس کاراکتر‌های غیر کلمه‌ای (حرف، رقم یا _) شکسته شود و داکیومنت‌ها اندیس شوند.
• برای ساخت dateIndex هر داکیومنت براساس ویژگی date خودش اندیس می‌شود.

متد search: این متد وظیفه دارد تا داکیومنت‌هایی را براساس کوئری ورودی برگرداند. هر کدام از ویژگی‌های کلاس Query می‌تواند نال باشند ولی در صورتی که هر کدام از مقادیر نال نبود باید داکیومنت‌هایی براساس اولویت زیر برگردانده شوند:

1. متن
2. بازه زمانی (این به این معنی است که اگر در کوئری بازه زمانی وارد شده بود، این بازه اولویت بیشتری دارد)
3. زمان دقیق

مثال🔗

مثال‌هایی به صورت تست نمونه در اختیار شما قرار داده شده است که می‌توانید از آن‌ها کمک بگیرید. به عنوان مثال به مورد زیر دقت کنید:

Index index = new Index();

index.IndexDocument(new Document(1, "Quera online coding contests", DateTime.Now));
index.IndexDocument(new Document(2, "Quera for programmers", DateTime.Now.AddDays(-4)));
index.IndexDocument(new Document(3, "Practice coding skills", DateTime.Now.AddMonths(-11)));

Query query = new Query("Quera", null, null);
List<Document> result = index.Search(query);

خروجی مثال بالا باید داکیومنت‌ها با آی‌دی 1و 2 را برگرداند.

نکات🔗

• دو کلاس Document و Query باید شامل کانستراکتوری با همه ویژگی‌ها باشند.
• تضمین می‌شود داکیومنت با آی‌دی تکراری وارد نخواهد شد.
• دقت کنید که ساختار ابتدایی کلاس‌ها را تغییر ندهید.
• دقت کنید که کلاس‌های شما در صورت لزوم باید قابلیت سریالایز و دسریالایز شدن داشته باشند.

آن‌چه باید آپلود کنید🔗

پس از پیاده‌سازی موارد خواسته‌شده، فقط این سه کلاس را زیپ کرده و آپلود کنید.

[your-solution-file].zip
└── SearchEngine
    ├── Document.cs
    ├── Index.cs
    ├── Program.cs
    ├── Query.cs
    └── SearchEngine.csproj