## 11057 - Exact Sum

Moderator: Board moderators

### 11057 - Exact Sum

Code: Select all
`ACed`
Last edited by FAQ on Sun Aug 06, 2006 4:57 am, edited 1 time in total.
FAQ
Learning poster

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

Hint:

M = 2000000
N = 2
Books: 1000000 1 1000000
lbfacci
New poster

Posts: 4
Joined: Wed Nov 02, 2005 7:28 pm

thanks so much, I got AC
FAQ
Learning poster

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

### WA

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

Posts: 9
Joined: Wed Apr 25, 2007 3:29 pm
Location: Brazil

i have AC in 4.871 s .
i have used a O(n^2) algorithm. is there any linear algorithm for this problem ????
abhi
Learning poster

Posts: 94
Joined: Fri Nov 25, 2005 7:29 pm

abhi wrote:is there any linear algorithm for this problem ?

Yes.
mf
Guru

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

could you please describe the algo
abhi
Learning poster

Posts: 94
Joined: Fri Nov 25, 2005 7:29 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.

little joey
Guru

Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Hello, I can't see the error of this code:

Code: Select all
`(removed)`

Thank you.
renato_ferreira
New poster

Posts: 21
Joined: Thu Jun 14, 2007 11:45 pm

Input:
Code: Select all
`410 20 20 304035 35 2040`

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.
mf
Guru

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

I changed my code, but I got WA again:

Code: Select all
`(removed)`

Thank you.
renato_ferreira
New poster

Posts: 21
Joined: Thu Jun 14, 2007 11:45 pm

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.
mf
Guru

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

Now I got Presentation Error...

Code: Select all
`#include <stdio.h>#define MAX 10001int 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.
renato_ferreira
New poster

Posts: 21
Joined: Thu Jun 14, 2007 11:45 pm

After each test case you must print a blank line.
mf
Guru

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

### WA

why WA?
Code: Select all
`I've modified the code and got accfirst i thought thatfor input31 2 34output will bepeter should bye ... 1 and 3but i modified the code to have the outputpeter should bye ... 2 and 2 and got acc::: why should peter buy duplicate books?? :::`
afzal_du
New poster

Posts: 4
Joined: Mon Oct 10, 2005 7:14 pm