11057 - Exact Sum

[sapnil]

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]

y rte???

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


[me_br]

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]

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.

[zhoung2025]

up up up





replica watches, replica watch, fake watches, fake watch, replica handbags

[Shafaet_du]

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]

#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;
}

[mahade hasan]

cut>>ACC

[shopnobaj_raju]

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]

Try the input:

Code: Select all

4
4 6 2 8
10

[shopnobaj_raju]

Thanks brianfry. U r a great helper.

[biahll]

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.

[brianfry713]

Input

Code: Select all

3
1000000 100000 1
1100000

[biahll]

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

[Munchor]

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.