لینکهای مفید برای شرکت در مسابقه:
در طول مسابقه، میتوانید سؤالات خود را از قسمت «سؤال بپرسید» مطرح کنید.
دیواری به شکل یک جدول داریم. میتوانیم این دیوار را به صورت ستون در نظر بگیریم که در هر ستون دو ردیف بالا و پایین وجود دارد.
روی دیوار پریز برق وجود دارد. هر پریز، کاملاً یکی از واحدهای بالایی یا پایینی یک ستون را اشغال میکند.
میخواهیم این دیوار را کاغذ دیواری کنیم. هر تکه کاغذ دیواری، به شکل یک مستطیل است و کاغذ دیواری به هر ابعادی را به میزان کافی داریم. کاغذ دیواریها نباید روی پریزها را بپوشانند و همچنین نمیخواهیم آنها را پاره کنیم.
میخواهیم طوری این کار انجام شود که تعداد کاغذ دیواریهای مصرفی کمینه شود (دقت کنید ابعاد کاغذ دیواریها اهمیتی ندارد و هدف کمینه کردن تعداد آنهاست). از شما میخواهیم این تعداد کمینه را محاسبه کنید.
در سطر اول ورودی، عدد صحیح به شما داده میشود که تعداد تستهای ورودی را نشان میدهد.
سپس در سطر اول هر تست، به ترتیب، دو عدد صحیح و که با یک فاصله از هم جدا شدهاند آمده است که نشاندهندهی تعداد ستونهای دیوار و تعداد پریزهای روی دیوار هستند.
تضمین میشود برای همه تستها حداکثر باشد.
در سطر بعدی در هر سطر، کارکتر که برابر u
یا d
است و سپس با یک فاصله عدد صحیح آمده است. این دو عدد، موقعیت پریز ام را نشان میدهند.
تضمین میشود هیچ دو پریزی در موقعیت یکسان قرار ندارد.
خروجی سطر دارد، در هر سطر پاسخ تست متناظر یعنی کمترین تعداد تکه کاغذ دیواری را چاپ کنید.