- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
در زبان برنامهنویسی گولنگستان متغیرها حافظههای ۱، ۲، ۳ یا ۴ بایتی دارند. وقتی یک شئ با \(n\) متغیر به حجمهای \(s_1, s_2, \dots, s_n\,\) تعریف میکنیم. حافظهها با قاعدهی زیر در بستههای ۴ بایتی، پشت سرهم قرار میگیرند.
متغیرها را به ترتیب اضافه میکنیم. اگر متغیری که نوبت اضافه شدن آن است، به انتهای بستهی قبلی میتواند اضافه شود، آن را اضافه میکنیم و به سراغ متغیر بعدی (در صورت وجود) میرویم. اما اگر این متغیر نمیتواند به انتهای بستهی آخر اضافه شود، همهی فضای خالی آن را رها میکنیم و آن بسته را میبندیم (اصطلاحاً به این حافظههای تلف شده padding space میگویند). سپس در یک بستهی ۴ بایتی جدید، حافظه مورد نیاز متغیر بعدی را به بایتهای اول آن اختصاص میدهیم.
برای مثال فرض کنید \(n = 3\) متغیر داشته باشیم: \(s_1 = 1\)، \(s_2 = 4\) و \(s_3 = 1\). در این صورت متغیر \(s_1\) در ابتدای یک بسته قرار میگیرد، چون متغیر \(s_2\) را نمیتوان به همان بسته اضافه کرد، پس ۳ بایت باقیماندهی بستهی اول را padding space در نظر میگیریم. سپس متغیر \(s_2\) را در یک بستهی جدید قرار داده و در نهایت \(s_3\) را در بایت اول یک بسته قرار میدهیم. (در آخرین بسته padding space نداریم.)
به این ترتیب وضعیت نوار حافظه به صورت زیر خواهد بود و در مجموع ۳ حافظه تلف شده خواهیم داشت.
حال میدانیم اگر ترتیب این سه متغیر را به این صورت که \(s_1 = 4\)، \(s_2 = 1\) و \(s_3 = 1\) عوض میکردیم. وضعیت نوار حافظه به این صورت تغییر میکرد و هیچ حافظهای تلف نمیشود.
حال به شما ترتیب اولیه حافظه متغیرها داده میشود از شما میخواهیم ترتیب آنها را طوری تغییر دهید که حافظههای تلف شده (padding space) کمینه شود و در نهایت این کمینه مقدار را چاپ کنید.
ورودی
در سطر اول ورودی، عدد صحیح و مثبت \(t\) آمده که تعداد سناریوها را نشان میدهد.
\[1 \leq t \leq 1000\]
در سطر اول هر سناریو، عدد صحیح \(n\) که نشان دهندهی تعداد متغیرها است داده میشود.
\[1 \leq n \leq 100\]
در سطر دوم هر سناریو، \(n\) عدد صحیح که مقدار حافظهی متغیرها یعنی \(s_1, s_2, \dots, s_n\,\) را نشان میدهد.
\[1 \leq s_i \leq 4\]
خروجی
در \(t\) سطر برای هر سناریو، کمینه حافظهی تلف شده (padding space) در بین تمام ترتیبهای مختلف برای متغیرها را چاپ کنید.
مثالها
ورودی نمونه ۱
4
3
1 4 1
4
4 2 3 4
1
1
5
3 3 3 3 3
خروجی نمونه ۱
0
1
0
4
سناریو اول در صورت سوال توضیح داده شده.
یک نمونه از ترتیب بهینه، برای سناریو دوم، با ۱ حافظه تلف شده، به صورت زیر است:
تنها ترتیب ممکن، برای سناریو سوم، با ۰ حافظهی تلف شده، به صورت زیر است:
تنها ترتیب ممکن، برای سناریو چهارم، با ۴ حافظهی تلف شده، به صورت زیر است:
ارسال پاسخ برای این سؤال