پاسخ - SGU 199

متن اصلی سوال: http://acm.sgu.ru/problem.php?contest=0&problem=199

قبل نوشت: ترجمه نسبتا آزاد است.

ترجمه:

با اعتبار ترین کلوپ ورزشی شهر، دقیقا N عضو داره. هر کدوم از عضوها، یه درجه زیبایی و قدرت دارند. به بیان دقیق تر: i-امین عضو این کلوپ ( اعضا بر اساس هنگامی که وارد کلوپ شدن نامگزاری می شن ) قدرت S_i و زیبایی B_i داره. از اون جایی که این کلوپ، خیلی با اعتباره، اعضای اون خیلی پولدارن ( خوش به حالشون :D ) و کلا خیلی فوق العاده و خفنن. در نتیجه، معمولا کمتر از هم دیگه متنفر هستن. دقیق تر بخوایم بگیم: i-امین عضو از این کلوپ، آقای هـ از j-امین عضو این کلوپ آقای د متنفره اگر ( و فقط اگر ) S_i <= S_j و B_i>= B_j  یا این که S_i >= S_j  و   B_i <= B_j ( اگه جفت خصوصیات آقای هـ از آقای د بیشتر باشه، اصن آقای هـ متوجه آقای د نمی شه و اگه هم جفت خصوصیات کمتر باشه، آقای د به آقای هـ احترام میزاره. )

برای جشن سال نوی 2003 ( امسال 2013 ) میر کلوپ می خواد یه جشن رو برنامه ریزی کنه. البته می ترسه اگه دو تا از اعضایی که از هم متنفرن ، جفتشون به پارتی دعوت شن، ممکنه مست کنند و دعوا بشه. به خاطر همین نباید هیچ دو تا کسی که از هم متنفرن دعوت بشن. از طرف دیگه، مدیر می خواد اعتبار کلوپش رو حفظ کنه و برای این منظور، می خواد بیشترین تعداد افراد رو دعوت کنه.

یه برنامه بنویسید که بگه کی باید به پارتی دعوت بشه.

 

ورودی :

خط اوّل شامل متغیر n هست ( تعداد افراد عضو کلوپ )  . n خط بعدی هر کدوم دو تا عدد رو شامل می شه S_i و B_i .

خروجی :

در سطر اوّل از خروجی، تعداد بیشینه افرادی که باید به مهمونی دعوت بشند رو چاپ کنید. در خط بعدی، شماره اون افراد رو به ترتیبی که توی ورودی داده شده چاپ کنید. اگه چند تا پاسخ متفاوت وجود داشت ، یکیشون رو به دلخواه چاپ کنید.

 

پ.ن. 1: پارتی == مهمونی

پ.ن. 2: آقای هـ و آقای د همون آقای X و آقای Y هستن

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

 

---

راهنمایی :

از LIS استفاده کنید. ( اگه نمی دونید چیه تو ویکی پدیا سرچ کنید، یا تو Creative یا CLRS بخونید). بر اساس یکی از خصوصیات ، ورودی رو سورت کنید. بعد روی اون یکی خصوصیت LIS بزنید. ( البته در حین کد زدن، به یه سری مشکلات برمی خورین که الآن هر جوری فکر کردم نمی دونم چجوری بدون این که الگوریتم رو کامل بگم، این رو بگم ) .یعنی یه سری ریز کاری داره.

پ.ن. 1: کد LIS من شاید یه کمی با LIS ویکیپدیا تفاوت داشته باشه. عادت کردم اینطوری بزنم.

پ.ن. 2: من به انشاء خودم افتخار می کنم.

1 . کد ++C

2 . کد ++C

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

:)