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

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

562

Post by newhh2002 » Tue Jan 28, 2003 8:33 am

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
Location: SUST,BANGLADESH
Contact:

Post by razibcse » Thu Nov 06, 2003 4:57 pm

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:

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

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

562 - Dividing Coins

Post by Tomislav Novak » Wed Aug 11, 2004 4:24 pm

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

Minilek
Learning poster
Posts: 90
Joined: Tue Jul 27, 2004 9:34 am
Location: Cambridge, MA
Contact:

Post by Minilek » Tue Aug 17, 2004 4:27 am

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.

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

Post by Tomislav Novak » Tue Aug 17, 2004 2:30 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:

Post by Minilek » Tue Aug 17, 2004 4:37 pm

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 :D

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

Post by Tomislav Novak » Tue Aug 17, 2004 5:13 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 :D
Ok, thanks. ;-)

Minilek
Learning poster
Posts: 90
Joined: Tue Jul 27, 2004 9:34 am
Location: Cambridge, MA
Contact:

Post by Minilek » Wed Aug 18, 2004 2:24 am

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.

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

Post by Tomislav Novak » Wed Aug 18, 2004 10:07 am

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)

Post by halayli » Mon Nov 15, 2004 5:10 pm

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(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[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[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;
}

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

562 - Runtime error

Post by real_funghi » Tue Jul 19, 2005 12:45 pm

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[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[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;
}
Hala Madrid!

chulin nagasaki
New poster
Posts: 3
Joined: Wed Apr 26, 2006 7:06 pm

Post by chulin nagasaki » Sat Jul 22, 2006 9:55 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
Location: Hyderabad
Contact:

Post by sandy007smarty » Mon Aug 20, 2007 6:37 pm

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

Post by raykou » Sun Jun 29, 2008 5:35 am

I tested it will some test case, I don't know why wrong answer?
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;
 }

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

Re: 562 - Dividing Coins

Post by iit2006039 » Sun Jun 29, 2008 2:23 pm

@ raykou

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

Post Reply

Return to “Volume 5 (500-599)”