474 - Heads / Tails Probability

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

Moderator: Board moderators

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

474 problem

Post by ram » Thu May 23, 2002 10:52 pm

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

Post by obayashi » Sat Aug 03, 2002 5:48 pm

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]
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

Post by Ivan Golubev » Sat Aug 03, 2002 6:34 pm

How about this output produced by your program?

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

Post by obayashi » Sun Aug 04, 2002 4:04 am

I've changed my algorithm and got AC.
Perhaps I've been thinkin' too much.
Any way, thank you all the same :lol:
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)

Post by yeung » Mon Aug 19, 2002 4:43 pm

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
New poster
Posts: 6
Joined: Sun Jul 21, 2002 10:45 am

Post by yeung » Thu Aug 22, 2002 3:52 am

EggHead wrote: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
Learning poster
Posts: 100
Joined: Fri May 24, 2002 10:35 am
Location: Scheveningen, Holland

Post by xenon » Thu Aug 29, 2002 8:37 pm

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:

Post by anupam » Tue Oct 29, 2002 1:21 pm

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.
:oops:

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

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
"Everything should be made simple, but not always simpler"

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

474 - Heads / Tails Probability

Post by hank » Mon Jun 30, 2003 10:27 am

Hello !!
I don't know why I always got WA. I have try all the possibilities for many cases.And it works. :oops: :oops:
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:

Post by tep » Sat Jul 05, 2003 10:49 am

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;

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

Post by hank » Sat Jul 05, 2003 4:45 pm

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

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

474 Heads/ Tails Probability - Run Time Error

Post by Sanny » Sat Apr 24, 2004 11:06 am

Can anyone please figure out what's going wrong with my code. :cry:
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.

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

aaha

Post by sohel » Sat Apr 24, 2004 11:24 am

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.
:wink:

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

Thanks for the advice

Post by Sanny » Mon Apr 26, 2004 12:37 pm

Thanks for the advice.
The problem is solved :D .

Heartattack!
New poster
Posts: 45
Joined: Fri Jan 16, 2004 7:02 pm
Location: CSE::BUET
Contact:

Post by Heartattack! » Wed Nov 10, 2004 10:02 am

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]
We will, We will BREAK LOOP!!!!

Post Reply

Return to “Volume 4 (400-499)”