11057 - Exact Sum

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

Moderator: Board moderators

sapnil
Experienced poster
Posts: 106
Joined: Thu Apr 26, 2007 2:40 pm
Location: CSE-SUST
Contact:

Post by sapnil » Sun Oct 07, 2007 6:45 pm

To afzal_du

You may miss this line

Code: Select all

if there are multiple solutions print the solution that minimizes the difference between the prices i and j.
Thanks
Keep posting
sapnil
SUST

maruf
New poster
Posts: 17
Joined: Sat May 24, 2008 6:00 pm

Re: 11057 - Exact Sum

Post by maruf » Sun Aug 03, 2008 9:54 pm

y rte??? :roll:

Code: Select all

#include<stdio.h>
long dif(long a,long b);
int main()
{
	
    long n,p,x[10099],r=0,s,m,j,min,k;
    while(scanf("%ld",&n)==1)
	{
    for(long i=0;i<n;i++)
    scanf("%ld",&x[i]);
    scanf("%ld",&p);
    r=0;
    for(k=0;k<n-1;k++)
	{
		for(j=k+1;j<n;j++)
		{
			if(x[k]+x[j]==p)
			{
				min=dif(x[k],x[j]);
				{
					if(r==0)
						s=min;
					    r=1;
					if(min<=s)
						s=min;
					else
						continue;
					m=x[k];
					n=x[j];
				}
			}
		}
	}
	if(m>n)
	{
		s=m;
	    m=n;
		n=s;
	}
	int cs;
	if(cs==1)
		printf("\n");
	cs=1;
	printf("Peter should buy books whose prices are %ld and %ld.\n",m,n);
	}
	return 0;
      
}

long dif(long a,long b)
{
    if(a<=b)
      return b-a;
      else
    return a-b;
}     
lives for eternity......

me_br
New poster
Posts: 1
Joined: Sun Feb 15, 2009 6:16 pm

Re: 11057 - Exact Sum

Post by me_br » Sun Feb 15, 2009 6:18 pm

Does anyone see in the code below why I'm receiving Runtime Error?

Code: Select all

import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String args[]){
		Scanner in = new Scanner(System.in);
		
		String s;
		while((s = in.nextLine()) != null) {
			if(s.equals("\n") || s.equals("") || s.equals(" ")) continue;
			
			int n = Integer.parseInt(s);
			
			int[] values = new int[n];
			String num = in.nextLine();
			
			String[]nums = num.split(" ");
			for(int i = 0; i < values.length; i++) {
				values[i] = Integer.parseInt(nums[i]);
			}
			
			int m = in.nextInt();
			
			Arrays.sort(values);
			
			int ri = 0, rj = 0;
			for(int i = 0; i < values.length; i++) {
				int i1 = values[i];
				
				if(i1 > m) break;
				
				for(int j = i+1; j < values.length; j++) {
					int i2 = values[j];
					if(i2 > m) break;
					
					if(i1 + i2 == m) {
						if(ri + rj == i1 + i2) {
							if(rj - ri > i2 - i1) {
								ri = i1;
								rj = i2;
							}
						} else {
							ri = i1;
							rj = i2;
						}
					}
				}
			}
			
			System.out.printf("Peter should buy books whose prices are %d and %d.\n", ri, rj);
		}
	}
}
Thanks a lot!

lnr
Experienced poster
Posts: 141
Joined: Sat Jun 30, 2007 2:52 pm
Location: Dhaka,Bangladesh

Re:

Post by lnr » Fri Sep 11, 2009 10:26 am

abhi wrote:i have AC in 4.871 s .
i have used a O(n^2) algorithm. is there any linear algorithm for this problem ????
AC in 4.871s.How?
Problems's time limit 1s.

Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Location: University Of Dhaka,Bangladesh
Contact:

Re: 11057 - Exact Sum

Post by Shafaet_du » Fri Oct 15, 2010 7:36 pm

This may help you a bit:

Code: Select all

5
10 20 30 40 50
60

10
1 20 34 67 78 34 67 34 56 100
101

8
0 32 23 14 15 16 17 37
37
output:

Code: Select all

Peter should buy books whose prices are 20 and 40.

Peter should buy books whose prices are 34 and 67.

Peter should buy books whose prices are 14 and 23.

Dont forget to print blank line after each output.

rahat khan
New poster
Posts: 10
Joined: Mon May 23, 2011 1:12 pm

Re: 11057 - Exact Sum

Post by rahat khan » Tue Aug 16, 2011 9:22 pm

Code: Select all

#include<stdio.h>
int main()
{
long long n,i,m,c,a[11000],x,y,j;
while(scanf("%lld",&n)!=EOF)
{
         for(i=0;i<n;i++)
         {
           scanf("%lld",&a[i]);
         }
          scanf("%lld",&m);
          c=m;
      for(i=0;i<n-1;i++)
      {
          for(j=i+1;j<=n-1;j++)
          {
            if((a[i]+a[j])==m)
	    {
                if((a[i]>a[j])&&(a[i]-a[j])<c)
                {
                   x=i;
                   y=j;
                }
                if((a[j]-a[i])<c)
                {
                   x=i;
                   y=j;
                }
	    }
          }
      }
      if(a[x]>a[y])
      printf("Peter should buy books whose prices are %lld and %lld.\n",a[y],a[x]);
      else
      printf("Peter should buy books whose prices are %lld and %lld.\n",a[x],a[y]);
      printf("\n");
}
return 0;
}

User avatar
mahade hasan
Learning poster
Posts: 87
Joined: Thu Dec 15, 2011 3:08 pm
Location: University of Rajshahi,Bangladesh

Re: 11057 - Exact Sum

Post by mahade hasan » Thu Jun 14, 2012 9:51 am

cut>>ACC
we r surrounded by happiness
need eyes to feel it!

shopnobaj_raju
New poster
Posts: 7
Joined: Wed Oct 19, 2011 5:07 pm

Re: 11057 - Exact Sum

Post by shopnobaj_raju » Sat Jun 16, 2012 2:47 pm

why am i getting wa??

Code: Select all

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

int main()
{
	int i,j,k,N;
	long int books[10002],M,sum,price1,price2,min_diff;
	while(scanf("%d\n",&N)!=EOF)
	{
		for(i=1;i<=N;i++) scanf("%ld",&books[i]);
		scanf("%ld",&M);
		price1=0;
		price2=0;
		min_diff=3000000;
		for(i=1;i<=N;i++)
		{
			for(j=i+1;j<=N;j++)
			{
				if(books[i]+books[j]==M)
				{
					if(abs(books[i]-books[j])<min_diff)
					{
						price1=books[i];
						price2=books[j];
					}
				}
			}
		}
		if(price1<=price2) printf("Peter should buy books whose prices are %ld and %ld.\n\n",price1,price2);
		else printf("Peter should buy books whose prices are %ld and %ld.\n\n",price2,price1);
	}
	return 0;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11057 - Exact Sum

Post by brianfry713 » Tue Jun 19, 2012 12:01 am

Try the input:

Code: Select all

4
4 6 2 8
10
Check input and AC output for thousands of problems on uDebug!

shopnobaj_raju
New poster
Posts: 7
Joined: Wed Oct 19, 2011 5:07 pm

Re: 11057 - Exact Sum

Post by shopnobaj_raju » Thu Jun 21, 2012 8:48 pm

Thanks brianfry. U r a great helper. :)

biahll
New poster
Posts: 3
Joined: Mon Jun 25, 2012 11:10 pm

Re: 11057 - Exact Sum

Post by biahll » Mon Jun 25, 2012 11:13 pm

Hey guys.

I'm getting Runtime Error on this one. It works for every input/output I tried, but still... runtime error on valladolid =/

I have to do it in Java. College stuff. Here's my code.

Code: Select all

Code removed after got AC =)
Can anyone help me?
Tyvm.
Last edited by biahll on Thu Jun 28, 2012 8:01 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11057 - Exact Sum

Post by brianfry713 » Tue Jun 26, 2012 12:20 am

Input

Code: Select all

3
1000000 100000 1
1100000
Check input and AC output for thousands of problems on uDebug!

biahll
New poster
Posts: 3
Joined: Mon Jun 25, 2012 11:10 pm

Re: 11057 - Exact Sum

Post by biahll » Thu Jun 28, 2012 8:00 pm

Thanks, I was missing one condition before getting into array's position =)

tarsun
New poster
Posts: 7
Joined: Thu Sep 20, 2012 7:58 pm
Contact:

11057 - Exact Sum

Post by tarsun » Tue Nov 06, 2012 8:20 pm

Why Wrong Answer?? pls help

Code: Select all

#include<stdio.h>
#include<string.h>

int main()
{
     static long long int n,ary[10002],m,i,j,k,val,small,i1,i2;
//     freopen("F:\\a.txt","r",stdin);
//    freopen("F:\\b.txt","w",stdout);
     while(scanf("%lld\n",&n)==1)
     {
	  for(i=1;i<=n;i++)
		scanf("%lld",&ary[i]);
	  scanf("%lld",&m);//price
	  small=0;
	  for(j=1;j<n;j++)
		for(k=j+1;k<=n;k++)
		{	if(ary[j]+ary[k]==m)
			{  if(ary[j]>ary[k])
			   {	val=ary[j]-ary[k];
				i1=ary[k];
				i2=ary[j];
			   }
			   else
			   {
				val=ary[k]-ary[j];
				i1=ary[j];
				i2=ary[k];
			   }
			   if(small==0)
			     small=val;

			   else if(val<=small)
				 small=val;

			}

		}
		printf("Peter should buy books whose prices are %lld and %lld.\n",i1,i2);
		if(i!=n)
			printf("\n");
     }
     return 0;
}


Munchor
New poster
Posts: 19
Joined: Sun Mar 03, 2013 4:03 pm

Re: 11057 - Exact Sum

Post by Munchor » Wed Mar 20, 2013 10:54 pm

Code: Select all

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

using namespace std;

#define MAX 10001
long long int books[MAX];

int main()
{
  long long int n_books, i, u, solution[2], money;

  while (scanf("%lld", &n_books) != EOF)
  {
    memset(books, 0, sizeof books);
    memset(solution, 0, sizeof solution);

    for (i = 0; i < n_books; i++)
    {
      scanf("%lld", &books[i]);
    }

    scanf("%lld", &money);

    for (i = 0; i < n_books - 1; i++)
    {
      for (u = i + 1; u < n_books; u++)
      {
        if (books[i] + books[u] == money)
        {
          if (solution[0] == 0 && solution[1] == 0)
          {
            solution[0] = books[i];
            solution[1] = books[u];
          }
          else
          {
            if (abs(books[i] - books[u]) < abs(solution[0] - solution[1]))
            {
              solution[0] = books[i];
              solution[1] = books[u];
            }
          }

          break;
        }
      }
    }

    printf("Peter should buy books whose prices are %lld and %lld.\n", solution[0], solution[1]);
  }

  return 0;
}
That's my code and it solves example IO and works for big numbers too since I'm using long long it. However, I'm getting WA. Can somebody provide critical input or give me some ideas regarding my code?

I also tried Binary Search, but with Binary Search I get Runtime Error.

Code: Select all

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>

using namespace std;

#define MAX 10001
vector<long long int> books;

long long int books_binary_search(long long int key, long long int min, long long int max, int original)
{
  if (max < min)
  {
    return 0;
  }
  else
  {
    int middle_value = (min + max) / 2;
    //printf("middle_value = %d, books[%d] = %lld, key=%lld\n", middle_value, middle_value, books[middle_value], key);

    if (books[middle_value] > key)
    {
      return books_binary_search(key, min, middle_value - 1, original);
    }
    else if (books[middle_value] < key)
    {
      return books_binary_search(key, middle_value + 1, max, original);
    }
    else
    {
      if (middle_value == original)
      {
        return 0;
      }
      
      return 1;
    }
  }
}

int main()
{
  long long int n_books, i, u, solution[2], money;

  while (scanf("%lld", &n_books) != EOF)
  {
    books.clear();
    memset(solution, 0, sizeof solution);

    for (i = 0; i < n_books; i++)
    {
      books.push_back(0);
      scanf("%lld", &books[i]);
    }

    sort(books.begin(), books.end());

    scanf("%lld", &money);

    for (i = 0; i < n_books - 1; i++)
    {
      //printf("%lld\n", books[i]);

      if (books_binary_search(0, n_books - 1, money - books[i], i))
      {
        if (solution[0] == 0 && solution[1] == 0)
        {
          solution[0] = books[i];
          solution[1] = money - books[i];
        }
        else
        {
          if (abs(books[i] - (money - books[i])) < abs(solution[0] - solution[1]))
          {
            solution[0] = books[i];
            solution[1] = money - books[i];
          }
        }
      }
    }

    printf("Peter should buy books whose prices are %lld and %lld.\n", solution[0], solution[1]);
  }

  return 0;
}
Thank you.

Post Reply

Return to “Volume 110 (11000-11099)”