شاه ترناس به وزیرش دستور داده که یک بازی فکری برای پسرش آرتوس طراحی کند تا قابلیت‌های فکری پسرش بالا برود. وزیر یک بازی فکری به این صورت طراحی کرد. $N$ صندوق با شماره‌های $۱$ تا $N$ قرار داده شده است. هر صندوق یک قفل مخصوص دارد که تنها با استفاده از کلید مخصوص آن باز می‌شود. قبل از شروع بازی وزیر به ازای هر $i$ دو کپی از کلید صندوق $i$ را داخل صندوق‌های $i - 1$ و $i + 1$ (در صورت وجود) قرار داد. سپس $D$ الماس در $D$ صندوق متفاوت قرار داد. در آخر، همه صندوق‌ها را قفل کرد و کلید $M$ صندوق را به او داد. آرتوس باید تمام الماس‌ها را جمع‌آوری کند طوری که تعداد صندوق هایی که در طی جمع‌آوری الماس‌ها باز کرده کمینه شود.
آرتوس خیلی از فکر کردن خوشش نمی‌آید. او می گوید «رایانه‌ها به چه دردی می‌خورند، اگر قرار باشد ما فکر کنیم؟». بنابراین او، پرنس آرتوس، پسر شاه ترناس، به شما دستور داد که کاری کنید که رایانه به جای او فکر کند و این مسئله را حل کند.
برای هر سناریو، در یک خط کم‌ترین تعداد صندوقی که آرتوس باید باز کند تا بتواند همه‌ی الماس‌ها را جمع‌آوری کند چاپ کنید.
| ورودی نمونه | خروجی نمونه |
|---|---|
| 5 1 5 1 1 2 3 4 5 5 3 3 1 2 3 3 4 5 5 3 1 1 2 3 5 0 0 0 | 5 3 3 |
پاسخ
منتظر پر کردن این قسمت توسط علاقمندان هستیم.