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

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Sat Oct 20, 2007 5:36 pm

malloc() declares memory but not initializes it. So, you must initialize y[0] before using it. Hope it helps.
Ami ekhono shopno dekhi...
HomePage

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

Post by amine.hamdaoui » Tue Oct 23, 2007 5:58 pm

I did it, but it still doesn't work WA. Do you have any others ideas?

DD
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:

Re: 545

Post by DD » Thu Nov 06, 2008 11:05 am

amine.hamdaoui wrote: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;
}
I would recommand you to use interget to substitute double and perform exact calculation, since it maybe lost precison due to the using of double.

P.S. After two times W.A. by using the formula of 474, I decided to use exact calculation by interger and got A.C. finally. :D
Have you ever...
  • Wanted to work at best companies?
  • Struggled with interview problems that could be solved in 15 minutes?
  • Wished you could study real-world problems?
If so, you need to read Elements of Programming Interviews.

User avatar
plamplam
Experienced poster
Posts: 150
Joined: Fri May 06, 2011 11:37 am

Re: 545

Post by plamplam » Wed Jul 13, 2011 7:02 pm

I solved both 545 and 474 without log or log10 or pow or bigint. For 474, after you calculate the result, use the following snippet to output your result.
cout << showpoint << setprecision(4) << result;
The correct output for 6 is 1.562e-2 and not 1.563e-2 for 474. This is because the number is not rounded in this problem.

For 545, I got Wrong Answer thrice before I got Accepted. After I got Accepted, I thought I would compare the output of my programs and I wanted to post here some special cases, but guess what? The two outputs incisively matched on codeblocks. If you want to get accepted then one hint (I got accepted after adding 3 lines):

Consider the numbers 1.11450, 1.11550, 1.11650 and 1.11650.
Say x = 1.11450. Now if you print x with %0.3lf then the outputs for the four numbers will be:
1.115, 1.115, 1.117 and 1.117
Modify your code so that the output for these four numbers are instead:
1.115, 1.116, 1.117 and 1.118

Even after this modification, all the values from 1 to 9000 still remain unchanged(at least on my compiler) but for some eerie reason, the online judge doesn't accept without this rounding alteration.
This should help you :)
You tried your best and you failed miserably. The lesson is 'never try'. -Homer Simpson

xander7b
New poster
Posts: 3
Joined: Wed Aug 25, 2010 4:57 pm

Re: 545

Post by xander7b » Mon Jun 11, 2012 2:09 pm

I got AC after replacing long double with double ! Used log10, pow and cin<<fixed and cin.precision(3) cin.precision(0)

achan8501
New poster
Posts: 6
Joined: Mon Nov 05, 2012 9:13 pm

Re: 545

Post by achan8501 » Tue Dec 04, 2012 6:21 am

I honestly do not know what's wrong with my code. I used the square and double method, which worked perfectly well on 474, and is failing hard here. Eventually I took the suggestion of using BigInt, and got it accepted. I still have no idea what's wrong though, since both code gives the same output for all 9000 values.

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 545 - Heads

Post by lighted » Thu Nov 13, 2014 6:15 pm

Dominik Michniewski wrote:try to use log2() instead of log10() .... log2() means log(), I think .....

I remember, that it was difference in rounding ....

Dominik Michniewski
Got accepted with log10() and pow() in 0.015. There is no need in BigInt. :)
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

metaphysis
Experienced poster
Posts: 139
Joined: Wed May 18, 2011 3:04 pm

Re: 545 - Heads

Post by metaphysis » Thu Aug 18, 2016 8:40 am

The format of Sample Input is wrong, there is no r in first line.

Post Reply

Return to “Volume 5 (500-599)”