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

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

11057 - Exact Sum

Post by FAQ » Sun Aug 06, 2006 4:25 am

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

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

Post by lbfacci » Sun Aug 06, 2006 4:48 am

Hint:

M = 2000000
N = 2
Books: 1000000 1 1000000

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

Post by FAQ » Sun Aug 06, 2006 4:57 am

thanks so much, I got AC :D

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

WA

Post by sfelixjr » Fri May 25, 2007 3:31 pm

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

Post by abhi » Wed Jun 20, 2007 4:59 am

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:

Post by mf » Wed Jun 20, 2007 6:22 am

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

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

Post by abhi » Wed Jun 20, 2007 10:21 am

could you please describe the algo

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

Post by little joey » Wed Jun 20, 2007 12:19 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

Post by renato_ferreira » Fri Jun 29, 2007 9:48 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:

Post by mf » Fri Jun 29, 2007 10:00 pm

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

Post by renato_ferreira » Fri Jun 29, 2007 10:55 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:

Post by mf » Fri Jun 29, 2007 11:13 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.

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

Post by renato_ferreira » Sat Jun 30, 2007 12:03 am

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:

Post by mf » Sat Jun 30, 2007 12:13 am

After each test case you must print a blank line.

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

WA

Post by afzal_du » Tue Sep 04, 2007 9:16 pm

why WA? :cry:

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

Post Reply

Return to “Volume 110 (11000-11099)”