المپدیا

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

ابزار کاربر

ابزار سایت


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

دزد‌های بیچاره

تعدادی دزد و تعدادی پلیس در یک صف ایستاده‌اند. در ابتدای هر ثانیه، رئیس پلیس شهر، مرتضی، فرمان آتش می‌دهد و هر پلیس در صورت تمایل به یکی از دزدهای در تیررس خود شلیک می‌کند و در ثانیه‌ی بعدی هیچ اثری از آن دزد بیچاره باقی نخواهد ماند. دقت کنید که نور از داخل آدم‌ها عبور نمی‌کند. هدف این گروه نابود کردن همه‌ی دزدها در کم‌ترین تعداد سوت (فرمان آتش) است.

ورودی

در سطر اول فایل ورودی تعداد آدم‌ها و در $n$ سسطر بعد، در هر سطر یک حرف که نشان‌دهنده‌ی هویت فرد $i$ ام است که یا $T$ به معنی دزد و یا $P$ به معنی پلیس است و سپس یک عدد که مکان (مولفه $x$) مشخص می‌کند، آمده است. ($1\leq n \leq 10^5$ و $0\leq x_i \leq 10^8$ و در ضمن از اونجایی که مرتضی آدم قدرت طلبی است، هیچ وقت تعداد پلیس‌های تحت فرمانش «صفر» نیستند.)

خروجی

در فایل خروجی یک عدد بنویسید که تعداد مراحل لازم است.

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

ورودي نمونه خروجي نمونه
5
P 1
T 2
T 3
T 4
P 5
2

ابزار صفحه