کد،کد و بازهم کد

این وبلاگ همش کده!

کد،کد و بازهم کد

این وبلاگ همش کده!

*هیچ*

طبقه بندی موضوعی

چند موضوعی - 270B

یک سوال نسبتا نکته دار و متوسط رو به بالا به اسم چند موضوعی و با شماره ی 270B از سایت عظیم کدفورسس!


چند موضوعی - 270B

سپهر به سایت کدفوسس علاقه شدیدی داشت و هی صفحه رو ریفرش می کرد تا تغییری را در قسمت recent actions از دست نده!او دوست داره موضوعاتی رو بخونه که توی اون موضوعات پیام جدیدی باشه.

recent actions نشان دهنده ی n موضوع مختلف است که بر اساس زمان آخرین پیام در موضوع طبقه بندی شده اند.وقتی پیام جدید در موضوعی می آید، آن موضوع به اول لیست می آید.هیچ دو پیامی از موضوعات مختلف همزمان نمی آیند.

سپهر فقط همه ی موضوعاتی که باز کرده رو می خونه و دوباره صفحه رو ریفرش می کنه تا پیام های جدیدتری بیاد.او می دونه که هیچ موضوعی در لیست ظاهر نشده و در i امین جا در لیست موضوعی وجود داره که در ai امین جا قبلا بوده است.وی اصلا دوست نداره که وقتش رو با پیام های قدیمی هدر بده و فقط دوست داره موضوعاتی رو باز کنه که پیام جدید دارن. 

به سپهر کمک کنید که تعداد موضوعاتی رو پیدا کنه که قطعا پیام جدید دارند.موضوع x قطعا پیام جدید داره در صورتی که هیچ دنباله ای از موضوعات وجود نداشته باشه که هر دو شرایط زیر را داشته باشند.

  1. موضوع x آپدیت نشده باشه (پیام جدیدی نداشته باشه).
  2. ترتیب لیست از یک تا n تبدیل بشه به a1a2, ..., an.

ورودی:

در خط اول عدد صحیح n که (1 ≤ n ≤ 105و در خط بعد n عدد صحیح a1a2, ..., aکه هر کدام از بزرگتر مساوی یک و کوچکتر مساوی n هستند که جایگاه قدیمیِ i امین موضوع در لیست جدید هستند.مطمئن باشید که همه ی ai ها متمایز اند.

خروجی:

تعداد موضوعاتی رو چاپ کنید که مطمئن هستید دارای پیام جدید اند.

 

 

ورودی
5
5 2 1 3 4
خروجی
2
ورودی
3
1 2 3
خروجی
0
ورودی
4
4 3 2 1
خروجی
3

نکته:

در مثال اول موضوعات 2 و 5 قبل از موضوع 1 اند.برای همین این موضوعات مطمئناً باید پبام جدید داشته باشند.موضوعات 1 و 3 و 4 ممکن است پیام جدید نداشته باشند، اگر فقط 2 و 5 پیام جدید داشته باشند.

در مثال دوم ممکن است پیام جدیدی وجود نداشته باشد چون اصلا ترتیبشان تغییر نکرده است.

در مثال سوم فقط موضوع 1 می تواند پیام جدید نداشته باشد.

جواب: http://tny.cz/da677e74


اینم از کدفورسس که می خواستین! بازم می ذارم. :دی

  • سپهر محمدی

270B

Greedy

Multithreading

implementation

نظرات  (۰)

هیچ نظری هنوز ثبت نشده است
ارسال نظر آزاد است، اما اگر قبلا در بیان ثبت نام کرده اید می توانید ابتدا وارد شوید.
شما میتوانید از این تگهای html استفاده کنید:
<b> یا <strong>، <em> یا <i>، <u>، <strike> یا <s>، <sup>، <sub>، <blockquote>، <code>، <pre>، <hr>، <br>، <p>، <a href="" title="">، <span style="">، <div align="">
تجدید کد امنیتی