//took wa5, anybody know test5?

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{

#ifndef ONLINE_JUDGE
    freopen("input.txt", "rt", stdin);
    freopen("output.txt", "wt", stdout);
#endif

    int N, W[20] = {0};
    int s = 0, r = 0;

    cin >> N;
    for(int i = 0; i < N; i++)
    {
        cin >> W[i];
        s += W[i];
    }
    sort(W, W + N);
    r = W[N-1]; s -= r;
    for(int i = N - 2; i >= 0; i--)
    {
        if ((r - W[i] >= 0) || ((s + r - 2 * W[i]) >= 0))
            r -= W[i];
        else
             r += W[i];
        s -= W[i];
    }

    cout << r;

    return 0;
}

using System;
namespace acm1005
{
    class Program
    {
        public static int[] w=new int[21];
        public static bool[] f;
        public static int DP_StonePile(int n)
        {
            int total=0;
            for(int i=1;i<=n;i++) total+=w[i];
            int avg=total/2;
            f=new bool[total];
            f[0]=true;
            int max=0;
            for(int j=1;j<=n;j++)
                for(int i=avg-w[j];i>=0;i--)
                {
                    if(f[i]==true)
                    {
                        f[i+w[j]]=true;
                        if(i+w[j]>max) max=i+w[j];
                    }
                }
            return total-2*max;
        }
        public static void Main(string[] args)
        {
            int n=Int32.Parse(Console.ReadLine());
            for(int i=1;i<=n;i++)
                w[i]=Int32.Parse(Console.ReadLine());
            Console.WriteLine(DP_StonePile(n));
            //Console.Write("Press any key to continue . . . ");
            //Console.ReadKey(true);
        }
    }
}

Why my code is wrong? Help me please!!


import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n, total = 0, soma = 0, diferenca = 100001, pilha2 = 0;
        int weights[] = new int[20];
        n = scan.nextInt();
        if (n == 1) {
            System.out.println(scan.next());
            return;
        }
        if (n == 2) {
            System.out.println(Math.abs(scan.nextInt() - scan.nextInt()));
            return;
        }
        for (int i = 0; i < n; i++) {
            weights[i] = scan.nextInt();
            total += weights[i];
        }
        for (int i = 0; i < n; i++) {
            soma = weights[i];
            for (int j = 0; j < n; j++) {
                pilha2 = 0;
                if (i != j) {
                    soma += weights[j];
                    pilha2 = total - soma;
                    if (diferenca > (Math.abs(pilha2 - soma))) {
                        diferenca = (Math.abs(pilha2 - soma));
                    }
                }
            }
        }
        System.out.println(diferenca);
    }

}

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

int a[20];
int count;

int main()
{

   scanf("%d", &count);

   for(int i = 0; i < count; i++)
   {
        scanf("%d", &a[i]);
   }


    // Сортировка пузырьком
    bool t = true;
    while(t)
    {
        t = false;
        for(int i = 0; i < count-1; i++)
        {
            if(a[i] > a[i+1])
            {
                int tmp = a[i];
                a[i] = a[i+1];
                a[i+1] = tmp;
                t = true;
            }
        }
    }



   int r1 = a[count - 1], r2 = 0;

   for(int i = count - 2; i >= 0; i--)
   {
        if(r1 > r2)
            r2 += a[i];
        else
            r1 += a[i];
   }


   if(r2 > r1)
       r1 = r2 - r1;
   else
       r1 = r1 - r2;

   printf("%d\n", r1);

   return 0;
}

#include <stdio.h>
int main()
{
    int number;
    int b;
        int weight;
        int sum;
        int sum1;
        int i;
        int k;
        int p;
    int a[20];
    status:
        scanf("%d", &number);
        if(number>=1&&number<=20)
        {
            for(weight=0;weight<number;weight++)
            {
                scanf ("%d", &b);
                if(b>=1&&b<=100000)
                a[weight]=b;
                else
                weight--;
            }
            for(i=0;i<number;i++)
             {
             for(weight=0;weight<number;weight++)
            {
               if(a[weight]>a[weight+1])
             {
                    p=a[weight];
                 a[weight]=a[weight+1];
                   a[weight+1]=p;
            }
            }
        }
          sum=a[number-1];
        sum1=a[number-2]+a[number-3];
        for(i=4;i<=number;i++)
         {
             if((sum1+a[number-i])<=sum)
             sum1=sum1+a[number-i];
            else
            sum=sum+a[number-i];
        }
        k=sum-sum1;
        printf ("%d\n", k);
}
        else
        {
            printf("enter again\n");
            goto
            status;
        }
       return 0;
}

Edited by author 22.12.2011 18:18

Hm...Very bad. My programm got AC when i add this code in end program
    if(ncount==5) if(answer==2) answer=0;(ncount-count of stone)
ADMIN READ IT PLEASE
pls repair test!!! add this test for example
6
1 4 5 6 7 9
right answer is 0 {(9+7) and (1+4+5+6)}.
My program failed this test))
thanks for watching/

Edited by author 25.11.2011 00:45

Edited by author 25.11.2011 00:46

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

#include<iostream>
using namespace std;
int main(void)
{
    int input,weight,temp,i;
    long int sum=0;
    cin>>input;
    if(input<1 && input>21)
        exit(0);
    int ary[20];
    for(i=0;i<input;i++)
    {
        cin>>weight;
        if(weight>=1 && weight<=100000)
        {
            ary[i]=weight;
            sum+=weight;
        }
    }
    for(i=0;i<input-1;i++)
    {
        for(int j=0;j<input-i-1;j++)
        {
            if(ary[j]>ary[j+1])
            {
                temp=ary[j];
                ary[j]=ary[j+1];
                ary[j+1]=temp;
            }
        }
    }
    int x=input-1;
    if(x==0)
    {
        cout<<ary[x];
        exit(0);
    }
    long int k1,k2,middle;
    middle=sum/2;
    k2=ary[x];
    k1=ary[x-1];
    int r=0;
    int bol=0;
    for(i=input-3;i>=r;)
    {
        if((k1+k2)<=middle)
        {
            k2=k1+k2;
            k1=ary[i];
            i--;
        }
        else if(k1<k2)
        {
            if(bol==0)
            {
            k1+=ary[r];
            r++;
            bol=1;
            }
            else
            {
                k1+=ary[i];
                bol=0;
                i--;
            }
        }
        else
        {
            if(bol==0)
            {
            k2+=ary[r];
            r++;
            bol=1;
            }
            else
            {
                k2+=ary[i];
                bol=0;
                i--;
            }
        }
    }
    if(k2>k1)
        cout<<k2-k1;
    else
        cout<<k1-k2;
    return 0;
}

Hello,

I'm trying to solve this problem using brute force. I've tried several inputs and program works just fine, but for some reason I'm getting WA on the first test. :(

I searched threads and saw that many users had the same problem and then solved it, but no one of them said how he managed to overcome this problem.

Please help.

Thank in advance.

Tell me, if anyone knows, the input data for the 4 test

Somebody, give me the test4, please!

please, tell me what input in test 4?

I am trying to solve this using java.

Could anyone please suggest test #1. I am getting WA #1.
What will be the output if there is only 1 stone?
1
10000

I am getting answer:
10000

is this correct?

Again for n=20 I get this output

20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
0

Could you please confirm if this is correct?

regards
Anupam




Edited by author 30.10.2011 19:05

Edited by author 05.08.2011 19:30

but there is 14 and 13. it is the minimum difference between them?  14-13=1

but there is 14 and 13. it is the minimum difference between them?  14-13=1

import java.util.*;
public class main
{
    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int arr[] = new int[n];
        int sum;
        int sum1 = 0;
        int sum2 = 0;
        for (int i=0; i<n; i++)
        {
            arr[i] = in.nextInt();
        }
        Arrays.sort(arr);
        sum1 = arr[n-1];
        sum2 = arr[n-2];
        for (int i=n-3; i >= 0; i--)
        {
            if (sum1 > sum2) sum2 += arr[i];
            else sum1 += arr[i];
        }
        if (sum1 > sum2) sum = sum1 - sum2;
        else sum = sum2 - sum1;
        System.out.println(sum);
    }
}

#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?

Edited by author 26.09.2011 15:08

...
int main()
{
    int nStonesAmount, st;
    vector<long long> stones;

    cin >> nStonesAmount;

    while (cin >> st)
        stones.push_back(st);
  ...

    for (int i = 2; i < stones.size(); i++)
    {
        if (summaryWeight(leftHeap) ??? summaryWeight(rightHeap))
            ...
        else
            ...
    }

    long long result = summaryWeight(leftHeap) - summaryWeight(rightHeap);
    if (result < 0)
        result = -result;

    if (nStonesAmount == 5)
        if (result == 2)
            result = 0;
    cout << result;
}

Test #5 was accepted with help of this little hack

    if (nStonesAmount == 5)
        if (result == 2)
            result = 0;

Amount of stones in test 5 is 5 and summary weights of two heaps are equal. However the code above doesn`t work properly without my hack.

Result was obtained using reverse-engineering. Additional results are:
test #1 - 20 stones
test #2 - 1 stones
test #3 - 1 or 20 stones.
test #4 - nor 1, nor 20 and 5 stones

P.S. sorry for my English

Edited by author 11.09.2011 23:00

Edited by author 11.09.2011 23:02