10056 - What is the Probability ?

[StatujaLeha]

It is my program. I use the same algorithm, but i get WA. ReiVaX18, do you use any tricks for printing the result?

Code: Select all

       if((p != 0)&&(p != 1))
      {
         q = 1.0 - p;
         printf("%.4lf\n",(pow(q,I - 1)*p)/(1.0 - pow(q,N)));
      }
      else
      {
         if(p == 0)
            printf("%.4lf\n",0.0000);
         else//p == 1
         {
            if(N == 1)
               printf("%.4lf\n",1.0000);
            else
               printf("%.4lf\n",0.0000);
         }
      }

[ReiVaX18]

I can't see any error, the only difference is that I use long double, but I think this should not be a problem

Code: Select all

#include <iostream>
#include <iomanip>
using namespace std;

long double pawah( long double b, int e ) {
	long double r = 1.0;
	for( int i = 0; i < e; i++ ) r *= b;
	return r;
}

int main() {
	cout.setf( ios::fixed );
	cout.precision( 4 );
	int s, n, k;
	long double p;
	cin >> s;
	while( s-- ) {
		cin >> n >> p >> k;
		if( p > 0.0 ) cout << p*pawah(1-p,k-1)/(1-pawah(1-p,n)) << endl;
		else cout << 0.0 << endl;
	}
}

[StatujaLeha]

I find the mistake

Code: Select all

       if((p != 0)&&(p != 1))
      {
         q = 1.0 - p;
         printf("%.4lf\n",(pow(q,I - 1)*p)/(1.0 - pow(q,N)));
      }
      else
      {
         if(p == 0)
            printf("%.4lf\n",0.0000);
         else//p == 1
         {
            if([b]I[/b] == 1)
               printf("%.4lf\n",1.0000);
            else
               printf("%.4lf\n",0.0000);
         }
      }

[mido]

I think you meant I==1 instead of N==1....

[StatujaLeha]

I think you meant I==1 instead of N==1....

yes There I have fixed it. http://online-judge.uva.es/board/viewtopic.php?t=5530

[Darko]

Ok, I have no idea what I'm doing wrong, except using Java

Can someone please check these and/or post some input data?

Input:

19
2 0.166666 1
2 0.166666 2
100 0.000001 1
100 0.000001 99
999 0.00023 591
100 0.0 4
915 0.166666 1
23 0.1111 13
1 1.0 2
1 1.0 1
2 1.0 1
1000 0.0001 500
7 0.33333333 4
13 0.11111111 5
123 0.27362732 29
12 0.123456789 10
12 0.00000001 10
12 0.123456789 2
12 0.00000001 2

Output:

0.5455
0.4545
0.0100
0.0100
0.0010
0.0000
0.1667
0.0290
0.0000
1.0000
1.0000
0.0010
0.1049
0.0885
0.0000
0.0475
0.0833
0.1362
0.0833

Thanks,

Darko

[Darko]

I/O above is correct - I think adding EPS to the output did it for me, but I am not sure.

[greynolds]

I am getting Wrong Answer with my java code, and I seem to get the same output as the other forum posters. I am not sure what "adding EPS" means above...

Code: Select all

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.text.DecimalFormat;
import java.text.NumberFormat;


public class Main {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		BufferedReader stdin = 
			new BufferedReader(new InputStreamReader(System.in));
		
		try {
			while (stdin.ready())
			{
				String sLine = stdin.readLine();
				String outValue = winProbability(sLine);
				if (outValue != null)
				{
					System.out.println(outValue);
				}
				
			}
		} catch (IOException e) {
			e.printStackTrace();
		}

	}
	
	static String winProbability(String input)
	{
		String [] fields = input.split(" +");
		if (fields.length != 3)
		{
			return null;
		}
		long N = Long.parseLong(fields[0]);
		double p = Double.parseDouble(fields[1]);
		long i = Long.parseLong(fields[2]);
		
		NumberFormat form = new DecimalFormat("0.0000");
		double prob = winProbability(N,p,i);
		return form.format(prob);
	}

	private static double winProbability(long n, double p, long i) {
		if (p == 0)
		{
			return 0;
		}

		return Math.pow(1.0-p,i-1.0)
		/((1/p)*(1.0-Math.pow(1.0-p,n)));
	}
}

Using the input

Code: Select all

19
2 0.166666 1
2 0.166666 2
100 0.000001 1
100 0.000001 99
999 0.00023 591
100 0.0 4
915 0.166666 1
23 0.1111 13
1 1.0 2
1 1.0 1
2 1.0 1
1000 0.0001 500
7 0.33333333 4
13 0.11111111 5
123 0.27362732 29
12 0.123456789 10
12 0.00000001 10
12 0.123456789 2
12 0.00000001 2

Gives

Code: Select all

0.5455
0.4545
0.0100
0.0100
0.0010
0.0000
0.1667
0.0290
0.0000
1.0000
1.0000
0.0010
0.1049
0.0885
0.0000
0.0475
0.0833
0.1362
0.0833

[Darko]

Means add small value to the result before formatting (usually referred to as epsilon or EPS in code).

In your case, you can try adding 1e-10 (or some suitable value) to prob before printing it.

[mf]

Adding an epsilon is needed because if your answer is very close to zero, small rounding errors could make it negative and make it print as -0.0000. Alternatively, you can print Math.max(0, your answer).

Also, Math.pow(1.0-p,i-1.0) will be NaN for p=1, i=1, and NaN's are never a good thing.

And here:

Code: Select all

      try {
         while (stdin.ready())
         {
            String sLine = stdin.readLine();
            ...
         }
      } catch (IOException e) {
         e.printStackTrace();
      }

you shouldn't be catching exceptions or printing any stack traces. Let it be thrown out of main() - then the judge has a chance to say you got "runtime error" instead of potentially confusing "wrong answer".

I'd use this to read the input:

Code: Select all

int T = Integer.parseInt(stdin.readLine().trim());   // <- don't just ignore it!
for (int cs = 1; cs <= T; cs++) {
    String sLine = stdin.readLine();
     ...
}

And here:

Code: Select all

      String [] fields = input.split(" +");
      if (fields.length != 3) {

I think it's not going to work for leading or trailing whitespace on lines.

[greynolds]

Thanks for the replies. It's still not working though...

The code now is

Code: Select all

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.text.DecimalFormat;
import java.text.NumberFormat;


public class Main {

  /**
   * @param args
   * @throws IOException 
   * @throws NumberFormatException 
   */
  public static void main(String[] args) throws NumberFormatException, IOException {
    BufferedReader stdin = 
      new BufferedReader(new InputStreamReader(System.in));
    int T = Integer.parseInt(stdin.readLine().trim());
    for (int cs = 1; cs <= T; cs++) {      
      String sLine = stdin.readLine();
      String outValue = winProbability(sLine);
      if (outValue != null)
      {
        System.out.println(outValue);
      }            
    }
  }

  static String winProbability(String input)
  {
    String [] fields = input.trim().split(" +");

    long N = Long.parseLong(fields[0]);
    double p = Double.parseDouble(fields[1]);
    long i = Long.parseLong(fields[2]);

    NumberFormat form = new DecimalFormat("0.0000");
    double prob = winProbability(N,p,i);
    return form.format(prob);
  }

  private static double winProbability(long n, double p, long i) {
    if (p == 0)
    {
      return 0;
    }
    if (p >= 1)
    {
      return 1;
    }

    double q = 1 - p;

    double a = Math.pow(q,i-1) * p;
    double b = Math.pow(q, n);

    return Math.max(a / (1 - b) + 1e-10,0);
  }
}

[Shafaet_du]

Spoiler

Ans=(P(i-P)^i-1)/(1-(1-P)^n);

i've used 1e-8 as eps. Special case: if P==0 then ans=0;

Spoiler