562 - Dividing coins

[raykou]

your code have some missing brackets.
see to it and paste again your code.

I got AC, thank you.

[a13032002]

I got WA. And I still can't find my mistakes.
Could anyone give me some test data?
Here is my code

Code: Select all

#include <cstdio>
#include <memory>
#define abs(a) ((a)>=0?(a):-(a))
int main(){
    int q;
    scanf("%d",&q);
    while(q--){
               bool *a1=new bool[501];
               bool *a2=new bool[501];
               bool *now;
               bool *tmp;
               memset(a1,false,501);
               memset(a2,false,501);
               a1[0]=true;
               now=a1;
               tmp=a2;
               int m;
               scanf("%d",&m);
               while(m--){
                          int n;
                          scanf("%d",&n);
                          for(int i=0;i<=500;i++)
                                  if(now[i]){
                                  tmp[i]=false;
                                  if (i+n<=500)
                                     tmp[i+n]=true;
                                  tmp[abs(i-n)]=true;
                                  }
                          bool *e=tmp;
                          tmp=now;
                          memset(tmp,false,501);
                          now =e;
               }
               for(int i=0;i<=500;i++)
                       if (now[i]){
                          printf("%d\n",i);
                          break;
                       }
    }
    return 0;
}

[naffi]

Hi, I am a little confused about this problem and getting WA.

1. if, in input,m = 0, is there going to be a blank line in the following line?
2.is this correct?

Code: Select all

      W = sum/2;
		for(i = 0; i <= W; i++)A[0][i] = 0;		
		for(i = 1; i <= n; i++)
		{
			A[i][0] = 0;
			for(j = 1; j <= W; j++)
			{
				if(v[i] <= j)
				{
					if(v[i] + A[i-1][j-v[i]] > A[i-1][j])A[i][j] = v[i] + A[i-1][j-v[i]];
					else A[i][j] = A[i-1][j];
				}
				else A[i][j] = A[i-1][j];
			}
		}
		printf("%d\n",sum-2*A[n][W]);

can some one give me some IO?

[L I M O N]

here you can get help http://www.youngprogrammer.com

[naffi]

Hi Limon,

You should stop advertising about youngprogrammer.com. There, source codes are availavle and it is totally spoiler. You should stop referring that, that is actually no help but no help.

[L I M O N]

Hi Limon,

You should stop advertising about youngprogrammer.com. There, source codes are availavle and it is totally spoiler. You should stop referring that, that is actually no help but no help.

This site is completely personal and non commercial. no reason to advertising. indeed this site is under construction and my future plane is different. if you do not get any help from it, then simple ignore it. but already many coders of this site sent me mail and also their Accepted codes. their option is opposite to you. i never request for codes from their.

Most of the solutions are given in my site is very easy. i put it just to share my concept to others. and you know its totally free, then why need to advertising a personal site ? you might think about some ads at my site. do you know what is the cost of my web hosting ? it is 120$+ per months as it is a US based server, and how much i can earn from those add ? it is profitable ? you are good programmer , hope you can calculate easily.

[mf]

I totally agree with naffi. Please stop spamming the forum with link to your site.

you might think about some ads at my site. do you know what is the cost of my web hosting ? it is 120$+ per months as it is a US based server

You know, there are some free web hosting services out there. Google App Engine/Google SItes, for example. And there are existing wikis, such as algorithmist.com, have you thought about contributing to them instead?

[L I M O N]

You know, there are some free web hosting services out there. Google App Engine/Google SItes, for example. And there are existing wikis, such as algorithmist.com, have you thought about contributing to them instead?

i know very well about free web hosting. but why should not i host myself ?
As i mentioned at my previous post, this is my personal site and my future plan is different . programming contest or other topic related to contest is not my ultimate plan. that's why i need some other facilities from web hosting service that are not usually available for free service.

Ok, thank you all for your option. whatever i say, it's my wrong. extremely sorry for that. if it is possible , i request site admin to remove all my post related to refer my site.

thank you mf, thank you nafii.

[naffi]

Thanks LIMON.

However, would someone please reply to my previous post? I am getting WA.

[mf]

1. if, in input,m = 0, is there going to be a blank line in the following line?

I guess there should be one.
But if you use something like scanf("%d", &x) to read input, it doesn't matter.

2.is this correct?

Looks good to me.

[porker2008]

i think there are some misunderstandings between u and LIMON.

u thought programmers should not show their acc code, and LIMON just want to let others who can not pass the questions get help.

If u are serious and confident that u can solve the problem, u should not refer to the website.

However, if u have no idea about the algorithm and nobody give u advices, you may get crazy.

But that's possible for u to get idea from others acc code. Also, if u just copy the acc code and submit, it is meaningless. What u get will just some useless data.

But if u absorb the idea and write your own code and get AC, it will help you anyway.

[naffi]

Hi everyone,

I think the way Mr. LIMON and Mr. porker are thinking is not right. It is polluting this environment. There are a lots of helping sites from where we can get help for algorithm and IO.

1.http://uvatoolkit.com/problemssolve.php
2.http://felix-halim.net/uva/hunting.php
3.http://shygypsy.com/acm/
4.http://www.comp.nus.edu.sg/~stevenha/pr ... acmoj.html

and the great wikipedia and this forum.

but they do not show Acc code. U know determination and ambition degrades when there are no need to try, seeing others acc code doesnot help bro, think about it.

[eliascfc]

i am always getting WA for this but i have try every test case here with correct output but i still get WA

can anyone help me telling me what is my problem

Code: Select all

#include <iostream>
#include <string>
#include <fstream>
#include <vector>
#include <cstdlib>
#include <cmath>
#include <algorithm>

using namespace std;

int compare_function(const void *a, const void *b);

int main()
{
    //freopen("input2.txt","r",stdin);
    //freopen("output2.txt","w",stdout);
    
    int testCase;
    
    cin >> testCase;
    
    for (int i=0; i<testCase;i++){
        
        int n;
        
        cin >> n;
        
        if (n==0){
           cout << "0" << endl;
           continue;          
        }
        
        int values[n], totalValue = 0 , difference = 0;
        
        for(int j=0;j<n;j++){
                cin >> values[j];
                totalValue += values[j];
        }
        
        int averageVal = totalValue/2;
        
        qsort(values,n,sizeof(int),compare_function);       
        
        int valP1 , valP2 = 0;
        
        valP1 = values[0];
        
        if (valP1 >= averageVal){
                  for(int k=1;k<n;k++){
                          valP2 += values[k];
                  }
                  
                  if (valP1 > valP2)
                            difference = valP1 - valP2;
                  else
                            difference = valP2 - valP1;
                  
        }
        else{
             
             int bal1 , bal2;
             
             bal1 = averageVal - valP1;
             bal2 = averageVal - valP2;
             
             for (int j=1;j<n;j++){
                 if(bal1 < values[j]){
                         valP2 += values[j];
                         bal2 -= values[j];
                 }
                 else{
                         valP1 += values[j];
                         bal1 -= values[j];
                 }
                         
             }
             
             
        }

        
        if (valP1 > valP2)
                            difference = valP1 - valP2;
        else
                            difference = valP2 - valP1;
        
        
        cout << difference << endl;
    }
    

    system ("pause");
    return 0;
}

int compare_function(const void *a, const void *b){
    
    int *x = (int *) a;
    int *y = (int *) b;
    return *y - *x;
    
}

[mf]

First of all, this is wrong:

Code: Select all

system ("pause");

In fact, I think judge shouldn't even let you compile that code in the first place at all! Or at least it should've said "runtime error", because your program is not supposed to be messing around with such dangerous functions as system().

And what the **** does system("pause"); even do? There's no such command as pause. All I get is:

Code: Select all

sh: pause: not found

(it gets printed on stdout along with the output of your program. So, if for some reason judge allows system() calls, that might also be a reason for WA!)

Second, your algorithm is totally wrong. Learn about knapsack problem and dynamic programming.

[matioli]

Hi... I'm learning about DP and I realized this problem is a 0-1 knapsack problem with the maxweight = sum coins / 2. Or am I wrong?

So, I tried this code (the dp_01_knapsack function I've created based on this site and some discussions on the internet) but it get's WA (and I couldn't think in any test cases that the code fails):

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXWEIGHT 25100 // The maximum sum of coins is 50000, so the maximum possible to get is 50000/2 = 25000
#define MAXITENS 110

int c[MAXITENS][MAXWEIGHT];

void dp_01_knapsack(int weights[], int values[], int n, int W){
    int w, i;
    //for (w = 0; w <= W; w++)
    //    c[0][w] = 0;
    memset(c[0], 0, sizeof(int) * (W+1));
    for (i = 1; i <= n; ++i){
        c[i][0] = 0;
        for (w = 1; w <= W; ++w){
            if ((weights[i] <= w) && (values[i] + c[i-1][w-weights[i]])){
                c[i][w] = values[i] + c[i-1][w-weights[i]];
            }else{
                c[i][w] = c[i-1][w];
            }
        }
    }
    #ifdef _DEBUG_
    for (i = n, w = W; i > 0; --i){
        if (c[i][w] != c[i-1][w]){
            printf("Take %d\n", weights[i]);
            w -= weights[i];
        }else{
            printf("Leave %d\n", weights[i]);
        }
    }
    #endif
}

int getdiff(int coins[], int ncoins, int sum){
    int i, w;
    int tot_take = 0, tot_leave = 0;
    
    dp_01_knapsack(coins, coins, ncoins, sum/2);
    
    for (i = ncoins, w = sum/2; i > 0; --i){
        if (c[i][w] != c[i-1][w]){
            tot_take += coins[i];
            w -= coins[i];
        }else{
            tot_leave += coins[i];
        }
    }
    return tot_leave > tot_take ? tot_leave - tot_take : tot_take - tot_leave;
}

int main(void){
    int ncases, ncoins, sum, i;
    int coins[MAXITENS];
    
    scanf(" %d", &ncases);
    while(ncases--){
        sum = 0;
        scanf(" %d", &ncoins);
        for (i = 1; i <= ncoins; i++){
            scanf(" %d", &coins[i]);
            sum += coins[i];
        }
        printf("%d\n", getdiff(coins, ncoins, sum));
    }
    return 0;
} 

Please can someone give me some help or some test case that this code fails?

Thank you...