====== چهارتایی‌های نحس شام مرغ‌افکن ======
خوش‌بختانه، آقای کاف در کوله‌پشتی‌اش، سه جفت کفش ورزشی، مهمونی و پوتین داشت که سایزهایشان سه و چهار و پنج بود و ...‎
خلاصه آن‌ها از آن مخمصه جان سالم به‌درد بردند و قاضی هم که فکر می‌کرد آن کفش‌ها متعلق به سه تا سه‌قلواست، آن‌ها را بخشید و حتی برای دل‌جویی از دانش‌پژوهان، روز دستگیری آن‌ها را ‎«روز مرگ بر سیب‌زمینی و تربچه‎» نامید‎!‎

با این وصف، قاضی چون حس می‌کرد ‎ی.ا.د.ا.ک هنوز از موضوع زندان دل‌خور است، ترتیب ضیافت شام «مرغ‌افکن» (که
در آن به هر یک از مهمانان یک مرغ شکم‌پُر شیرافکنی داده می‌شود) را به افتخار آن‌ها
داد. ‎‎ی.ا.د.ا.ک ‎با فهمیدن موضوع، ابتدا مانند سایرین خیلی خوش‌حال شد، اما ناگهان فریاد کشید: ‎«اوه... نه»‎!

ی.ا.د.ا.ک‎ به سایرین گفت که خانه‌ی قاضی ‎$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$‎ نفری که قرار است به مهمانی بروند و نیز نحوه‌ی نشستن‌شان دور میزها را طوری مشخّص که مجموع بدیُمنی تمامی میزهاکمینه شده و نتیجتاً شانس نجات دانش‌پژوهان بیشینه شود. الگوریتم خود را تحلیل و اثبات کنید‎.
  * [[سوال ۱۴|سوال بعد]]
  * [[سوال ۱۲|سوال قبل]]