+ محدودیت زمان: ۳ ثانیه + محدودیت حافظه: ۵۱۲ مگابایت + منبع: انتخابی دوره اول رهنما کالج، Quera ---------- این سوال را با یک داستان شروع می‌کنیم و در نهایت به یک نتیجه‌ی اخلاقی می‌رسیم، باشد که به آن عمل کنید. در یک شب مهتابی، حسن و دوستانش در حال بازگشت از استخر دانشگاه بودند که ناگهان یکی از آن‌ها گشنه‌اش شد. گشنگی موضوعی نیست که بتوان به سادگی از کنار آن گذشت، اما چه راه‌کاری می‌توانستند برای آن بیابند؟ (همان ابتدا پیشنهاد دوغ و باقلوا مطرح شد ولی با مخالفت جدی مواجه شد، معلوم نیست چرا.) پس از مدتی تفکر برای یافتن چاره و سرگردانی در خیابان‌های شهر، خود را در مکانی نورانی دیدند که برایشان نا آشنا بود. فضا پر از رایحه‌های گوناگون بود و صدای موسیقی ملایمی می‌آمد. آن‌ها به سمت منبع نور رفتند و ناگهان با منظره‌ای عجیب مواجه شدند. منظره‌ای عجیب که همه‌ی آن‌ها با دیدن آن بهت‌زده، دقایقی را سر جای خود میخ‌کوب ماندند. آن منظره آن‌قدر عجیب بود که تا مدت‌ها از یادشان نرفت، و تا سالیان سال آن را برای دیگران تعریف می‌کردند. حال شما باید برنامه‌ای بنویسید که با ورودی گرفتن تعدادی عکس، ستاره‌های داخل آن‌ عکس‌ها را بیابد! در تست‌های این سوال ۸ عکس واقعی از آسمان وجود دارد که هرچه شما تعداد بیشتری ستاره بتوانید در این‌ها پیدا کنید، نمره‌ی بیشتری از این سوال می‌گیرید. به این شکل که در ورودی هر تست پیش از توصیف عکس، یک مقدار $expected$ آمده‌است که یعنی اگر شما حداقل به تعداد $expected$ ستاره در عکس بیابید، نمره‌ی تست را دریافت می‌کنید. هر عکس سه بار در تست‌ها آمده‌است که مقدار $expected$ در این سه تست تفاوت دارد. برنامه‌ی شما باید پس از دریافت عکس (توصیف دقیق فرمت تست‌ها را می‌توانید در بخش "ورودی" بیابید) تعداد ستاره‌هایی که پیدا کرده‌است را چاپ کند و سپس مختصات حداقل یک نقطه از هریک از این ستارگان را در خروجی بنویسد. سپس سیستم تعداد ستاره‌هایی که برنامه‌ی شما یافته‌ را بررسی می‌کند. اگر کمتر از ۷۵٪ تعدادی که برنامه‌ی شما ادعا کرده‌است ستاره شامل نقاط خروجی شما وجود داشت، برنامه‌ی شما نمره‌ی آن تست را دریافت نمی‌کند. برنامه‌ی شما کافیست ستارگانی را بیابد که با چشم عادی قابل تشخیص و تفکیک از هم هستند. تضمین می‌شود در ورودی‌ها، اندازه‌ی چنین ستارگانی بزرگتر از دیگر ستارگان باشند و در حقیقت تمایز ستارگان کوچکتر از هم با چشم انسان قابل تشخیص نباشد. برای مثال عکس زیر بخشی از یکی از عکس‌های موجود در تست‌ها است:  در این مثال تنها ۵ ستاره وجود دارد که شما باید آن‌ها را بیابید. یا برای مثال، در عکس زیر (که بازهم بخشی از یکی از عکس‌های تست‌ها است) ۱۲ ستاره وجود دارد که شما باید آن‌ها را بیابید:  (ورودی مثال این دو عکس و یک خروجی معتبرشان در نمونه‌های سوال آمده‌اند.) **دقت کنید که لازم نیست تمام ستارگان با شرایط گفته‌شده را بیابید؛ شما کافیست به تعداد $expected$ ستاره با این شرایط پیدا کنید و می‌توانید تا $\frac 4 3 $ تعداد کل ستارگان با شرایط گفته شده نقطه خروجی دهید. تضمین می‌شود بیش از $\lceil \frac 5 4 \rceil$ مقدار $expected$ در هر تست، ستاره با شرایط گفته شده یافت شود.** جهت تشخیص درست ستاره‌ها، تلاش کنید نقطه‌ای که در ستاره‌ی معرفی شده ارائه می‌دهید در گوشه‌های آن نباشد. (بعنوان مثال، می‌توانید مرکز ثقل شکل ستاره یافت‌شده را خروجی دهید!) # ورودی در سطر اول ورودی، سه عدد $h$ و $w$ و $expected$ آمده‌است که به ترتیب نمایانگر مقدار ارتفاع و عرض عکس ورودی و تعداد ستاره‌هایی که باید یافت شوند هستند. $$150 \le w, h \le 800$$ سپس در $h$ سطر بعدی، هر سطر رنگ $w$ نقطه‌ از تصویر توصیف شده‌است. توصیف هر نقطه بصورت $(r,\ g,\ b)$ می‌باشد که نمایانگر رنگ این نقطه در صورت نمایش بصورت `RGB` است. توصیف‌ نقاط با فاصله (space) از هم جدا شده‌اند. تضمین می‌شود در هریک از تست‌های داده شده، حداکثر ۵۰ ستاره با شرایط گفته شده وجود دارد. به ورودی‌های نمونه دقت کنید! # خروجی در سطر اول خروجی یک عدد $k$ چاپ کنید که نمایانگر تعداد ستاره‌هایی است که در عکس یافت شده‌اند. سپس در هریک از $k$ سطر بعدی، مختصات یکی از نقاط یکی از ستاره‌های یافت شده را خروجی دهید. هر مختصات باید بصورت $(h', w')$ باشد که یعنی این نقطه در سطر $h'$ توصیف عکس در ورودی سوال، نقطه‌ی $w'$امی بوده‌است که توصیف شده‌است. # مثال ## ورودی نمونه ۱ ورودی نمونه‌را می‌توانید در [اینجا](http://bayanbox.ir/view/8308334677184368854/sample1.txt) ببینید. ## خروجی نمونه ۱ ``` 5 13 23 78 139 25 60 67 61 103 130 ``` ## ورودی نمونه ۲ ورودی نمونه‌را می‌توانید در [اینجا](http://bayanbox.ir/view/3019360505981934109/sample2.txt) ببینید. ## خروجی نمونه ۲ ``` 12 83 160 22 147 88 137 175 229 15 290 144 172 136 119 147 179 47 98 111 97 163 284 154 278 ``` نکته اخلاقی: استخر زیاد برید، خیلی خوبه! :)

حل سؤال در بانک سؤالات