562 - Dividing coins

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

Moderator: Board moderators

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

Re: 562 - Dividing Coins

Post by raykou » Mon Jun 30, 2008 4:52 am

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

Post by a13032002 » Wed Aug 27, 2008 7:13 pm

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
Location: BUET, Bangladesh
Contact:

Re: 562 - Dividing Coins WA

Post by naffi » Thu Nov 06, 2008 5:45 am

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?
Always At Your Help.

L I M O N
Learning poster
Posts: 58
Joined: Wed Dec 31, 2003 8:43 am
Location: Dhaka, Bangladesh
Contact:

Re: 562 - Dividing Coins

Post by L I M O N » Thu Nov 06, 2008 11:37 am

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

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

Re: 562 - Dividing Coins

Post by naffi » Thu Nov 06, 2008 3:08 pm

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.
Always At Your Help.

L I M O N
Learning poster
Posts: 58
Joined: Wed Dec 31, 2003 8:43 am
Location: Dhaka, Bangladesh
Contact:

Re: 562 - Dividing Coins

Post by L I M O N » Thu Nov 06, 2008 3:33 pm

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

Post by mf » Thu Nov 06, 2008 4:23 pm

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

Re: 562 - Dividing Coins

Post by L I M O N » Thu Nov 06, 2008 5:02 pm

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
Location: BUET, Bangladesh
Contact:

Re: 562 - Dividing Coins

Post by naffi » Thu Nov 06, 2008 6:21 pm

Thanks LIMON.

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

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

Re: 562 - Dividing Coins WA

Post by mf » Thu Nov 06, 2008 7:27 pm

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

Post by porker2008 » Thu Nov 06, 2008 7:36 pm

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
Location: BUET, Bangladesh
Contact:

Re: 562 - Dividing Coins

Post by naffi » Fri Nov 07, 2008 4:29 am

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.
Always At Your Help.

eliascfc
New poster
Posts: 1
Joined: Fri Dec 12, 2008 9:50 am

Re: 562 - Dividing Coins

Post by eliascfc » Sat Jul 25, 2009 2:48 pm

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

Post by mf » Sat Jul 25, 2009 5:29 pm

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

Post by matioli » Thu Jun 03, 2010 8:45 pm

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

Post Reply

Return to “Volume 5 (500-599)”