- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
در یک کافی‌نت $n$ کامپیوتر در یک ردیف، کنار هم قرار گرفته‌اند. کامپیوترها از $1$ تا $n$ به ترتیب شماره‌گذاری شده‌اند.
در ابتدای روز همه‌ی کامپیوترها خالی است. در یک روز $m$ گروه به ترتیب در زمان‌های مختلف به این کافی‌نت می‌آیند. هر گروه دو عدد $s$ و $\ell$ ارائه می‌دهد. یعنی این گروه شامل یک جمع $\ell$ نفره است و می‌خواهند پشت $\ell$ کامپیوتر متوالی با شماره‌های بیشتر یا مساوی $s$ بنشینند.
حال از شما می‌خواهیم که این سیستم را مدیریت کنید. یعنی این $\ell$ نفر را پشت کامپیوترهای با شماره‌های متوالی و بیشتر یا مساوی $s$ قرار دهید. اگر چند بازه برای نشستن این گروه وجود داشت، آن‌ها را روی بازه‌ای با کمترین شماره قرار دهید. اگر انجام چنین کاری ممکن نبود، به آن‌ها «نه» بگویید تا کافی‌نت را ترک کنند.
برای بهتر متوجه شدن خواسته‌ی سوال به نمونه‌ها مراجعه کنید.
ورودی
در سطر اول ورودی، به ترتیب دو عدد صحیح و مثبت $n$ و $m$ که با یک فاصله از هم جدا شده‌اند، داده می‌شود. $$1 \leq n, m \leq 200$$
در $m$ سطر بعدی، در هر سطر به ترتیب دو عدد صحیح $s$ و $\ell$ که با یک فاصله از هم جدا شده‌اند داده می‌شود. $$1 \leq s, \ell \leq n$$
خروجی
در $m$ سطر، بعد از درخواست، وضعیت مشغول بودن یا نبودن کامپیوترها را بعد از نشستن آن گروه به صورت یک رشته از 0 (خالی) و 1 (پر) چاپ کنید.
ورودی نمونه ۱
6 5
2 3
1 3
1 2
3 1
1 2
خروجی نمونه ۱
011100
011100
011111
011111
011111
- گروه اول، شامل ۳ نفر است و می‌خواهند پشت ۳ کامپیوتر با شماره‌های بیشتر یا مساوی ۲ کنار هم بنشینند. چون همه‌ی کامپیوترها خالی است، اولین بازه‌ی ممکن برای آن‌ها کامپیوترهای ۲، ۳ و ۴ می‌نشینند.
- گروه دوم، شامل ۳ نفر است و می‌خواهند پشت ۳ کامپیوتر با شماره‌های بیشتر یا مساوی ۱ کنار هم بنشینند. با اینکه ۳ کامپیوتر خالی وجود دارد ولی چون این ۳ کامپیوتر در یک بازه‌ی متوالی نیست، پس آن‌ها از کافی‌نت خارج می‌شوند.
- گروه سوم، شامل ۲ نفر است و می‌خواهند پشت ۲ کامپیوتر با شماره‌های بیشتر یا مساوی ۱ بنشینند. تنها بازه‌ی ممکن برای آن‌ها کامپیوترهای ۵ و ۶ است.
- گروه چهارم، شامل ۱ نفر است و می‌خواهد پشت کامپیوتر با شماره‌ی بیشتر یا مساوی ۳ بنشیند، ولی هیچ کامپیوتری با این شماره، خالی نیست. پس او از کافی‌نت خارج می‌شود.
- گروه پنجم، شامل ۲ نفر است و می‌خواند پشت ۲ کامپیوتر با شماره‌های بیشتر یا مساوی ۱ بنشینند ولی ۲ کامپیوتر خالی در کافی‌نت وجود ندارد، پس آن‌ها از کافی‌نت خارج می‌شوند.
ارسال پاسخ برای این سؤال