چهارتایی‌های نحس شام مرغ‌افکن
خوش‌بختانه، آقای کاف در کوله‌پشتی‌اش، سه جفت کفش ورزشی، مهمونی و پوتین داشت که سایزهایشان سه و چهار و پنج بود و … خلاصه آن‌ها از آن مخمصه جان سالم به‌درد بردند و قاضی هم که فکر می‌کرد آن کفش‌ها متعلق به سه تا سه‌قلواست، آن‌ها را بخشید و حتی برای دل‌جویی از دانش‌پژوهان، روز دستگیری آن‌ها را «روز مرگ بر سیب‌زمینی و تربچه» نامید!
با این وصف، قاضی چون حس می‌کرد ی.ا.د.ا.ک هنوز از موضوع زندان دل‌خور است، ترتیب ضیافت شام «مرغ‌افکن» (که در آن به هر یک از مهمانان یک مرغ شکم‌پُر شیرافکنی داده می‌شود) را به افتخار آن‌ها داد. ی.ا.د.ا.ک با فهمیدن موضوع، ابتدا مانند سایرین خیلی خوش‌حال شد، اما ناگهان فریاد کشید: «اوه… نه»!
ی.ا.د.ا.ک به سایرین گفت که خانه‌ی قاضی $k$ تا میز چهارنفره دارد و او همیشه دوست دارد مهمان‌هایش دور این میزها بنشینند. قاضی معتقد است اگر افراد $A$، $B$، $C$ و $D$ پشت یک میز بنشینند و سایز پاهای آن‌ها $P_A<P_B<P_C<P_D$ باشد، آن میز دقیقاً به میزان مجذور تفاضل شماره‌ی پای دو نفری که شماره‌ی پای‌شان در آن میز نه بیش‌ترین است و نه کم‌ترین یعنی دقیقاً $(P_B-P_C)^2$ واحد، بدیُمن می‌شود. از سوی دیگر، اگر قاضی ببیند که مجموع بدیُمنی تمام میزها، از یک حدّ خاص بیش‌تر شده‌است؛ فرمان قتل همه را صادر می‌کند!
می‌دانیم $1 \leq k \leq \lfloor\frac{n}{4}\rfloor$ است و سایز هر پای هریک از افراد حداکثر $n^3$ است. و دقیقاً $4k$ نفر باید به مهمانی قاضی بروند. با این وصف، الگوریتمی از زمان اجرای $O(nk)$ ارائه دهید که با داشتن مقدار $k$ و سایز پای هر یک از $n$ دانش‌پژوه، $4k$ نفری که قرار است به مهمانی بروند و نیز نحوه‌ی نشستن‌شان دور میزها را طوری مشخّص که مجموع بدیُمنی تمامی میزهاکمینه شده و نتیجتاً شانس نجات دانش‌پژوهان بیشینه شود. الگوریتم خود را تحلیل و اثبات کنید.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
