- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
در یک شرکت تاکسیرانی $n$ تاکسی در یک صف و $4n$ نفر در صفی دیگر قرار دارند. افراد صف به ترتیب سوار جلوترین تاکسی می‌شوند و هر تاکسی که پر شود (۴ نفر سوار آن شوند) بلافاصله حرکت می‌کند.
هر تاکسی دو قسمت دارد. صندلی جلو که دقیقاً یک مسافر سوار می‌شود و صندلی‌های عقب که دقیقاً ۳ مسافر سوار می‌شوند. همچنین لازم به ذکر است مسافران تنها از درِ سمت راست قادر به سوار شدن یا پیاده شدن در صندلی‌های عقب هستند.
شهر، یک خیابان اصلی دارد و ۱۰۱ ایستگاه با شماره‌های ۰ تا ۱۰۰ به ترتیب روی خیابان قرار دارند. ایستگاه ۰ همان شرکت تاکسیرانی است و مقصد هر شخص یکی از ایستگاه‌های ۱ تا ۱۰۰ است. هر تاکسی از ایستگاه ۰ شروع کرده و به سمت ایستگاه ۱۰۰ می‌رود و هر وقت به مقصد یکی از مسافران می‌رسد توقف می‌کند. از آنجایی که فقط درِ سمت راست امکان باز شدن دارد، وقتی شخصی از صندلی‌های عقب می‌خواهد در مقصد خود پیاده شود افرادی که سمت راست او هستند هم مجبور به پیاده شدن می‌شوند و این باعث ناراحتی آن‌ها می‌شود.
به طور دقیق‌تر میزان ناراحتی افراد یک تاکسی برابر با تعداد دفعاتی است که آن‌ها در ایستگاهی به جز مقصد خود پیاده شده‌اند. توجه کنید یک فرد ممکن است چند بار ناراحت شود و هربار میزان ناراحتی‌اش زیاد می‌شود.
هر شخص در زمان سوار شدن یا در صندلی جلو می‌نشنید یا از درِ راست وارد صندلی‌های عقب می‌شود و در چپ‌ترین صندلی خالی می‌نشیند. حال شرکت تاکسیرانی از شما می‌خواهد با دانستن مقاصد ۴ نفر مسافر هر تاکسی، تعیین کنید در هر تاکسی کدام شخص جلو بنشیند تا مجموع میزان ناراحتی افراد کمینه شود.
برای درک بیشتر، به توضیحات مثال‌ها مراجعه کنید.
ورودی
در سطر اول ورودی $n$ تعداد تاکسی‌ها می‌آید و در $4 \times n$ سطر بعد $d_i$ مقصد فرد $i$ام می‌آید. $$ 1 \le n \le 20 , 000$$ $$ 1 \le d_i \le 100$$
خروجی
در سطر $i$ام کمینه مجموع ناراحتی افراد تاکسی $i$ام خروجی داده شود.
مثال
ورودی نمونه ۱
3
1
1
1
1
2
1
1
2
3
1
4
2
خروجی نمونه ۱
0
0
1
در تاکسی اول ۴ نفر با مقصد یکسان سوار می‌شوند و در تمام حالات سوار شدن هیچ کس ناراحت نمی‌شود.
در تاکسی دوم افراد به ترتیب با مقصدهای ۲ و ۱ و ۱ و ۲ قرار است سوار شوند و اگر سه نفر اول به ترتیب عقب بنشینند و نفر آخر جلو بنشیند آنگاه هیچ ناراحتی وجود نخواهد داشت. چون در ایستگاه ۱ دو نفری که آخر از همه سوار شده‌اند پیاده می‌شوند و در ایستگاه ۲ هم دو نفر دیگر پیاده می‌شوند.
در تاکسی سوم اگر فرد با مقصد ۱ جلو بنشیند و افراد با مقصدهای ۳ و ۴ و ۲ به ترتیب عقب سوار شوند مجموع میزان ناراحتی ۱ است و می‌توان برسی کرد حالتی با ۰ ناراحتی وجود ندارد. ابتدا در ایستگاه ۱ فرد با مقصد ۱ که جلو نشسته است پیاده می‌شود. در ایستگاه ۲ نیز همینطور فرد ۲ بدون ایجاد ناراحتی پیاده می‌شود. اما در ایستگاه ۳ چون فرد ۴ بعد از فرد ۳ عقب نشسته پس به در نزدیک‌تر است و مجبور است برای نفر ۳ یکبار پیاده و دوباره سوار شود و ۱ ناراحتی به وجود می‌آید.
ارسال پاسخ برای این سؤال