474 - Heads / Tails Probability

[ram]

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]

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[1001][2];
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[0] = a;
val[1] = b;
}
val[0][0] = 1;
val[0][1] = 0;
}
int main () {
long p,e;
double b;
pre();
while (cin>>p) {
if (p<=1000) {
b = 1/val[p][0];
e = val[p][1];
} else {
long sq,tail;
sq = long(sqrt(p)+0.005);
tail = p-sq*sq;
b = pow(val[sq][0],sq)*val[tail][0];
e = val[sq][1]*sq+val[tail][1];
b = 1/b;
}
while (b<1) {
b *= 10;
e++;
}
cout<<"2^-"<<p<<" = "<<setiosflags(ios::fixed)<<setprecision(3)<<b<<"e-"<<e<<endl;
}
return 0;
}
[/cpp]

[Ivan Golubev]

How about this output produced by your program?

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

[obayashi]

I've changed my algorithm and got AC.
Perhaps I've been thinkin' too much.
Any way, thank you all the same

[yeung]

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
readln(f1,n);
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]

Hello everyone!
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]

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]

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.
--please anybody help me.
thanks

[hank]

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]

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]

I have fixed it...Thanks a lot!!

[Sanny]

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.

[sohel]

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]

Thanks for the advice.
The problem is solved .

[Heartattack!]

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[1000002];
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]