## 562 - Dividing coins

Moderator: Board moderators

raykou
New poster
Posts: 4
Joined: Sun Jul 01, 2007 10:14 am

### Re: 562 - Dividing Coins

your code have some missing brackets.
see to it and paste again your code.
I got AC, thank you.

a13032002
New poster
Posts: 5
Joined: Wed Aug 27, 2008 7:05 pm

### Re: 562 - Dividing Coins

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
New poster
Posts: 23
Joined: Wed Mar 19, 2008 12:25 pm
Contact:

### Re: 562 - Dividing Coins 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
Learning poster
Posts: 58
Joined: Wed Dec 31, 2003 8:43 am
Contact:

### Re: 562 - Dividing Coins

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

naffi
New poster
Posts: 23
Joined: Wed Mar 19, 2008 12:25 pm
Contact:

### Re: 562 - Dividing Coins

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
Learning poster
Posts: 58
Joined: Wed Dec 31, 2003 8:43 am
Contact:

### Re: 562 - Dividing Coins

naffi wrote: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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

### Re: 562 - Dividing Coins

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
Learning poster
Posts: 58
Joined: Wed Dec 31, 2003 8:43 am
Contact:

### Re: 562 - Dividing Coins

mf wrote: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
New poster
Posts: 23
Joined: Wed Mar 19, 2008 12:25 pm
Contact:

### Re: 562 - Dividing Coins

Thanks LIMON.

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

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

### Re: 562 - Dividing Coins WA

naffi wrote: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
New poster
Posts: 21
Joined: Wed Oct 08, 2008 7:04 am

### To naffi

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
New poster
Posts: 23
Joined: Wed Mar 19, 2008 12:25 pm
Contact:

### Re: 562 - Dividing Coins

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
New poster
Posts: 1
Joined: Fri Dec 12, 2008 9:50 am

### Re: 562 - Dividing Coins

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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

### Re: 562 - Dividing Coins

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
New poster
Posts: 1
Joined: Thu Jun 03, 2010 8:36 pm

### Re: 562 - Dividing Coins

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...