## 474 - Heads / Tails Probability

Moderator: Board moderators

ram
New poster
Posts: 30
Joined: Wed Mar 06, 2002 2:00 am
Contact:

### 474 problem

My code works fine with all the test cases I tested. but I am getting a WA.
Can anybody help me out??? Here is the code
[cpp]
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>
#include <iomanip>

using namespace std;

int main(){
string x;

double res;
int nums,r2,i,j,k;

while(cin>>nums){
res=log10(2);

res*=-1;
res*=nums;
r2=floor(res);
res=res-r2;
res=pow(10,res);
while(res<1){
res*=10;
r2--;
}

cout<<setiosflags(ios::fixed)<<setprecision(3)<<res<<"e"<<r2<<endl;

}

return 0;
}
[/cpp]

thanks
ram

obayashi
New poster
Posts: 33
Joined: Thu Jun 20, 2002 1:18 pm

### p474 keepin' WA

i don't think that my code is wrong, and i check the output with the calculator.
i am now confused...
any one help me pls![cpp]

#include <iostream>
#include <iomanip>
#include <math.h>
using namespace std;
double val;
void pre () {
double a;
long b;
for (int i=1;i<=1000;i++) {
a = pow(2,i);
b = long(log10(a)+0.005);
a = a/pow(10,b);
val = a;
val = b;
}
val = 1;
val = 0;
}
int main () {
long p,e;
double b;
pre();
while (cin>>p) {
if (p<=1000) {
b = 1/val[p];
e = val[p];
} else {
long sq,tail;
sq = long(sqrt(p)+0.005);
tail = p-sq*sq;
b = pow(val[sq],sq)*val[tail];
e = val[sq]*sq+val[tail];
b = 1/b;
}
while (b<1) {
b *= 10;
e++;
}
cout<<"2^-"<<p<<" = "<<setiosflags(ios::fixed)<<setprecision(3)<<b<<"e-"<<e<<endl;
}
return 0;
}
[/cpp]
Time makes a fool of memory
And yet my memories still shine

Ivan Golubev
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia

2^-10200 = Infinitye-3030
2^-10403 = Infinitye-3060
2^-10608 = Infinitye-3193

obayashi
New poster
Posts: 33
Joined: Thu Jun 20, 2002 1:18 pm
I've changed my algorithm and got AC.
Perhaps I've been thinkin' too much.
Any way, thank you all the same Time makes a fool of memory
And yet my memories still shine

yeung
New poster
Posts: 6
Joined: Sun Jul 21, 2002 10:45 am

### help:474 (WA)

I try n times,but...
[pascal]
const
fi='';
fo='';
var
f1,f2:text;
n,y:longint;
log2e,loge2,x:real;
function ppow(x,y:real):real;
begin
ppow:=exp(y*ln(x));
end;
function ceil(x:real):longint;
begin
if trunc(x)=x
then ceil:=trunc(x)
else ceil:=trunc(x)+1;
end;
begin
assign(f1,fi);
assign(f2,fo);
rewrite(f2);
reset(f1);
log2e:=ln(10)/ln(2);
loge2:=ln(2)/ln(10);
while not eof(f1) do
begin
y:=ceil(n*loge2);
x:=ppow(2, y*log2e - n);
writeln(f2,'2^-',n,' = ',x:0:3,'e-',y);
end;
close(f1);
close(f2);
end.
[/pascal]

yeung
New poster
Posts: 6
Joined: Sun Jul 21, 2002 10:45 am
I made a pascal program and try to pass 474, but failed all the time. And I found nearly no pascal programmers passed that. And some used C or C++ said they cannot pass with pascal! Why? Who can tell me? Thanks?
I have same question.

xenon
Learning poster
Posts: 100
Joined: Fri May 24, 2002 10:35 am
Location: Scheveningen, Holland
There is a lot of discussion on the regular board for this problem, and I remember I solved it (in Pascal) after carefull study of what was said there. As always with computations using real variables, the crux lies in avoiding rounding errors. The case n=6 in particular can be used to augment your code until you get the right answer. See the forementioned board(s).
My program also has special code to handle empty lines in the input, but I can't remember if that was necessary for this problem, or that I put it in as a precaution.

-xenon

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
Hello,
i have tried with many types adviced by u,but i got wa for abot 10 times.
will those person look about the matter why it is getting wa. Code: Select all

``````[b]
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int main()
{
long N, expo,n,k;
double l;
int m;
int start = 0;
while(1)
{
if (fscanf (stdin,"%ld",&N) == EOF)
break;
expo = (long)ceil(log10(2)*N);
l=exp(expo*log(10)-N*log(2));
m=floor(l*1000);
n=m;
m=floor(l*10000)-(m*10);
if(m>5) n++;
else if(m<5);
else
{
k=floor(l*10000);
k=floor(l*100000)-(k*10);
if(k) n++;
else
{
k=floor(l*100);
k=floor(l*1000)-(k*10);
if(k%2)n++;
}
}
l=(double)(n)/1000.00;
if(m>=5 && l>=9)
l=l/10,expo--;
if(start) printf("\n");
printf ("2^-%ld = %.3lfe-%ld",N,l,expo);
/*printf("\n");*/
start++;
}
return 0;
}

another coding

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int main()
{
long N, expo,n;
double l;
int m;
int start = 0;
while(1)
{
if (fscanf (stdin,"%ld",&N) == EOF)
break;
expo = (long)ceil(log10(2)*N);
l=exp(expo*log(10)-N*log(2));
m=floor(l*1000);
n=m;
m=floor(l*10000)-(m*10);
if(m>((10.0-1.00)/2.00)) n++;
l=(double)(n)/1000.00;
if(m>=5 && l>=9)
l=l/10,expo--;
if(start) printf("\n");
printf ("2^-%ld = %.3lfe-%ld",N,l,expo);
/*printf("\n");*/
start++;
}
return 0;
}

here again getting wa
:oops:  :oops:
[/b]``````
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int main()
{
long N, expo;
char start = 1;
while(1) {
if (fscanf (stdin,"%ld",&N) == EOF)
break;
expo = (long)ceil(log10(2)*N);
printf ("2^-%ld = %.3fe-%ld\n",N,exp(expo*log(10)-N*log(2)),expo);
}
return 1;
}

again wa  Code: Select all

``````#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int main()
{
long long int N, expo;
char start = 1;

fscanf (stdin,"%lld",&N);
while(1) {
if (fscanf (stdin,"%lld",&N) == EOF)
break;

if (start) start = 0;
else printf ("\n");

expo = (long long int)ceil(log10(2)*N);
printf ("2^-%lld = %.3fE-%lld\n",N,exp(expo*log(10)-N*log(2)),expo);
}
return 1;
}

wa.
:oops:  :evil:  :evil:  :evil:
but i got ac on 545 the same problem.
thanks``````
"Everything should be made simple, but not always simpler"

hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

### 474 - Heads / Tails Probability

Hello !!
I don't know why I always got WA. I have try all the possibilities for many cases.And it works.  Here is my output

Code: Select all

``````2^-1 = 5.000e-1
2^-2 = 2.500e-1
2^-3 = 1.250e-1
2^-4 = 6.250e-2
2^-5 = 3.125e-2
2^-6 = 1.563e-2
2^-7 = 7.813e-3
2^-8 = 3.906e-3
2^-16 = 1.526e-5
2^-17 = 7.629e-6
2^-18 = 3.815e-6
2^-19 = 1.907e-6
2^-20 = 9.537e-7``````
and here is my code:
[cpp]
#include "stdio.h"
#include "math.h"
void main()
{
double n,x;
while( scanf("%lf",&n)==1 ){
x=-n*log10(2);
printf("2^-%.0f = %.3fe%.0f\n",n,pow(10,x-floor(x)),floor(x));
}
}[/cpp]

and my method is:

Code: Select all

`````` for example, to calculate "2^-100"
(1)  2^-100=a
(2) log(2^-100)=log(a)
(3) -100*log(2)=log(a)
(4) 10^(-100*log(2))=a

... so we can get the answer .``````
I cannot find any bug!~~~~I hope you can HELP me!! ^_^||(thanks!)

tep
New poster
Posts: 23
Joined: Fri Jun 13, 2003 6:08 am
Contact:
Hi there...
before I'm also frustated why i get WA..
the only one reason is precision error..
try changing the logarithm base... here's my method

digit = floor(log10(2)*n + 1);

// find the x.xxx
a = 10^digit / 2^n
log2(a) = log2(10^digit) - n*log2(2);
log2(a) = digit*log2(10) - n;
log2(a) = digit / log10(2) - n;

then
x.xxx = 2^(digit / log10(2) - n);
y = -digit;

hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.
I have fixed it...Thanks a lot!! Sanny
Learning poster
Posts: 78
Joined: Sat Feb 14, 2004 3:59 pm
Location: BUET
Contact:

### 474 Heads/ Tails Probability - Run Time Error

Can anyone please figure out what's going wrong with my code. I used DP to store all the results. My previous non - DP solution resulted in TLE. And this one is facing RTE.

//solved

Thanks in advance for any help.
Last edited by Sanny on Wed Nov 10, 2004 11:51 pm, edited 1 time in total.

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

### aaha

Sanny:

You can not declare array of huge size inside the main function().

Either make the array global or make it static.

IE :

use
[c]
double first[size];
long second[size];
main()
{
}
[/c]

and not

[c]
main()
{
double first[size];
double second[size];
}
[/c]

Hope it helps. Sanny
Learning poster
Posts: 78
Joined: Sat Feb 14, 2004 3:59 pm
Location: BUET
Contact:

The problem is solved .

Heartattack!
New poster
Posts: 45
Joined: Fri Jan 16, 2004 7:02 pm
Location: CSE::BUET
Contact:
I think I'm using the same algo. I'm getting WA. Here's my code. Could someone give me sample input/output? Thanks in advance.
[cpp]

// p474.Heads.cpp : Defines the entry point for the console application.
//

@begin_of_source_code
/* @JUDGE_ID: ******* 474 C++ */
#include "stdio.h"

struct res
{
long double x;
long y;
};
struct res a;
void genans()
{
long double x=1;
long n,y=0;

for(n=1;n<=1000000;++n)
{
x/=2.0;
if(x<1.0)
{
x*=10;
y++;
}
a[n].x=x;
a[n].y=y;
}

}

void main()
{
long n;
genans();
while(scanf("%ld",&n)!=EOF)
{
printf("2^-%ld = %1.3fe-%d\n",n,a[n].x,a[n].y);
}

}

@end_of_source_code

[/cpp]
We will, We will BREAK LOOP!!!!