> یک مسابقه‌ی انتخابی **سخت** و **پرچالش** بعد...
**آمین چیپس‌خور** *(Aaaamin Chipskhor)،* از دیگر **آمین‌های** تاثیرگذار کوئرا که این روزها **پس از بازگشت زودهنگام از خدمت مقدس سربازی،** هنوز وظایف قبلی خود را در کوئرا دوباره تحویل نگرفته‌است، **میزور** *(Mizzor)* این سری از [**#المپیک‌فناوری پردیس**](https://quera.org/events/techolympics-0407) شده‌است. از آن‌جایی که تعداد تیم‌های شرکت‌کننده امسال چندین برابر سال گذشته شده، او باید برای همه‌ی آن‌ها **میز مشخصی** تعیین کند تا نظم مسابقه حفظ شود. با این حال، **آمین** علاقه‌ای به استفاده از روش‌های ساده و تصادفی **ندارد** و تصمیم می‌گیرد از **یک روش محاسباتی خاص** و **منحصربه‌فرد** برای محاسبه‌ی **شماره میز تیم‌ها** استفاده کند. این روش عجیب که در کوئرا شهره‌ی خاص و عام است، **سیستم میزور** *(Mizzor System)* نام دارد.
در این سیستم، **هر کدام از تیم‌های شرکت‌کننده** در سری جدید [**#المپیک‌فناوری پردیس**](https://quera.org/events/techolympics-0407)، از **تعدادی عضو** تشکیل شده و **نام** هر عضو در **محاسبه‌ی شماره‌ی میز** تأثیر دارد. آمین میزور برای این کار ابتدا **برای هر عضو گروه** یک **مقدار هش‌شده** محاسبه می‌کند که از ترکیب کد عددی کاراکترها و [**دنباله‌ی فیبوناچی** *(Fibonacci sequence)،*](https://en.wikipedia.org/wiki/Fibonacci_sequence) *که در مدت زمان سربازی مطالعات زیادی بر روی این سری اعداد داشته،* به دست می‌آید. سپس با جمع کردن این مقادیر و **درنظر گرفتن تعداد اعضا،** یک عدد نهایی برای هر تیم محاسبه می‌کند. در نهایت، **شماره‌ی میز تیم** برابر با **باقی‌مانده‌ی این عدد بر تعداد میزهای موجود در سالن** خواهد بود.
# **پروژه‌ی اولیه**
برای دانلود **پروژه‌ی اولیه** روی [این لینک](/problemset/assignments/4367/download_problem_initial_project/316831/) کلیک کنید.
# **جزئیات پروژه**
**تابعی** که شما باید در این سوال پیاده‌سازی کنید، **تابع** `assign_tables` می‌باشد و **دو آرگومان ورودی** می‌گیرد؛ یکی `groups` که **دیکشنری‌ای از نام تیم‌ها و اعضایشان** است و دیگری `tables_num` **تعداد کل میزهای موجود.** همچنین این تابع در خروجی به ترتیب دو مقدار بر خواهد گرداند: **دیکشنری‌ای شامل شماره‌ی میز اختصاص‌یافته به هر تیم** و لیستی از **برخوردهایی** *(Collisions)* که **در طی تخصیص میز** رخ داده‌اند. اگر برخوردی پیش بیاید، باید در خروجی مشخص شود **کدام تیم جدید** با **کدام تیم قبلی** روی یک میز افتاده‌است.
برای مثال، فرض کنید **دیکشنری تیم‌ها شامل سه گروه باشد** که بعضی از آن‌ها **هش یکسان** دارند. پس از اجرای تابع، خروجی شامل **شماره‌ی میز هر تیم** خواهد بود. اگر دو تیم مقدار **هش** *(Hash)* یکسانی داشته باشند **در یک میز مشترک قرار می‌گیرند.** سیستم در این حالت آن را به‌عنوان یک **برخورد** ثبت می‌کند و در خروجی نمایش می‌دهد تا **آمین** بتواند موقتاً با مشغول کردن اعضای این تیم‌ها با بسته‌های طعم‌های مختلف چیپس، **تصمیم بگیرد کدام‌یک باید به میز دیگری منتقل شود!**
- **تابع هش برای نام اعضای تیم‌ها:**
$$H(\text{name}) = \sum_{i=1}^{L} \big( \text{ord}(c_i) \times F(i) \big)$$
- **که در آن** $ord(c_i)$ [**کد عددی یونیکد** *(Unicode code point)*](https://quera.org/qbox/view/PwFzRF07yR/List_of_Unicode_characters.pdf) **کاراکتر** $i$**-ام نام عضو تیم،** مقدار $L$ **طول نام آن عضو** مشخص و $F(i)$ **عنصر** $i$**-ام سری فیبوناچی** $F$ **است که به شکل زیر تعریف می‌شود:**
$$F(0) = 0,\quad F(1) = 1,\quad F(n) = F(n-1) + F(n-2) \quad \forall n \ge 2$$
- **حال برای محاسبه شماره میز برای هر تیم به شکل زیر اقدام می‌کنیم که در آن مقدار** $k$ **برابر با تعداد اعضای تیم است و در این رابطه مجموع مقدار هش شده‌ی اسامی اعضای تیم را با هم جمع کرده، در تعداد اعضای تیم ضرب و در نهایت باقی‌مانده آن را بر** $N$ *(تعداد میزهای مسابقه)* **محاسبه می‌کنیم:**
$$T(G) = \Bigg( \big( \sum_{j=1}^{k} H(M_j) \big) \times k \Bigg) \bmod N$$
- **همچنین تعریف برخورد به شکل زیر خواهد بود:**
$$T(G_1) = T(G_2) \implies \text{Collision} = (\, G_2,\, T(G_2),\, G_1 \,)$$
# **ورودی**
**توجه داشته باشید که این مسئله ورودی استاندارد ندارد.**
به‌جای آن، تابع زیر را در **فایل** `solution.py` پیاده‌سازی کنید. این تابع ورودی‌ها را به‌صورت آرگومان توسط سیستم داوری، دریافت خواهد کرد.
```python solution.py python
def assign_tables(groups: dict[str, list[str]], tables_num: int) -> tuple[dict[str, int], list[tuple[str, int, str]]]:
return {}, []
```
- **پارامتر** `groups`**:** یک دیکشنری است که در آن **کلیدها به صورت نام تیم‌های شرکت‌کننده** و **مقدار** هر کلید**، فهرستی از اسامی اعضای آن تیم** است. هر عضو با رشته‌ای نمایش داده می‌شود و ترتیب اعضا در فهرست اهمیتی **ندارد.** تابع باید بر اساس ترکیب نام اعضا برای هر تیم، شماره‌ی میز اختصاصی را محاسبه کند.
- **پارامتر** `tables_num`**:** یک عدد صحیح است که **نشان‌دهنده‌ی تعداد کل میزهای موجود** در سالن برگزاری مسابقه است. تمامی شماره‌های میز باید در بازه‌ی `[0, tables_num - 1]` قرار داشته باشند. شماره‌ی میز هر تیم با استفاده از عملیات باقی‌مانده نسبت به این عدد محاسبه می‌شود.
**نکته:** اگر در فرایند تخصیص میز، دو تیم به یک شماره‌ی میز مشابه برسند، به این وضعیت **برخورد میز** *(Table Collision)* گفته می‌شود. در این صورت، تابع باید آن برخورد را در خروجی گزارش دهد تا مشخص شود کدام تیم‌ها روی یک میز افتاده‌اند. **برخوردها باید در قالب فهرستی از سه‌تایی‌ها شامل** `(نام تیم جدید، شماره‌ی میز، نام تیم قبلی)` **بازگردانده شوند.**
# **خروجی**
تابع به ترتیب باید یک **تاپل** *(Tuple)* با دو مقدار برگرداند. **مقدار اول،** یک دیکشنری است که کلیدهای آن نام تیم‌ها و مقادیرشان شماره‌ی میز اختصاص‌یافته است و **مقدار دوم،** فهرستی از برخوردهای احتمالی است که در فرایند تخصیص میز شناسایی شده‌اند.
# **مثال**
### **ورودی نمونه ۱**
```python solution.py python
groups = {
"Team1": ["Ali", "Sara"],
"Team2": ["Reza", "Nina"],
"Team3": ["Ali", "Sara"]
}
assign_tables(groups, 4)
```
### **خروجی نمونه ۱**
```python solution.py python
({'Team1': 0, 'Team2': 0, 'Team3': 0}, [('Team2', 0, 'Team1'), ('Team3', 0, 'Team2')])
```
<details class="blue">
<summary>
**توضیحات نحوه محاسبه مقادیر برای ورودی ۱**
</summary>
محاسبات را **مرحله به مرحله** برای داده‌ها به شکل زیر انجام می‌دهیم:
```python solution.py python
groups = {
"Team1": ["Ali", "Sara"],
"Team2": ["Reza", "Nina"],
"Team3": ["Ali", "Sara"]
}
```
ابتدا برای **نام** `Ali` سه حرف (`A`, `l`, `i`) داریم. **مقدار** `ord` برای آن‌ها به ترتیب `65`، `108` و `105` است. با توجه به دنبالهٔ فیبوناچی $(F(i$ داریم:
$$65 \times F(1) = 65 \times 1 = 65$$
$$108 \times F(2) = 108 \times 1 = 108$$
$$105 \times F(3) = 105 \times 2 = 210$$
جمع این سه مقدار برابر است با:
$$65 + 108 + 210 = 383$$
بنابراین:
$$H("Ali") = 383$$
برای **نام** `Sara` چهار حرف (`S`, `a`, `r`, `a`) داریم. **مقدار** `ord` برای آن‌ها به ترتیب `83`، `97`، `114` و `97` است. محاسبات به شکل زیر است:
$$83 \times F(1) = 83 \times 1 = 83$$
$$97 \times F(2) = 97 \times 1 = 97$$
$$114 \times F(3) = 114 \times 2 = 228$$
$$97 \times F(4) = 97 \times 3 = 291$$
جمع چهار حاصل‌ضرب:
$$83 + 97 + 228 + 291 = 699$$
در نتیجه:
$$H("Sara") = 699$$
برای **نام** `Reza` **چهار حرف** (`R`, `e`, `z`, `a`) داریم که **مقدار** `ord` آن‌ها به ترتیب `82`، `101`، `122` و `97` است. بنابراین:
$$82 \times F(1) = 82 \times 1 = 82$$
$$101 \times F(2) = 101 \times 1 = 101$$
$$122 \times F(3) = 122 \times 2 = 244$$
$$97 \times F(4) = 97 \times 3 = 291$$
جمع این چهار مقدار برابر است با:
$$82 + 101 + 244 + 291 = 718$$
پس:
$$H("Reza") = 718$$
برای **نام** `Nina` چهار حرف (`N`, `i`, `n`, `a`) داریم که **مقادیر** `ord` آن‌ها به ترتیب `78`، `105`، `110` و `97` است. محاسبات به شکل زیر است:
$$78 \times F(1) = 78 \times 1 = 78$$
$$105 \times F(2) = 105 \times 1 = 105$$
$$110 \times F(3) = 110 \times 2 = 220$$
$$97 \times F(4) = 97 \times 3 = 29$$
و جمع آن‌ها برابر است با:
$$78 + 105 + 220 + 291 = 694$$
بنابراین:
$$H("Nina") = 694$$
اکنون مقدار شماره میز هر تیم را با استفاده از $(T(G$ محاسبه می‌کنیم. طبق فرمول:
$$T(G) = \Big( \big(\sum_{j=1}^{k} H(M_j) \big) \times k \Big) \bmod N$$
برای `Team1` با **اعضای** `Ali` و `Sara` داریم:
$$T(Team1) = ((383 + 699) \times 2) \bmod N = (1082 \times 2) \bmod N = 2164 \bmod 4 = 0$$
برای `Team2` با **اعضای** `Reza` و `Nina` داریم:
$$T(Team2) = ((718 + 694) \times 2) \bmod N = (1412 \times 2) \bmod N = 2824 \bmod 4 = 0$$
برای `Team3` که اعضایش همانند `Team1` هستند:
$$T(Team3) = ((383 + 699) \times 2) \bmod N = 2164 \bmod 4 = 0$$
در نتیجه مقدار نهایی شماره میز هر گروه (پیش از محاسبهٔ باقی‌مانده بر $N$) برابر است با:
$$T(Team1) = 0, \quad T(Team2) = 0, \quad T(Team3) = 0$$
چون `(T(Team1) = T(Team3))`، این دو تیم به یک میز اختصاص داده می‌شوند و در نتیجه یک برخورد رخ می‌دهد:
$$Collision = ('Team2', 1, 'Team1')$$
$$Collision = ('Team3', 1, 'Team2')$$
</details>
+ در این ورودی خاص، هر سه تیم در نهایت **عدد صفر** را به‌عنوان شماره‌ی میز خود به دست می‌آورند. دلیل این موضوع این است که مجموع هش‌های تولیدشده برای اعضا، پس از ضرب در اندازه‌ی تیم و گرفتن باقی‌مانده بر ۴، برابر با **صفر** شده است. به همین خاطر، **تمام تیم‌ها روی یک میز** *(میز شماره ۰)* قرار گرفته‌اند و تابع در خروجی، علاوه‌بر دیکشنری شماره میزها، لیستی از **برخوردها** را نیز برمی‌گرداند. در این لیست مشخص است که **تیم دوم** با **تیم اول** برخورد کرده (`('Team2', 0, 'Team1')`) و **تیم سوم** هم با **تیم دوم** (`('Team3', 0, 'Team2')`) به یک میز اختصاص داده شده‌اند، که نشان‌دهنده‌ی تداخل در تخصیص میزها است.
### **ورودی نمونه ۲**
```python solution.py python
groups = {
"QuantumCoders": ["Amir", "Reza", "Sara"],
"AIWarriors": ["Nina", "Ali", "Mina"],
"DataTitans": ["Omid", "Reza", "Sina", "Tara"],
"BugHunters": ["Amir", "Reza"],
"CyberFalcons": ["Nina", "Ali"],
"PixelLords": ["Mina", "Sina", "Tara"]
}
assign_tables(groups, 6)
```
### **خروجی نمونه ۲**
```python solution.py python
({'QuantumCoders': 3, 'AIWarriors': 0, 'DataTitans': 4, 'BugHunters': 2, 'CyberFalcons': 0, 'PixelLords': 0}, [('CyberFalcons', 0, 'AIWarriors'), ('PixelLords', 0, 'CyberFalcons')])
```
<details class="blue">
<summary>
**توضیحات نحوه محاسبه مقادیر برای ورودی ۲**
</summary>
محاسبات را **مرحله به مرحله** برای داده‌ها به شکل زیر انجام می‌دهیم:
```python solution.py python
groups = {
"QuantumCoders": ["Amir", "Reza", "Sara"],
"AIWarriors": ["Nina", "Ali", "Mina"],
"DataTitans": ["Omid", "Reza", "Sina", "Tara"],
"BugHunters": ["Amir", "Reza"],
"CyberFalcons": ["Nina", "Ali"],
"PixelLords": ["Mina", "Sina", "Tara"]
}
```
ابتدا برای **نام** `Amir` چهار حرف (`A`, `m`, `i`, `r`) داریم. **مقدار** `ord` آن‌ها به ترتیب `65`, `109`, `105`, `114` است. محاسبات با دنباله فیبوناچی:
$$65 \times F(1) = 65 \times 1 = 65$$
$$109 \times F(2) = 109 \times 1 = 109$$
$$105 \times F(3) = 105 \times 2 = 210$$
$$114 \times F(4) = 114 \times 3 = 342$$
جمع مقادیر:
$$65 + 109 + 210 + 342 = 726$$
بنابراین:
$$H("Amir") = 726$$
برای **نام** `Reza` همانند قبل:
$$H("Reza") = 718$$
برای **نام** `Sara`:
$$H("Sara") = 699$$
حال برای تیم `QuantumCoders` با اعضای `Amir`, `Reza`, `Sara` داریم ((k=3)):
$$T(QuantumCoders) = ((726 + 718 + 699) \times 3) \bmod 6 = (2143 \times 3) \bmod 6 = 6429 \bmod 6 = 3$$
برای **تیم** `AIWarriors` با اعضای `Nina`, `Ali`, `Mina`:
$$H("Nina") = 694$$
$$H("Ali") = 383$$
$$H("Mina") = 693$$
$$T(AIWarriors) = ((694 + 383 + 693) \times 3) \bmod 6 = (1770 \times 3) \bmod 6 = 5310 \bmod 6 = 0$$
برای **تیم** `DataTitans` با اعضای `Omid`, `Reza`, `Sina`, `Tara`:
$$H("Omid") = 698$$
$$H("Reza") = 718$$
$$H("Sina") = 699$$
$$H("Tara") = 700$$
$$T(DataTitans) = ((698 + 718 + 699 + 700) \times 4) \bmod 6 = (2815 \times 4) \bmod 6 = 11260 \bmod 6 = 4$$
برای **تیم** `BugHunters` با اعضای `Amir`, `Reza`:
$$T(BugHunters) = ((726 + 718) \times 2) \bmod 6 = (1444 \times 2) \bmod 6 = 2888 \bmod 6 = 2$$
برای **تیم** `CyberFalcons` با اعضای `Nina`, `Ali`:
$$T(CyberFalcons) = ((694 + 383) \times 2) \bmod 6 = (1077 \times 2) \bmod 6 = 2154 \bmod 6 = 0$$
برای **تیم** `PixelLords` با اعضای `Mina`, `Sina`, `Tara`:
$$T(PixelLords) = ((693 + 699 + 700) \times 3) \bmod 6 = (2092 \times 3) \bmod 6 = 6276 \bmod 6 = 0$$
در نتیجه مقدار نهایی شماره میز هر گروه برابر است با:
$$T(QuantumCoders) = 3, \quad T(AIWarriors) = 0, \quad T(DataTitans) = 4, \quad T(BugHunters) = 2, \quad T(CyberFalcons) = 0, \quad T(PixelLords) = 0$$
چون شماره میز بعضی تیم‌ها یکسان است، **برخوردها** *(Collision)* به شکل زیر رخ می‌دهد:
$$Collision = ('CyberFalcons', 0, 'AIWarriors')$$
$$Collision = ('PixelLords', 0, 'CyberFalcons')$$
</details>
+ برای مثال، **تیم** `QuantumCoders` متشکل از سه عضو است و هش نام‌های آن‌ها طوری محاسبه شده که مجموع نهایی پس از اعمال عملیات مشخص‌شده در تابع، منجر به تخصیص میز شماره **۳** می‌شود. در همین حال، **تیم‌های** `AIWarriors`، `CyberFalcons` و `PixelLords` همگی به میز شماره **۰** اختصاص داده شده‌اند، چون مقدار محاسبه‌شده‌ی نهایی آن‌ها در تقسیم بر ۶، باقی‌مانده‌ی **صفر** داده‌است. از آن‌جا که چند تیم به یک میز مشترک تخصیص یافته‌اند، تابع علاوه‌بر دیکشنری اصلی از شماره‌ی میزها، لیستی از **برخوردها** را نیز بازمی‌گرداند. در این لیست مشخص است که **تیم** `CyberFalcons` با `AIWarriors` بر سر میز شماره ۰ برخورد داشته و پس از آن **تیم** `PixelLords` نیز با `CyberFalcons` در همان میز تداخل پیدا کرده‌است.
# **زیرمسئله‌ها**
سیستم داوری برای این سوال به **زیرمسئله‌های** زیر برای نمره‌دهی تقسیم‌بندی شده است که می‌توانید **امتیاز** مربوط به هر کدام را در جدول زیر مشاهده کنید. **زیرمسئله‌های** این جدول **ابتدا بر اساس اولویت و پیشنیازی پیاده‌سازی** و سپس **بر اساس امتیاز** آن‌ها مرتب‌سازی شده‌اند. **لذا پیشنهاد می‌شود در پیاده‌سازی از زیرمسئله‌ی ابتدایی آغاز کنید.**
| **زیرمسئله** | **امتیاز** |
| ----------------------------- | ------ |
| **پیاده‌سازی تابع** `assign_tables` | `100` |
# **آن‌چه باید آپلود کنید**
+ **توجه**: پس از پیاده‌سازی تابع خواسته‌شده، **فایل** `solution.py` را برای سیستم داوری ارسال کنید.
+ **توجه**: شما مجاز به افزودن فایل جدیدی در این ساختار **نیستید** و تنها باید تغییرات را در **فایل** `solution.py` اعمال کنید.
+ **توجه**: ایجاد هرگونه **تغییرات اضافی** در **امضا** *(Signature)* و **خروجی تابع** `assign_tables` که خارج از تعریف سؤال باشد، در سیستم داوری **مورد پذیرش قرار نگرفته** و نمره‌ای دریافت **نخواهد** کرد.
+ **توجه:** **فایل** `solution.py` **نباید** هیچ **عملکرد اضافه‌ای** برای گرفتن **ورودی استاندارد** *(stdin)* و دادن **خروجی استاندارد** *(stdout)* مانند `print` کردن پاسخ را شامل باشد، در غیر این صورت نمره‌ای دریافت **نخواهد** کرد. سیستم داوری خود مسئول **فراخوانی تابع** `assign_tables`، دادن آرگومان‌های ورودی به آن و بررسی خروجی است.