صديقك لديه مجموعة من الأعداد يريد معرفة حاصل ضربهم ، سيستخدم الالة الحاسبة بالطبع.
عند ضرب أي عددين تستهلك الالة الحاسبة مقدار مضروبهما من الطاقة مثلا إذا كان لديك عددان x و y وقمت بضربهما باستخدام الالة الحاسبة فإن طاقتها ستنقص بمقدار x * y
بما أنك مبرمج طلب منك صديقك المساعدة فهل يمكنك أن تساعده؟
المدخلات
اول سطر يحتوي على عدد N
في السطر التالي يأتي N عدد
1 <= N <= 10^6
1 <= x, y <= 10^9
المخرجات
اقل قدر من الطاقة يمكن استهلاكه لضرب جميع الأعداد
مثال
لنأخذ كمثال هذا المدخل
4
3 2 10 7
المخرجات
468
التوضيح
هذا افضل ترتيب يمكن به ضرب الأعداد أي طريقة غير هذه ستؤدي لإستهلاك طاقة أكبر
min_energy = 0
3 * 2 = 6
min_energy = 6
6 * 7 = 42
min_energy = 42 + 6 = 48
10 * 42 = 420
min_energy = 420 + 48 = 468
يبدو لأن هذا الحل، هل يمكنك ارفق test case أخرى ؟
ربما ال-intuation خطأ ولكن نريد أن نعمل minimize لل-)sum (x*y، و-x هي accumulative product إذاً يجب أن نعمل minimize ال-x
حلك خاطئ جرب هذه ال test case
المفروض الناتج 9858
حاول التفكير بطريقة أخرى
هل يمكنك إرفاق testcase أكبر ؟
حلك صحيح
https://suar.me/a8aql
حلك يعمل في
افضل حل يعمل في n log n وهو كالتالي:
في اي مرحلة نريد ضرب أصغر عددين وإدخال الناتج في القائمة بحيث تكون مرتبة. يمكن تنفيذ هذه العملية بكفاءة بإستخدام heap تحديدا min heap
عملية إنشاء ال heap تعمل في n log n و ضرب الأعداد n log n الناتج n log n
الحل ببايثون
لمن هو مهتم هذا الحل ب c++
شكراً على المشاركة بالحل، لم أفكر بإستعمال min heap، نسيت أغلب Data structures.
insort تقوم بعمل binary search، المشكل انني أقوم بعمل pop(0) (كمبليكستي او(N)) إذاً صحيح كما قلت أنت O(N^2 log N) أحسنت، ولكن يمكن أن تكون O(N log N) إذا تم إستعمال stack و- binary search، شكراً مرة أخرى على مشاركة الحل.
لا أعرف لماذا لكن حلك الذي يعمل بال-min heap أسرع من BS + stack
-
ملاحظة bisect ليس فيه reverse
https://jsfiddle.net/zakariamouhid/5b3zb7x5
حلك خاطئ راجع ردي هنا https://io.hsoub.com/go/63468/331316