In this problem, the example input had these lines :
5
5 8 13 27 14

I am a bit confused about the input will be inserted to the console ?
Can i assume that :
 the first line is inserted and then (after hitting Enter), the second is inserted ?
and after that the output is produced ?

Thanks a lot

Edited by author 05.08.2011 19:30

#include<stdio.h>
#include<algorithm>
using namespace std;
int pile[22];//initial array size
int pile_cmp(const void*a,const void *b)
{
    return *(int*)a-*(int*)b;
}
int main()
{
     int num;
     scanf("%d",&num);
     int sum=0;
     for(int i=0;i<num;i++){
         scanf("%d",&(pile[i]));
         sum+=pile[i];
     }
         if(sum==0)printf("0\n");
         else{
         qsort(pile,num,sizeof(int),pile_cmp);
             int ptr=num-1,min=2000000,min_p,tmp;
         while( ptr>=0 && sum ){
         while(ptr>=0 && (sum-(pile[ptr]<<1))<0)ptr--;
         if(ptr<0)ptr++;
         tmp=pile[ptr]<<1;
         if(abs(sum-tmp)<min){
             sum=abs(sum-tmp);
             min=sum;
         }
         ptr--;
        }
        printf("%d\n",min);
    }
     return 0;
}
before i submit this ,i submit another one ,which got AC but produce different answer with this one;however this one also got AC
I wasn't quite clear about what is the correct algorithm for this problem

Edited by author 02.08.2011 00:58

Edited by author 02.08.2011 01:05

#include <stdio.h>

int main () {
    printf("3");
    return 0;
}

this gives me WA #1. test #1 isn't from the example, is it?

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Scanner;


public class PileOfStones {
    private static int sum = 0;
    private static int minSum = 0;
    private static int myMinSum;
    private static int min;
    private static int m=0;
    private static int error = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int pl = Integer.parseInt(in.readLine());
        if(pl>=1 && pl<=20){
            int[] stones = new int[pl];
            int k = stones.length-1;
            Scanner sc1=new Scanner(System.in);
            for (int i = 0; i < pl; i++) {
                stones[i] = sc1.nextInt();
                if(stones[i]<1 || stones[i]>100000){
                    error =1;
                    break;
                }
            }
            if(error!=1){
                for (int i = 0; i < stones.length; i++) {
                    sum+=stones[i];
                }
                Arrays.sort(stones);
                min=sum;
                while(k>0){
                    for (int i = k; i >= 0; i--) {
                        if((stones[i] + minSum)<=(sum/2)){
                            minSum+=stones[i];
                            k=i;
                        }
                    }
                    if((sum/2-minSum)<=min ){
                        myMinSum=minSum;
                    }
                    minSum-=stones[k];
                    if(k!=m){
                        m=k;
                    }
                    else{
                        k=-1;
                    }
                }
                System.out.println(sum-2*myMinSum);
            }
            }

        }


}

See, this is my code. For 4 stone (48 22 27 3) he said: 4. But correct answer is 2!

--------------------------------------------------

#include <stdio.h>
#include <algorithm>
using namespace std;
int main() {
    int n, i, s=0, x, y=0, *m;
    scanf("%d", &n);
    m = new int[n];
    for (i=0; i<n; i++) {
        scanf("%d", &m[i]);
        s += m[i];
    }
    s /= 2;
    sort(m, m+n);
    x = m[n-1];
    for (i=n-2; i>-1; i--)
        if (x+m[i] <= s)
            x += m[i];
        else
            y += m[i];
    printf("%d", (x>y)?(x-y):(y-x));
    return 0;
}

Edited by author 29.06.2011 04:25

#include <stdio.h>
#include <math.h>

int n;// the number of stones
int w[21];//store the weight of stones
int total;//the sum of all of the stones
int ans = 100000000;

//now is the sum of first piles
//index is index of w
void fun(int now,int index)
{
    if (index == n)// the end
        if (ans > abs(total - 2 * now))
            ans = abs(total - 2 * now);
    for (int i = index; i < n; i ++)
        if (now + w[i] < (total >> 1))
            fun(now + w[i],i + 1);
}

int main(void)
{
#ifndef ONLINE_JUDGE
   freopen("input.txt", "rt", stdin);
#endif
    scanf("%d",&n);
    total = 0;
    for (int i = 0; i < n; i ++)
    {
        scanf("%d",&w[i]);
        total += w[i];
    }
    fun(0,0);
    printf("%d\n",ans);
    return 0;
}

Hello

I have submitted my solution 2 times, and I get Time Limit Exceed, I dont understand why?, can someone help me, maybe its my loop, but I still dont understand, here its my code

import java.io.*;
import java.util.Arrays;

public class StonePile {

    public static void main(String args[]) throws IOException {
        StreamTokenizer str = new StreamTokenizer(new

BufferedReader(new InputStreamReader(System.in)));
        //int diff = 0;
        str.nextToken();
        int[] array = new int[(int) str.nval + 1];
        int array2[] = new int[array.length - 1];
        //System.out.println(array.length);
        int i = 0;
        int diff = 0;

        while (((str.nextToken() != StreamTokenizer.TT_EOL))) {

            if (str.ttype == StreamTokenizer.TT_NUMBER) {
                // System.out.println(i);
                array[i++] = (int) str.nval;

            }

        }


        for (int j = 0; j < array.length - 2; j++) {
            diff = Math.abs(array[j + 1] - array[j]);
            array2[j] = diff;
            // System.out.println("El array es en" + j+" es"+

array2[j]);
        }

        Arrays.sort(array2);
        System.out.println(array2[1]);



    }
}

#include<stdio.h>
#include<math.h>
#include<string.h>
int dp[21][10000];
int w[21];
int sum,n;
void beibao(int i,int x,int y)
{
   dp[i][abs(x-y)]=abs(x-y);
   if(i+1>n)return;
   beibao(i+1,x+w[i+1],y);
   beibao(i+1,x,y+w[i+1]);
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",w+i);
        sum+=w[i];
    }
    memset(dp,-1,sizeof(dp));
    beibao(0,0,0);
    int min=2147483647;
    for(int i=0;i<=sum;i++)
    {
        if(dp[n][i]>=0)
        {
            if(min>dp[n][i])
            {
                min=dp[n][i];
            }
        }
    }
    printf("%d\n",min);
    return 0;
}

0-1 Knapsack, O(sum*n)...For the week data, I haven't got TLE...

#include<iostream>
using namespace std;

int main(){
    int n,y=100001;
    int x=0;
    cin >> n;

    int *array = new int[n];

    for( int i=0; i<n; i++ )
    {
        cin >> array[i];
    }

    for (int i=0; i<n; i++)
    {
            x = (array[i+1] - array[i]);
            if(x < y && x >= 0) { y = x; }
    }

    cout << y;
    system("PAUSE");
    return 0;
}

----------------------------------------------------------------
Why WA#1?

I got 3 for:
5
5 8 13 27 14


So? Does someone know?

please tell me how do you?
I found one algo but it uses memory equal to W_i limitation. if maximum of W_i is 100000 it uses 100000 too. Maybe it use 2 times more.

Edited by author 05.04.2011 22:59

what is test #5?

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
int p[20];
using namespace std;
int main()
{
    int a;
    int i,j,x,y,c;
    cin>>a;
    for(i=0; i<a; i++)  cin>>p[i];

        for (i=0; i<a; i++)
    for (j=i+1; j<a; j++)
    if (p[i]<p[j]) { c=p[j]; p[j]=p[i]; p[i]=c; }

   if (a==1) cout<<p[0]; else if (a==2) cout<<abs(p[0]-p[1]);
   else
   x=p[0]; y=p[1];
   for (i=2; i<a; i++) {
if (x>y) y=y+p[i];
else x=x+p[i]; }

      if(a>2) cout<<abs(x-y);

      }




what i have wrong?
it sad "wrong answer"

problem 1005

Edited by author 11.02.2011 23:32

Edited by author 11.02.2011 23:33

Edited by author 11.02.2011 23:33
i am sure that my program produces the right output but your compiler is showing wrong answer.
my solution id is 3429148.

Edited by author 11.02.2011 23:36

Edited by author 11.02.2011 23:36

Why this solution got AC ? For the first test it outputs 15, but correct answer is 3 !!!!
#include <iostream>
#include <complex>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
using namespace std;
int main()
{
    int n,i,total=0,counter;
    int l;
    vector <int> x;
    cin>>n;
    for(i=0; i<n; i++)
    {
        cin>>l;
        x.push_back(l);
    }
    for(i=0; i<n; i++)
    {
        total+=x[i];
    }
    counter=total/2;
    for(i=0; i<n; i++)
    {
        if(x[i]<=counter)
        {
            counter-=x[i];
        }
    }
    cout<<2*counter+total%2;
    return 0;
}

Hi, Maybe I misunderstood the problem. With the given numbers, you could actually make two piles 27,8 in one and 13,14,5,5 in the other, and the difference would be just 2. Where did I misunderstand?

Can any one please explain meaning of the statement "delimited by whitespace" because all inputs are given in newline.