## 562 - Dividing coins

Moderator: Board moderators

newhh2002
New poster
Posts: 11
Joined: Sun Jan 26, 2003 4:25 pm
Contact:

### 562

could someone tell me how did those guys solved the problem in 0.0000 seconds? what algorithm did they use? thank you
none

razibcse
New poster
Posts: 50
Joined: Mon Jul 22, 2002 3:17 am
Contact:
I just can't understand why this program gets WA always...I checked all possible inputs which came to my mind,but no bug was found...

I tried to generate all possible numbers that can be made using the coins and set the flag of these numbers to 1. then I checked for the number which is half of the sum whether it's 1 or not. if not, then searched from right to get the first 1 and it's r1. r2 = sum - r1. the difference between r1 and r2 is the result..I assumed if there's only 1 coin,the answer is the value of the coin.Is the process wrong? someone help me please...

here's my code:

Code: Select all

``````#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
#define MAXCOIN 110
#define MAXCENT 500010

int comp(const void *a,const void *b)
{
return (*(long *)b - *(long *)a);
}

void main()
{
long n,m,num[MAXCOIN],sum1,s;
long i,j,sum,half,r1,r2,num_size;
int flag[MAXCENT];

scanf("%ld",&n);
while(n--)
{
scanf("%ld",&m);
if(m == 0) {printf("0\n"); continue;}
sum = 0;
for(i=0;i<m;i++)
{
scanf("%ld",&num[i]);
sum+=num[i];
}

if(m == 1)
{
printf("%ld\n",num);
continue;
}

qsort((void *)num, m, sizeof(num), comp);

if(m == 2)
{
printf("%ld\n",num-num);
continue;
}
num_size = sum+2;

for(i=0;i<num_size;i++)
flag[i] = 0;

flag = 1;
for(i=m-1;i>=0;i--)
{
flag[num[i]] = 1;
sum1 = num[i];
for(j=i-1;j>=0;j--)
{
s = num[i]+num[j];
flag[s] = 1;
sum1 += num[j];
flag[sum1] = 1;
}
}
half = sum/2;
for(i=half;i>=0;i--)
if(flag[i] == 1)
{
r1 = i;
r2 = sum - r1;
break;
}
if(r2 >= r1)
printf("%ld\n",r2-r1);
else printf("%ld\n",r1-r2);
}
}
``````
Wisdom is know what to do next; virtue is doing it.

Tomislav Novak
New poster
Posts: 44
Joined: Fri Feb 20, 2004 5:52 pm

### 562 - Dividing Coins

Hi. I'm trying to solve problem 562 (Dividing Coins) with dynamic programming. My program gives correct output to all test cases I could find on the board, but the judge still says WA. Here's the code:
[c]
#include <stdio.h>
#include <limits.h>

#define MAXCOINS 100
#define MAXCENTS 500
#define MAXSUM MAXCOINS * MAXCENTS
#define ABS(A) ((A) < 0 ? -((A)) : (A))

int possible[MAXSUM + 1];
int ncoins, value, sum;

int main()
{
int problems, i, j, min;

scanf("%d", &problems);
while (problems)
{
memset(possible, 0, sizeof(possible));
possible = 1;

sum = 0;

scanf("%d", &ncoins);
for (i = 0; i < ncoins; i++)
{
scanf("%d", &value);
sum += value;

for (j = MAXSUM - value; j >= 0; j--)
if (possible[j])
possible[j + value] = 1;
}

min = INT_MAX;

for (i = 1; i <= sum; i++)
if (possible && ABS(2 * i - sum) < min)
min = ABS(2 * i - sum);

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

problems--;
}

return 0;
}
[/c]

Any kind of help is appreciated. Minilek
Learning poster
Posts: 90
Joined: Tue Jul 27, 2004 9:34 am
Location: Cambridge, MA
Contact:
i submitted your code just as it is and it got AC. maybe it's the way you are submitting it? i tend to just submit via http://online-judge.uva.es/problemset/submit.php to avoid any of the weird errors that can occur from submitting via email.

Tomislav Novak
New poster
Posts: 44
Joined: Fri Feb 20, 2004 5:52 pm
Minilek wrote:i submitted your code just as it is and it got AC. maybe it's the way you are submitting it? i tend to just submit via http://online-judge.uva.es/problemset/submit.php to avoid any of the weird errors that can occur from submitting via email.
I submit via submit.php too... I've submited it again, twice, and it gave me WA both times. (after 0.004 secs) This is really weard...
I haven't had this problem when submitting other solutions?! You say you didn't make any changes?

Minilek
Learning poster
Posts: 90
Joined: Tue Jul 27, 2004 9:34 am
Location: Cambridge, MA
Contact:
hm..i guess i must have changed something after all. i copy/pasted your source again and resubmitted and now got WA..i don't remember changing anything though the first time ^^;

wait 'til tomorrow morning when i get to work, and i'll see what i did Tomislav Novak
New poster
Posts: 44
Joined: Fri Feb 20, 2004 5:52 pm
Minilek wrote:hm..i guess i must have changed something after all. i copy/pasted your source again and resubmitted and now got WA..i don't remember changing anything though the first time ^^;

wait 'til tomorrow morning when i get to work, and i'll see what i did Ok, thanks. Minilek
Learning poster
Posts: 90
Joined: Tue Jul 27, 2004 9:34 am
Location: Cambridge, MA
Contact:
AC. I changed

[c]
for (i = 1; i <= sum; i++)
if (possible && ABS(2 * i - sum) < min)
min = ABS(2 * i - sum);
[/c]

to this:

[c]
for (i = 0; i <= sum; i++)
if (possible && ABS(2 * i - sum) < min)
min = ABS(2 * i - sum);
[/c]

Basically the problem is that the problem statement says that ncoins is a nonnegative integer, not necessarily a *positive* integer. So your code will break out of the loop instantly when ncoins==0 and then print INT_MAX as the answer, when the correct answer for ncoins==0 is 0 since each person has 0 cents.

Tomislav Novak
New poster
Posts: 44
Joined: Fri Feb 20, 2004 5:52 pm
Minilek wrote: Basically the problem is that the problem statement says that ncoins is a nonnegative integer, not necessarily a *positive* integer. So your code will break out of the loop instantly when ncoins==0 and then print INT_MAX as the answer, when the correct answer for ncoins==0 is 0 since each person has 0 cents.
AC now. Thank you very much. halayli
New poster
Posts: 1
Joined: Mon Nov 15, 2004 5:07 pm

### 562 (Time limit exceeded)

Please can someone help me figure out why I'm getting "Time limit exceeded" from the OJ.

#include <stdio.h>
#include <stdlib.h>
int lst;
int lst1;
int limit;
int combination(int,int,int,int );
int cmp(int*,int*);
int main()
{
int totalcoins=0,coinvalues=0,z,x,y,i=0;
int totalinput;
int nearest=0,oldnearest=0;
char input;
int coins={0};
int sum=0;
fgets(input,1000,stdin);
totalinput=strtol(input,NULL,0);
while(totalinput){
sum=0;
i=0;
coinvalues=0;
scanf("%d",&totalcoins);
while(i!=totalcoins){
scanf("%d",&x);
coins[i++]=x;
}
for(x=0;x<totalcoins;x++)
coinvalues+=coins[x];
for(y=1;y<totalcoins;y++){
nearest=combination(totalcoins,y,coinvalues/2,coins);
if(abs(nearest-coinvalues/2)<=abs(oldnearest-coinvalues/2)){
for(z=0;z<limit;z++)
lst1[z]=lst[z];
oldnearest=nearest;
}
}
for(i=0;i<totalcoins;i++)
if(!bsearch(&i,lst1,limit,sizeof(int),(int(*)(const void*,const void*))cmp))
sum+=coins;
totalinput--;
printf("%d\n",abs(oldnearest-sum));
}
return 0;
}

int combination(int items,int pick,int casstime,int coins){
int a={0};
int number=items;
int select=pick;
int nearest=0;
int time=0,newtime=0;
int x,i,j;
for (i = 0; i < select; i++)
a = i + 1;

while (1)
{

if(newtime<time)
time=newtime;
newtime=0;

for (i = 0; i < select; i++)
newtime+= coins[a-1];
if(abs(newtime -casstime) < abs(time-casstime)){
time=newtime;
for(x=0;x<select;x++)
lst[x]=a[x]-1;
limit=select;
}

i = select - 1;
while (a == (number - select + i + 1))
--i;
if (i < 0) break;
++a;
for (j = i + 1; j < select; j++)
a[j] = a + j - i;
}
return time;
}
int cmp(int* a,int *b)
{
return *a-*b;
}

real_funghi
New poster
Posts: 1
Joined: Tue Jul 19, 2005 12:39 pm
Location: Ausztr
Contact:

### 562 - Runtime error

Hello, all!

Here's a code, that I wrote last week. The online judge says 'Runtime Error.

I tried it to compile in Borland C++ 5.01 & DevC++ 4.9.9.2
Both works.
I dont understand, where's the problem.

The Code:

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

void buborek(int t[], int n) {
int i,j,temp=0;

for (i=1;i<n;++i) {
for (j = n-1; j>=i; --j) {
if (t[j]<t[j-1]) {
temp = t[j];
t[j] = t[j-1];
t[j-1] = temp;
}
}
}
}

int main() {
int szor, cv;
int szam,i,legn=0;
int tomegek= {0};
int t1ossz=0,t2ossz=0;
float eredmenyek;

scanf("%d", &szor);
for (cv=0; cv<szor; ++cv) {
scanf("%d", &szam);

for (i=0; i<szam; ++i)
scanf("%d", &tomegek);

buborek(tomegek,szam);

legn=tomegek[szam-1];

t1ossz += legn;
for (i=szam-2; i>=0; --i) {
if (t1ossz <= t2ossz) t1ossz += tomegek; else t2ossz += tomegek;
}

eredmenyek[cv]=fabs(t1ossz-t2ossz);
t1ossz=0; t2ossz=0;
}

for (i=0; i<cv; ++i)
printf("%.0f\n", eredmenyek);

return 0;
}

chulin nagasaki
New poster
Posts: 3
Joined: Wed Apr 26, 2006 7:06 pm
Minilek wrote:AC. I changed

[c]
for (i = 1; i <= sum; i++)
if (possible && ABS(2 * i - sum) < min)
min = ABS(2 * i - sum);
[/c]

to this:

[c]
for (i = 0; i <= sum; i++)
if (possible && ABS(2 * i - sum) < min)
min = ABS(2 * i - sum);
[/c]

Basically the problem is that the problem statement says that ncoins is a nonnegative integer, not necessarily a *positive* integer. So your code will break out of the loop instantly when ncoins==0 and then print INT_MAX as the answer, when the correct answer for ncoins==0 is 0 since each person has 0 cents.

Well, the problem says:

Code: Select all

``````The value of a coin varies from 1 cent to 500 cents.
``````

sandy007smarty
New poster
Posts: 20
Joined: Thu Apr 20, 2006 6:55 pm
Contact:
The value of a coin varies from 1 cent to 500 cents.
Yes. But Minilek was talking about the case when there are 0 coins and not about a coin with value of 0 cents.

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

### Re: 562 - Dividing Coins

I tested it will some test case, I don't know why wrong answer?
Here is the code:

Code: Select all

``````#include<iostream>
using namespace std;

int calc(int *input, int n, int *sum){

int result=sum;
for(int i=0;i<n;i++){
int min = sum;
for(int j=0;j<=i;j++){
int temp = sum[j]-input[i];
if(temp>=0&&temp<min)
min = temp;
}
sum[i+1]=min;
if(min<result)
result = min;
}
return result;
}

int main(){

int m, n;
cin>>m;
for(int j=0;j<m;j++){
cin>>n;
if(n==0){
cout<<"0"<<endl;
continue;
}
int *input = new int[n];
int *sum = new int[n+1];
sum=0;
for(int i=0;i<n;i++){
cin>>input[i];
sum+=input[i];
input[i]*=2;
sum[i+1]=99999999;
}
cout<<calc(input, n, sum)<<endl;

delete input;
delete sum;
}``````

iit2006039
New poster
Posts: 2
Joined: Mon Jun 09, 2008 4:46 pm

### Re: 562 - Dividing Coins

@ raykou

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