المپدیا

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

ابزار کاربر

ابزار سایت


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

فهرست مندرجات

پیچ‌ها

$N$ عدد پیچ به شماره‌های ۱، ۲، … و $N$ داده شده‌اند. این پیچ‌ها با تعدادی کش به هم وصل شده‌اند. فرض کنید پیچ $i$ ام با $m_{ij}$ عدد کش به پیچ $j$ ام $(i\ne j)$ وصل شده است $(0\leq m_{ij} \leq 10)$. می‌خواهیم این پیچ‌ها را به ترتیبی روی یک خط راست به تکه چوبی فرو کنیم تا حداکثر تعداد کش‌هایی که از هر نقطه واقع بر این خط می‌گذرد کمینه شود. طول ابتدایی کش‌ها کم است و به اندازه‌ی دل‌خواه قابل کشیده شدن هستند. همچنین فرض کنید که قطر پیچ و کش‌ها صفر هستند.

برنامه‌ای بنویسید که با دریافت $N$ و $m_{ij}$ ها ترتیب قرار گرفتن پیچ‌ها را به‌دست آورد.

ورودي

در سطر اول فایل ورودی، $N$ و در سطرهای دوم به بعد، در هر سطر $i$ و $j$ و $m_{ij}$ آمده است. فرض کنید $N$ حداکثر ۵۰ است.

خروجي

در سطر اول فایل خروجی ترتیب قرار گرفتن پیچ‌ها (از چپ به راست) و در سطر دوم حداکثر تعداد کش‌هایی که از یک نقطه می‌گذرد چاپ می‌شود.


ابزار صفحه