المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی انتخاب تیم:دوره ی ۴:سوال ۱

انجام کارها

در کارخانه‌ای دو ماشین یکسان برای انجام کارها وجود دارد. می‌خواهیم با استفاده از این دو ماشین $N$ کار داده شده را انجام دهیم. انجام کار $i$ ام، $t_i$ دقیقه از وقت یکی از ماشین‌ها را می‌گیرد و هیچ ماشینی نمی‌تواند در هر لحظه بیش از یک کار انجام دهد. هر یک از کارها نیز باید به طور کامل و بدون وقفه روی یکی از ماشین‌ها انجام شود.

مسئله به این صورت است: به چه ترتیبی این کارها انجام شوند که متوسط زمان ختم کارها کمینه گردد؟ ( زمان ختم هر کار مجموع زمان انتظار و زمان اجرای آن کار است.)

برنامه‌ای بنوسید که از فایل ورودی عددهای $N$ و $t_i$ ها را دریافت کرده، یک جواب برای این مسئله در فایل خروجی بنویسد. در سطر اول این فایل، متوسط زمان ختم کارها و در دو سطر بعدی ( به همان ترتیبی که کارها اجرا می‌شوند) کارهایی را که هر یک از ماشین‌ها باید انجام دهد بنویسید. $N$ عددی طبیعی و کم‌تر از ۱۰۰ است و $t_i$ ها عددهایی طبیعی هستند.

ورودي و خروجي نمونه

ورودي نمونه خروجي نمونه
5
2
5
2
4
3
‎5.0
Jobs for machine #1: 1 5 2
Jobs for machine #2: 3 4‎

ابزار صفحه