Processing math: 100%

المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۲۳:عملی مقدماتی دوم:سوال ۱

سوسک کشی

تعدادی سوسک سیاه و سفید در تار عنکبوت غول پیکر گیر افتاده‌اند. تار عنکبوت غول پیکر به صورت شبکه‌ای مربعی به ضلع N است و در هر یک از N2 خانه آن سوسکی گیر افتاده است. یکی از بزرگترین لذت‌های عنکبوت غول پیکر در زندگی، له کردن سوسک‌های بیچاره است. زیرا وقتی سوسکی را له می‌کند،‌ آن سوسک منفجر شده و مواد سمی بدنش بر روی تعدادی از سوسک‌های سطر پایینی می‌ریزد که باعث انفجار آن‌ها نیز می‌شود و این روند تا سطر آخر ادامه پیدا می‌کند. می‌دانیم سوسک‌هایی که در سطر iام قرار دارند به هنگام انفجار مواد سمی‌شان بر روی تمام سوسک‌هایی که در پایین قرار دارند و شماره ستون شان حداکثر ri تا با سوسک منفجر شده تفاوت دارد،‌ می‌ریزد. عنکبوت از شما خواسته به ازای هر موقعیت داده شده، تعداد سوسک‌های سیاهی را پیدا کنید که منفجر می‌شوند. در موقعیت iام، عنکبوت سوسک‌های si تا eiام سطر rowi را له می‌کند.

ورودی

  • در خط اول ورودی N اندازه‌ی ضلع شبکه تار عنکبوت آمده است (1N2000)
  • در خط بعد N عدد آمده است که عدد iام نشان‌دهنده‌ی ri است (1ri2000).
  • در N خط بعدی در هر خط یک رشته N حرفی آمده است که حرف jام رشته iام آن X است اگر سوسکی که در سطر iام و ستون jام قرار دارد، سیاه باشد و . است اگر سفید باشد.
  • در خط بعدی q تعداد موقعیت‌ها آمده است (1q1000000)
  • در q خط بعد، در هر خط به ترتیب سه عدد rowi ،si و ei آمده‌اند که به ترتیب سطر، ابتدا و انتهای بازه موقعیت iام را مشخص می کنند (1rowin,1siein).
  • در حداقل ۳۰ درصد از ورودی‌ها 1N500 است.

خروجی

در q سطر خروجی در سطر iام تعداد سوسک‌های سیاهی که در موقعیت iام منفجر می‌شوند را بنویسید.

محدودیت‌ها

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

ورودی و خروجی نمونه

ورودی نمونه خروجی نمونه
5
0 1 3 2 1
.X.XX
X..XX
.X.XX
XX..X
X.XX.
5
2 5 5
4 1 2
3 3 4
1 2 3
2 1 5
9
5
7
9
12

ابزار صفحه