سوال ۶۴ کنکور ارشد مهندسی کامپیوتر ۱۴۰۰

یک ماتریس ۶۴ در ۶۴ داریم که درایه‌های آن همه ۰ یا ۱ هستند. می‌خواهیم این ماتریس را به‌صورت مارپیچی مرتب کنیم، یعنی اگر در انتها، سطر اول از راست به چپ به سطر دوم از راست به چپ و … بچسبانیم یک آرایهٔ ۴۰۹۶ تایی مرتب از ۰ و ۱ خواهیم داشت. ادعا می‌کنیم الگوریتم زیر این کار را انجام می‌دهد. $k$ بار تکرار کن:

‫a‪.‬ همهٔ سطرها را مستقلاً و در جهت خود مرتب کن، یعنی سطرهای فرد را از چپ به راست، سطرهای زوج را از راست به چپ مرتب کن.

‫b‪.‬ همهٔ ستون‌ها را از بالا به پایین مرتب کن.

کم‌ترین مقدار $k$ در بدترین حالت چند است؟