پرداخت بدهی
وضعیت اقتصادی خراب شده است و به دلیل کمبود پول در گردش اعتبار بسیاری از کارخانجات مقروض شده‌اند و توانایی پرداخت بدهی خود را ندارند. حداکثر ۱۰۰ کارخانه موجود است.
کارخانه‌ها هم فروشنده و هم خریدارند؛ آن‌ها محصولات خود را می‌فروشند و مواد اولیه می‌خرند. بنابراین آن‌ها به هم قرض دارند. فردی ایده‌ی جدیدی به ذهنش رسید تا کارخانه‌ها قرض را با قرض پرداخت نمایند.
به عنوان مثال، فرض کنید کارخانه $A$، ۱۰۰ دلار به کارخانه‌ی $B$، ۵۰ دلار به کارخانه‌ی $C$ و کارخانه‌ی $C$، ۷۵ دلار به کارخانه‌ی $A$ مقروض است. مجموع این قرض‌ها ۲۲۵ دلار است. $A$ از اعتباری که نزد $C$ دارد استفاده می‌کند تا قسمتی از قرض خود را به $B$ بپردازد. با این کار قرض‌ها به صورت زیر در می‌آیند.
$$A \quad to \quad B \quad $25 $$ $$B \quad to \quad C \quad $50 $$
$$C \quad to \quad B \quad $75 $$ با تکرار این عمل می‌توان مجموع قرض‌ها را به حداقل رساند؛ لیست قرض‌ها به صورت زیر در می‌آید. $$ A \quad to \quad B \quad $25 $$
$$ C \quad to \quad B \quad $25 $$
برنامه‌ای بنویسید تا بدهی کارخانه‌ها را به این صورت پرداخت نماید.
- لیست قرض‌ها را از فایل ورودی بخوانید و این ارقام را در فایل خروجی کارخانه و مقدار قرضی که کارخانه‌ی اول به دومی دارد. ورودی شامل لیست‌های مختلفی است که با یک سطر خالی از هم جدا شده‌اند، چنان که در مثال مشاهده می‌شود.
- لیست قرض‌ها را مجددا بازسازی کنید تا مجموع قرض کارخانه‌ها کمینه شود. لیست جدید را به همان قالب فایل ورودی در فایل خروجی بنویسید.
- مجموع کل قرض‌ها را در انتهای فایل خروجی بنویسید.
به مثال زیر توجه کنید.
ورودي و خروجي نمونه
| ورودي نمونه | خروجي نمونه |
|---|---|
| A B 100.00 B C 50.00 C A 75.00 A B 1500.00 B C 1100.00 D A 1400.00 | A B 100.00 B C 50.00 C A 75.00 total = \$225.00 A B 25.00 C B 25.00 total = \$50.00 A B 1500.00 B C 1100.00 D A 1400.00 total = \$4000.00 A B 100.00 D B 300.00 D C 1100.00 total = \$1500.00 |
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
