شما قرار است سیستم مالی جدیدی برای کشور مالی راه‌اندازی کنید. به همین منظور قرار است ارزش سکه‌های این کشور را طوری تعیین کنید که ارزش هر سکه‌ای مضربی از ارزش هر یک از سکه‌های کم‌ارزش‌تر از خودش باشد و حتما سکه‌ای با ارزش ۱ وجود داشته باشد.

در کشور مالی $n$ نوع کالا وجود دارد که هرکدام قیمت مشخصی دارد. قیمت کالا‌ها حداکثر $m$ است. هدف شما این است که طوری ارزش سکه‌ها را تعیین کنید که مجموع تعداد سکه‌های لازم برای خرید یک قلم از هر کالا کمینه شود. الگوریتمی از $O(mn\log(m))$ ارائه دهید که این مقدار کمینه را پیدا کند.

• سوال بعد
• سوال قبل