Baekjun no. 14298, Vote (with. Java)

This is an article about Baekjun No. 14298, Vote (with.Java).

I want to solve the coding test problem, find out how to solve it differently from the retrospective of the problem I solved, and get to know.

Let’s get to the problem first.

Problem

A and B are the only two candidates competing in a particular election.

We know from the polls that exactly N voters support A and exactly M voters support B.

I also know that A will win because N is greater than M.

Voters appear at the polls one at a time, in the order of all possible (N + M)!, in a uniformly randomly selected order.

After each voter casts a ballot, the poll worker updates the results and records which candidate has won (if any) so far.

(If the vote is tied, neither candidate is considered to have won.)

What is the probability that A will always remain in the lead?

In other words, what is the probability that A always wins every vote?

Input

The input starts with a single line that contains the integer T, the number of test cases.

Each test case consists of a line containing two integers N and M, which are the numbers of voters who support A and B, respectively.

Restrictions

1 ≤ T ≤ 100.

0 ≤ M < N ≤ 10.

Output

For each test case, output one line containing.

Case #x: y. where x test case number (starting from 1) is the probability that A will always win in every vote.

If the y absolute or relative error of the correct answer is within 10-6, it is considered the correct answer.

problem solving

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();

        for(int i = 1; i <= T; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());

            double p = (double) (N - M) / (N + M);
            sb.append(String.format("Case #%d: %.8f\n", i, p));
        }
        System.out.print(sb);
    }
}

Solution Description

This code is a program that calculates the probability that candidate A will always remain in the lead in a particular election.

First, use the Buffered Reader to quickly read the input, read the first input, and store it in an integer T, indicating the number of test cases.

The for statement is then repeated from i = 1 to T to handle each test case.

Use StringTokenizer to divide a line by space and convert it into N (number of voters supporting A) and M (number of voters supporting B), respectively.

The probability p that A always maintains the lead is calculated by using the Ballot Theorem formula as (N - M) / (N + M).

Here, N - M represents the difference that A must precede B, and N + M represents the total number of voters, so this probability implies the probability that A will always remain in the lead.

이후 String.format(“Case #%d: %.8f\n”, i, p) is used to match the output format required by the problem.

“Case #%d” represents the test case number and “%8.8f” outputs probability values up to 8 decimal places \nmake a new line by adding.

And after accumulating the string using StringBuilder, you can use System.out.print(sb) to output it all at once, which improves performance over calling System.out.println() multiple times.

Example Input 2 Given 1 1 10, the probability of the first test case (2, 1) is (2-1) / (2+1) = 1/3 = 0.333333333 and the probability of the second test case (1, 0) is (1-0) / (1+0) = 1/1 = 1.000000.

Since each test case receives N and M and performs simple operations, it has the time complexity of O(1) and the overall time complexity of O(T).

Since T is up to 100 and N and M have a maximum of 10, it runs very quickly.