562  Dividing coins
Moderator: Board moderators
562
could someone tell me how did those guys solved the problem in 0.0000 seconds? what algorithm did they use? thank you
none
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...
thanks in advance
here's my code:
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...
thanks in advance
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[0]);
continue;
}
qsort((void *)num, m, sizeof(num[0]), comp);
if(m == 2)
{
printf("%ld\n",num[0]num[1]);
continue;
}
num_size = sum+2;
for(i=0;i<num_size;i++)
flag[i] = 0;
flag[0] = 1;
for(i=m1;i>=0;i)
{
flag[num[i]] = 1;
sum1 = num[i];
for(j=i1;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",r2r1);
else printf("%ld\n",r1r2);
}
}
Wisdom is know what to do next; virtue is doing it.

 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[0] = 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.
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[0] = 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.
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://onlinejudge.uva.es/problemset/submit.php to avoid any of the weird errors that can occur from submitting via email.

 New poster
 Posts: 44
 Joined: Fri Feb 20, 2004 5:52 pm
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...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://onlinejudge.uva.es/problemset/submit.php to avoid any of the weird errors that can occur from submitting via email.
I haven't had this problem when submitting other solutions?!
You say you didn't make any changes?

 New poster
 Posts: 44
 Joined: Fri Feb 20, 2004 5:52 pm
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.
[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.

 New poster
 Posts: 44
 Joined: Fri Feb 20, 2004 5:52 pm
AC now. Thank you very much.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.
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[100];
int lst1[100];
int limit;
int combination(int,int,int,int [100]);
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[500];
int coins[100]={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(nearestcoinvalues/2)<=abs(oldnearestcoinvalues/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(oldnearestsum));
}
return 0;
}
int combination(int items,int pick,int casstime,int coins[100]){
int a[100]={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[a1];
if(abs(newtime casstime) < abs(timecasstime)){
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;
}
#include <stdio.h>
#include <stdlib.h>
int lst[100];
int lst1[100];
int limit;
int combination(int,int,int,int [100]);
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[500];
int coins[100]={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(nearestcoinvalues/2)<=abs(oldnearestcoinvalues/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(oldnearestsum));
}
return 0;
}
int combination(int items,int pick,int casstime,int coins[100]){
int a[100]={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[a1];
if(abs(newtime casstime) < abs(timecasstime)){
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;
}

 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 = n1; j>=i; j) {
if (t[j]<t[j1]) {
temp = t[j];
t[j] = t[j1];
t[j1] = temp;
}
}
}
}
int main() {
int szor, cv;
int szam,i,legn=0;
int tomegek[20]= {0};
int t1ossz=0,t2ossz=0;
float eredmenyek[100000];
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[szam1];
t1ossz += legn;
for (i=szam2; i>=0; i) {
if (t1ossz <= t2ossz) t1ossz += tomegek; else t2ossz += tomegek;
}
eredmenyek[cv]=fabs(t1osszt2ossz);
t1ossz=0; t2ossz=0;
}
for (i=0; i<cv; ++i)
printf("%.0f\n", eredmenyek);
return 0;
}
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 = n1; j>=i; j) {
if (t[j]<t[j1]) {
temp = t[j];
t[j] = t[j1];
t[j1] = temp;
}
}
}
}
int main() {
int szor, cv;
int szam,i,legn=0;
int tomegek[20]= {0};
int t1ossz=0,t2ossz=0;
float eredmenyek[100000];
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[szam1];
t1ossz += legn;
for (i=szam2; i>=0; i) {
if (t1ossz <= t2ossz) t1ossz += tomegek; else t2ossz += tomegek;
}
eredmenyek[cv]=fabs(t1osszt2ossz);
t1ossz=0; t2ossz=0;
}
for (i=0; i<cv; ++i)
printf("%.0f\n", eredmenyek);
return 0;
}
Hala Madrid!

 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.

 New poster
 Posts: 20
 Joined: Thu Apr 20, 2006 6:55 pm
 Location: Hyderabad
 Contact:
Re: 562  Dividing Coins
I tested it will some test case, I don't know why wrong answer?
Please help me, thank you.
Here is the code:
Please help me, thank you.
Here is the code:
Code: Select all
#include<iostream>
using namespace std;
int calc(int *input, int n, int *sum){
int result=sum[0];
for(int i=0;i<n;i++){
int min = sum[0];
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]=0;
for(int i=0;i<n;i++){
cin>>input[i];
sum[0]+=input[i];
input[i]*=2;
sum[i+1]=99999999;
}
cout<<calc(input, n, sum)<<endl;
delete input;
delete sum;
}

 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.
your code have some missing brackets.
see to it and paste again your code.