المپدیا

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

ابزار کاربر

ابزار سایت


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

مدارهای سری موازی

یک مدار الکتریکی سری موازی نامیده می‌شود، اگر بتوان آن را با اتصال سری و موازی قطعات به هم به‌دست آورد. به دست آوردن مقاومت این مدارها به سادگی امکان‌پذیر است، در حالی که این کار در مدارهای کلی همیشه ساده نیست.

هر مدار الکتریکی را می‌توانیم با گرافی مانند $G$ و دو راس $s$ و $t$‌از آن به عنوان دو سر مدار مشخص کنیم. در این صورت، گراف سری موازی را می‌توان به صورت بازگشتی به این صورت تعریف کرد:

  • گراف $K_2$ یک گراف سری موازی است و دو سر آن دو راس آن هستند. مقاومت این مدار برابر ۱ است.(شکل بالا «الف» را ببینید.)
  • اگر گراف‌های $G_1$ و $G_2$ سری موازی باشند و رئوس $s_1$ و $t_1$ و $s_2$ و $t_2$ به ترتیب دو سر آن‌ها باشند، گرافی که مانند شکل بالا «ب» از وصل کردن رئوس $t_1$ و $s_2$ با یک یال به‌دست می‌آید نیز یک گراف سری موازی است که $s_1$‌و $t_2$ دو سر آن هستند. اگر مقاومت $G_1$ و $G_2$ به ترتیب برابر $R_1$ و $R_2$ باشد، مقاومت این مدار $R_1 +R_2$ است.
  • اگر گراف‌های $G_1$ و $G_2$‌ با رئوس $s_1$ و $t_1$ و $s_2$ و $t_2$ به عنوان دو سر آن‌ها، سری موازی باشند، گرافی که مانند شکل بالا «ج» از افزودن دو راس $s$ و $t$ و متصل کردن $s$ به $s_1$ و $s_2$ و $t$ به $t_1$ و $t_2$ به دست می‌آید نیز یک گراف سری موازی است و $s$ و $t$ دو سر آن هستند. اگر مقاومت $G_1$ و $G_2$، به ترتیب، برابر $R_1$ و $R_2$ باشد، مقاومت این مدار برابر $\frac{1}{\frac{1}{R_1}+ \frac{1}{R_2}}$ است.

ورودي

برنامه‌ای بنویسید که از سطر اول فایل ورودی، به ترتیب تعداد رئوس، تعداد یال‌ها و شماره‌ی رئوس دو سر مدار و از سطرهای بعد لیست یال‌های یک گراف را دریافت کرده، مشخص کند که آیا این گراف سری موازی است یا خیر و اگر سری موازی بود مقاومت آن را تعیین کند.

خروجي

اطلاعات در فایل خروجی به این صورت ذخیره می‌شود: در سطر اول این فایل، سری موازی بودن مدار را با یکی از پیغام‌های Serial-parallel یا Not Serial-parallel مشخص کنید و در سطر دوم فایل، اگر مدار سری موازی بود، عددی حقیقی بنویسید که نشان‌دهنده‌‌ی مقاومت مدار است.

فرض کنید که تعداد رئوس و تعداد یال‌های گراف به ترتیب از ۵۰ و ۵۰۰ بیش‌تر نیست. به مثال زیر توجه کنید. مدار ورودی این مثال در شکل زیر نشان داده شده است.

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

ورودي نمونه خروجي نمونه
10 11 1 4 $ \quad$ –> 7 6
1 2 $\quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad$ 7 8
2 3 $\quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad$ 6 5
3 4 $\quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad$ 8 9
4 5 $\quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad$ 9 10
1 8 $\quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad$ 10 5
–>
‎Is serial-parallel
0.66‎

ابزار صفحه