+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۱۲۸ مگابایت ---------- زانا سالی یک بار یک جشن خاص برگزار می‌کند و تعدادی از دوستانش را به این جشن دعوت می‌کند. اسم این جشن «جشن هدیه‌ها» است! هر فردی که در این جشن شرکت می‌کند مقداری پول به همراه خود دارد و به تعدادی از دوستانش هدیه می‌دهد. روش هدیه دادن در این جشن کمی عجیب است! هر کدام از افراد یک لیست هدیه دارد که در آن لیست، نام تعدادی از دوستانش که در جشن شرکت کرده‌اند نوشته شده است و تمام پولی که همراه دارد را بین افراد این لیست به طور مساوی تقسیم می‌کند و این پول را به آنها هدیه می‌دهد! چون پول اعشاری (کوچکتر از یک) نداریم ، این تقسیم‌ها تقسیم صحیح هستند و اگر تقسیم پول بین اعضای لیست باقیمانده‌ای داشته باشد ، فرد هدیه دهنده این باقیمانده را برای خود نگه می‌دارد. به طور مثال اگر ساینا ۱۱ واحد پول داشته باشد و در لیست او فقط سه نفر باشند ، به هر کدام از آنها ۳ واحد پول میدهد و ۲ واحد از پول خود را برای خود نگه می‌دارد. حال شما برنامه‌ای بنویسید که پس از گرفتن اسامی شرکت کنندگان، مقدار پول اولیه‌ی هر کدام و لیست هدیه هر کس، مشخص کند که هرکسی چقدر سود یا زیان کرده است! # ورودی + خط 1 : عدد `n` که برابر است با تعداد شرکت کنندگان در جشن. + خط 2 تا `n+1` : در هر خط اسم یکی از شرکت کنندگان. + خط `n+1` الی آخر : از این خط به بعد ورودی به `n` دسته تقسیم می‌شود که هرکدام مطابق زیر است: خط اول نام فردی که قرار است هدیه بدهد. در خط دوم دو عدد می‌آید: عدد اول مقدار پول آن فرد، عدد دوم `(k)` تعداد افراد موجود در لیست هدیه‌ی آن فرد در `k` خط بعدی در هر خط نام یکی از افراد موجود در لیست هدیه‌ی آن فرد. می‌توانید فرض کنید نام هر دو نفر از افراد شرکت‌کننده در جشن متمایز است و $$ 2 \leq n \leq 10$$ # خروجی در خروجی باید `n` خط چاپ کنید که در هر ابتدای هر خط نام هر شخص و بعد از آن مقدار سود او آورده شود. (اگر آن شخص ضرر کرده است، باید منفی مقدار ضرر چاپ شود.) ترتیب نام‌ها در خروجی باید مانند ترتیب نام‌ها در خطوط `2` تا `n+1` ورودی باشد. # مثال ## ورودی نمونه ``` 5 dave laura owen vick amr dave 200 3 laura owen vick owen 500 1 dave amr 150 2 vick owen laura 0 2 amr vick vick 0 0 ``` ## خروجی نمونه ``` dave 302 laura 66 owen -359 vick 141 amr -150 ```

جشن هدیه‌ها

لوزی‌های ستاره‌ای

سیگماگیر

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۱۲۸ مگابایت ---------- چندی پیش سازمان اطلاعاتی جمهوری کره(ساجک) اعلام کرد با همکاری `SSIS(Sharif Security Intelligence Service` سازمان اطلاعات امنیت شریف، سیستم انتقال پیام `ETA`(گروهک تروریستی باسکی) را رمزگشایی کرده است. سیستم انتقال اطلاعات در این شبکه به طرز قابل تحسینی تر و تمیز و شگفت آور بود. این گروه براي انتقال یک متن، پس از انتقال **خود** کلمات پیام (که شیوه ي آن در این مسئله بررسی نمی شود)، **ترتیب و جایگشت آن ها** را تبدیل به یک رشته ي باینري می کرد که در عملیاتی ترین شرایط هم به سادگی قابل انتقال بود. (در آخرین مورد درگیري، جاسوس محاصره شده با دنباله اي از شلیک کردن/ نکردن با تفنگ خالیش، لو رفتن عملیات را به اعضاي گروهک خبر داد) در حقیقت، رشته ي باینري حاوي اطلاعات فرایند مرتب سازي ادغامی بر روي جایگشت اولیه و اصلی کلمات بود که در نهایت کلمات را به حالت مرتب شده در می آورد. گیرنده ي پیام، باید با مهندسی معکوس جایگشت اولیه از کلمات که در حقیقت اصل پیغام بوده را بازیابی می کرد. نحوه ي تولید رشته در شبه کد زیر توضیح داده شده است: ``` mergeSort(array a) array b = a.subarray (0, a.size / 2), array c = a.subarray(a.size() / 2, a.size()) mergeSort(b) mergeSort(c) a = merge(b, c) merge(array a, array b) do the famous merge method. in each step: if the element is chosen from a add '0' to the binary string else add 1 to the binary string ``` فرستنده در ابتدا تابع `mergeSort` را روي کل آرایه ي رشته ها (که همان متن اصلیست) صدا می زد و در نهایت با کد بالا، رشته‌ي دودویی مورد نظر تولید و آماده ي ارسال می گردد. کد رمزنگار رشته ها را هم با شیوه ي خاصی مقایسه و نهایتا مرتب می کرد. به این ترتیب که اگر یکی از رشته ها شامل زیررشته`moji` بود، زود تر از رشته ي دیگر می آید. کوچکی و بزرگی حروف مهم نیست؛ `MojI` یا `mOJI` هم همین طور هستند (کسی هنوز معناي دقیق این کلمه ي محلی را نمی داند!). اگر هر دو رشته این زیر دنباله را داشتند یا هر دو نداشتند رشته ها معمولی `(lexicographically)` مقایسه می شوند؛ به همان سیستمی که در لغتنامه ها لغت ها را مرتب می کنند. سازمان امنیت اطلاعات دانشگاه، بعد از رسانه اي کردن این موضوع براي بازیابی اطلاعات آرشیو شده از مکالمات رمزي این گروه، از شما یک برنامه ي رمزگشایی تقاضا کرده. شما باید با دریافت یک پیام رمزنگاري شده، اصل متن را بازیابی کنید. # ورودی در ورودی ابتدا عدد `n` تعداد رشته ها ، و سپس به همین تعداد رشته، و سپس رشته‌ی دودویی که باید رمزگشایی شود می‌آید. رشته‌ها شامل حروف کوچک و بزرگ انگلیسی هستند و تعداد آن‌ها حداکثر ۱۰۰۰۰۰ تاست. # خروجی در خروجی باید کلمات متن اصلی را هرکدام در یک خط چاپ کنید. # مثال ## ورودی نمونه ``` 7 ACSmojicLm mOJICVKnHLYJs NHCpGb uRcGD ZxMOjIC cUUbXcf RdEt 01110010101010010111 ``` ## خروجی نمونه ``` NHCpGb ACSmojicLm ZxMOjIC mOJICVKnHLYJs cUUbXcf RdEt uRcGD ```

گشایش رمز

+ محدودیت زمان: ۶ ثانیه + محدودیت حافظه: ۵۱۲ مگابایت ---------- شما بایستی از الگوریتم $A*$ برای حل مسئله راه‌بندان استفاده کنید. در این مسئله، یک خودروی قرمز رنگ به همراه چند خودروی دیگر در یک پارکینگ مشابه شکل پارک شده‌اند. می‌خواهیم با جابجا کردن خودرو‌‌ها، برای خودروی قرمز رنگ که بین سایر خودروها گرفتار شده است، راهی باز کرده و آن را از پارکینگ خارج نماییم. همه‌ی خودروها در این پارکینگ به صورت افقی و عمودی پارک شده‌اند. از آنجایی که اکنون امکان دور زدن وجود ندارد، خودروهایی که به صورت افقی قرار دارند تنها می‌توانند به چپ و راست حرکت کرده و خودروهای عمودی نیز فقط امکان بالا و پایین رفتن دارند. ![شکل](http://bayanbox.ir/view/5467912378468147959/parking.png) هدف این است که با کمترین تعداد حرکت، خودروی قرمز رنگ را که همواره به صورت افقی و روبروی درب خروجی (که در ضلع شرقی پارکینگ قرار دارد) پارک شده است، از پارکینگ خارج نماییم. در هر حرکت، یک خودرو می‌تواند در راستایی که قرار دارد به هر تعداد خانه دلخواه جابجا شود، مشروط بر اینکه با سایر خودروها و یا دیوار برخورد نکند. همچنین خارج کردن خودروهای دیگر به جز خودروی قرمز رنگ از پارکینگ مجاز نمی‌باشد. # ورودی ورودی شامل مشخصات پارکینگ و خودروهای پارک شده در آن به همراه موقعیت خودروی قرمز رنگ است. خط اول ورودی عدد $T$ است که تعداد پارکینگ‌ها را مشخص می‌کند. پس از آن مشخصات $T$ پارکینگ به صورت پشت سر هم در ورودی می‌آید. برای هر پارکینگ، در خط اول سه عدد $N$ ،$M$ و $V$ قرار دارد که به ترتیب تعداد سطرها و ستون‌های پارکینگ و تعداد خودروهای درون آن (شامل خودروی قرمز رنگ) را مشخص می‌کند. $V$ خط بعدی هر یک مشخصات یک خودرو را نشان می‌دهد. در هر خط، ابتدا دو عدد $R$ و $C$ قرار دارند که به ترتیب سطر و ستون قسمت بالا و سمت چپ خودرو را مشخص می‌کنند. در ادامه راستای خودرو با یک کاراکتر $h$ برای افقی و یا $v$ برای عمودی مشخص می‌شود. در انتهای خط نیز عدد $L$ طول خودرو را نشان می‌دهد. لازم به ذکر است که خانه بالای سمت چپ در سطر ١ و ستون ١ قرار داشته و خانه پایین سمت راست در سطر $N$ و ستون $M$ قرار دارد. ضمناً اولین خط از لیست مشخصات خودروها متعلق به خودروی قرمز رنگ است. نمونه ورودی متناسب با شکل در زیر آمده است. # خروجی به ازای هر پارکینگ، برنامه باید کمترین تعداد حرکات که منجر به خروج خودروی قرمز رنگ از پارکینگ می‌شود را چاپ کند. نمونه خروجی برای شکل در زیر آمده است. ## ورودی نمونه ``` 1 6 6 13 3 1 h 2 1 1 v 2 1 2 v 2 1 4 h 3 2 3 h 2 2 5 h 2 3 4 v 2 4 2 v 2 5 3 h 2 5 5 v 2 5 6 v 2 6 1 h 2 6 3 h 2 ``` ## خروجی نمونه ``` Test #1: 16 ```

مسئله راه‌بندان

مهد کودک شریف

طول و مجموع ارقام

مبنا

مثلث خیام

فرزاد بازی‌کن

حلزون مختصاتی

+ محدودیت زمان: ۶ ثانیه + محدودیت حافظه: ۵۱۲ مگابایت ---------- مسئله‌ای به شما داده شده است که بایستی به صورت یک مسئله $CSP$ آن را فرموله کرده و پیاده‌سازی نمایید. فرض کنید گرافی در اختیار داریم که گره‌های آن می‌توانند هر یک از اشکال مثلث، مربع، پنج ضلعی، شش ضلعی و یا دایره باشند. می‌خواهیم به هر گره از این گراف، یک عدد بین ١ تا ٩ نسبت دهیم به صورتی که شروط زیر برقرار باشند: + عدد منتسب به هر گره مثلثی شکل، برابر سمت چپ ترین رقم حاصل ضرب اعداد منتسب به گره‌های مجاور آن باشد. + عدد منتسب به هر گره به شکل مربع، برابر سمت راست ترین رقم حاصل ضرب اعداد منتسب به گره‌های مجاور آن باشد. + عدد منتسب به هر گره به شکل پنج ضلعی، برابر سمت چپ ترین رقم حاصل جمع اعداد منتسب به گره‌های مجاور آن باشد. + عدد منتسب به هر گره به شکل شش ضلعی، برابر سمت راست ترین رقم حاصل جمع اعداد منتسب به گره‌های مجاور آن باشد. + محدودیتی برای گره‌های دایره‌ای شکل وجود ندارد. شکل یک گراف نمونه با اعداد منتسب شده به هر گره را نشان می‌دهد. از شما خواسته شده است تا با دریافت مشخصات گراف، اعداد منتسب به گره‌های آن را پیدا کنید. ![شکل](http://bayanbox.ir/view/7841130710501802859/Untitled.png) # ورودی خط اول ورودی عدد $T$ است که تعداد تست‌ها را نشان می‌دهند. خط اول هر تست، شامل اعداد $V$ و $E$ است که اولی نشان دهنده تعداد گره‌ها و دومی نشان دهنده تعداد یال‌های گراف است. در خط بعد $V$ کاراکتر از بین یکی ͬاز کاراکترهای `T`برای مثلث، `S` برای مربع، `P` برای پنج ضلعی، `H` برای شش ضلعی و `C` برای دایره، که با یک فاصله از هم جدا شده‌اند می‌آید که کاراکتر $i$ام، شکل گره $i$ام را مشخص می‌کند (0 ≥ $i$). پس از آن، $E$ خط به صورت ‍‍`i j` می‌آید. که نشان می‌دهد یالی میان گره $i$ام و گره $j$ام وجود دارد. نمونه ورودی متناظر با شکل در ادامه آمده است. # خروجی به ازای هر تست، یک خط خروجی می‌آید که شامل $V$ عدد بین ١ تا ٩ است که با فاصله از هم جدا شده اند و عدد $i$ام، مقدار منتسب به گره $i$ام را نشان می‌دهد. # مثال ## ورودی نمونه ۱ ``` 1 9 8 C P H S S H H T C 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 ``` ## خروجی نمونه ۱ ``` 9 1 7 6 8 3 5 2 4 ```

مسئله گراف اعداد

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۱۲۸ مگابایت ---------- حالا که امتحان های میان ترم فرزاد تمام شده است و زمان بیشتری دارد، او به فکر کار افتاده است. پس از جستجوهای فراوان نهایتاً در شرکت دانیال اینا کاری به او داده شد. کار او به این صورت است که به او چند عدد صحیح می دهند که میزان سود یا ضرر شرکت در روزهای متوالی است. (واحد اعداد میلیون تومان است.) او باید بگوید بیشترین سود شرکت چقدر بوده است. مثلاً در روز اول به او این عددها را دادند: $1,2,-5,4,-3,2$. واضح است که بیشترین سود شرکت در چهارمین روز بوده است، که برابر ۴ میلیون تومان است. چون مجموع اعضای هر زیر آرایه دیگری از این آرایه داده شده، مقداری کوچک تر از ۴ دارد. دقت کنید که اگر همه اعداد، منفی (ضرر) بودند، میزان سود برابر ۰ است. برنامه‌ای بنویسید که فرزاد به وسیله آن بدون محاسبات ذهنی، کار خود را انجام دهد. # ورودی در خط اول ورودی تعداد روزهایی که قرار است سود و ضرر و در ادامه آرایه‌ی سود و ضررها در این روزها گرفته می‌شود. $$ 1 \le n \le 100$$ # خروجی در خروجی شما باید میزان بیشترین سود را بیان کنید. به ورودی و خروجی نمونه دقت کنید. # مثال ## ورودی نمونه ۱ ``` 12 7 -1 -2 1 5 -11 9 1 4 -1 3 -10 ``` ## خروجی نمونه ۱ ``` 16 ``` توضیح خروجی: بیشترین سود شرکت در روزهای ۷ تا ۱۱ است که مجموع اعداد شماره ۷ تا ۱۱ برابر ‍۱۶ است. ## ورودی نمونه ۲ ``` 5 -5 -2 -9 -1 -3 ``` ## خروجی نمونه ۲ ``` 0 ```

فرزاد کارکن

انتخابات ریاست جمهوری

دترمینان ماتریس‌ها

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- سرانجام هری‌پاتر توانست طلسم شکست دادن دشمن بزرگ خود مالفوی را ابداع کند! هری یک جفت دستبند قدرت دایره‌ای ساخته که روی مچ دست‌های راست و چپش بسته می‌شود. او روی هر دستبند دنباله‌ای از حروف جادویی نوشته است که هر حرف فعال قدرت او را تقریبا به اندازه یک بید کتک‌زن افزایش می‌دهد! با این حال یک مشکل وجود دارد. دستبندها فقط زمانی کار می‌کنند که زیردنباله حروف فعال شده روی هر دو دستبند یکسان باشد. برای مثال در شکل زیر یک جفت دستبند داده شده که حروف دو رشته $ababdcbcc$ و $aabdccccbd$ به عنوان حروف جادویی روی آنها قرار گرفته است که یک فعال‌سازی بهینه از این حروف به هری قدرتی به اندازه ۱۴ بید کتک‌زن می‌دهد. ![توضیح تصویر](http://bayanbox.ir/view/5916576924462676934/pic1.png) روی دستبند اول حروف $babdccc$ در جهت ساعت‌گرد و روی دستبند دوم همین حروف در جهت پادساعت‌گرد فعال شده است. بطور کلی ترتیب حروف مهم است اما جهت زیر دنباله فعال روی هر دستبند (در جهت عقربه‌های ساعت یا خلاف جهت) ممکن است یکسان باشد یا نباشد. فراموش نکنید که دستبندها دایره‌ای هستند! شما باید به هری کمک کنید که تصمیم بگیرد چه زیردنباله بهینه‌ای از حروف روی دستبندهایش را لازم است فعال کند تا بتواند مالفوی را شکست دهد. # ورودی فایل ورودی حداکثر شامل ۱۰۰ نمونه ورودی است. (حداکثر شامل ۵ نمونه بزرگ) هر نمونه یک خط شامل یک جفت رشته که با فاصله جدا شده اند و مربوط به همان دنباله حروف روی دستبندهای قدرت چپ و راست هری است (به ترتیب) می باشد و هر رشته تنها از حروف کوچک تشکیل خواهد شد. طول هر رشته ورودی بین $1$ تا $100$ کاراکتر است به جز در نمونه های بزرگ که طول هر رشته ورودی بین $1$ تا $1500$ کاراکتر می باشد. # خروجی حداکثر قدرتی که هری با فعال کردن حروف روی دستبندها می تواند برسد (بر حسب واحد بید کتک‌زن) را چاپ کنید. # مثال ## ورودی نمونه ``` ababdcbcc aabdccccbd harrypotter plorppothaa potterharry plorppothaa ``` ## خروجی نمونه ``` 14 12 12 ```

طلسم هری‌پاتر

اعداد هگزا دسیمال

انتقام از TA‌ سخت‌گیر

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- مبین خیلی عیدی دوست دارد! در یک مهمانی عمویش به او جدولی داد و گفت « هر چقدر `EYDI` در این جدول پیدا کنی به همان تعداد سکه به تو عیدی می‌دهم». در هر خانه‌ی جدول یکی از حروف `E, Y, D, I` نوشته شده است. روش بازی به صورت زیر است: + مبین در ابتدا در خانه شامل حرف `E` است. + خانه‌ای شامل حرف `Y` پیدا می‌کند که مجاور با خانه‌ی قبلی باشد. + خانه‌ای شامل حرف `D` پیدا می‌کند که مجاور با خانه‌ی قبلی باشد. + خانه‌ای شامل حرف `I` پیدا می‌کند که مجاور با خانه‌ی قبلی باشد. + یک سکه به دست می‌آورد! + خانه‌ای شامل حرف `E` پیدا می‌کند که مجاور با خانه‌ی قبلی باشد. سپس به گام دوم برمی‌گردد. اگر انجام هر یک از گام‌های بالا ممکن نباشد بازی به پایان می‌رسد. مبین از شما خواسته برنامه‌ای برای او بنویسید تا به کمک آن بیشترین سکه را به دست بیاورد. # ورودی در خط اول ورودی دو عدد `n`و `m` می‌آیند که به ترتیب تعداد سطرها و تعداد ستون‌های جدول هستند. `n` خط بعدی هر کدام شامل `m` حرف است، به این صورت که حرف `j`ام از `i`امین خط ($1 \leq j \leq m $ و $1 \leq i \leq n$) حرفی است که در خانه‌ی `(i,j)` از جدول قرار دارد. $$1 \le n, m \le 600$$ # خروجی اگر مبین نمی‌تواند سکه‌ای به دست بیاورد عبارت `!Poor Mobin` را چاپ کنید. اگر مبین می‌تواند نامتناهی سکه به دست بیاورد عبارت `!Poor Uncle` را چاپ نمایید. در غیر این صورت حداکثر تعداد سکه‌هایی را بنویسید که مبین می‌تواند به دست بیاورد. # مثال ## ورودی نمونه ۱ ``` 1 2 EY ``` ## خروجی نمونه ۱ ``` Poor Mobin! ``` ## ورودی نمونه ۲ ``` 2 2 DI YE ``` ## خروجی نمونه ۲ ``` Poor Uncle! ``` ## ورودی نمونه ۳ ``` 5 5 EYDIE EYDIY EYDID EEDII IIDYE ``` ## خروجی نمونه ۳ ``` 4 ```

عیدی

+ محدودیت زمان: ۳ ثانیه + محدودیت حافظه: ۵۱۲ مگابایت ---------- روزی از روزها، قرار شد که Quera برای رهنما مسابقاتی برگزار کند و از بین شرکت کنندگان تعدادی ستاره برگزیند و به رهنما معرفی کند. یکی از دوستان Quera با شنیدن چنین خبری سریعا به Quera رفت و پیشنهاد جالبی به آن‌ها داد! او گفت که می‌تواند تعدادی ستاره به Quera بدهد که دیگر نیازی به برگزاری مسابقه نباشد و Quera نیز طبعاً از این پیشنهاد بسیار استقبال کرد! پس از گذشت روزها، بالاخره این دوست ستاره‌ها را برای Quera فرستاد، اما این ستارگان با آنچه Quera انتظار داشت بسیار متفاوت بودند. او تعدادی عکس از ستارگان برای Quera‌ فرستاده بود! Quera پس از این اتفاق، خونسردی خود را حفظ کرد و تلاش کرد تهدیدها را تبدیل به فرصت‌ها کند؛ پس چالشی از روی این‌ها برای شما پدید آورد! شما باید برنامه‌ای بنویسید که با ورودی گرفتن این عکس‌ها، ستاره‌های داخل آن‌ را بیابد! در تست‌های این سوال ۸ عکس واقعی از آسمان وجود دارد که هرچه شما تعداد بیشتری ستاره بتوانید در این‌ها پیدا کنید، نمره‌ی بیشتری از این سوال می‌گیرید. به این شکل که در ورودی هر تست پیش از توصیف عکس، یک مقدار $expected$ آمده‌است که یعنی اگر شما حداقل به تعداد $expected$ ستاره در عکس بیابید، نمره‌ی تست را دریافت می‌کنید. هر عکس سه بار در تست‌ها آمده‌است که مقدار $expected$ در این سه تست تفاوت دارد. برنامه‌ی شما باید پس از دریافت عکس (توصیف دقیق فرمت تست‌ها را می‌توانید در بخش "ورودی" بیابید) تعداد ستاره‌هایی که پیدا کرده‌است را چاپ کند و سپس مختصات حداقل یک نقطه از هریک از این ستارگان را در خروجی بنویسد. سپس سیستم تعداد ستاره‌هایی که برنامه‌ی شما یافته‌ را بررسی می‌کند. اگر کمتر از ۷۵٪ تعدادی که برنامه‌ی شما ادعا کرده‌است ستاره شامل نقاط خروجی شما وجود داشت، برنامه‌ی شما نمره‌ی آن تست را دریافت نمی‌کند. برنامه‌ی شما کافیست ستارگانی را بیابد که با چشم عادی قابل تشخیص و تفکیک از هم هستند. تضمین می‌شود در ورودی‌ها، اندازه‌ی چنین ستارگانی بزرگتر از دیگر ستارگان باشند و در حقیقت تمایز ستارگان کوچکتر از هم با چشم انسان قابل تشخیص نباشد. برای مثال عکس زیر بخشی از یکی از عکس‌های موجود در تست‌ها است: ![ستاره‌ها ۱](http://bayanbox.ir/view/7308863370557304825/sample1.png) در این مثال تنها ۵ ستاره وجود دارد که شما باید آن‌ها را بیابید. یا برای مثال، در عکس زیر (که بازهم بخشی از یکی از عکس‌های تست‌ها است) ۱۲ ستاره وجود دارد که شما باید آن‌ها را بیابید: ![ستاره‌ها ۲](http://bayanbox.ir/view/9199682119511457755/sample2.jpg) (ورودی مثال این دو عکس و یک خروجی معتبرشان در نمونه‌های سوال آمده‌اند.) دقت کنید که لازم نیست تمام ستارگان با شرایط گفته‌شده را بیابید؛ شما کافیست به تعداد $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 ```