## 11057 - Exact Sum

Moderator: Board moderators

FAQ
Learning poster
Posts: 84
Joined: Wed Jan 28, 2004 6:23 pm

### 11057 - Exact Sum

Code: Select all

ACed
Last edited by FAQ on Sun Aug 06, 2006 4:57 am, edited 1 time in total.

lbfacci
New poster
Posts: 4
Joined: Wed Nov 02, 2005 7:28 pm
Hint:

M = 2000000
N = 2
Books: 1000000 1 1000000

FAQ
Learning poster
Posts: 84
Joined: Wed Jan 28, 2004 6:23 pm
thanks so much, I got AC

sfelixjr
New poster
Posts: 9
Joined: Wed Apr 25, 2007 3:29 pm
Location: Brazil
Contact:

### WA

Hi Guys, i've tried to solve this problem, but i got wa, do u have any test cases?

abhi
Learning poster
Posts: 94
Joined: Fri Nov 25, 2005 7:29 pm
i have AC in 4.871 s .
i have used a O(n^2) algorithm. is there any linear algorithm for this problem ????

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
abhi wrote:is there any linear algorithm for this problem ?
Yes.

abhi
Learning poster
Posts: 94
Joined: Fri Nov 25, 2005 7:29 pm
could you please describe the algo

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
Spoiler:

Imagine you have an array of booleans where you remember if a book of a certain price is already read from the input. Then if you read a book of price p, and you have already read a book of price money-p, then you have a valid combination. Remember the valid combination that minimizes the difference. So you have the answer when you've finished reading the input in O(n).

[Sorry mf for answering this for you ]
The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.

renato_ferreira
New poster
Posts: 21
Joined: Thu Jun 14, 2007 11:45 pm
Hello, I can't see the error of this code:

Code: Select all

(removed)
Thank you.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
Input:

Code: Select all

4
10 20 20 30
40

3
5 35 20
40
Correct output:

Code: Select all

Peter should buy books whose prices are 20 and 20.

Peter should buy books whose prices are 5 and 35.

Edit: there should be a blank line at the end of output.
Last edited by mf on Sat Jun 30, 2007 12:17 am, edited 1 time in total.

renato_ferreira
New poster
Posts: 21
Joined: Thu Jun 14, 2007 11:45 pm
I changed my code, but I got WA again:

Code: Select all

(removed)
Thank you.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
You're first putting results in res[1..cont], and then seek the minimum-difference one among res[0..cont-1].
And the seeking part is wrong, too.

renato_ferreira
New poster
Posts: 21
Joined: Thu Jun 14, 2007 11:45 pm
Now I got Presentation Error...

Code: Select all

#include <stdio.h>

#define MAX 10001

int main()
{
int i, j, livros, sub, menor, dinheiro, preco[MAX], res[MAX][2], pos, flag = 0, cont, soma;

while (scanf("%d\n", &livros) == 1)
{
for (i = 0; i < livros; i++)
{
scanf("%d", &preco[i]);
}

scanf("%d", &dinheiro);

cont = 0;

for (i = 0; i < livros; i++)
{
for (j = i; j < livros; j++)
{
if (i != j)
{
soma = preco[i] + preco[j];

if (soma == dinheiro)
{
cont++;

if (preco[i] > preco[j])
{
res[cont][0] = preco[i];
res[cont][1] = preco[j];
}

else
{
res[cont][0] = preco[j];
res[cont][1] = preco[i];
}
}
}
}
}

menor = 1000001;

if (cont > 1)
{
for (i = 1; i < (cont + 1); i++)
{
sub = res[i][0] - res[i][1];

if (sub < menor)
{
menor = sub;
pos = i;
}
}
}

else
{
pos = 1;
}

if (flag == 1)
{
printf("\n");
}

else
{
flag = 1;
}

if (res[pos][0] < res[pos][1])
{
printf("Peter should buy books whose prices are %d and %d.\n", res[pos][0], res[pos][1]);
}

else
{
printf("Peter should buy books whose prices are %d and %d.\n", res[pos][1], res[pos][0]);
}
}

return 0;
}
Thank you.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
After each test case you must print a blank line.

afzal_du
New poster
Posts: 4
Joined: Mon Oct 10, 2005 7:14 pm
Contact:

### WA

why WA?

Code: Select all

I've modified the code and got acc

first i thought that
for input
3
1 2 3
4
output will be
peter should bye ... 1 and 3

but i modified the code to have the output
peter should bye ... 2 and 2
and got acc

::: why should peter buy duplicate books?? :::