المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره‌ی انتخاب تیم:دوره‌ی ۱۶:سوال ۶

Mafia

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

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

رئیس مافیا ار ما خواسته برای او نقشه‌ی بنای ساختمان‌ها با خاصیت فوق را بکشیم. برای این منظور او به ما بلندی و پهنای $n$ ساختمان را می‌دهد (هیچ دو ساختمانی دارای بلندی یکسان نیستند.) و از ما می‌خواهد محل قرار گرفتن هر ساختمان روی محور $x$ و جلو یا عقب بودن آن را تعیین کنیم.

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

  • $n$ و مشخصات هر یک از ساختمان‌ها را از ورودی بخواند.
  • کم‌ترین تعداد ساختمان‌های قابل رویت از روبرو را بیابید و در خروجی چاپ کنید.
  • یکی از روش‌های بنای ساختمان‌ها طوری که این کمینه به‌دست می‌آید را در خروجی چاپ کنید.

ورودی

در سطر اول ورودی عدد $n$، تعداد ساختمان‌ها آمده است.($1\leq n \leq 500$ و بلندی و پهنای ساختمان‌ها اعداد طبیعی و ناصفر هستند و هیچ دو ساختمانی هم ارتفاع نیست.)

در $n$ سطر بعد، در هر سطر مشخصات یک ساختمان می‌آید. در خط $i$ام به ترتیب دو عدد طبیعی $w_i$ و $h_i$ آمده است که به ترتیب پهنا و بلندی آن ساختمان هستند.( پهنای هر ساختمان کوچکتر از ۱۰۰ و بلندی هر ساختمان کوچک‌تر از $10^9$ است.)

تنها نقشه‌هایی از قرار گرفتن ساختمان‌ها قابل قبول است که در آن ضلع سمت چپ ساختمان‌ها عددی با تایپ $int$ و بزرگ‌‌تر مساوی صفر باشد.

خروجی

در سطر اول خروجی کم‌ترین تعداد ساختمان‌های قابل رویت را بنویسید.

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

محدودیت‌ها

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

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

ورودی نمونه خروجی نمونه
4
3 3
5 5
4 4
1 6
3
0 back
0 front
4 back
3 back

ابزار صفحه