Dairəvi tövləyə yenidən baxış

Mal-qara tövləsi $n$ otaqdan ibarət bir üzükdən (dairədən) ibarətdir və otaqlar tövlənin ətrafı boyunca saat əqrəbi istiqamətində $1$-dən $n$-ə qədər nömrələnib. Hər bir otağın onu qonşu iki otaqla birləşdirən qapıları, həmçinin tövlədən bayıra çıxan bir qapısı var.

Fermer Con $i$ otağında dəqiq r_i inək olmasını istəyir. İnəkləri mütəşəkkil şəkildə tövləyə yığmaq üçün o, $k$ ədəd bayır qapısını açmağı və inəklərin yalnız bu qapılardan içəri girməsinə icazə verməyi planlaşdırır. İçəri girdikdən sonra hər bir inək münasib təyinat yerinə çatana qədər saat əqrəbi istiqamətində otaqlar boyunca hərəkət edir. Fermer Con $k$ ədəd bayır qapısını elə seçmək istəyir ki, tövləyə girdikdən sonra inəklərin birlikdə qət etdikləri məsafələrin cəmi mümkün qədər az olsun. Əvvəlcə inəklər açıq olan $k$ qapının bayırında istənilən ardıcıllıqla düzülə bilər və bu, ümumi qət olunan məsafəyə daxil edilmir. Fermer Con açmaq üçün optimal $k$ qapını seçdikdə inəklərin qət etməli olduğu minimal ümumi məsafəni müəyyən edin.