سلام دوست عزیز😃👋

به آزمون ورودی کارآموزی تابستانه Software Engineering کداستار خوش آمدید!

مسابقه به مدت ۵ ساعت ادامه خواهد داشت و در مجموع شامل ۵ سوال است.

  • ۳ سوال اول الگوریتمی
  • ۲ سوال آخر پیاده‌سازی

سوالات به گونه‌ای تنظیم شده‌اند که با توجه به دانشی که دارید بتوانید بخشی از نمره‌ی سوال را بگیرید. به عنوان مثال اگر نتوانید سوال دوم را به طور کامل حل کنید، این امکان وجود دارد که بتوانید بخشی از آن را حل کنید؛ بنابراین حتما به تمام سوالات مراجعه کنید.

لینک‌های مفید برای شرکت در مسابقه:

موفق باشید 😉✌

تاکسی‌ها


  • محدودیت زمان: ۱ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

در یک شرکت تاکسیرانی nn تاکسی در یک صف و 4n4n نفر در صفی دیگر قرار دارند. افراد صف به ترتیب سوار جلوترین تاکسی می‌شوند و هر تاکسی که پر شود (۴ نفر سوار آن شوند) بلافاصله حرکت می‌کند.

هر تاکسی دو قسمت دارد. صندلی جلو که دقیقاً یک مسافر سوار می‌شود و صندلی‌های عقب که دقیقاً ۳ مسافر سوار می‌شوند. همچنین لازم به ذکر است مسافران تنها از درِ سمت راست قادر به سوار شدن یا پیاده شدن در صندلی‌های عقب هستند.

شهر، یک خیابان اصلی دارد و ۱۰۱ ایستگاه با شماره‌های ۰ تا ۱۰۰ به ترتیب روی خیابان قرار دارند. ایستگاه ۰ همان شرکت تاکسیرانی است و مقصد هر شخص یکی از ایستگاه‌های ۱ تا ۱۰۰ است. هر تاکسی از ایستگاه ۰ شروع کرده و به سمت ایستگاه ۱۰۰ می‌رود و هر وقت به مقصد یکی از مسافران می‌رسد توقف می‌کند. از آنجایی که فقط درِ سمت راست امکان باز شدن دارد، وقتی شخصی از صندلی‌های عقب می‌خواهد در مقصد خود پیاده شود افرادی که سمت راست او هستند هم مجبور به پیاده شدن می‌شوند و این باعث ناراحتی آن‌ها می‌شود.

به طور دقیق‌تر میزان ناراحتی افراد یک تاکسی برابر با تعداد دفعاتی است که آن‌ها در ایستگاهی به جز مقصد خود پیاده شده‌اند. توجه کنید یک فرد ممکن است چند بار ناراحت شود و هربار میزان ناراحتی‌اش زیاد می‌شود.

هر شخص در زمان سوار شدن یا در صندلی جلو می‌نشنید یا از درِ راست وارد صندلی‌های عقب می‌شود و در چپ‌ترین صندلی خالی می‌نشیند. حال شرکت تاکسیرانی از شما می‌خواهد با دانستن مقاصد ۴ نفر مسافر هر تاکسی، تعیین کنید در هر تاکسی کدام شخص جلو بنشیند تا مجموع میزان ناراحتی افراد کمینه شود.

برای درک بیشتر، به توضیحات مثال‌ها مراجعه کنید.

ورودی🔗

در سطر اول ورودی nn تعداد تاکسی‌ها می‌آید و در 4×n4 \times n سطر بعد did_i مقصد فرد iiام می‌آید. 1n20000 1 \le n \le 20 \, 000 1di100 1 \le d_i \le 100

خروجی🔗

در سطر iiام کمینه مجموع ناراحتی افراد تاکسی iiام خروجی داده شود.

مثال🔗

ورودی نمونه ۱🔗

3
1
1
1
1
2
1
1
2
3
1
4
2
Plain text

خروجی نمونه ۱🔗

0
0
1
Plain text

در تاکسی اول ۴ نفر با مقصد یکسان سوار می‌شوند و در تمام حالات سوار شدن هیچ کس ناراحت نمی‌شود.

در تاکسی دوم افراد به ترتیب با مقصدهای ۲ و ۱ و ۱ و ۲ قرار است سوار شوند و اگر سه نفر اول به ترتیب عقب بنشینند و نفر آخر جلو بنشیند آنگاه هیچ ناراحتی وجود نخواهد داشت. چون در ایستگاه ۱ دو نفری که آخر از همه سوار شده‌اند پیاده می‌شوند و در ایستگاه ۲ هم دو نفر دیگر پیاده ‌می‌شوند.

در تاکسی سوم اگر فرد با مقصد ۱ جلو بنشیند و افراد با مقصدهای ۳ و ۴ و ۲ به ترتیب عقب سوار شوند مجموع میزان ناراحتی ۱ است و می‌توان برسی کرد حالتی با ۰ ناراحتی وجود ندارد. ابتدا در ایستگاه ۱ فرد با مقصد ۱ که جلو نشسته است پیاده می‌شود. در ایستگاه ۲ نیز همینطور فرد ۲ بدون ایجاد ناراحتی پیاده ‌می‌شود. اما در ایستگاه ۳ چون فرد ۴ بعد از فرد ۳ عقب نشسته پس به در نزدیک‌تر است و مجبور است برای نفر ۳ یکبار پیاده و دوباره سوار شود و ۱ ناراحتی به وجود می‌آید.

ارسال پاسخ برای این سؤال
در حال حاضر شما دسترسی ندارید.