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

ستاره‌های گلرنگ رشته‌های 0 و 1 را به روش خاص خودشان می‌سازند و نمایش می‌دهند.

نمایش 0 به صورت زیر است:

***
*.*
***

نمایش 1 به صورت زیر است:

.*.
.*.
.*.

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

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

ورودی🔗

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

در سطر دوم، یک رشته از 0 و 1 به طول $n$ داده می‌شود.

خروجی🔗

در سه سطر، رشته داده شده را به روش ستارگان گلرنگ نمایش دهید.

مثال‌ها🔗

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

4
0101

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

***.*.***.*.
*.*.*.*.*.*.
***.*.***.*.

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

5
10011

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

.*.******.*..*.
.*.*.**.*.*..*.
.*.******.*..*.

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

گلابی کوچولو در حمام نشسته و با تیله‌های ته شامپوهای تیله‌ای گلرنگ بازی می‌کند. در لحظات مختلف، گلی کوچولو وارد حمام می‌شود و به گلابی کوچولو یک شامپو می‌دهد که مدت زمان مصرف آن $x_i$ دقیقه است و در دقیقه‌ی $t_i$ تحویل داده می‌شود.

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

در این مسئله، به شما زمان‌های $t_i$ و مدت زمان مصرف‌های $x_i$ به ترتیب داده می‌شود. از شما خواسته شده است که برنامه‌ای بنویسید که در هر لحظه مشخص کند گلابی در حال مصرف کدام شامپو است، اگر او از روشی که گفته شد برای انتخاب شامپوها استفاده کند.

ورودی🔗

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

در $n$ خط بعدی، هر خط شامل دو عدد $t_i$ و $x_i$ است که به ترتیب زمان تحویل و زمان مصرف شامپوی $i$ام را نشان می‌دهند. تضمین می‌شود که در تست‌های داده شده شرایط زیر برقرار باشد.

$1 \leq x_i \leq 100$

$0 = t_1 < t_2 < \dots < t_n \leq 100$

خروجی🔗

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

مثال‌ها🔗

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

2
0 10
4 7

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

1
1

در این نمونه، در لحظه ۰ گلابی شامپوی اول را دریافت می‌کند که ۱۰ دقیقه زمان مصرف دارد. از آن‌جایی که گلابی در ابتدا تنها این شامپو را دارد، بلافاصله شروع به استفاده از آن می‌کند. سپس در لحظه ۴ گلابی شامپوی دوم را دریافت می‌کند که زمان مصرف آن ۷ دقیقه است. با اینکه شامپوی دوم تازه وارد شده است، گلابی همچنان در حال استفاده از شامپوی اول است چون ۶ دقیقه تا پایان آن باقی مانده است. بنابراین، در هر دو لحظه، گلابی همچنان در حال مصرف شامپوی شماره ۱ است.

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

3
0 10
10 20
31 40

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

1
2
3

در این نمونه، در لحظه ۰ گلابی شامپوی اول را دریافت می‌کند که ۱۰ دقیقه مصرف دارد و شروع به استفاده از آن می‌کند. در لحظه ۱۰ گلابی شامپوی دوم را دریافت می‌کند که زمان مصرف آن ۲۰ دقیقه است. از آن‌جایی که شامپوی اول تا زمان ۱۰ تمام می‌شود، گلابی از شامپوی دوم استفاده می‌کند. در لحظه ۳۱، گلابی شامپوی سوم را دریافت می‌کند که ۴۰ دقیقه زمان مصرف دارد. از آن‌جایی که شامپوی دوم تا زمان ۳۱ تمام می‌شود، گلابی از شامپوی سوم استفاده می‌کند.

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

3
0 10
1 9
19 100

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

1
1
3

در این نمونه، در لحظه ۰ گلابی شامپوی اول را دریافت می‌کند که ۱۰ دقیقه مصرف دارد و شروع به استفاده از آن می‌کند. در لحظه ۱ گلابی شامپوی دوم را دریافت می‌کند که زمان مصرف آن ۹ دقیقه است. از آن‌جایی که شامپوی اول هم ۹ دقیقه‌ی دیگر تمام می‌شود، گلابی از شامپوی اول استفاده می‌کند. در لحظه ۱۹، گلابی شامپوی سوم را دریافت می‌کند که ۱۰۰ دقیقه زمان مصرف دارد. از آن‌جایی که شامپوی اول و دوم تا زمان ۱۹ تمام می‌شود، گلابی از شامپوی سوم استفاده می‌کند.

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

3
0 10
1 9
18 100

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

1
1
2

در این نمونه، در لحظه ۰ گلابی شامپوی اول را دریافت می‌کند که ۱۰ دقیقه مصرف دارد و شروع به استفاده از آن می‌کند. در لحظه ۱ گلابی شامپوی دوم را دریافت می‌کند که زمان مصرف آن ۹ دقیقه است. از آن‌جایی که شامپوی اول ۹ دقیقه‌ی دیگر تمام می‌شود، گلابی از شامپوی اول استفاده می‌کند. در لحظه ۱۹، گلابی شامپوی سوم را دریافت می‌کند که ۱۰۰ دقیقه زمان مصرف دارد. از آن‌جایی که شامپوی اول و دوم تا زمان ۱۹ تمام می‌شود، در لحظه‌ی ۱۸ گلابی از شامپوی دوم استفاده می‌کند.

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

در شهر گلرنگ $n$ خیابان افقی یک‌طرفه شمال به جنوب و $m$ خیابان عمودی یک‌طرفه غرب به شرق وجود دارد. همانطور که انتظار داریم تمام خیابان‌های عمودی با یکدیگر و تمام خیابان‌های افقی نیز با یکدیگر موازی‌اند و همچنین هر خیابان افقی با تمام خیابان‌های عمودی متقاطع است. تعدادی تپسی داریم که می‌خواهند این خیابان‌ها را از ابتدا تا انتها طی کنند.

در هر تقاطع یک چراغ راهنمایی وجود دارد که در هر لحظه برای یکی از دو خیابان تقاطع سبز و برای دیگری قرمز است. هر کدام از چراغ‌ها یک عدد به نام $x$ دارند که با شروع از لحظه صفر برای خیابان افقی آن تقاطع به طور متناوب $x$ ثانیه سبز و سپس $x$ ثانیه قرمز اند. همچنین هر تقاطع یک عدد $y$ نیز دارد که نشان می‌دهد در در هر ثانیه در آن تقاطع حداکثر $y$ تپسی می‌توانند عبور کنند.

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

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

ورودی🔗

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

سپس در $n$ خط بعدی در هر خط $2m$ عدد نشانگر اطلاعات چهارراه‌های خیابان‌های افقی است. در هر خط به ترتیب $m$ جفت $x_i$ و $y_i$ داده می‌شود که $x_i$ بیانگر میزان ثانیه سبز برای چراغ $i$ در این خیابان است و $y_i$ برابر حداکثر تعداد تپسی ای است که در یک ثانیه از این چهارراه می‌تواند عبور کند.

$1 \leq n, m, y_i \leq 500$$0 \leq x_i\leq 1,000,000,000$ $\sum_{i = 0}^{i = n} y_i + \sum_{i = 0}^{i = m} y_i \leq 500$

خروجی🔗

در تنها سطر خروجی ثانیه‌ای که در پایان آن، آخرین تپسی به مقصد می‌رسد را چاپ کنید.

مثال‌ها🔗

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

1 1
6
8
7 4

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

8

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

3 2
35 7 4
160 104
4 7 7 1
7 5 7 2
9 7 3 9

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

208

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

دور یک میز گرد $n$ کارمند از شرکت گلرنگ و $m$ کارمند از شرکت کوئرا ایستاده‌اند و می‌خواهند دور میز شام بنشینند. سرآشپز می‌خواهد به کارمندان کوئرا کباب کوبیده و به کارمندان گلرنگ جوجه کباب بدهد، بنابراین می‌خواهد همه‌ی کارمندان کوئرا کنار هم و همه‌ی کارمندان گلرنگ کنار هم بنشینند.

مشکل اینجاست که اکنون همه‌ی این $n+m$ نفر نشسته‌اند و حالا باید جای خود را تغییر بدهند. برای تغییر جا با توجه به اینکه مبل‌های راحتی در نظر گرفته شده، می‌توانیم یک کارمند را از دور میز بلند کنیم و در جایی دیگر بین دو کارمند اضافه کنیم. این کار یک واحد انرژی جمع را کم می‌کند.

سوال اینجاست کمترین میزان انرژی که لازم داریم تا همه‌ی کارمندهای گلرنگ و کوئرا کنار هم باشند چقدر است؟

ورودی🔗

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

در سطر اول هر تست، دو عدد صحیح و مثبت $n$ و $m$ داده می‌شود که تعداد کارمندان گلرنگ و کوئرا را نشان می‌دهد. $1 \leq n+m \leq 1,000,000$

در سطر دوم هر تست، یک رشته به طول $n + m$ از کاراکترهای G و Q آمده است که وضعیت نشستن کارمندان را نشان می‌دهد.

تضمین می‌شود که مجموع $n + m$ برای همه‌ی $t$ تست حداکثر $2,000,000$ باشد.

خروجی🔗

برای هر تست، در یک خط به ترتیب کمترین میزان انرژی لازم برای درست کردن ترتیب را چاپ کنید.

مثال‌ها🔗

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

2
2 3
GQGQQ
4 1
GGGQG

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

1
0

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

2
1 0
G
0 1
Q

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

0
0

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

روی نقشه شهر گلرنگ $n$ مرکز خرید وجود دارد، مرکز خریدها با اعداد ۱ تا $n$ شماره‌گذاری شده‌اند. مرکز شماره‌ی $i$ در نقطه‌ی $(x_i, y_i)$ قرار دارد.

گل آقا عاشق کیک دوقولوی تاینی است. این کیک فقط در مراکز اکلا وجود دارد. می‌دانیم مرکز $i$ام $a_i$ کیک دارد و از اولین لحظه‌ای که این مقدار تمام شود. $t$ روز بعد، مجدداً $a_i$ کیک به این فروشگاه ارسال می‌شود. هیچ کس جز گل آقا از این کیک‌ها نمی‌خرد.

حال گل آقا در نقطه‌ی $(0, 0)$ است. سرعت حرکت او $1$ است. او اکنون $T$ ثانیه وقت دارد که در شهر بچرخد و بیشترین تعداد کیک را بخرد. از شما می‌خواهیم برنامه‌ای بنویسید که این بیشترین مقدار را حساب کند.

توجه کنید زمان مراجعه‌ها لزوماً اعداد صحیح نیستند، همچنین باید فاصله‌ی زمان مراجعه کردن به دو فروشگاه قابل رسیدن باشد. فرض می‌شود که زمان خرید کردن ناچیز بوده و به مجض مراجعه همه‌ی کیک‌های موجود خریداری می‌شود.

همچنین می‌توان نزیک یک فروشگاه ایستاد و چندبار از آن خرید کرد اما باید $t$ ثانیه از خرید قبلی گذشته باشد.

ورودی🔗

در سطر اول ورودی، سه عدد صحیح $n$، $t$ و $T$ آمده که تعداد فروشگاه‌ها، زمان شارژ شدن کیک و کل زمانی که گل آقا دارد را نشان می‌دهد. $1 \leq n, t \leq 100$ $1 \leq T \leq 1000$

در $n$ سطر بعدی، در هر سطر سه عدد $x_i$، $y_i$ و $a_i$ آمده که مختصات و تعداد کیک‌ها را نشان می‌دهد. $1 \leq x_i, y_i, a_i \leq 100$

تضمین می‌شود هیچ دو مرکز اکلا در یک نقطه قرار ندارند.

خروجی🔗

در سطر اول، دو عدد صحیح $m$ $k$ چاپ کنید که به ترتیب حداکثر مجموع کیک‌هایی و تعداد فروشگاه‌های مراجعه شده را نشان می‌دهد.

$0 \leq k \leq 1000$

در $k$ سطر بعدی، در هر سطر دو عدد $d_i$ و $m_i$ آمده که زمان مراجعه و شماره‌ی فروشگاه را نشان می‌دهد. $0 \leq d_i \leq T$ $1 \leq m_i \leq n$

مثال‌ها🔗

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

4 6 10
1 1 3
5 1 7
1 5 4
5 5 10

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

20 3
1.414215 1
5.414216 2
9.414217 4

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

4 6 20
1 1 3
5 1 7
1 5 4
5 5 10

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

37 5
1.414215 1
5.414216 2
9.414217 4
13.414218 2
17.414219 4