545 - Heads

All about problems in Volume 5. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Antonio Ocampo
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per

Post by Antonio Ocampo » Sun Jan 30, 2005 5:05 am

Please, help me. I don't know why I got WA.
Last edited by Antonio Ocampo on Mon Jan 31, 2005 3:14 am, edited 1 time in total.

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

Post by Emilio » Sun Jan 30, 2005 7:41 am

Hi Antonio,

Firstly, you must catch correctly the input. See my post, for example.

Secondly, I have compared your output with mine for the 9000 possible cases and are the same!!! I have sent your code corrected and obtain WA!!!
I think that is a problem of small differences with the compilers (I have used Dev-C++).

Sorry, I can't help you much!!!

I'll try later, now I'm going to study. Next exam this monday 8)

Bye.

Antonio Ocampo
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per

Post by Antonio Ocampo » Sun Jan 30, 2005 8:06 am

Emilio wrote:
Hi Antonio,

Firstly, you must catch correctly the input. See my post, for example.

Secondly, I have compared your output with mine for the 9000 possible cases and are the same!!! I have sent your code corrected and obtain WA!!!
I think that is a problem of small differences with the compilers (I have used Dev-C++).

Well, I have used Dev-C++ too :-? . I don't know what's going on :evil:
Could someone tell me how to cath the input?? I don't know what to do :oops:

Thanks in advance

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

Post by Emilio » Sun Jan 30, 2005 11:40 pm

Your problem when you catch the input data is that you don't see if there is a blank line no time. You must do it as multiple input specification say. In the post where is my code you can see an example of this.

By another way, I used Dev-C++, and with this compiler I have compared your result and mine, and are the same, but the OJ say that no. And by this I think that the compiler of OJ obtain correct result for my code, but no for your code. I have used an approach different of yours.

Antonio Ocampo
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per

Post by Antonio Ocampo » Mon Jan 31, 2005 3:17 am

I have corrected my code, but I still got WA. I don't know what's going on :x

My code is this

Code: Select all


Deleted
Last edited by Antonio Ocampo on Fri May 06, 2005 12:28 am, edited 1 time in total.

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

Post by Emilio » Mon Jan 31, 2005 4:49 am

I solved your problem,

First, see another time my code in this post and see as I realized the output of the blank line, yours is wrong.

Second, your results are right, you only must see if the fourth decimal digit is == 5, in this case sum 0.0001 at the result and print it.

Only that.
Good luck!!!

Antonio Ocampo
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per

Post by Antonio Ocampo » Mon Jan 31, 2005 6:33 pm

This is my corrected program, again. :oops: But it doesn
Last edited by Antonio Ocampo on Fri May 06, 2005 12:29 am, edited 1 time in total.

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

Post by Emilio » Mon Jan 31, 2005 11:57 pm

First, you must change

Code: Select all

if (casos>1)
by

Code: Select all

if (casos>=1)
Second, you only must sum 0.0001 if the fourth decimal digit (after the point) is == 5

Third, you must change "s" by "n" in printf function.

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Mon May 02, 2005 7:38 am

nnahas, my code prints the same answers as the 150 that you posted, but it's still WA. Could you send me all of the 9000 answers? Here is my code. It's almost the same as the ones posted above.

Code: Select all

int main()
{
    int N; cin >> N;
    while( N-- )
    {
        int n; cin >> n;
        int exp = ( int )ceil( log10( ( long double )2.0 ) * n );
        long double mantissa = pow( 10.0, exp - log10( ( long double )2.0 ) * n );
        printf( "2^%d = %.3LfE%d\n", -n, mantissa, -exp );
    }
    return 0;
}
I think this problem should require 7 decimal places, but have a special judge to allow plus or minus one in the last digit. Otherwise, in these problems you have to get lucky and make the same choices as the problem setter. :-(
If only I had as much free time as I did in college...

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

Post by little joey » Thu May 05, 2005 9:43 am

I am afraid I don't agree with you here.
For this problem it is quite possible to calculate the exact answers (using arbitrary precision calculus and rounding) and I think this is what the problemsetter had in mind. If you choose to use an approximation (using floating point calculus) you should be prepared to get (language and implementation specific) precision errors, like the ones you encounter. But then don't blame the problemsetter... :)

FYI:
My first program, using arbitrary precision and rounding, got AC at once in about 2 seconds.
My second program, using approximation, gets accepted in about 0.15 seconds, but I had to write several versions before all 9000 possible answers were exactly the same as the ones I calculated using my first program.

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Thu May 05, 2005 4:30 pm

Ok. That's fair. If the exact solution gets accepted, then I like this problem much more now. :-) I'll do it with BigInt.
If only I had as much free time as I did in college...

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Thu May 05, 2005 7:23 pm

Accepted at last!

One detail that cost me a couple of WA submissions is that sometimes the number may look like this:
3.9996.... x 10^-p
In this case, make sure that you print
4.000E-p
If only I had as much free time as I did in college...

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

Post by Eduard » Thu May 05, 2005 8:37 pm

Hello.
I have solved this problem using DP and Pascal.But 474 I solve using C++.
And I solve this one from first submission.
I think it is better to try this problem using Pascal,but 474 using C++.
Eduard.
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Tue Aug 22, 2006 8:32 pm

About the arbitrary precision and rounding - it is true, you have to do that, although I had to manually round the numbers, couldn't use Java's Math.round()

I used BigInt (start with 1000...000) and if I converted first five digits into a double and rounded it with Math.round() it didn't work. When I used integers and rounded it with something like
if (s.charAt(4) > '4') tmp++;
, it worked.

Here are a few interesting cases:
Input:

Code: Select all

3
287
669
4168
Output:

Code: Select all

2^-287 = 4.022E-87
2^-669 = 4.083E-202
2^-4168 = 2.028E-1255
EDIT: It was just rounding after all - arbitrary precision is NOT needed, I used doubles and kept them in [1.0,10.0), but manually rounded them (as described above). I am not sure why Math.round() approach wasn't working.

amine.hamdaoui
New poster
Posts: 10
Joined: Tue Aug 07, 2007 7:33 pm

Post by amine.hamdaoui » Fri Oct 19, 2007 7:30 pm

Why do i get WA. I use exact calculation. I have tested my code for all the tests in this topic, and it match!!!!

Code: Select all

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int i,j,r,n,*y,a;
    double *x;

    y = (int *) malloc(sizeof(int )*1000001);
    x = (double *) malloc(sizeof(double)*1000001);

    x[0] = 1;
    y[0] = 0;
    for(j=1 ; j<1000001 ; j++)
    {
        x[j] =x[j-1]/2.0;
        if(x[j]<1)
        {
            x[j] *=10.0;
            y[j]=y[j-1]+1;
        }
        else y[j]=y[j-1];
    }
    scanf("%d",&r);

    for(i=1 ; i<=r ; i++)
    {
        scanf("%d",&n);
        printf("2^-%d = %1.3fE-%d\n",n,x[n],y[n]);
    }
	return 0;
}
Last edited by amine.hamdaoui on Tue Oct 23, 2007 5:56 pm, edited 2 times in total.

Post Reply

Return to “Volume 5 (500-599)”