Processing math: 100%

المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۱۰:عملی:سوال ۶

شبکه عصبی

یک شبکه عصبی را به صورت زیر تعریف کرده‌ایم:

گرافی با n مجموعه راس ana1‌که تعداد رئوس ai برابر ci‌است. رئوس ابتدا و انتهای هر یال گراف در دو دسته‌ی رئوس با شماره‌های متوالی قرار دارند. مثلا رئوس واقع در a1‌فقط می‌توانند به رئوس واقع در a2‌یال داشته باشند در حالی که رئوس واقع در a2‌ می‌توانند هم به رئوس a1 و هم به رئوس a3 متصل باشند. (دقت کنید بین رئوس واقع در یک مجموعه راسی، یالی وجود ندارد).

هدف آن است که تعداد مولفه‌های همبندی گراف فوق را بیابیم.

ورودي

در فایل ورودی ابتدا n و در سطر دوم مقادیر c1cn‌ نوشته شده است. سپس به ازای هر i بین ۲ و n، یک ماتریس با ci سطر و ci1 ستون از صفر و یک آمده است به گونه‌ای که درایه در سطر k‌ ام و ستون l‌ ام آن یک است اگر و تنها اگر بین راس k‌ ام از ai و راس l ام از ai1 یال باشد (تمامی یال‌ها بدون جهت هستند).

خروجي

در فایل خروجی تعداد مولفه‌های گراف داده شده را بنویسید. در ضمن فرض کنید که (n1000) و به ازای هر i بین ۱ و n داریم ci200.

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

ورودي نمونه خروجي نمونه
3
2 3 4
1 0
0 0
0 1
0 0 0
1 1 0
0 0 0
0 0 1
4

ابزار صفحه