- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
سه زیرشرکت کوئرا با نام‌های کالج، بوت‌کمپ و کانتست مراودات مالی دارند. جدول زیر میزان بدهی هر شرکت به شرکت دیگر را نشان می‌دهد. هر سلول جدول $A[i][j]$ نشان‌دهنده مبلغی است که شرکت $i$ به شرکت $j$ بدهکار است.
| کانتست | بوت‌کمپ | کالج | |
|---|---|---|---|
| $100$ | $200$ | $0$ | کالج |
| $50$ | $0$ | $300$ | بوت‌کمپ |
| $0$ | $0$ | $150$ | کانتست |
در مثال بالا بعد از ساده کردن حساب‌ها بوت‌کمپ ۱۵۰ به کالج بدهکار می‌شود.
هدف این است که حساب‌های مالی این سه شرکت را تا حد امکان ساده‌سازی کنیم. ساده‌سازی باید به دو روش اولویت‌بندی شده انجام شود:
- اولویت اول: کاهش مجموع پرداختی‌ها بین شرکت‌ها. یعنی باید مجموع مبالغی که شرکت‌ها به یکدیگر پرداخت می‌کنند کمینه شود.
- اولویت دوم: کاهش تعداد پرداخت‌ها. یعنی باید تعداد افرادی که پول پرداخت می‌کنند یا دریافت می‌کنند کمینه شود.
پس از ساده‌سازی، ممکن است برخی از پرداخت‌ها حذف یا تعدیل شوند تا مجموع بدهی‌ها و تعداد بدهکاران و بستانکاران کاهش یابد. نکته مهم این است که این ساده‌سازی نباید مجموع بدهی و طلب هر شرکت را تغییر دهد.
ورودی
ورودی شامل سه سطر است و هر سطر سه عدد دارد که نشان‌دهنده حساب‌های مالی بین این سه شرکت است. عدد $j$ام در سطر $i$ام برابر با $A[i][j]$ است و نشان می‌دهد که شرکت $i$ به شرکت $j$ چقدر بدهکار است.
$$1 \leq A[i][j] \leq 1,000,000$$
خروجی
در خروجی، باید جدول ساده‌شده را در سه سطر و هر سطر شامل سه عدد چاپ کنید که نشان‌دهنده وضعیت حساب‌های مالی بعد از ساده‌سازی است. باید دقت کنید که هیچ عدد منفی در جدول وجود نداشته باشد.
اگر چندین روش برای ساده‌سازی وجود دارد، یکی را به دلخواه چاپ کنید.
مثال‌ها
ورودی نمونه ۱
0 10000 1000
2000 0 45000
30000 7000 0
خروجی نمونه ۱
0 0 0
21000 0 9000
0 0 0
ورودی نمونه ۲
50000 10000 15000
0 20000 6000
2000 6000 0
خروجی نمونه ۲
0 10000 13000
0 0 0
0 0 0
ارسال پاسخ برای این سؤال