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

فرض کنید گروه خونی هر انسان، یکی از ۸ حالت زیر را دارد:

$O^- \quad O^+ \quad A^- \quad A^+ \quad B^- \quad B^+ \quad AB^- \quad AB^+$

در واقع به عقیده‌ی زیست شناسان ۳ نوع ماده‌ی $A$، $B$ و $+$ وجود دارند که هر کدام از آن‌ها می‌توانند در خون ظاهر شوند یا نشوند. (نیامدن ماده‌ی $+$ را با $-$ نشان می‌دهند و نیامدن هیچ‌کدام از $A$ و $B$ را با $O$ نشان می‌دهند.)

می‌دانیم ماده‌های موجود در خون هر فرزند، زیرمجموعه‌ی اجتماع ماده‌های موجود در خون پدر و مادر او است. یعنی برای مثال اگر هیچ کدام از پدر و مادر در خون خود، ماده‌ی $A$ را نداشته باشند، امکان ندارد در خون فرزند ماده‌ی $A$ وجود داشته باشد. (برای فهم بهتر مثال‌های نمونه را مطالعه کنید.)

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

ورودی🔗

در سطر اول ورودی، عدد صحیح و مثبت $t$ داده می‌شود که تعداد تست‌ها را نشان می‌دهد.

$1 \leq t \leq 512$

در $t$ سطر بعدی، در هر سطر سه رشته‌ی $d$، $m$ و $c$ که با یک فاصله از هم جدا‌شده‌اند داده می‌شود که به ترتیب گروه خونی پدر، مادر و فرزند را نشان می‌دهد.

گروه‌های خونی را با رشته‌های O-، O+، A-، A+، B-، B+، AB- و AB+ نمایش می‌دهیم.

خروجی🔗

خروجی، $t$ سطر دارد و در هر سطر، در صورت قابل قبول بودن آزمایش، رشته‌ی valid و در غیر این‌صورت invalid را چاپ کنید.

مثال🔗

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

3
AB+ A+ O-
B+ A- AB+
A+ A- B+

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

valid
valid
invalid

در آزمایش اول، گروه خونی پدر $AB^+$، گروه خونی مادر $A^+$ و گروه خونی فرزند $O^-$ است. کافی است هیچ‌کدام از ماده‌های $A$، $B$ و $+$ به فرزند منتقل نشود تا گروه خونی فرزند $O^-$ شود. پس نتیجه‌ی آزمایش قابل قبول است.

در آزمایش دوم، گروه خونی پدر $B^+$، گروه خونی مادر $A^-$ و گروه خونی فرزند $AB^+$ است. کافی است ماده‌های $B$ و $+$ از پدر و ماده‌ی $A$ از مادر به فرزند منتقل شود تا گروه خونی فرزند $AB^+$ شود. پس نتیجه‌ی آزمایش قابل قبول است.

در آزمایش سوم، گروه خونی پدر $A^+$، گروه خونی مادر $A^-$ و گروه خونی فرزند $B^+$ است. فرزند نمی‌تواند ماده‌ی $B$ در خون خود داشته باشد. (هیچ‌کدام از پدر و مادر این ماده را در خون خود ندارند.) پس نتیجه‌ی این آزمایش قابل قبول نیست.

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

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

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

ورودی🔗

در خط اول عدد $n$ و در خط دوم مقادیر $p_i$ با هم فاصله از هم آمده اند. تمامی مقادیر ورودی صحیح هستند.

$1 \le n \le 1000$ $0 \le p_i \le 100$

خروجی🔗

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

مثال🔗

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

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

3
70 90 85

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

45 70

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

4
30 30 30 30

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

0 30

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

روی یک میز، $n$ ظرف شیر، در یک ردیف پشت هم قرار گرفته‌اند. ظرف‌ها از چپ به راست با اعداد $1$ تا $n$ شماره‌گذاری شده‌اند. می‌دانیم در ابتدا در ظرف $i$ام $a_i$ لیتر شیر وجود دارد.

پارسا به ترتیب از سمت راست‌ترین ظرف (ظرف شماره‌ی $n$) شروع می‌کند و به سمت چپ‌ترین ظرف (ظرف شماره‌ی $1$) می‌رود.

او هر وقت به یک ظرف شیر رسید، شیر موجود در آن را به طور مساوی بین ظرف‌هایی که هنوز به سراغ آن‌ها نرفته پخش می‌کند.

یعنی ابتدا شیر ظرف $n$ام را به صورت مساوی بین تمام $n - 1$ ظرف دیگر تقسیم می‌کند، سپس به سراغ ظرف $n - 1$ام می‌رود و همین روند را ادامه می‌دهد. وقتی به ظرف $1$ می‌رسد، کار تمام می‌شود. (چون ظرفی بعد از آن نیست.) همچنین ظرف‌ها به اندازه‌ی خیلی زیادی ظرفیت دارند و هیچ‌وقت سرریز نمی‌کنند.

اکنون پارسا از شما می‌خواهد که برای هر ظرف، مقدار شیری که در لحظه‌ای که به سراغ آن می‌رود در آن موجود است را محاسبه کنید.

برای درک بهتر فرآیند به ورودی و خروجی نمونه مراجعه کنید.

ورودی🔗

در سطر اول ورودی، عدد صحیح و مثبت $n$ آمده که تعداد ظرف‌های شیر را نشان می‌دهد.

$1 \leq n \leq 10^6$

در سطر دوم ورودی، $n$ عدد صحیح و مثبت $a_1, a_2, \dots, a_n \,$ که با یک فاصله از هم جدا شده‌اند آمده که $a_i$ مقدار اولیه شیر ظرف $i$ام را نشان می‌دهد.

$0 \leq a_i \leq 10^6$

خروجی🔗

در تنها سطر خروجی، $n$ عدد صحیح $ans_1, ans_2, \dots, ans_n\,$ که با یک فاصله از هم جدا شده‌اند را چاپ کنید به‌طوری که $ans_i$ مقدار شیر موجود در ظرف $i$ام، در لحظه‌ای که به سراغ آن می‌رویم را نشان می‌دهد.

پاسخ شما زمانی درست در نظر گرفته می‌شود که تا $5$ رقم بعد از اعشار دقیق باشد.

مثال‌ها🔗

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

6
2 1 0 6 0 5

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

14.00000 6.50000 3.66667 7.25000 1.00000 5.00000

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

1
0

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

0.00000

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

دیواری به شکل یک جدول $2 \times n$ داریم. می‌توانیم این دیوار را به صورت $n$ ستون در نظر بگیریم که در هر ستون دو ردیف بالا و پایین وجود دارد.

روی دیوار $k$ پریز برق وجود دارد. هر پریز، کاملاً یکی از واحدهای بالایی یا پایینی یک ستون را اشغال می‌کند.

می‌خواهیم این دیوار را کاغذ دیواری کنیم. هر تکه کاغذ دیواری، به شکل یک مستطیل است و کاغذ دیواری به هر ابعادی را به میزان کافی داریم. کاغذ دیواری‌ها نباید روی پریزها را بپوشانند و همچنین نمی‌خواهیم آن‌ها را پاره کنیم.

می‌خواهیم طوری این کار انجام شود که تعداد کاغذ دیواری‌های مصرفی کمینه شود (دقت کنید ابعاد کاغذ دیواری‌ها اهمیتی ندارد و هدف کمینه کردن تعداد آن‌هاست). از شما می‌خواهیم این تعداد کمینه را محاسبه کنید.

ورودی🔗

در سطر اول ورودی، عدد صحیح $t$ به شما داده می‌شود که تعداد تست‌های ورودی را نشان می‌دهد. $1 \leq t \leq 3 \times 10^5$

سپس در سطر اول هر تست، به ترتیب، دو عدد صحیح $n$ و $k$ که با یک فاصله از هم جدا شده‌اند آمده است که نشان‌دهنده‌ی تعداد ستون‌های دیوار و تعداد پریزهای روی دیوار هستند.

$1 \leq n \leq {10}^{18} \quad , \quad 1 \leq k \leq \min\{2n, 3 \times 10^5\}$

تضمین می‌شود $\sum k$ برای همه تست‌ها حداکثر $3 \times 10^5$ باشد.

در $k$ سطر بعدی در هر سطر، کارکتر $r_i$ که برابر u یا d است و سپس با یک فاصله عدد صحیح $c_i$ آمده است. این دو عدد، موقعیت پریز $i$ام را نشان می‌دهند.

$r_i \in \{u, d\} \quad \quad 1 \leq c_i \leq n$

تضمین می‌شود هیچ دو پریزی در موقعیت یکسان قرار ندارد.

خروجی🔗

خروجی $t$ سطر دارد، در هر سطر پاسخ تست متناظر یعنی کمترین تعداد تکه کاغذ دیواری را چاپ کنید.

مثال🔗

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

4
1 1
d 1
4 2
d 3
u 3
1000000000000 0
4 2
u 1
d 4

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

1
2
1
2

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

1
2 1
u 2

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

2

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

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

به یک دنباله از افراد «موج مکزیکی» می‌گوییم اگر عدد صحیحی مثل $k$ موجود باشد به طوری که:

• تعداد افراد ضریبی از $2k$ باشد.
• $k$ نفر اول نشسته، $k$ نفر بعدی ایستاده، $k$ نفر بعدی نشسته، و ... باشند، یا $k$ نفر اول ایستاده، $k$ نفر بعدی نشسته، $k$ نفر بعدی ایستاده، و ... باشند.

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

ورودی🔗

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

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

در سطر دوم هر تست، یک رشته به طول $n$ از حروف U (ایستاده) و D (نشسته) داده می‌شود.

تضمین می‌شود $\sum n$ به ازای همه‌ی $t$ تست حداکثر $10^6$ است.

خروجی🔗

خروجی $t$ سطر دارد، در هر سطر بیشترین طول ممکن برای یک زیر دنباله‌ی موج مکزیکی چاپ کنید.

مثال🔗

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

4
5
UUUUU
6
UDUUDD
6
DDDUUU
14
DUDUDDDUUUDUDU

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

0
4
6
10

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

مش‌رجب برای تولد ۶ سالگی خود یک نوار به طول $n$ هدیه گرفته است که در هر کدام از خانه‌های آن یک عدد مثبت نوشته شده است.

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

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

ورودی🔗

در خط اول ورودی عدد $n$ آمده است. در خط دوم $n$ عدد آمده است که عدد $i$-ام آن‌‌‌‌ $a_i$ یا همان عدد خانه $i$-ام ست. در خط سوم $n$ عدد آمده است که ترتیب قرمز شدن خانه‌ها را نمایش می‌دهد، اعداد این خط یک جایگشت از اعداد ۱ تا $n$ هستند.

$1 \le n \le 10^5$

$1 \le a_i \le 10^9$

خروجی🔗

در تنها خط خروجی باید $n$ عدد چاپ کنید که عدد $i$-ام نشان می‌دهد میزان علاقه مش‌رجب به نوار بعد از مرحله $i$-ام چقدر است.

مثال🔗

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

4
7 4 6 10
3 1 2 4

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

6 9 17 27 

بعد از قرمز شدن خانه سوم نوار، زیبا‌ترین بازه از نظر مش‌رجب بازه‌ی [۳,۳] است و زیبایی ۶ دارد. وقتی خانه اول نیز قرمز می‌شود، زیباترین بازه از نظر مش‌رجب بازه [۱,۳] است که زیبایی ۹ دارد.

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

10
4 2 7 6 4 2 6 3 1 7
8 3 1 6 2 7 10 4 5 9

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

3 7 9 9 13 14 20 32 40 42 

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

10
75 98 33 45 27 57 91 54 42 59 
8 6 5 9 1 2 7 10 3 4 

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

54 57 84 96 96 184 366 425 491 581 

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

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

کوئرای عزیز،

به یک درخت ریشه‌دار، درخت دودویی می‌گوییم اگر و تنها اگر هر راس آن دقیقا ۰ یا ۲ بچه (یک بچه‌ی چپ و یک بچه‌ی راست) داشته باشد.

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

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

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

با احترام، کا. گ. ب.

ورودی🔗

در خط اول ورودی دو عدد $n$ و ریشه‌ی درخت داده شده است.

در $n-1$ خط بعدی، یال‌های درخت داده شده اند.

$1 \le n \le 5 \times 10^5$

خروجی🔗

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

مثال🔗

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

1 1

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

1

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

3 2
1 2
2 3

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

3

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

9 5
5 3
5 7
5 8
3 1
3 4
7 2
7 6
7 9

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

7

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

15 8
8 4
8 12
4 2
2 1
2 3
4 6
6 5
6 7
12 10
10 9
10 11
12 14
14 13
14 15

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

15