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

علی که حسابی از کار کشاورزی سود کرده... تصمیم گرفت یک شرکت با هدف موتور جست و جوی کالا، تاسیس کند و به یاد مرحوم ترب، نام آن را ترب گذاشته...

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

در این سوال یک دنباله از اعداد طبیعی مانند $a_1, a_2, a_3, ..., a_n\$ آمده است و از تربچه خواسته شده تا حاصل عبارت زیر را محاسبه کند. $\sum_{i=1}^{n}\sum_{j=1}^{n}\lfloor\frac{a_i}{a_j}\rfloor$

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

ورودی🔗

در سطر اول ورودی عدد صحیح $n$ که نشان دهنده تعداد اعداد دنباله است و در سطر دوم $n$ عدد صحیح با فاصله آمده که عدد $i$ام نشان دهنده مقدار $a_i$ است.

$1 \le n, a_i \le 100\ 000$

خروجی🔗

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

مثال🔗

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

3
1 2 3

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

9

حاصل عبارت برابر است با: $\lfloor\frac{1}{1}\rfloor + \lfloor\frac{1}{2}\rfloor + \lfloor\frac{1}{3}\rfloor + \lfloor\frac{2}{1}\rfloor + \lfloor\frac{2}{2}\rfloor + \lfloor\frac{2}{3}\rfloor + \lfloor\frac{3}{1}\rfloor + \lfloor\frac{3}{2}\rfloor + \lfloor\frac{3}{3}\rfloor =$ $1 + 0 + 0 + 2 + 1 + 0 + 3 + 1 + 1 = 9$

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

4
1 1 1 1

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

16

چون همه مقادیر باهم برابر است حاصل عبارت برابر است با: $4 \times 4 \times \lfloor\frac{1}{1}\rfloor = 16$

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

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

علی از تربچه خواسته ابتدا تربچین را در قطعه $(0, 0)$ زمین قرار ‌دهد. تربچه برای آغاز کار یک رشته از حروف $\{L, R, U, D, ?\}$ دریافت می‌کند و طبق آن روی قطعه‌های زمین حرکت می‌کند و در هر قطعه که قرار بگیرد ترب داخل آن را می‌چیند.

همچنین اگر در یک خانه از جدول بیش از یک بار قرار بگیرد دیگر تربی برداشت نمی‌کند.

اگر رشته داده شده به تربچین $s_1s_2s_3...s_n\$ باشد. تربچین با توجه به این رشته $n$ حرکت انجام می‌دهد.اگر تربچین در خانه $(x, y)$ باشد بعد از انجام حرکت $i$ام :

• اگر $s_i=L$ باشد به خانه $(x-1, y)$
• اگر $s_i=R$ باشد به خانه $(x+1, y)$
• اگر $s_i=U$ باشد به خانه $(x, y+1)$
• اگر $s_i=D$ باشد به خانه $(x, y-1)$
• اگر $s_i=?$ باشد به یکی از چهار قطعه مجاور ضلعی

می‌رود.

علی رشته $s_1s_2s_3...s_n\$ را به ترب داده و او ترتیب عناصر این رشته را به هم ‌می‌ریزد. توجه کنید او نمی‌تواند حرفی به رشته اضافه یا کم کند!

علی که پیش‌بینی برایش خیلی مهم است؛ می‌خواهد بداند برای همه حالت‌های مختلف که ممکن است اتفاق بیفتد حداقل و حداکثر چند ترب توسط تربچین برداشت خواهد شد.

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

ورودی🔗

در خط اول ورودی عدد $t$ داده می‌شود. در هر یک از $t$ سطر بعدی هر کدام یک رشته از حروف $\{L, R, U, D, ?\}$ داده می‌شود. تضمین می‌شود مجموع طول همه رشته‌ها از $100\ 000$ بیشتر نمی‌شود.

خروجی🔗

خروجی باید شامل $t$ سطر باشد که در سطر $i$ام دو عدد $a_i$ و $b_i$ چاپ می‌شود که نشان دهنده حداقل و حداکثر تعداد ترب‌های برداشت شده توسط تربچین است.

مثال🔗

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

5
L
L?
UDU
????
LRURLDURDDD

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

2 2
2 3
2 3
2 5
4 12

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

$L \to min = max = 2$

$LU \to max = 3, LR \to min = 2$

$UDU\to min = 2, UDU\to max = 3$

$LRLR \to min = 2, DDDD \to max = 5$

$RLRLRDUDUDD \to min = 4$

$LLUURRRDDDD \to max = 12$

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

علی برای افزایش روحیه تیم ترب تصمیم گرفته آن‌ها را به اسکیپ روم ببرد... آن‌ها باید سوال زیر را حل کنند تا وارد مرحله بعد شوند... به آن‌ها کمک کنید تا این گردش برایشان جذاب شود

یک گراف ساده مانند $G$ با $n$ راس با شماره‌های ۱ تا $n$ و $m$ یال دو طرفه داریم. بین هر دو راس حداکثر یک یال وجود دارد. هر یال دو راس مختلف را به هم وصل می‌کند. توجه کنید لزوماً این گراف همبند نیست!

هر راس از این گراف در ابتدا با یکی از دو رنگ سیاه و سفید رنگ آمیزی شده است.

در هر عملیات می‌توانیم یک زیر مجموعه از رئوس مانند $S$، انتخاب کنیم و رنگ هر راس در مجموعه $S$ و همه رئوسی که به حداقل یک راس از $S$ یال دارند را عوض کنیم. (رنگ سفید را به سیاه و رنگ سیاه را به سفید)

می‌خواهیم با حداکثر $n + 1$ عملیات کل رئوس گراف را سفید کنیم. اگر چنین کاری ممکن است یک روش برای انجام این کار ارائه دهید در غیر اینصورت بگویید این کار ممکن نیست.

ورودی🔗

در خط اول ورودی دو عدد صحیح $n$ و $m$ با فاصله از هم آمده است. $0 \le n \le 1500$$0 \le m \le \frac{n(n - 1)}{2}$

در سطر بعدی یک رشته از $0$ و $1$ به طول $n$ آمده است که اگر عدد $i$ام آن $0$ باشد یعنی راس شماره $i$ سفید و اگر $1$ باشد یعنی رنگ راس شماره $i$ سیاه است.

در $m$ سطر بعدی هر کدوم دو عدد $u$ و $v$ آمده است. که نشان دهنده یال‌های گراف است. $1 \le u \neq v \le n$

خروجی🔗

در صورت امکان پذیر بودن در سطر اول $k$ که تعداد مراحلی که نیاز دارید تا رنگ همه رئوس را سفید کنید چاپ کنید. $0 \le k \le n + 1$ در $k$ سطر بعدی در هر سطر یک رشته از $0$ و $1$ چاپ کنید که عدد $i$ام آن $1$ است اگر راس شماره $i$ در مرحله $i$ام در مجموعه $S$ باشد و در غیر اینصورت $0$ خواهد بود.

در صورت امکان پذیر نبودن در تنها سطر خروجی -1 را چاپ کنید.

مثال🔗

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

4 3
0110
1 2
2 3
3 4

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

3
0100
0010
1001

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

3 3
110
1 2
2 3
3 1

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

-1

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

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

برای هر عدد طبیعی فرض کنید $P_n$ مجموعه همه دنباله‌هایی از اعداد طبیعی باشد که جمع اعضای این دنباله برابر $n$ است. به عبارت دیگر: $P_n = \{ (a_1a_2a_3\dots a_m) | a_1+a_2+a_3+\dots+a_m=n\}$ اکنون ترب می‌خواهد عبارت زیر را محاسبه کند. $\sum_{(a_1a_2a_3\dots a_m) \in P_n} {a_1}^k{a_2}^k{a_3}^k\dots{a_m}^k$ به ترب کمک کنید تا این عبارت را محاسبه کند چون ممکن است پاسخ شما بسیار عدد بزرگی باشد باقی‌مانده آن را به پیمانه $10^9+7$ حساب کنید.

ورودی🔗

ورودی تنها شامل یک خط است که در آن دو عدد طبیعی $n$ و $k$ با فاصله از هم آمده است. $1 \le k\le 100,1 \le n\le 10^9$

خروجی🔗

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

مثال🔗

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

1 1

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

1

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

4 2

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

63

تمام اعضای مجموعه $P_4$ عبارت است از: $P_4=\{ (1,1,1,1), (2,1,1), (1,2,1), (1,1,2), (2,2), (3,1), (1,3), (4) \}$ بنابراین حاصل مجموع فوق برابر است با: $1 + 4 + 4 + 4 + 16 + 9 + 9 + 16 = 63$

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

علی که در این گرمای تابستان اعضای شرکت را به اسکیپ روم برده بود برای رفع خستگی تصمیم می‌گیرد برای آن‌ها نوشابه بخرد... اما می‌خواهد تنها برای افرادی نوشابه بخرد که بتوانند سوالات زیر را درباره گراف پاسخ دهند...

فرض کنید $G$ یک گراف وزن دار بدون جهت همبند باشد. $G$ دارای $n$ راس و $m$ یال است. هر یال $G$ دو راس مختلف را به هم متصل می‌کند.

همچنین راس‌های این گراف با ۱ تا $n$ شماره گذاری شده‌اند. روی راس شماره $i$ عدد $a_i$ نوشته شده است.

از ما تعدادی سوال پرسیده می‌شود. در هر سوال سه عدد $v$ و $x$ و $k$ داده می‌شود و از ما کوچک‌ترین مقدار $w$ را می‌خواهند که حداقل $k$ راس وجود داشته باشند که فاصله آن‌ها از $v$ فاصله حداکثر $w$ باشد و عدد نوشته شده روی آن نسبت به $x$ اول باشد.

منظور از وزن یک مسیر بزرگ ترین عددی است که روی یال‌های آن مسیر وجود دارد.

منظور از فاصله دو راس مانند $u$ و $v$ کمینه مقدار وزن تمام مسیرهای ممکن بین $u$ و $v$ است.

ورودی🔗

در سطر اول ورودی سه عدد طبیعی $n$ و $m$ و$q$ با فاصله از هم آمده است که به ترتیب نشان دهنده تعداد رئوس، یال‌ها و سوالاتی است که باید به آن‌ها پاسخ بدهیم. $1 \le n, m, q \le 100\ 000$ در سطر دوم $n$ عدد مانند $a_1, a_2, a_3,..., a_n$ با فاصله آمده که نشان دهنده اعداد نوشته شده روی رئوس گراف است.

در $i$امین سطر از $m$ سطر بعدی، سه عدد $v_i$ و $u_i$ و $w_i$ عدد آمده است که نشان‌دهنده وجود یالی با وزن $w_i$ بین دو راس $v_i$ و $u_i$ است. دقت کنید که لزومی ندارد گراف ساده باشد و ممکن است طوقه یا یال چندگانه داشته باشیم. $1 \le u_i, v_i \le n$ $1 \le w_i \le 10^9$

در $j$امین سطر از $q$ سطر بعدی، سه عدد $v_j$ و $x_j$ و $k_j$ آمده است که نشان دهنده سوال علی از شماست؟$1 \le a_i, x_j \le 500\ 000$ $1 \le v_j \le n$ $2 \le k_j \le n$

خروجی🔗

در $q$ سطر خروجی در سطر $i$ام پاسخ سوال $i$ام را چاپ کنید.

مثال🔗

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

3 3 2
6 9 5
1 2 10
2 3 20
1 3 30
3 7 2
1 25 2

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

20
10

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

4 3 4
1 2 3 4
1 2 10
2 3 1
3 4 2
3 3 2
4 5 3
4 5 4
1 2 4

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

2
2
10
-1