المپدیا

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

ابزار کاربر

ابزار سایت


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

تیراندازی

آقا داوود برای تفریح شاگردانش یک مسابقه تیراندازی ترتیب داده است. مسابقه به این صورت برگزار می‌شود که آقا داوود $N$ سیبل در یک ردیف قرار می‌دهد که بر روی هر سیبل یکی از حروف {J, V , D} قرار دارد. حال در هر نوبت یک تفنگ با سه تیر به یکی از شاگردان داده می‌شود. او باید سه سیبلی که تا به حال به آن‌ها شلیک نشده را انتخاب و به آن‌ها تیراندازی کند. در صورتی که حروف روی این سیبل‌ها از چپ به راست کلمه‌ی JVD را تشکیل دهند، او برنده‌ی جوراب ورزشی داوود می‌شود، و در صورتی که کلمه‌ی DVD را تشکیل دهند، برنده‌ی دستکش ورزشی داوود، می‌شود و اگر هیچ کدام از این دو حالت اتفاق نیافتد، هیچ جایزه‌ای نمی‌برد. (آقا داوود صاحب کارخانه‌ی لوازم ورزشی داوود است). با گرفتن وضعیت اولیه سیبل‌ها بیشترین تعداد جایزه‌ای که می‌توان برد را به دست آورید.

ورودی

  • سطر اول ورودی شامل یک عدد طبیعی، $1 \leq N \leq 10^6$، تعداد سیبل‌ها، است.
  • سطر دوم شامل یک رشته‌ی $N$ حرفی از حروف {J, V , D} است که حروف روی سیبل‌ها را به ترتیب از چپ به راست نشان می‌دهند.
  • در ۱۰ درصد از ورودی‌ها، $1 \leq N \leq 15$، است.
  • در ۳۰ درصد از ورودی‌ها، $1 \leq N \leq 50$، است.
  • در ۵۰ درصد از ورودی‌ها، $1 \leq N \leq 3000$، است.

خروجی

در تنها سطر خروجی بیشترین تعداد جایزه‌ای که می‌توان برد را چاپ کنید.

محدودیت‌ها

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

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

ورودی نمونه خروجی نمونه
6
JDVDVD
2
15
JJVDDVVJVJDVDDV
4

ابزار صفحه