+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- بعد از آنکه برگزارکنندگان رویداد در مرحله‌ی قبل با کمک شما برندگان را انتخاب کردند، تصمیم گرفتند اطلاعات مسابقات برگزار شده را به آرشیو خود اضافه کنند.اما هنگام انجام این کار متوجه شدند که **رتبه‌بندی یکی از حوزه‌های مسابقه گم شده است**. اطلاعات مربوط به سایر حوزه‌ها و همچنین **رتبه‌بندی نهایی شرکت‌کنندگان** در اختیار شما قرار گرفته است. وظیفه‌ی شما این است که **رتبه‌بندی گمشده را بازیابی کنید.** <details> <summary> **توضیح محاسبه رتبه بندی نهایی شرکت کنندگان** </summary> امتیاز هر شرکت‌کننده در یک حوزه طبق فرمول زیر محاسبه می‌شود: $$S \times \frac{P - R}{P - 1} = Score$$ که در آن: + S: امتیاز کل آن حوزه + P: تعداد شرکت‌کنندگان در آن حوزه + R: رتبه‌ی شرکت‌کننده در آن حوزه در صورتی که تنها یک شرکت‌کننده در حوزه وجود داشته باشد، او **تمام امتیاز آن حوزه (S)** را دریافت می‌کند. اگر شرکت‌کننده‌ای در بیش از یک حوزه شرکت کرده باشد، **امتیاز نهایی او برابر مجموع امتیازهایش در تمام حوزه‌ها** است.رتبه‌بندی نهایی نیز بر اساس **امتیاز کل** محاسبه می‌شود. </details> # ورودی در خط اول عدد صحیح $n$ (تعداد حوزه‌هایی که اطلاعات آنها موجود است) داده می‌شود. $$0 \le n \le 200$$ سپس برای هر حوزه دو خط داده خواهد شد: + خط اول شامل دو عدد صحیح $S$ (امتیاز حوزه) و $P$ (تعداد شرکت‌کنندگان حوزه) است. $$0 \le S \le 1000 , 0 \le P \le 100$$ + خط دوم شامل $P$ نام کاربری است که با `,` از هم جدا شده‌اند.این نام‌ها به ترتیب رتبه مرتب شده‌اند (نام اول رتبه ۱، نام دوم رتبه ۲، و …). پس از آن، اطلاعات مربوط به رتبه بندی گم شده داده خواهد شد: + خط اول شامل دو عدد صحیح $S$ (امتیاز حوزه) و $P$ (تعداد شرکت‌کنندگان حوزه) است. $$0 \le S \le 1000 , 0 \le P \le 8$$ + خط دوم شامل $P$ نام کاربری است که با `,` از هم جدا شده‌اند.توجه کنید که **این نام‌ها ترتیبی ندارند** (رتبه مشخص نیست). در نهایت، اطلاعات مربوط به رتبه بندی نهایی داده خواهد شد: + خط اول شامل یک عدد صحیح $P$ (تعداد کل شرکت‌کنندگان) است. $$0 \le P \le 100$$ + خط دوم شامل $P$ نام کاربری است که با `,` از هم جدا شده‌اند.این نام‌ها به ترتیب رتبه مرتب شده‌اند (نام اول رتبه ۱، نام دوم رتبه ۲، و …). # خروجی رتبه بندی حوزه گم شده را چاپ کنید. هر نام کاربری را در یک خط جداگانه چاپ کنید( به خروجی نمونه دقت کنید.) + در صورت وجود چند پاسخ معتبر (مثلاً رتبه بندی های متفاوت)، هر ترتیب درست قابل قبول است. # مثال ## ورودی نمونه ۱ ``` 1 200 3 ali,sara,reza 150 2 omid,sara 4 sara,ali,omid,reza ``` ## خروجی نمونه ۱ ``` sara omid ```

رتبه بندی گم شده

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- پارک پردیس برای برگزاری مسابقات المپیک فناوری تعداد زیادی استف استخدام کرده تا این مسابقات به بهترین نحو ممکن برگزار بشن، حالا نیاز به سامانه ای برای مدیریت سلف دارد و از شما میخواهد تا این سامانه را طراحی کنید. این سامانه از دو بخش تشکیل شده است. <details class="blue"> <summary> **بخش کاربران** </summary> <details class="green"> <summary> **ثبت نام** </summary> کارمندان جدید نیاز دارند در سامانه ثبت نام کنند. برای اینکار دستور زیر را وارد میکنند: ``` REGISTER username password ``` $username$ نام‌کاربری مورد نظر $password$ رمز عبور مورد نظر در صورتی که شخصی با این نام کاربری از پیش در سامانه وجود داشته باشد پیام زیر نمایش داده میشود: ``` USERNAME username ALREADY EXISTS ``` رمز عبور وارد شده توسط کاربر (password) باید حداقل هشت کاراکتر داشته باشد و شامل ارقام، حروف کوچک و بزرگ و کاراکترهای خاص ( +=_-)(*&^%$#@! ) باشد. در غیر این صورت پیام زیر نمایش داده میشود: ``` PASSWORD IS NOT STRONG ENOGH ``` در صورتی که کاربر از قبل داخل سامانه باشد، پیام زیر نمایش داده میشود: ``` YOU NEED TO LOGOUT FIRST ``` در صورت موفقیت آمیز بودن ثبت نام، پیام زیر نمایش داده میشود: ``` username REGISTERED SUCCESSFULLY ``` </details> <details class="green"> <summary> **ورود** </summary> بعد از ثبت نام، کاربران باید توسط بخش مدیریت تایید شوند تا بتوانند از سامانه استفاده کنند که دستورات مربوط به آن در بخش مدیریت آورده شده است. کارمندان برای ورود به سامانه دستور زیر را وارد میکنند: ``` LOGIN username password ``` در صورتی که شخصی با نام کاربری username از پیش در سامانه وجود نداشته باشد یا رمز عبور نادرست باشد، پیام زیر نمایش داده میشود: ``` WRONG PASSWORD OR USERNAME DOESN'T EXIST ``` در صورتی که حساب کاربر توسط مدیریت تایید نشده باشد یا غیرفعال شده باشد ، پیام زیر نمایش داده میشود: ``` ACCOUNT IS DEACTIVE ``` در صورتی که کاربر از قبل داخل سامانه باشد، پیام زیر نمایش داده میشود: ``` YOU NEED TO LOGOUT FIRST ``` در صورت موفقیت آمیز بودن ورود پیام زیر نمایش داده میشود : ``` username LOGGEDIN SUCCESSFULLY ``` </details> <details class="green"> <summary> **خروج** </summary> کارمندان برای خروج از سامانه دستور زیر را وارد میکنند: ``` LOGOUT ``` در صورتی که کاربر وارد سامانه نشده باشد، پیام زیر نمایش داده می‌شود: ``` YOU NEED TO LOGIN FIRST ``` در صورت موفقیت آمیز بودن خروج پیام زیر نمایش داده میشود : ``` LOGGEDOUT SUCCESSFULLY ``` </details> <details class="green"> <summary> **مشاهده برنامه غذایی** </summary> کارمندان برای مشاهده برنامه غذایی ارائه شده در بازه تاریخی مورد نظرشان دستور زیر را وارد میکنند: ``` MENU startdate enddate ``` مقادیر $startdate$ و $enddate$ با فرمت YYYY-MM-DD وارد میشود. در صورتی که کاربر وارد سامانه نشده باشد، پیام زیر نمایش داده می‌شود: ``` YOU NEED TO LOGIN FIRST ``` در صورتی که تاریخ شروع (startdate) قبل از (enddate) باشد، پیام زیر نمایش داده میشود : ``` STARTDATE MUST BE BEFORE ENDDATE ``` برنامه غذایی به فرم زیر به کاربر نمایش داده میشود: ``` date1: food1:remaining,food2:remaining,... date2: food1:remaining,food2:remaining,... ``` مقدار date باید با فرمت YYYY-MM-DD باشد. در صورتی که برای روزی منو غذایی تعریف نشده باشد، آن روز نمایش داده نمیشود. در صورتی که برای یک روز بیش از یک غذا تعریف شده باشد، نام غذاها رابه صورت مرتب شده (به ترتیب حروف الفبا) با $,$ از هم جدا میشود. در صورتی که باقی مانده یک غذا صفر شده باشد، آن غذا نمایش داده نمیشود و در نتیجه اگر تمام غذاهای یک روز رزرو شده باشند و باقی‌مانده نداشته باشند، آن روز نمایش داده نمیشود. برای درک بهتر به نمونه زیر توجه کنید. ورودی ``` MENU 2024-10-19 2024-10-23 ``` خروجی ``` 2024-10-19: GhormeSabzi:10 2024-10-21: AdasPolo:20 2024-10-23: Fesenjoon:5,Abgoosht:15 ``` در مثال فوق برای روز ۱۹ ام ۱۰ قورمه‌سبزی باقی مانده و برای روز های ۲۰ ام و ۲۲ ام غذایی تعریف نشده و یا تمام غذاهای آنها رزرو شده اند،بنابراین در لیست آورده نشده اند. </details> <details class="green"> <summary> **رزرو** </summary> کارمندان برای رزرو غذا دستور زیر را وارد میکنند: ``` RESERVE date food ``` در صورتی که کاربر وارد سامانه نشده باشد، پیام زیر نمایش داده می‌شود: ``` YOU NEED TO LOGIN FIRST ``` در صورتی که غذا مورد نظر در آن روز وجود نداشته باشد و یا همه آن رزرو شده باشد، پیام زیر نمایش داده می‌شود: ``` SELECTED FOOD WAS NOT SERVED ``` کاربر برای هر روز تنها میتواند یک غذا رزرو کند، بنابر این اگر کاربر از قبل برای آن روز غذایی رزرو کرده باشد، نمی‌تواند غذای دیگری رزرو کند و پیام زیر نمایش داده می‌شود: ``` RESERVATION ALREADY EXISTS FOR THIS DATE ``` در صورت موفقیت آمیز بودن رزرو، از تعداد باقی مانده غذا کاسته میشود و پیام زیر نمایش داده میشود : ``` SUCCESSFULLY RESERVED ``` </details> </details> <details class="orange"> <summary> **بخش مدیریت** </summary> <details> <summary> **مدیریت کاربران** </summary> <details class="purple"> <summary> **فعال کردن کاربران** </summary> برای فعال کردن یک کاربر مدیر دستور زیر را وارد میکند: ``` ACTIVE username ``` در صورتی که نام کاربری (username) در سیستم وجود نداشته باشد، پیام زیر نمایش داده می‌شود: ``` USER NOT FOUND ``` در صورتی که کاربر از قبل فعال باشد، پیام زیر نمایش داده میشود: ``` USER WAS ALREADY ACTIVE ``` </details> <details class="purple"> <summary> **غیرفعال کردن کاربران** </summary> برای فعال کردن یک کاربر مدیر دستور زیر را وارد میکند: ``` INACTIVE username ``` در صورتی که نام کاربری (username) در سیستم وجود نداشته باشد، پیام زیر نمایش داده می‌شود: ``` USER NOT FOUND ``` در صورتی که کاربر از قبل غیرفعال باشد، پیام زیر نمایش داده میشود: ``` USER WAS ALREADY INACTIVE ``` </details> <details class="purple"> <summary> **مشاهده لیست کاربران** </summary> برای مشاده لیست کاربران مدیر دستور زیر را وارد میکند: ``` LIST ACTIVE/DEACTIVE/(empty) ``` در صورت وارد شدن $ACTIVE$ یا $DEACTIVE$ به ترتیب لیست کاربران فعال یا غیر فعال نمایش داده میشود و در صورت خالی بودن بخش دوم (منظور از empty آمدن دستور $LIST$ به تنهایی است)، لیست تمام کاربران نمایش داده میشود. لیست کاربران به فرمت زیر نمایش داده میشود: ``` user1 user2 user3 ``` لیست کاربران رابه صورت مرتب شده (به ترتیب حروف الفبا) و هر نام کاربری در یک خط جداگانه چاپ کنید. </details> </details> <details> <summary> **مدیریت غذاها** </summary> <details class="purple"> <summary> **افزودن غذا** </summary> برای افزودن غذا به برنامه غذایی مدیر دستور زیر را وارد میکند: ``` ADDFOOD food amount date ``` تعداد موردنظر (amount) باید بزرگتر از $۰$ باشد در غیر این صورت پیام زیر نمایش داده میشود : ``` AMOUNT SHOULD BE BIGGER THAN 0 ``` این دستور غذا مورد نظر (food) را با تعداد قابل رزرو مورد نظر (amount) به برنامه روز موردنظر (date) اضافه میکند. در صورتی که غذای وارد شده از قبل در آن روز وجود داشته باشد، تعداد قابل رزرو جدید به تعداد قبلی افزوده میشود. </details> <details class="purple"> <summary> **حذف غذا** </summary> برای حذف غذا از برنامه غذایی، مدیر دستور زیر را وارد میکند: ``` REMOVEFOOD food date ``` این دستور غذا مورد نظر (food) را از برنامه روز موردنظر (date) حذف میکند. در صورتی که غذای وارد شده در برنامه آن روز وجود نداشته باشد پیام زیر نمایش داده میشود : ``` FOOD NOT FOUND IN SELECTED DATE ``` در صورتی که شخصی غذای موردنظر را رزرو کرده باشد، مدیر دیگر نمیتواند آن غذا را از لیست حذف کند و پیام زیر نمایش داده میشود : ``` FOOD IS RESERVED AND CAN'T BE REMOVED ``` </details> <details class="purple"> <summary> **گزارش رزرو‌ها** </summary> برای گزارش‌گیری از وضعیت غذاهای رزرو شده در بازه زمانی مورد نظر (از تاریخ $startdate$ تا تاریخ $enddate$)، مدیر دستور زیر را وارد میکند: ``` REPORT startdate enddate ``` مقادیر $startdate$ و $enddate$ با فرمت YYYY-MM-DD وارد میشود. در صورتی که تاریخ شروع (startdate) قبل از (enddate) باشد، پیام زیر نمایش داده میشود : ``` STARTDATE MUST BE BEFORE ENDDATE ``` گزارش به صورت زیر ارائه میشود : ``` date1: food1:amount rserved, food2:amount reserved date2: food1:amount rserved, food2:amount reserved . . . ``` مقدار $date$ تاریخ و به فرمت YYYY-MM-DD مقدار $food$ نام غذا مقدار $amount$ تعداد اولیه تعریف شده غذا مقدار $reserved$ تعداد رزرو شده غذا تاریخ هایی که در آنها غذایی وجود ندارد در لیست نمایش داده نمیشوند. در صورتی که در یک روز بیش از یک غذا وجود داشته باشد نام غذا ها به صورت مرتب شده(به ترتیب حروف الفبا) و با $,$ از هم جدا میشوند. برای درک بهتر به نمونه زیر توجه کنید: ورودی ``` REPORT 2024-10-19 2024-10-23 ``` خروجی ``` 2024-10-19: GhormeSabzi:50 30 2024-10-20: AdasPolo:40 15, ZereshkPolo:20 10 2024-10-23: Fesenjoon:25 5 ``` در مثال فوق، در تاریخ ۱۹م از ۵۰ پرس قورمه‌سبزی، ۳۰ پرس رزرو شده است.در تاریخ ۲۰م دو غذا با مقادیر اولیه و تعداد رزرو متفاوت وجود دارد، و در تاریخ ۲۳م تنها فسنجون ارائه شده است. </details> </details> </details> مدیر برای ورود از دستور ورود که در بخش کاربران آورده شده با نام کاربری و کلمه عبور زیر استفاده میکند. ``` username : admin password : admin ``` در صورتی که کاربر ساده دستورات مربوط به بخش مدیر را وارد کند یا مدیر دستورات مربوط به کاربر(مشاهده برنامه غذایی و رزرو) را وارد کند، پیام زیر نمایش داده میشود: ``` ACCESS DENIED ``` # ورودی در خط اول عدد صحیح $n$ وارد میشود که بیانگر تعداد دستورات است. در $n$ خط بعدی دستورات به نحوی که در بالا توضیح داده شده است وارد میشود. # خروجی خروجی هر دستور در بخش توضیحات آن دستور آورده شده. # مثال ## ورودی نمونه ۱ ``` 10 REGISTER reza 1234Reza! LOGIN admin admin LIST DEACTIVE ACTIVE reza ADDFOOD GhormeSabzi 50 2024-10-27 LOGOUT LOGIN reza 1234Reza! MENU 2024-10-25 2024-10-28 RESERVE 2024-10-27 GhormeSabzi LOGOUT ``` ## خروجی نمونه ۱ ``` reza REGISTERED SUCCESSFULLY admin LOGGEDIN SUCCESSFULLY reza LOGGEDOUT SUCCESSFULLY reza LOGGEDIN SUCCESSFULLY 2024-10-27: GhormeSabzi:50 SUCCESSFULLY RESERVED LOGGEDOUT SUCCESSFULLY ```

مدیریت سلف

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- در شهر اعداد، تعداد n عدد به‌صورت گروهی زندگی می‌کنند. آنها که مرام بالایی دارند، به‌طور خودجوش برای انجام کارهای شهر داوطلب می‌شوند. حال، مشکلی رخ داده! فردا آنها مسابقه بزرگ المپیک فناوری را در پیش دارند و هرکدام می‌خواهند بهترین عملکرد را داشته باشند و حاضر به گردن گرفتن وظیفه خطیر شستن ظروف کل ملت نیستند. از طرفی، موفقیت شهر را موفقیت خود می‌دانند و از شما می‌خواهند کمک کنید تا بدانند بیشینه موفقیت شهر اعداد در المپیک فناوری چقدر است. به‌طور دقیق‌تر، میزان موفقیت تعدادی از اعداد، «یا-بیتی» (bitwise OR) آنها محسوب می‌شود و شما باید بیشینه این مقدار را میان تمام حالت‌های انتخاب یک نفر برای ظرف‌شستن و فرستادن دیگران به آزمون بیابید. # ورودی در سطر اول ورودی عدد $t$ تعداد شهرهای اعداد(سناریوهای مستقل) می‌آید. سپس در سطر‌های بعد اطلاعات $t$ سناریو به ترتیب می‌آید. در سزر اول هر سناریو عدد $n$ تعداد شهروندان می‌آید و سپس در سطر بعد $n$ عدد $a_1, a_2, \ldots, a_n$ می‌آید که اطلاعات شهروندان شهر را نشان می‌دهد. $$1 \le t \le 1000$$ $$1 \le n \le 10^4$$ $$0 \le a_i < 2^{64} \quad (1 \le i \le n)$$ جمع $n$ به ازای سناریوهای مختلف حداکثر $10^4$ است. # خروجی .برای هر سناریو، یک عدد نشانگر بیشینه میزان موفقیت ممکن شهر را در سطری جداگانه خروجی دهید. # مثال ## ورودی نمونه ۱ ``` 3 2 1 2 3 1 2 3 3 6 1 2 ``` ## خروجی نمونه ۱ ``` 2 3 7 ``` در مثال اول، اگر فرد نخست ظروف را بشوید و فرد دوم به مسابقه برود، میزان موفقیت برابر **۲** خواهد بود. در مثال دوم، اگر فرد دوم ظروف را بشوید و فرد اول و سوم به مسابقه بروند، میزان موفقیت برابر $1\ \text{or}\ 3 = 3$ خواهد بود. در مثال سوم، چنانچه فرد سوم ظروف را بشوید، میزان موفقیت بیشینه می‌شود و برابر $6\ \text{or}\ 1 = 7$ خواهد بود.

شهر اعداد: شستن ظروف

رضا، دانشجوی سال آخر کارشناسی است. او برای پایان‌نامه‌اش دوباره با ریاضی سروکار پیدا کرده و نیاز دارد تعدادی تابع را در هم ضرب کند. اما از آن‌جا که مدت زیادی از آخرین باری که ریاضی خوانده گذشته است، تنها عبارت زیر را از ضرب تابع‌ها به یاد می‌آورد: $$if f(x) = g(x) * h(x) then for x0 : f(x0) = g(x0)*h(x0)$$او تصمیم می‌گیرد برنامه‌ای بنویسد که با گرفتن مقادیر ورودی و تابع‌ها، مقدار خروجی را برای مقادیر داده‌شده محاسبه کند.رضا که به‌تازگی با **کانال‌ها (channels)** و **گوروتین‌ها (goroutines)** در زبان Go آشنا شده است، تصمیم دارد این برنامه را با استفاده از آن‌ها پیاده‌سازی کند، اما تنها توانسته امضا (signature) تابع‌ها را تعریف کند.پروژه‌ی او را از [این لینک](/contest/assignments/91475/download_problem_initial_project/310366/) دانلود کنید و بخش‌هایی را که با `//TODO` مشخص شده رو کامل کنید. **بخش هایی که باید پیاده سازی شوند** <details class="blue"> <summary> **Item** </summary> ```Go type Item struct{ //TODO } ``` از این ساختار (struct) برای ایجاد کانال‌ها و تبادل اطلاعات بین آن‌ها استفاده شده است.اطلاعات مورد نیاز خود را در آن قرار دهید. </details> <details class="blue"> <summary> **MakeBroadcast** </summary> ```Go func MakeBroadcast(n int) ([]chan Item, func(Item)) { // TODO } ``` **ورودی** عدد صحیح `n` که نشون می‌ده چند تا کانال نیاز داریم. **خروجی** یک آرایه از کانال‌ها به طول `n`. یه تابع که با گرفتن یه مقدار از نوع `Item`، اون رو توی همه‌ی کانال‌ها بفرسته. </details> <details class="blue"> <summary> **BroadcastArray** </summary> ```Go func BroadcastArray(arr []int, broadcast func(Item)) { //TODO } ``` **ورودی** یه آرایه از اعداد صحیح. تابع `broadcast` (خروجی تابع قبلی). **عملکرد** برای هر عدد داخل آرایه، تابع `broadcast` رو صدا بزن تا مقدار توی همه‌ی کانال‌ها پخش بشه. </details> <details class="blue"> <summary> **ApplyFunctions** </summary> ```Go func ApplyFunctions( inChannel []chan Item, funcs []func(int) int, outChannel []chan Item, ) []chan Item { // TODO } ``` **ورودی** یه آرایه از کانال‌های ورودی (`inChannel`) یک آرایه از تابع‌ها (`funcs`) یک آرایه از کانال‌های خروجی (`outChannel`) **توضیح** تعداد کانال‌ها و تابع‌ها با هم برابره. **عملکرد** برای هر تابع: + مقدار از کانال ورودی خونده بشه + تابع روی اون اعمال بشه + نتیجه توی کانال خروجی نوشته بشه </details> <details class="blue"> <summary> **CollectAndMultiply** </summary> ```Go func CollectAndMultiply(chans []chan int, n int) []int { // TODO } ``` **ورودی** یک آرایه از کانال‌ها (خروجی‌های مرحله‌ی قبل) یک عدد صحیح $n$(تعداد ورودی‌های اولیه) **خروجی** یک آرایه از اعداد **عملکرد** حاصل تابع اصلی (حاصل ضرب تابع های داده شده) به ازای مقادیر آرایه ورودی با همان ترتیب در آرایه خروجی نوشته بشه. </details> <details class="blue"> <summary> **JoinChannels** </summary> ```Go func JoinChannels(chans []chan Item) chan Item { //TODO } ``` **ورودی** یک آرایه از کانال‌ها **خروجی** یک کانال **عملکرد** مقادیر تمام کانال‌های موجود در آرایه ورودی را خوانده و در کانال خروجی میریزد و بعد از بسته شدن تمامی کانال‌های ورودی این کانال نیز باید بسته شود. </details> **نکات** + در تست کیس ها مواردی وجود دارد که به هر چنل چندین تابع مصرف کننده(از یک نوع) متصل است. + تنها اجازه ایجاد تغییر در فایل functionmuliplexer.go را دارید. + امضا(signature) تابع ها را تغییر ندهید. + در فایل main_test.go یک نمونه از تست کیس ها آورده شده. + برای این سوال امکان ارسال جواب هم به صورت تک فایل (تنها فایل fm.go) و هم به صورت .zip وجود دارد.

ضرب تابع‌ها

پس از موفقیت چشم‌گیر در پروژه‌ی `Dockerious`، تیم فنی پارک علم و فناوری پردیس متوجه نیاز به یک سیستم کش سریع و سبک برای سرویس‌های داخلی شده است. با الهام گرفتن از *Redis*، پروژه‌ی ساخت یک دیتابیس *in-memory* بومی با نام **`Redious`** به شما سپرده شده است. این دیتابیس باید بتواند داده‌ها را به صورت *Key-Value* در حافظه نگه دارد و از دیتاتایپ معمول پشتیبانی کند و یک سیاست حذف از کش *LRU (Least Recently Used)* برای مدیریت حافظه داشته باشد. شما در این سوال باید استارت پیاده‌‌سازی این دیتابیس را بزنید. ### جزئیات پروژه پروژه اولیه را از [این لینک](/contest/assignments/91475/download_problem_initial_project/310367/) دانلود کنید. ساختار پروژه به شکل زیر است: ```shell redious/ ├── datastore/ │ └── redious.go # TODO Implement └── main.go # Just to see the sample result and run on your local ``` در این پروژه، شما باید اینترفیس `DataStore` و توابع مربوطه را در فایل `datastore/redious.go` پیاده‌سازی کنید. ### آن‌چه باید پیاده‌سازی کنید شما باید *struct* های `cacheEntry` و `rediousStore` را تعریف کرده و تابع سازنده `NewDataStore` و تمام متدهای اینترفیس `DataStore` را در فایل `datastore/redious.go` پیاده‌سازی کنید. ```go datastore/redious.go package datastore // ZMember is used to pass score-member pairs to the ZAdd command. type ZMember struct { Score float64 Member string } // DataStore is the main interface for our in-memory database. type DataStore interface { Set(key, value string) Get(key string) (string, bool) LPush(key string, values ...string) int RPush(key string, values ...string) int LRange(key string, start, stop int) []string ZAdd(key string, members ...ZMember) int ZRange(key string, start, stop int) []string Incr(key string) (int, error) // Atomic operations } // cacheEntry holds the key and the value (actual data) type cacheEntry struct { // TODO: Define necessary fields based on the table below. } // rediousStore is the internal implementation of our DataStore. type rediousStore struct { // TODO: Define necessary fields based on the table below. } // NewDataStore creates a new DataStore with a given capacity. // The capacity determines the maximum number of keys the store can hold. // If capacity is 0, the cache has unlimited size. func NewDataStore(capacity int) DataStore { // TODO: Initialize and return an instance of rediousStore return nil // Placeholder } // --- String Commands --- func (ds *rediousStore) Set(key, value string) { // TODO: Implement } func (ds *rediousStore) Get(key string) (string, bool) { // TODO: Implement return "", false // Placeholder } func (ds *rediousStore) Incr(key string) (int, error) { // TODO: Implement return 0, nil // Placeholder } // --- List Commands --- func (ds *rediousStore) LPush(key string, values ...string) int { // TODO: Implement return 0 // Placeholder } func (ds *rediousStore) RPush(key string, values ...string) int { // TODO: Implement return 0 // Placeholder } func (ds *rediousStore) LRange(key string, start, stop int) []string { // TODO: Implement return nil // Placeholder } // --- Sorted Set Commands --- func (ds *rediousStore) ZAdd(key string, members ...ZMember) int { // TODO: Implement return 0 // Placeholder } func (ds *rediousStore) ZRange(key string, start, stop int) []string { // TODO: Implement return nil // Placeholder } ``` \**نکته مهم:** دیتابیس شما باید **Thread-Safe** باشد. یعنی چندین گوروتین باید بتوانند به صورت همزمان با آن کار کنند بدون اینکه *race condition* رخ دهد. #### ساختار `cacheEntry` این استراکت برای نگه‌داری اطلاعات مربوط به هر آیتم در کش استفاده می‌شود و شامل کلید و مقدار آن آیتم است. مقدار می‌تواند از هر نوع داده‌ای باشد (رشته، لیست، مجموعه و ...). | فیلد | کاربرد | |-------|----------| | `key` | نگه‌داری کلید هر آیتم در کش | | `value` | نگه‌داری مقدار آیتم (قابل پشتیبانی از انواع مختلف داده‌ها) | #### ساختار `rediousStore` این استراکت پیاده‌سازی اصلی اینترفیس `DataStore` است و وضعیت کلی دیتابیس در حافظه را مدیریت می‌کند. | فیلد | کاربرد | |-------|----------| | `capacity` | تعیین حداکثر تعداد آیتم‌های قابل نگه‌داری در کش | | `items` | نگه‌داری کلید و عنصر لیست برای دسترسی سریع | | `ll` | نگه‌داری ترتیب استفاده آیتم‌ها برای پیاده‌سازی الگوریتم *LRU* | ### نیازمندی‌ها - **ظرفیت و LRU (Least Recently Used):** - تابع سازنده `NewDataStore(capacity int)` یک ظرفیت دریافت می‌کند که حداکثر تعداد کلیدهای قابل ذخیره را مشخص می‌کند. - اگر `capacity` برابر با `0` باشد، دیتابیس ظرفیت نامحدود دارد و هیچ کلیدی حذف نمی‌شود. - اگر `capacity` بزرگ‌تر از `0` باشد: - هر عملیات خواندن (`Get`, `LRange`, `ZRange`) یا نوشتن (`Set`, `LPush`, `RPush`, `ZAdd`, `Incr`) روی یک کلید، آن را به عنوان **بیشترین استفاده‌ی اخیر (MRU)** علامت‌گذاری می‌کند. - زمانی که یک کلید جدید اضافه می‌شود و تعداد کلیدها به ظرفیت رسیده است، کلید **کمترین استفاده‌ی اخیر (LRU)** باید حذف شود. - به‌روزرسانی مقدار یک کلید موجود نباید منجر به حذف کلید دیگری شود، اما همان کلید باید به‌عنوان *MRU* به‌روزرسانی شود. - **مدیریت انواع داده (Type Safety):** - هر کلید تنها می‌تواند یکی از سه نوع داده را در خود نگه دارد: **String**, **List**, یا **Sorted Set (ZSet)**. - دستور **`Set`** می‌تواند نوع داده‌ی یک کلید را **تغییر دهد** (مثلاً از List به String). - سایر دستورات (مثل `LPush`, `RPush`, `ZAdd`, `Incr`) **نباید نوع موجود کلید را تغییر دهند**: - اگر نوع کلید با دستور ناسازگار باشد، عملیات باید **بدون تغییر داده** و **بدون ایجاد کلید جدید** خاتمه یابد. - مقدار بازگشتی در این حالت باید نشان‌دهنده‌ی شکست باشد: - `0` برای `LPush`, `RPush`, `ZAdd` - `false` یا مقدار تهی (`""`, `nil`, `[]`) برای `Get`, `LRange`, `ZRange` - خطا (`error`) برای `Incr` --- <details class="blue"><summary>دستورات `String`</summary> \**نیازمندی‌ها:** - **`Set(key, value string)`** - مقدار رشته‌ای `value` را برای کلید `key` تنظیم می‌کند. - اگر کلید از قبل وجود داشته باشد (از هر نوعی)، مقدار و نوع آن **کاملاً جایگزین** می‌شود. - **`Get(key string) (string, bool)`** - مقدار رشته‌ای ذخیره‌شده برای `key` را برمی‌گرداند. - اگر کلید وجود نداشته باشد یا از نوع رشته‌ای نباشد، باید `""` و `false` برگرداند. - **`Incr(key string) (int, error)`** - مقدار رشته‌ای ذخیره‌شده در `key` را به عدد صحیح تبدیل کرده و یک واحد به آن اضافه می‌کند. - اگر کلید وجود نداشته باشد، باید با مقدار `"1"` ایجاد شود و مقدار `1` و `nil` برگرداند. - اگر کلید وجود داشته باشد ولی از نوع رشته‌ای نباشد، باید خطا با پیام `value at key is not a string` برگرداند. - اگر کلید وجود داشته باشد ولی مقدار رشته‌ای آن قابل تبدیل به عدد صحیح نباشد (مثلاً `"abc"` یا `""`)، باید خطا با پیام `value at key is not an integer` برگرداند. - در صورت موفقیت، باید مقدار جدید (به‌روزشده) و `nil` برگردانده شود. - این عملیات باید **اتمیک (atomic)** باشد. </details> <details class="blue"><summary>دستورات `List`</summary> \**نیازمندی‌ها:** - **`LPush(key string, values ...string) int`** - یک یا چند مقدار را به ابتدای لیست اضافه می‌کند. - ترتیب اضافه شدن باید مطابق رفتار *Redis* باشد: آخرین آرگومان ورودی (`values`)، اولین عضو جدید لیست می‌شود. (برای مثال `LPush key a b c` لیست را به `[c, b, a, <old_items>]` تبدیل می‌کند). - اگر کلید وجود نداشته باشد، لیست جدید ایجاد می‌شود. - اگر نوع کلید متفاوت باشد، عملیات انجام نمی‌شود و `0` برمی‌گردد. - در صورت موفقیت، طول جدید لیست بازگردانده می‌شود. - **`RPush(key string, values ...string) int`** - مشابه `LPush` است ولی مقادیر را به انتهای لیست اضافه می‌کند. - سایر رفتارها مشابه `LPush` است. - **`LRange(key string, start, stop int) []string`** - اعضای لیست را در بازه‌ی `[start, stop]` بازمی‌گرداند. - از ایندکس‌های منفی پشتیبانی می‌کند. - اگر کلید وجود نداشته باشد یا نوع آن `List` نباشد، باید `[]string{}` برگرداند. - **نکته مهم:** اسلایس بازگشتی باید یک **کپی** از داده‌های داخلی باشد، نه یک ارجاع مستقیم به آن. </details> <details class="blue"><summary>دستورات `Sorted Set` (ZSET)</summary> \**نیازمندی‌ها:** - **`ZAdd(key string, members ...ZMember) int`** - یک یا چند عضو دارای امتیاز (`Score`) را به مجموعه‌ی مرتب‌شده اضافه می‌کند. - اگر کلید وجود نداشته باشد، مجموعه‌ی جدید ایجاد می‌شود. - اگر کلید نوع دیگری داشته باشد، عملیات انجام نمی‌شود و `0` برمی‌گردد. - اگر عضوی از قبل وجود داشته باشد، امتیاز آن باید به‌روزرسانی شود. - مجموعه باید همواره بر اساس امتیاز (و در صورت تساوی، نام عضو به ترتیب الفبایی) مرتب بماند. - مقدار بازگشتی باید تعداد **اعضای جدیدی** باشد که به مجموعه اضافه شده‌اند. - اگر یک `Member` چند بار در همان فراخوانی `ZAdd` تکرار شود، تنها **آخرین Score** آن معتبر است. - **`ZRange(key string, start, stop int) []string`** - اعضای مجموعه‌ی مرتب‌شده را بر اساس رتبه در بازه‌ی `[start, stop]` بازمی‌گرداند. - از ایندکس‌های منفی پشتیبانی می‌کند. - اگر کلید وجود نداشته باشد یا نوع آن *Sorted Set* نباشد، باید `[]string{}` برگرداند. </details> --- ### نکات - تمرکز اصلی این سؤال بر روی **مدیریت صحیح ساختار داده‌های داخلی**، **همزمانی (Concurrency)** و **منطق LRU** است. ### چه چیزی را آپلود کنید پس از پیاده‌سازی کامل، صرفا تک فایل `datastore/redious.go` را آپلود کنید.