10954 - Add All

All about problems in Volume 109. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10954 - Add All

Post by brianfry713 » Wed Oct 01, 2014 11:13 pm

To get the minimum total cost, you should always add the two smallest numbers. You can accomplish that using a priority queue.

9 9 9 9 9 9
9 + 9 = 18, total cost = 18
9 9 9 9 18
9 + 9 = 18, total cost = 36
9 9 18 18
9 + 9 = 18, total cost = 54
18 18 18
18 + 18 = 36, total cost = 90
18 36
18 + 36 = 54, total cost = 144
Check input and AC output for thousands of problems on uDebug!

bgcsaif
New poster
Posts: 38
Joined: Mon Sep 29, 2014 4:03 pm

Re: 10954 - Add All

Post by bgcsaif » Fri Oct 03, 2014 11:05 am

What should be output of single input

Code: Select all

1
87
0
And should I print new line after each case output?

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 10954 - Add All

Post by lighted » Fri Oct 03, 2014 11:47 am

There won't be input where N = 1. According to problem description N >= 2.
Each test case will start with a positive number, N (2 ? N ? 5000)
Sort array. Each time get sum of two smallest numbers then place new sum into array to preserve it sorted and add current sum to total cost. :)
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

bgcsaif
New poster
Posts: 38
Joined: Mon Sep 29, 2014 4:03 pm

Re: 10954 - Add All

Post by bgcsaif » Fri Oct 03, 2014 1:22 pm

Thank you very much to get me out of my confusion. Sometimes over thinking makes one to think so complex that he forgets the simplest thing. I got Accepted! Thanks lighted

tanvir cse
New poster
Posts: 2
Joined: Wed Oct 22, 2014 11:20 am

10954

Post by tanvir cse » Thu May 28, 2015 12:34 pm

why it time limit?????

Code: Select all

/*      TANVIR HASAN */

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <string>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <set>
#include <algorithm>
#include <iterator>
#include <bitset>

//#include <bits/stdc++.h>
using namespace std;

#define uu         first
#define vv         second
#define pb         push_back
#define mp         make_pair
#define LL         long long
#define inf        INT_MAX/3
#define mod        1000000007ll
#define PI         acos(-1.0)
#define linf       (1ll<<60)-1
#define FOR(I,A,B)  for(int I = (A); I < (B); ++I)
#define ALL(A)     ((A).begin(), (A).end())
#define set0(ar)   memset(ar,0,sizeof ar)
#define setinf(ar) memset(ar,126,sizeof ar)
#define vsort(v)   sort(v.begin(),v.end())
#define pii        pair<int,int>


template <class T> inline T bigmod(T p,T e,T M)
{
    LL ret = 1;
    for(; e > 0; e >>= 1)
    {
        if(e & 1) ret = (ret * p) % M;
        p = (p * p) % M;
    }
    return (T)ret;
}
template <class T> inline T gcd(T a,T b)
{
    if(b==0)return a;
    return gcd(b,a%b);
}
template <class T> inline T modinverse(T a,T M)
{
    return bigmod(a,M-2,M);
}



int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n,m,p;
    vector<int> cst;
    while(scanf("%d",&n)==1 && n)
    {

        vector<int> cst;
        FOR(i,0,n)
        {
            scanf("%d",&m);
            cst.pb(m);
        }
         m=0;
        while(cst.size()!=1)
        {

           vsort(cst);
           p=cst[0]+cst[1];
            cst.pb(p);
            m+=p;
            cst.erase(cst.begin(),cst.begin()+2);
        }
       // vsort(cst);
        cout<<m<<endl;


    }





    return 0;
}
Last edited by brianfry713 on Fri Jun 19, 2015 6:59 am, edited 1 time in total.
Reason: Added code blocks

predicate
New poster
Posts: 18
Joined: Tue Jun 17, 2014 9:32 pm
Location: Hyderabad, India

Re: 10954

Post by predicate » Sun Jun 07, 2015 8:09 pm

if the size of the array is n, you sort the array n times, so the worst case run time of your program is O(n^2 lg(n)) which will be TLE for the given max size of n, which is 5000. You cannot sort the array every time you add two numbers. Think of a better approach which decreases the runtime of your algorithm.

Post Reply

Return to “Volume 109 (10900-10999)”