• محدودیت زمان: ۰٫۵ ثانیه
• محدودیت حافظه: ۵۰ مگابایت
• محدودیت اعداد: تمامی اعداد ورودی و خروجی از $10^{18}$ کوچک‌ترند.
• داستان‌های این مسابقه با اقتباس از کتاب چارلی و کارخانه‌ی شکلات‌سازی نوشته‌ی رولد دال نگاشته شده‌است و شما در ۵ سؤال ابتدایی نقش اومپا-لومپا ها با مسئولیت‌های مختلف و در سؤال آخر نقش چارلی را بازی می‌کنید.

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

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

شما به عنوان اومپا-لومپای مسئول تحقیقات باید به او کمک کنید.

ورودی🔗

در سطر اول عدد $n \leq 10^5$ — تعداد دانه‌های کاکائو آمده‌است.

در سطر دوم $n$ عدد با فاصله آمده‌اند که $i$مین عدد نشان‌دهنده‌ی مقدار شیرینی دانه‌ی $i$م است. (هرچه شیرین‌تر، عدد بزرگ‌تر)

خروجی🔗

دو عدد خروجی داده شود که اولی فاصله‌ی مقدار شیرینی دو دانه‌ی کاکائو انتخابی و دومی، تعداد روش‌های انتخاب این دو دانه است.

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

2
1 2

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

1 1

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

4
-3 5 4 5

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

8 2

پ.ن. برای آشنایی بیشتر با محصولات این شرکت، ویدئوی فرآیند تولید گاب‌استاپر فک‌خردکن رو ببینید.

• محدودیت زمان: ۰٫۵ ثانیه
• محدودیت حافظه: ۵۰ مگابایت
• محدودیت اعداد: تمامی اعداد ورودی و خروجی از $10^{18}$ کوچک‌ترند.

اومپا-لومپا ها مانند تمامی موجودات زنده نیاز به استراحت یا خواب دارند. استراحت‌گاه آن‌ها به شکل یک جدول $n \times m$ است که در یکی از خانه‌های آن دست‌به‌آب قرار دارد. هر اومپا-لومپا دو خانه‌ی مجاور از این خوابگاه را برای استراحت نیاز دارد و اشغال می‌کند. هم‌چنین اومپا-لومپا ها در زمان خواب ممکن است غلت بزنند یا لگد بپرانند؛ لذا اگر اومپا-لومپای دیگری در آن خانه با او مشترک باشد، ممکن است بل‍ایی سرش بیاید! پس هر خانه‌ای حداکثر متعلق به یک اومپا-لومپا است.

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

ورودی🔗

در سطر اول اعداد $n \leq 10^9$ — طول و $m \leq 10^9$ — عرض استراحت‌گاه آمده‌است.

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

خروجی🔗

یک عدد چاپ کنید که حداکثر اومپا-لومپا هایی که می‌توانند در این خوابگاه استراحت کنند را نشان می‌دهد.

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

9 7
5 3

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

31

• محدودیت زمان: ۰٫۵ ثانیه
• محدودیت حافظه: ۵۰ مگابایت
• محدودیت اعداد: تمامی اعداد ورودی و خروجی از $10^{18}$ کوچک‌ترند.

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

وظیفه‌ی شما به عنوان اومپا-لومپای مسئول حفظ اسرار و پتنت‌های شرکت (وابسته به WIPO) این است که در بین افرادی که هم‌اکنون در کارخونه کار می‌کنند (و ویلی‌وانکا لیست‌ مرتب‌شده‌ی بر حسب شماره‌ی شناسایی آن‌ها را دارد)، دنبال خائنین بگردید و نام آن‌ها را به ویلی‌وانکا اطل‍اع دهید.

ورودی🔗

در خط اول عدد $n \leq 10^5$ — تعداد کارکنان حال حاضر کارخانه و عدد $k \leq 10^5$ — تعداد افراد مظنون به خیانت آمده‌است.

در $n$ خط بعدی شماره‌ی شناسایی و نام کارکنان فعلی کارخونه آمده‌است. نام هرکس از یک نام کوچک و یک نام خانوادگی تشکیل شده و هم‌چنین شماره‌های شناسایی لزومن از ۱ تا $n$ نیستند؛ چون ممکن است یک اومپا-لومپا پس از مدتی از کارخونه رفته‌باشد.

در خط آخر نیز $k$ عدد آمده‌است که شماره‌ی شناسایی افراد مظنون می‌باشد.

تضمین می‌شود نام کارکنان به ترتیب شماره‌ی شناسایی آن‌ها (که ترتیب استخدام‌شان است) داده‌شود.

خروجی🔗

به ازای هر مظنون اگر هنوز در شرکت مشغول بود، نام او را چاپ کند و اگر در لیست ویلی‌وانکا پیدا نشد، در خروجی عبارت This employee has gone رو چاپ کند.

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

8 5
1 Raees Ghabile
2 Hamsare Raees
4 Nayeb Raees
21 Raees Javan
338 Oompaaye Koochooloo
5326 Olampiadi Khafan
19998 Sep Zame
123456789 Amu Asadi
3 4 60 5 338

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

This employee has gone
Nayeb Raees
This employee has gone
This employee has gone
Oompaaye Koochooloo

• محدودیت زمان: ۰٫۵ ثانیه
• محدودیت حافظه: ۵۰ مگابایت
• محدودیت اعداد: تمامی اعداد ورودی و خروجی از $10^{18}$ کوچک‌ترند.

ویلی‌وانکا، برای این‌که مردم نتونن دزدکی وارد کارخونه بشن، تله‌هایی در جاها و به شکل‌های مختلف ایجاد کرده که یکی از اون‌ها این شکلیه:

توی دروازه‌ی ورودی به کارخونه یه شبکه‌ی $n \times m$ داره که اومپا-لومپا ها بتونن ازش رد شن، اما آدما نتونن. چه‌طوری؟ هرکسی برای رد شدن از این شبکه باید از نقطه‌ی (۰,۰) به نقطه‌ی $(m,n)$ برسه. برای رد شدن از این شبکه باید اولن فقط از روی خطوط بری؛ دومن کوتاه‌ترین مسیر رو بری و سومن وزن مسیرت یه مقدار خاص باشه. وزن مسیر هم تعداد خونه‌هاییه که زیر مسیرتن. مثلن در شبکه‌ی $8 \times 11$ بال‍ا، وزن مسیر ۴۰ است.

حال شما به عنوان اومپا-لومپای مسئول امنیت می‌خواهید بدانید که در کل چند مسیر وجود دارد و مجموع وزن تمامی مسیرها چند است؟

ورودی🔗

در تنها خط ورودی، دو عدد $m \leq 1000$ ‫—‬ تعداد نقاط افقی و $n \leq 1000$ ‫—‬ تعداد نقاط عمودی آمده‌است.

خروجی🔗

دو عدد چاپ شود که اولی تعداد تمامی مسیرها و دومی مجموع وزن تمامی مسیرها در شبکه‌ی داده‌شده است.

از آن‌جا که ممکن است اعداد بسیار بزرگ باشند، باقی‌مانده‌ی این دو عدد بر $10^9+7$ را چاپ کنید.

ورودی نمونه🔗

3 4

خروجی نمونه🔗

10 30

• محدودیت زمان: ۰٫۵ ثانیه
• محدودیت حافظه: ۵۰ مگابایت
• محدودیت اعداد: تمامی اعداد ورودی و خروجی از $10^{18}$ کوچک‌ترند.

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

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

اگر ما $n$ نوع کاکائو با شیرینی‌های مختلف داشته‌باشیم و آن‌ها را به ترتیب $\{a_1, a_2, ..., a_n\}$ که $a_i$ شیرینی دانه‌ی $i$م است، به ترکیب اضافه کنیم؛ شکلات رویال ساخته می‌شود.

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

شفاف‌سازی: $\sum_{(i<j) and (a_i > a_j)} a_i \times a_j$

حال در فرآیند آنالیز شکلات رویال ارسالی به مسابقات، شما اومپا-لومپای مسئول کیفیت هستید که باید امتیاز شکلات رویالی که به شما داده می‌شود را محاسبه کنید.

ورودی🔗

در سطر اول عدد $n \leq 10^5$ — تعداد دانه‌های کاکائو مختلف برای ساختن شکلات رویال آمده‌است.

در سطر دوم $n$ عدد آمده که $i$می آن‌ها، $|a_i| \leq 1000$، شیرینی $i$مین دانه‌ی کاکائو است که به ترکیب اضافه می‌شود. هرچه دانه شیرین‌تر باشد، عدد شیرینی‌اش بزرگ‌تر است.

توجه شود که شیرینی 0 یعنی شکلات نه تلخ است و نه شیرین. در نتیجه شیرینی دانه‌های تلخ، عددی منفی‌ست. در میان دانه‌های کاکائو، حداکثر یک دانه‌ی تلخ (با شیرینی منفی قرار دارد).

تضمین می‌شود که امتیاز حاصل از $10^{18}$ کوچک‌تر است.

خروجی🔗

یک عدد چاپ شود که امتیاز شکلات رویال مورد تحقیق است.

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

5
10 3 6 12 2

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

152

توضیح🔗

امتیاز این شکلات رویال برابر است با:

10×3 + 10×6 + 10×2 + 3×2 + 6×2 + 12×2 = 152

• محدودیت زمان: ۰٫۵ ثانیه
• محدودیت حافظه: ۵۰ مگابایت
• محدودیت اعداد: تمامی اعداد ورودی و خروجی از $10^{18}$ کوچک‌ترند.

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

جایگشت $n$ تایی $A$ به دنباله‌ای دارای $n$ عدد مانند $<a_1, a_2, ..., a_n>$ گفته می‌شود که هریک از اعداد ۱ تا $n$ دقیقا یک بار در آن ظاهر شده‌باشند. حال جایگشت $n$ تایی $X$ را در نظر بگیرید. جایگشت $Y$ را این‌گونه تعریف می‌کنیم:

• داریم: $y_1 = 1$
• به ازای هر $i$ بین ۲ تا $n$ اگر هیچ‌یک از اعداد $y_1$ تا $y_{i-1}$ در $Y$ برابر $x_{i-1}$ نبود، آن‌گاه $y_i = x_{i-1}$. در غیر این‌صورت $y_i$ را برابر کوچک‌ترین عددی از ۱ تا $n$ می‌گذاریم که برابر هیچ‌یک از اعداد $y_1$ تا $y_{i-1}$ در $Y$ نباشد. در این صورت جایگشت $Y$ را تصویری از جایگشت $X$ می‌نامیم و می‌گوییم: $f(X) = Y$.

حال $g(Y)$ را تعداد جواب‌های معادله‌ی $f(X) = Y$ تعریف می‌کنیم.به عبارت دیگر $g(Y)$ تعداد تمام جایگشت‌های $n$ تایی‌ای مانند $X$ است که $f(X) = Y$.

ویلی‌وانکا به‌عنوان آخرین چالش چارلی به او دو عدد $L$ و $R$ را می‌دهد و چارلی باید تعداد تمام جایگشت‌های $n$ تایی از اعداد ۱ تا $n$ مانند $A$ که $L \leq g(A) \leq R$ باشد را به او پاسخ دهد. از آن‌جا که این عدد ممکن است خیلی بزرگ باشد، باقی‌مانده‌ی تقسیم آن بر $10^9 + 7$ را خروجی دهید.

ورودی🔗

در سطر اول عدد $n \leq 2 \times 10^5$ ‫‫—‬ اندازه‌ی جایگشت‌ها آمده‌است.

در سطر بعدی دو عدد $L, R \leq 10^{18}$ آمده‌است.

خروجی🔗

باقی‌مانده‌ی جواب مسئله بر $10^9+7$ را چاپ کنید.

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

3 
0 10

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

6

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

3
2 1

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

0

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

7
8 14

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

225