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

تیم بسکتبال دانشکده مدتی است که از دوران اوج خود خارج فاضله گرفته و به افول دچار شده است. کیانوش علت این امر را در دفاع خطی ۴تایی یا همان "سطحسطحسحطسطح" می‌داند. برای حل این مشکل او قصد دارد سیستم دفاع خطی ۶تایی یا "سطحسطحسحطسطحسطحسحط" را در تیم پیاده کند. در این سیستم بازیکنان مطابق شکل زیر در ۳۱ شش‌ضلعی مجاور چیده می‌شوند.

می‌دانیم شماره لباس هریک از اعضای تیم یکی از اعداد ۱ تا $k$ است و اگر دو نفر شماره لباس یکسان داشته باشند، به دلایل شخصی(!) دوست ندارند در یک سطر ( در هر یک از ۳ جهت ممکن) قرار بگیرند. هم‌چنین در هر یک از شش‌ضلعی‌های کوچک‌تر شامل ۷خانه که مرکز آن‌ها با خانه‌های سیاه مشخص شده است نیز نباید ۲ بازیکن با شماره لباس یکسان قرار بگیرند. (‌می‌توانید چند نمونه از سطرها و شش‌ضلعی‌های ۷ خانه‌ای را در دو شکل زیر ببینید.)

در شکل بالا منظور از سه جهت ممکن از سطرها مشخص شده.

در شکل بالا هردوتا از ۷ عدد موجود در شش‌ضلعی‌های دور یک‌ خانه سیاه و خودش باید متفاوت باشند.

هم‌چنین شماره لباس برخی از بازیکنان نیز از قبل مشخض شده است و غیرقابل تغییر است. حال کیانوش باید شماره لباس سایر دانشجویان را طوری تعیین کند که شرایط بالا برقرار باشد. هم‌اکنون کیانوش درگیر مذاکرات پیچیده با دانشجویان حول مبحث "نقض قوانین حق تکثیر و استفاده از عکس‌ شخصی وی به عنوان عکس پروفایل" است، پس از شما خواسته که یک چینش مناسب برای تیم ارائه کنید.

ورودی🔗

در خط اول ورودی عدد طبیعی $k$ آمده است: $1 \le k \le 31$ در خط بعدی ۳۱ عدد آمده است که عدد $i$ ام نشان‌دهنده این است که لباس دانشجوی خانه $i$ ام چه شماره‌ای دارد. اگر این عدد ۰ باشد، یعنی کیانوش می‌تواند لباس با هر شماره‌ای که میخواهد را به او بدهد.

تضمین می‌شود که ورودی طوری انتخاب می‌شود که حداقل یک شماره‌دهی مناسب وجود داشته باشد.

خروجی🔗

در تنها خط خروجی یک شماره‌دهی مناسب برای لباس افراد ارائه دهید. در صورت وجود چند خروجی متفاوت، یکی را به دل‌خواه خروجی دهید.

مثال🔗

ورودی نمونه🔗

8
1 0 0 3 0 0 0 0 4 0 0 0 0 0 5 0 0 0 0 0 0 0 0 0 0 6 0 0 0 0 0 

خروجی نمونه🔗

1 2 1 3 4 5 2 2 4 6 7 1 3 7 5 1 8 6 2 1 3 4 5 7 8 6 7 2 3 5 8 

خروجی مطابق مثال بالا را می‌توانید در شکل زیر مشاهده کنید:

• محدودیت زمان: ۳ ثانیه
• محدودیت حافظه: ۵۱۲ مگابایت
• منبع: انتخابی دوره اول رهنما کالج، 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'$امی بوده‌است که توصیف شده‌است.

مثال🔗

ورودی نمونه ۱🔗

ورودی نمونه‌را می‌توانید در اینجا ببینید.

خروجی نمونه ۱🔗

5
13 23
78 139
25 60
67 61
103 130

ورودی نمونه ۲🔗

ورودی نمونه‌را می‌توانید در اینجا ببینید.

خروجی نمونه ۲🔗

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

نکته اخلاقی: استخر زیاد برید، خیلی خوبه! :)

• محدودیت زمان: ۲.۵ ثانیه
• محدودیت حافظه: ۵۱۲ مگابایت
• منبع: IOI2013

دولف، که یک نقاش آماتور است، می‌خواهد در کلاس هنر ثبت‌نام کند. او شنبه در امتحان ورودی کلاس شرکت می‌کند؛ اما چون در کل هفته مشغول طرح سوال برای KAI Cup‌ بوده‌است، فرصت نکرده‌است که برای امتحان آماده شود. بنابراین شما باید به دولف کمک کنید که در امتحان ورودی کلاس قبول شود تا زحماتش بر باد نرود. آینده در دستان شماست، تا به دولف کمک کنید که در آکادمی هنر عضو شود و به یک هنرمند تبدیل شود.

آزمون ورودی متشکل از تعدادی نقاشی است که هر کدام از یکی از ۴ سبک زیر تبعیت می‌کنند:

۱)هنر مدرن نئوپلاستیک مانند:

۲)مناظر امپرسیونیست مانند:

۳)نقاشی‌های اکسپرسیونیست مانند:

۴)میدان رنگی یا کالر فیلد مانند:

شما باید با ورودی گرفتن نقاشی‌ها مشخص کنید که هر کدام به چه سبکی تعلق دارد. برای این کار، به شما یک نقاشی $H\times W$ به شکل سه آرایه دوبعدی با ابعاد $H\times W$ ورودی داده می‌شود -که هر آرایه نشان‌دهندهٔ یکی از سه مشخصهٔ $R$، $G$ و $B$ خانه‌های جدول است- و متناسب با آن باید سبک نقاشی را مشخص کنید.

ورودی🔗

ورودی تنها شامل یک خط است که در آن دو عدد طبیعی $H$ و $W$ با فاصله از هم آمده است. $1 \le H, W \le 500$ در $3H$ خط بعدی، در هر خط $W$ عدد می‌آید. اعداد $i$ام از سطرهای $j+1$، $j+H+1$ و $j+2H+1$ سه عدد مولفه‌های رنگی(RGB) پیکسل $i,j$ از نقاشی هستند.

خروجی🔗

در تنها خط خروجی باید یک عدد بین ۱ تا ۴ چاپ کنید که مشخص می‌کند که نقاشی ورودی به کدام سبک تعلق دارد.

نمره‌دهی🔗

تست‌های این سوال ۱۰۲ نقاشی از سبک‌های مختلف هستند. این تست‌ها به طور تصادفی به ۵۱ جفت تست تقسیم شده اند و اگر شما نمره‌ی هردو تست از یک جفت را دریافت کنید، نمره‌ی آن جفت را دریافت می‌کنید و اگر حداقل یکی از آن دو را اشتباه تشخیص دهید، نمره‌ی هیچ‌یک را دریافت نمی‌کنید. (پس شما نمی‌توانید با خروجی دادن تنها یک سبک برای همه‌ی تست‌ها ۱/۴ نمره را بگیرید!)

مثال🔗

در این فایل فشرده از هریک از ۴ سبک نقاشی ۹ عکس به همراه ورودی مناسب آن برای برنامه‌ی شما آمده است تا بتوانید برنامه‌ی خود را با آن‌ها تست کنید: لینک دانلود

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

لیتی، بنده‌ای از بندگان مخلص خداست که برای دور نشدن از یاد خدا به ریاضت روی آورده است و به سرزمینی دور مهاجرت کرده است، در این سفر به طور کاملا اتفاقی مهرسا و السا عاشق و دلباخته او می‌شوند. لیتی که بسیار بسیار داغ تر از این حرف هاست برای این دو دختر شرط ریاضت می‌گذارد و البته به هردو آن‌ها قول ازدواج می‌دهد، مهرسا و السا باید در هزار و یک روز طولانی با هم بازی عشق، آتش، خون را انجام بدهند.

در بازی عشق، آتش، خون در هر‌روز ابتدا هر نفر از حرکت روز قبل حریفش خبردار می‌شود و انتخاب امروزش را از میان عشق و آتش و خون برای لیتی می‌فرستد.

طبق افسانه‌ها می‌دانیم که عشق از آتش، آتش از خون و خون از عشق برتر است.

لیتی در روز $i$-ام پس از دریافت کردن انتخاب هر‌دو نفر ابتدا بزرگترین $j$ کوچکتر مساوی $i$ را پیدا می‌کند، به طوری که یا انتخاب روز $i$-ام مهرسا با انتخاب روز $j$-ام السا مخالف باشد، یا انتخاب روز $i$-ام السا با انتخاب روز $j$-ام مهرسا مخالف باشد. یعنی اگر در همان روز $i$-ام السا و مهرسا انتخاب‌های مختلفی کرده باشند $j$ برابر همان $i$ می‌شود، وگرنه به سراغ حرکت پیشین آن دو می‌رود. اگر حرکت پیشین السا با حرکت کنونی مهرسا یکسان بود و هم‌چنین حرکت پیشین مهرسا هم با حرکت کنونی السا یکسان بود، به سراغ حرکت قبلی آن می‌رود و ...

• سپس به مهرسا یک امتیاز می‌دهد در صورتی که انتخاب روز $i$-ام مهرسا از انتخاب روز $j$-ام السا برتر باشد.
• و به السا یک امتیاز می‌دهد در صورتی که انتخاب روز $i$-ام السا از انتخاب روز $j$-ام مهرسا برتر باشد.
• ( در ضمن اگر $j$ مورد نظر پیدا نشود هیچ کسی در آن روز امتیاز نمی‌گیرد )

در پایان این هزار و یک روز اگر امتیاز مهرسا بیشتر از امتیاز السا باشد، لیتی ابتدا با مهرسا ازدواج می‌کند و ازدواج او با السا به تعویق می‌افتد. و در صورتی که امتیاز السا بیشترمساوی امتیاز مهرسا شود ابتدا با السا ازدواج خواهد کرد. ( کمی ناعادلانه است متاسفانه، ولی چه کنیم؟ )

از شما خواسته شده تا به السا کمک کنید و او را راهنمایی کنید تا در هر‌روز چه چیزی برای لیتی بفرستد. ( واقعا از اولش هم این بی‌انصافی ها رواج داشت، دلیلش نامعلومه :/ )

یعنی شما باید برنامه‌ای بنویسید که بتواند استراتژی خوبی برای امتیاز زیادی گرفتن داشته باشد. این استراتژی می‌تواند به حرکات حریف هم مربوط باشد؛ یعنی شما می‌توانید فرض کنید که حریف هم یک برنامه‌ی کامپیوتری است که طبق یک استراتژی دارد با شما بازی می‌کند. برای مثال می‌توانید برنامه‌ای بنویسید که پس از هر مرحله تلاش کند استراتژی حریف را یاد بگیرد و در مراحل بعدی در مقابل حرکات وی خوب عمل کند! اما توجه کنید که ممکن است حریف هم تلاش کند که استراتژی شما را یاد بگیرد، و این‌جاست که سوال جذابیت خاص خود را می‌یابد! :)

پیاده سازی🔗

باید این سوال را به زبان C++ پیاده سازی کنید. دقت کنید که غالب دستورهای زبان C نیز در C++ پشتیبانی می‌شوند.

باید ‍riazat.h را در فایل ‍c++ خود include کنید.

** !! در فایل ارسالی شما نباید تابع int main() وجود داشته باشد !! **

شما باید دو تابع void init() و int next(int prev) را پیاده سازی کنید.

تابع void init() که شما می‌نویسید فقط یک‌بار در ابتدا توسط برنامه اصلی صدا زده می‌شود و شما می‌توانید در بدنه این تابع محاسبات یا پیش‌محاسباتی را که لازم دارید قبل از بازی انجام دهید

تابع int next(int prev) که شما می‌نویسید، به ازای هر‌روز یک‌بار صدا زده می‌شود که ورودی آن نشاندهنده حرکت قبلی حریف است ( اولین باری که تابع صدا زده می‌شود مقدار ورودی برابر -1 خواهد بود و در بقیه گام‌ها 0، 1 یا 2 خواهد بود. )

در پیاده سازی 0 به معنای عشق، 1 به معنای آتش و 2 به معنای خون می‌باشد.

بنابراین کدی که شما خواهید نوشت همانند کد زیر خواهد بود :

#include <bits/stdc++.h>
#include "riazat.h"

void init()
{
  /* YOUR CODE HERE */
}

int next(int previous_opponent_move)
{
  /* YOUR CODE HERE */
  //return 0;
}

توجه کنید که شما می‌توانید در هرجای دیگری از این فایل کد مورد نظر خود یا توابع مورد‌نظر خود را بنویسید، اما فقط توابع نامبرده شده از طرف برنامه اصلی صدا زده خواهند شد.

ورودی🔗

این سوال ورودی استاندارد ندارد و شما باید دو تابع ‍void init() و int next() را پیاده سازی کنید.

خروجی🔗

این سوال خروجی استاندارد ندارد و تنها خروجی برنامه شما مقادیر برگردانده شده توسط تابع int next() هستند.