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

Bear

در یک قفس دایره شکل به شعاع ‎$R$‎، ‎$n$‎ خرس خوابیده‌اند. رئیس باغ‌وحش قصد دارد یک سری دیوار در این قفس بسازد تا خرس‌ها به دسته‌های حداکثر ‎$k$‎ تایی دسته بندی شوند. زیرا اگر در هنگام بیدار شدن آن‌ها، بیش از ‎$k$‎ تا خرس در یک اتاق باشند، با هم دعوا می کنند. دورتادور قفس دقیقاً ‎$360$‎ تا میله با فواصل مساوی چیده شده است . میله‌ی صفرم روی نقطه‌ی ‎$(R,0)$‎ و مرکز قفس هم در ‎$(0,0)$‎ می‌باشد. شماره‌ی میله‌ها از ‎$0$‎ تا ‎$359$‎ است و درجهت پادساعت گرد افزایش می یابد. به عبارت دیگر میله‌ی ‎$i$‎ام در امتداد ‎$i$‎ درجه از مرکز (نسبت به میله ی صفرم) قرار دارد. تمام دیوارها باید بین دو میله به صورت خطی مستقیم کشیده شوند و تضمین شده که نمی‌توان دیواری کشید که از روی یک خرس عبور کند (هیچ خرسی روی خط واصل بین دو میله قرار ندارد). از طرفی دیوارها نباید در هیچ نقطه‌ای به جز در نقاط انتهایی اشتراک داشته باشند و نباید یک‌دیگر را قطع کنند. رئیس باغ‌وحش یک شرط دیگر هم می‌گذارد و آن این است که هیچ یک از اتاق‌های پدید آمده، بیش از سه گوشه نداشته باشد (چه خرسی در آن اتاق باشد و چه نباشد). برای نمونه به شکل‌های زیر توجه کنید:

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

هزینه‌ی ساخت هر دیوار ‎$l+C$‎ است که ‎$l$‎ طول دیوار و ‎$C$‎ یک عدد ثابت است . رئیس باغ‌وحش می‌خواهد این دیوارکشی علاوه بر شرط‌های گفته شده کم‌ترین هزینه‌ی ممکن را داشته باشد و برای این کار از شما کمک خواسته است (عجب رئیس پررویی!). ضمناً رئیس باغ‌وحش تضمین کرده که چنین دیوارکشی‌ای وجود دارد.

ورودی

خروجی

محدودیت‌ها

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

ورودی نمونه خروجی نمونه
2 1 7 1
5.5 3
1 1.3 		1
2 55