تحدي برمجي[012][متوسط] بطارية الالة الحاسبة

صديقك لديه مجموعة من الأعداد يريد معرفة حاصل ضربهم ، سيستخدم الالة الحاسبة بالطبع.

عند ضرب أي عددين تستهلك الالة الحاسبة مقدار مضروبهما من الطاقة مثلا إذا كان لديك عددان x و y وقمت بضربهما باستخدام الالة الحاسبة فإن طاقتها ستنقص بمقدار x * y

بما أنك مبرمج طلب منك صديقك المساعدة فهل يمكنك أن تساعده؟

المدخلات

اول سطر يحتوي على عدد N

في السطر التالي يأتي N عدد

1 <= N <= 10^6
1 <= x, y <= 10^9

المخرجات

اقل قدر من الطاقة يمكن استهلاكه لضرب جميع الأعداد

مثال

لنأخذ كمثال هذا المدخل

4
3 2 10 7

المخرجات

التوضيح

هذا افضل ترتيب يمكن به ضرب الأعداد أي طريقة غير هذه ستؤدي لإستهلاك طاقة أكبر

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

cc

يبدو لأن هذا الحل، هل يمكنك ارفق test case أخرى ؟

$ cat a.py
raw_input()
f = sorted(map(int, raw_input().split()))
p = f.pop(0)
s = 0
for e in f:
    p *= e
    s += p
print(s)

ربما ال-intuation خطأ ولكن نريد أن نعمل minimize لل-)sum (x*y، و-x هي accumulative product إذاً يجب أن نعمل minimize ال-x

حلك خاطئ جرب هذه ال test case

5
4 6 19 7 3

المفروض الناتج 9858

حاول التفكير بطريقة أخرى

هل يمكنك إرفاق testcase أكبر ؟

from bisect import insort_left

def k(f):
    s = 0
    while len(f) != 1:
        p = f.pop(0) * f.pop(0)
        s += p
        insort_left(f, p)
    print(s)

raw_input()
a = list(map(int, raw_input().split()))
a.sort()
k(a)

حلك صحيح

https://suar.me/a8aql

حلك يعمل في

O(N^2 log N)

افضل حل يعمل في n log n وهو كالتالي:

في اي مرحلة نريد ضرب أصغر عددين وإدخال الناتج في القائمة بحيث تكون مرتبة. يمكن تنفيذ هذه العملية بكفاءة بإستخدام heap تحديدا min heap

عملية إنشاء ال heap تعمل في n log n و ضرب الأعداد n log n الناتج n log n

الحل ببايثون

from heapq import heappush, heappop

heap = []
n = input()
for i in map(int, input().split()):
    heappush(heap, i)

energy = 0
while len(heap) > 1:
    mul = heappop(heap) * heappop(heap)
    energy += mul
    heappush(heap, mul)

print(energy)

لمن هو مهتم هذا الحل ب c++

#include <iostream>
#include <queue>

using namespace std;

int main(){
    int n;
    cin >> n;
    int x;
    priority_queue<int> pq;
    while(n--){
        cin >> x;
        pq.push(-x);
    }
    int a, b;
    int energy = 0;
    while(pq.size() > 1){
        a = pq.top(); pq.pop();
        b = pq.top(); pq.pop();
        energy += a * b;
        pq.push(-(a * b));
    }
    cout << energy;
    return 0;
}

شكراً على المشاركة بالحل، لم أفكر بإستعمال 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

def reverse_insort(a, x, lo=0, hi=None):
    """Insert item x in list a, and keep it reverse-sorted assuming a
    is reverse-sorted.

    If x is already in a, insert it to the right of the rightmost x.

    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
    """
    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if x > a[mid]: hi = mid
        else: lo = mid+1
    a.insert(lo, x)

def k(f):
    s = 0
    while len(f) != 1:
        p = f.pop() * f.pop()
        s += p
        reverse_insort(f, p)
    print(s)

a = range(1, 10 ** 5)
a.sort(reverse=True)
k(a)

$ /usr/bin/time -v python /home/mo/a.py > /dev/null
Command being timed: "python /home/mo/a.py"
User time (seconds): 5.83
System time (seconds): 0.14
Percent of CPU this job got: 99%
Elapsed (wall clock) time (h:mm:ss or m:ss): 0:05.99
Average shared text size (kbytes): 0
Average unshared data size (kbytes): 0
Average stack size (kbytes): 0
Average total size (kbytes): 0
Maximum resident set size (kbytes): 10576
Average resident set size (kbytes): 0
Major (requiring I/O) page faults: 0
Minor (reclaiming a frame) page faults: 2612
Voluntary context switches: 1
Involuntary context switches: 96
Swaps: 0
File system inputs: 0
File system outputs: 0
Socket messages sent: 0
Socket messages received: 0
Signals delivered: 0
Page size (bytes): 4096
Exit status: 0

$ cat b.py
from heapq import heappush, heappop

heap = []
for i in xrange(1, 10 ** 5):
    heappush(heap, i)

energy = 0
while len(heap) > 1:
    mul = heappop(heap) * heappop(heap)
    energy += mul
    heappush(heap, mul)

print(energy)

$ /usr/bin/time -v python /home/mo/b.py > /dev/null
Command being timed: "python /home/mo/b.py"
User time (seconds): 4.10
System time (seconds): 0.00
Percent of CPU this job got: 99%
Elapsed (wall clock) time (h:mm:ss or m:ss): 0:04.11
Average shared text size (kbytes): 0
Average unshared data size (kbytes): 0
Average stack size (kbytes): 0
Average total size (kbytes): 0
Maximum resident set size (kbytes): 10688
Average resident set size (kbytes): 0
Major (requiring I/O) page faults: 0
Minor (reclaiming a frame) page faults: 2589
Voluntary context switches: 1
Involuntary context switches: 67
Swaps: 0
File system inputs: 0
File system outputs: 0
Socket messages sent: 0
Socket messages received: 0
Signals delivered: 0
Page size (bytes): 4096
Exit status: 0

ملاحظة bisect ليس فيه reverse

https://jsfiddle.net/zakariamouhid/5b3zb7x5

// JavaScript
function solve(input) {
  input = input.split("\n")[1].split(" ").map(Number).sort((a, b) => (a - b));
  var p = input[0], s = 0, i;
  for (i = 1; i < input.length; i += 1) {
    p *= input[i];
    s += p;
  }
  return s;
}

حلك خاطئ راجع ردي هنا https://io.hsoub.com/go/63468/331316

#include <bits/stdc++.h>

using namespace std;

int main(){

    int n,x,eng=0;
    cin>>n;
    multiset<int> st;
    while(n--)cin>>x,st.insert(x);
    while(!st.empty()){
        int f=*st.begin();st.erase(st.begin());
        if(st.empty())break;
        int s=*st.begin();st.erase(st.begin());
        eng+=(f*s);
        st.insert(f*s);
    }
    cout<<eng<<endl;

    return 0;
}