11057 - Exact Sum

[FAQ]

I wonder why I got RE in 0.014s. please help me

Code: Select all

ACed


[lbfacci]

Hint:

M = 2000000
N = 2
Books: 1000000 1 1000000

[FAQ]

thanks so much, I got AC

[sfelixjr]

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

[abhi]

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

[mf]

is there any linear algorithm for this problem ?

Yes.

[abhi]

could you please describe the algo

[little joey]

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 ]

[renato_ferreira]

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

Code: Select all

(removed)

Thank you.

[mf]

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.

[renato_ferreira]

I changed my code, but I got WA again:

Code: Select all

(removed)

Thank you.

[mf]

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]

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]

After each test case you must print a blank line.

[afzal_du]

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