لینک‌های مفید برای شرکت در مسابقه:

در طول مسابقه، می‌توانید سؤالات خود را از قسمت «سؤال بپرسید» مطرح کنید.

کاغذ دیواری


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

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

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

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

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

ورودی🔗

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

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

1n1018,1kmin{2n,3×105}1 \leq n \leq {10}^{18} \quad , \quad 1 \leq k \leq \min\{2n, 3 \times 10^5\}

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

در kk سطر بعدی در هر سطر، کارکتر rir_i که برابر u یا d است و سپس با یک فاصله عدد صحیح cic_i آمده است. این دو عدد، موقعیت پریز iiام را نشان می‌دهند.

ri{u,d}1cinr_i \in \{u, d\} \quad \quad 1 \leq c_i \leq n

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

خروجی🔗

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

مثال🔗

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

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

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

1
2
1
2
Plain text

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

1
2 1
u 2
Plain text

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

2
Plain text
ارسال پاسخ برای این سؤال
در حال حاضر شما دسترسی ندارید.