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

در یک شرکت تاکسیرانی $n$ تاکسی در یک صف و $4n$ نفر در صفی دیگر قرار دارند. افراد صف به ترتیب سوار جلوترین تاکسی می‌شوند و هر تاکسی که پر شود (۴ نفر سوار آن شوند) بلافاصله حرکت می‌کند.

هر تاکسی دو قسمت دارد. صندلی جلو که دقیقاً یک مسافر سوار می‌شود و صندلی‌های عقب که دقیقاً ۳ مسافر سوار می‌شوند. همچنین لازم به ذکر است مسافران تنها از درِ سمت راست قادر به سوار شدن یا پیاده شدن در صندلی‌های عقب هستند.

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

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

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

برای درک بیشتر، به توضیحات مثال‌ها مراجعه کنید.

ورودی🔗

در سطر اول ورودی $n$ تعداد تاکسی‌ها می‌آید و در $4 \times n$ سطر بعد $d_i$ مقصد فرد $i$ام می‌آید. $1 \le n \le 20 \, 000$ $1 \le d_i \le 100$

خروجی🔗

در سطر $i$ام کمینه مجموع ناراحتی افراد تاکسی $i$ام خروجی داده شود.

مثال🔗

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

3
1
1
1
1
2
1
1
2
3
1
4
2

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

0
0
1

در تاکسی اول ۴ نفر با مقصد یکسان سوار می‌شوند و در تمام حالات سوار شدن هیچ کس ناراحت نمی‌شود.

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

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

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

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

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

ورودی🔗

در خط اول ورودی عدد $n$ آمده است که نمایانگر تعداد راس‌های درخت است.

در خط دوم رشته‌ای به طول $n$ آمده که هر کدام از حرف‌هایش می‌تواند R یا B باشد. حرف $i$-ام این رشته نشان‌دهنده‌ی رنگ راس $i$-ام است (R به معنای قرمز و B به معنای مشکی)

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

در نهایت در $n-1$ خط آخر، در هر خط دو عدد $u$ و $v$ آمده است که نشان‌دهنده‌ی وجود یال میان رئوس $u$ و $v$ است.

$1 \le n \le 10^6$ $-10^9 \le a_i \le 10^9$ $1 \le u, v \le n$

خروجی🔗

در تنها خط خروجی باید پاسخ خواسته شده را چاپ کنید.

مثال🔗

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

3
RBB
3 5 -2
1 2
1 3

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

8

درخت این نمونه در شکل زیر نمایش داده شده است. بهترین حالت این است که زیردرختمان شامل راس‌های ۱ و ۲ باشد که مجموع آن‌ها ۸ است.

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

5
BBRRB
-3 2 4 2 1
1 2
1 3
3 4
3 5

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

7

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

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

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

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

12

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

13
BBRRBBRBRRBBB
8 -11 -2 3 12 7 -3 -16 7 2 4 5 4
1 2
1 3
1 4
2 5
3 6
3 7
4 8
4 9
4 10
7 11
7 12
9 13

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

36

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

آرایه‌ای متشکل از $n$ عدد داریم. یک بازه از این اعداد را زیبا می‌نامیم اگر و تنها اگر مجموع اعداد حاضر در این بازه کمتر یا مساوی عدد $k$ و بیشتر یا مساوی عدد $-k$ باشد. به عبارتی دیگر، قدر مطلق مجموع اعداد این بازه باید حداکثر $k$ باشد.

روی این آرایه $q$ بار عملیات انجام شده است، هر عملیات به این صورت است که دو عدد $i$ و $x$ مشخص شده‌اند ($1 \le i \le n-1$)، سپس عضو $i$-ام آرایه با عدد $x$ جمع می‌شود و از عضو $i+1$-ام آرایه عدد $x$ تفریق می‌شود. (توجه کنید که مقدار $x$ می‌تواند منفی هم باشد)

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

دقت کنید تمامی عملیات‌ها پایا هستند، یعنی اثر آن‌ها در عملیات‌های بعدی نیز روی آرایه می‌ماند.

ورودی🔗

در خط اول ورودی به ترتیب سه عدد $n$، $k$ و $q$ آمده‌اند. در خط دوم $n$ عدد آمده‌اند که اعداد اولیه‌ی آرایه هستند و عدد $i$ را با $a_i$ نمایش می‌دهیم. در $q$ خط بعدی، در هر خط به ترتیب دو عدد $i$ و $x$ آمده‌اند که عملیات را مشخص می‌کنند.

$2 \le n \le 100 \, 000$ $1 \le q \le 100 \, 000$ $0 \le k \le 10 ^ 9$ $-10 ^ 9 \le a_i, x \le 10 ^ 9$ $1 \le i \le n - 1$

همچنین تضمین می‌شود قدر مطلق تمامی اعداد آرایه بعد از هر کوئری حداکثر $10^9$ خواهد ماند.

خروجی🔗

خروجی شما باید شامل $q+1$ خط باشد که نشان دهد در ابتدا و بعد از انجام هر عملیات تعداد بازه‌های زیبای آرایه چقدر است.

مثال🔗

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

5 3 2
1 2 3 4 5 
3 -2
2 4

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

4
5
4

در این نمونه در ابتدا بازه‌های $[1]$، $[2]$، $[3]$ و $[1,2]$ زیبا هستند.

بعد از عملیات اول آرایه تبدیل می‌شود به: $1, 2, 1, 6, 5$. بعد از این تغییر بازه‌های $[1]$، $[2]$، $[3]$، $[1,2]$ و $[2,3]$ زیبا خواهند بود.

بعد از عملیات دوم آرایه به این صورت خواهد بود: $1, 6, -3, 6, 5$. بعد از این تغییر بازه‌های $[1]$، $[3]$، $[2,3]$ و $[3,4]$ زیبا هستند.

(منظور از بازه‌ی $[i,j]$ بازه‌ای است که از عضو $i$ام شروع شده و تا عضو $j$ام ادامه دارد)

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

5 5 5
-3 -4 0 5 -5 
2 1
2 3
4 -4
2 -1
3 5

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

12
12
13
12
12
13

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

7 5 10
-10 11 -15 -8 6 8 8 
2 -16
6 -7
2 13
2 -18
4 -6
3 -8
4 10
5 7
2 -2
6 17

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

6
7
10
8
9
8
6
10
8
7
7

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

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

طبق این نظریه، الکترون‌ها در تعدادی «لایه» قرار دارند، هر «لایه» از تعدادی «زیرلایه» تشکیل شده که هر کدام ظرفیت تعدادی الکترون دارند. ۴ نوع زیرلایه داریم که با حروف s، p، d و f نشان می‌دهیم. ظرفیت این لایه‌ها به‌ترتیب ۲، ۶، ۱۰ و ۱۴ الکترون است. هر «لایه»، از تعدادی «زیرلایه» تشکیل شده:

• لایه‌ی اول ($n = 1$). یک زیرلایه‌ی s.
• لایه‌ی دوم ($n = 2$). یک زیرلایه‌ی s و یک زیرلایه‌ی p.
• لایه‌ی سوم ($n = 3$). یک زیرلایه‌ی s، یک زیرلایه‌ی p و یک زیرلایه‌ی d.
• لایه‌ی چهارم به بعد ($n \ge 3$). یک زیرلایه‌ی s، یک زیرلایه‌ی p، یک زیرلایه‌ی d و یک زیرلایه‌ی f.

حال می‌توانیم لایه و زیرلایه‌ها را به صورت یک رشته با دو کاراکتر نشان دهیم. مثلاً 3p یعنی زیرلایه‌ی نوع p در لایه‌ی سوم.

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

در این اتم‌های Cu، Cr، Nb، Mo، Ru، Rh، Pd، Ag، La، Ce، Gd، Pt، Au، Ac، Th، Pa، U، Np، Cm و Lr استثنا هستند و از قوانین گفته شده پیروی نمی‌کنند. می‌توانید آرایش الکترونی آن‌ها را از اینجا مشاهده کنید.

ورودی🔗

در سطر اول ورودی، عدد صحیح $t$ داده می‌شود. $1 \leq t \leq 10$ در $t$ سطر بعدی، در هر سطر، نام یک عنصر به صورت یک رشته از حروف کوچک و بزرگ انگلیسی است که حرف اول بزرگ و سایر حرف‌ها کوچک است داده می‌شود.تضمین می‌شود نام این عنصر در ۱۰۴ عنصر اول جدول تناوبی موجود باشد.

خروجی🔗

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

مثال🔗

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

2
Mg
Cu

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

1s2 2s2 2p6 3s2
1s2 2s2 2p6 3s2 3p6 3d10 4s1

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

بازی StickMan:Legacy یک بازی استراتژیک است که در آن هر کس ارتش خودش را تجهیز می‌کند و به جنگ دشمنان می‌رود. از شما می‌خواهیم برنامه‌ای بنویسید که درخواست‌های بازیکن را مدیریت کند.

توضیحات بازی🔗

شما برای ملحق کردن افراد به ارتش باید به آن‌ها سکه بدهید. همچنین نمی‌تواند بیش از ۵۰ واحد نیرو زنده در ارتش خود داشته‌باشید. در ابتدای بازی ۵۰۰ سکه دارید و هیچ کسی در ارتش شما نیست. دولت از لحظه‌ی ابتدایی بازی، هر ۲۰ ثانیه یکبار ۱۸۰ سکه به ارتش شما می‌دهد. (به‌جز لحظه‌ی شروع)

در این ارتش ۶ سِمَت مختلف «معدن‌کار»، «شمشیرزن»، «تیرانداز»، «سپردار»، «جادوگر» و «غول» برای افراد وجود دارد. هر کدام از این سِمَت‌ها ویژگی و شرایط مختلفی دارند که در پایین توضیح داده می‌شود.

هر کس بسته به سمتی که دارد، مقداری جان دارد، اگر در جنگ آسیبی به کسی وارد شود، به همان اندازه از جانش کم می‌شود و اگر جان کسی بعد از یک صدمه، کمتر یا مساوی ۰ شود، می‌میرد.

ارتش شما باید به مبارزه با یک اژدها برود. این اژدها $h$ واحد جان دارد و هر چندوقت یکبار به یکی از افراد ارتش شما صدمه می‌زند.

در میدان جنگ ۴ معدن وجود دارد و روی هر معدن حداکثر دو معدن‌کار می‌توانند کار کنند. اگر تعداد معدن‌کارها بیشتر ۸ باشد، ۸ نفر روی معادن کار می‌کنند و بقیه بی‌کار می‌ایستند.

ویژگی سِمَت‌ها🔗

• معدن‌کار (miner): هر معدن‌کار یک‌ واحد نیرو حساب می‌شود. جان هر معدن‌کار ۱۰۰ است. استخدام کردن یک معدن‌کار ۱۵۰ سکه نیاز دارد. هر معدن‌کار بعد از استخدام، در صورتی که بتواند روی یک معدن مشغول شود، هر ۱۰ ثانیه، ۱۰۰ سکه به دارای شما اضافه می‌کند.
• شمشیرزن (swordwrath):‌ هر شمشیرزن یک واحد نیرو حساب می‌شود. جان هر شمشیرزن ۱۲۰ است. استخدام کردن یک شمشیرزن ۱۲۵ سکه نیاز دارد. شمشیرزن هر ثانیه بعد از استخدام، یک ضربه به اژدها می‌زند و از جان او ۲۰ واحد کم می‌کند.
• تیرانداز (archidon): هر تیرانداز یک واحد نیرو حساب می‌شود. جان هر تیرانداز ۸۰ است. استخدام کردن یک تیرانداز ۳۰۰ سکه نیاز دارد. تیرانداز هر ثانیه بعد از استخدام، یک تیر به اژدها می‌زند و از جان او ۱۰ واحد کم می‌کند.
• سپردار (spearton): هر سپردار دو واحد نیرو حساب می‌شود. جان هر سپردار ۲۵۰ است. استخدام کردن یک سپردار ۵۰۰ سکه نیاز دارد. سپردار هر سه ثانیه بعد از استخدام، یک نیزه به اژدها می‌زند و از جان او ۳۵ واحد کم می‌کند.
• جادوگر (magikill): هر جادوگر چهار واحد نیرو حساب می‌شود. جان هر جادوگر ۸۰ است. استخدام کردن یک جادوگر ۱۲۰۰ سکه نیاز دارد. جادوگر هر پنج ثانیه بعد از استخدام، یک آتش به اژدها می‌زند و از جان او ۲۰۰ واحد کم می‌کند.
• غول (giant): هر غول چهار واحد نیرو حساب می‌شود. جان هر غول ۱۰۰۰ است. استخدام کردن یک غول ۱۵۰۰ سکه نیاز دارد. غول هر چهار ثانیه بعد از استخدام، یک ضربه به اژدها می‌زند و از جان او ۱۵۰ واحد کم می‌کند.

برنامه‌ای که باید بنویسید🔗

در این سوال از شما می‌خواهیم $q$ درخواست که بازیکن از ارتش دارد را مدیریت کنید.

add <role> <timestamp>

damage <idx> <d> <timestamp>

enemy-status <timestamp>

army-status <timestamp>

money-status <timestamp>

نکات🔗

• هر درخواست در یک زمانی داده می‌شود که با <timestamp> نشان می‌دهیم. فرمت هر کدام به صورت mm:ss:xxx است که یعنی اتفاق در دقیقه mm، ثانیه ss و میلی‌ثانیه xxx اتفاق افتاد است.
• تضمین می‌شود هیچ دو اتفاقی حتی سکه اضافه کردن‌ها و صدمه زدن‌هایی که به تناوب تکرار می‌شوند، همزمان نباشد.

ورودی🔗

در سطر اول ورودی، دو عدد صحیح $q$ و $h$ با یک فاصله داده می‌شود که به ترتیب نشان‌دهنده‌ی تعداد درخواست‌ها و جان اژدها است.

$1 \leq q \lt 1000$ $1 \leq h \leq 10^9$

در $q$ سطر بعدی، در هر سطر یکی از دستوراتی که در صورت سوال گفته شده می‌آید.

تضمین می‌شود زمان همه‌ی درخواست‌ها از نظر زمانی مرتب هستند و هیچ دو اتفاقی حتی اتفاق‌هایی که به تناوب تکرار می‌شوند، همزمان رخ نمی‌دهد.

خروجی🔗

خروجی $q$ سطر دارد و در هر سطر خروجی متناسب با درخواست‌ها را به ترتیب چاپ کنید.

مثال‌ها🔗

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

12 132
money-status 00:19:999
money-status 00:20:001
add miner 00:20:002
money-status 00:20:003
add miner 00:20:004
money-status 00:20:005
add miner 00:20:006
money-status 00:20:007
add miner 00:20:008
money-status 00:20:009
add miner 00:29:010
add miner 00:30:011

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

500
680
1
530
2
380
3
230
4
80
not enough money
5

همانطور که در سوال گفته شد؛ دولت بعد از شروع بازی هر ۲۰ ثانیه، ۱۸۰ سکه به ارتش کمک می‌کند. پس تا لحظه‌ی قبل از ثانیه ۲۰، مقدار پول ارتش همان ۵۰۰ سکه‌ای است که از ابتدا دارد و اولین لحظه بعد از ثانیه ۲۰، ۱۸۰ سکه به ارتش اضافه می‌شود.

در ۴ درخواست بعدی، در هر درخواست یک معدن‌کار به ارتش اضافه می‌شود. هر معدن‌کار برای استخدام ۱۵۰ سکه نیاز دارد. پس بعد از استخدام معدن‌کار ۴ام دیگر پول کافی برای استخدام معدن‌کار ۵ام در لحظه‌ی ۲۹:۰۰۹ نداریم. اما در لحظه‌ی ۳۰:۰۱۰، هر ۴ معدن‌کار ۱۰ ثانیه هست که مشغول به کار شدند و هر کدام ۱۰۰ سکه به ارتش اضافه کرده‌اند. پس می‌توانیم در این لحظه یک معدن‌کار داشته باشیم.

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

32 10000
money-status 00:00:001
add miner 00:00:002
add miner 00:00:003
add miner 00:00:004
money-status 00:00:005
add miner 00:10:006
add miner 00:10:007
add swordwrath 02:00:008
add archidon 02:00:009
army-status 02:00:010
add spearton 02:00:011
add magikill 02:00:012
add giant 02:00:013
enemy-status 02:00:014
army-status 02:00:015
damage 1 10 02:01:016
damage 2 10 02:01:017
damage 3 20 02:01:018
damage 4 3 02:01:019
damage 5 15 02:01:020
damage 6 1000 02:01:021
damage 7 60 02:01:022
damage 8 16 02:01:023
damage 16 16 02:01:024
enemy-status 02:01:025
army-status 02:01:026
damage 6 17 02:31:027
damage 7 18 02:31:028
damage 8 19 02:31:029
damage 9 20 02:31:030
enemy-status 02:31:031
army-status 02:31:032

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

500
1
2
3
50
4
5
6
7
5 1 1 0 0 0
8
9
10
10000
5 1 1 1 1 1
90
90
80
97
85
dead
20
234
no matter
9970
5 0 1 1 1 1
no matter
2
215
60
7070
5 0 1 1 1 1