Expected move Solution Codechef

Expected move Solution Codechef

You are given a fair coin and two integers X and N.

You repeatedly flip the coin and perform the following operation based on the result:

• If it lands on heads, then X will increase by 1. However, if X = N then X will not change.
• If it lands on tails, X will decrease by 1.

You stop as soon as the value of X becomes 1. Find the expected number of coin flips.

Note that it is guaranteed that under the given constraints, the answer is an integer and does not exceed 2⋅10¹⁸

Input Format

• The first line contains a single integer T — the number of test cases. Then the test cases follow.
• The first and only line of each test case contains two space separated integers X and N.

Output Format

For each testcase, output the expected number of coin flips.

Constraints

• 1≤T≤10⁵
• 1≤X≤N≤10⁹

Sample 1:

Input

4
1 3
2 2
12 12
568 57800

Output

0
2
132
65223144

Explanation:

In the first test case, X is already 1. So, the expected number of coin flip in this case is 0.

In the second test case, if the coin lands on head, X will not change because X is equal to N here. Whenever the coin lands on tail, X will decrease by 1 and the game ends as X becomes 1. The expected number of coin flips to get the first tail is 2. So, the answer for the case is 2.

SOLUTION

Program: Expected move Solution in Python

for t in range(int(input())):
    x,n=map(int,input().split())   
    print((x-1)*(2*n-x))

Program: Expected move Solution in C++

#include<iostream>
#include<cmath>
#include<vector>
#include<set>
using namespace std;
#define ll long long int
void solve_case()
{
    ll x, n;
    cin>>x>>n;
    ll ans;
    ans=(2*n-x)*(x-1);
    cout<<ans<<endl;
    return;
}
int main()
{
    int t;
    cin>>t;
    while (t--)
    {
        solve_case();
    }
    return 0;
}

Program: Expected move Solution in Java

import java.util.*;
import java.lang.*;
import java.io.*;
class Codechef
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner sc = new Scanner(System.in);
		int t=sc.nextInt();
		while(t-->0){
		    long x=sc.nextInt(),n=sc.nextInt();
		    long ans =(x-1)*(2*n-x);
		    System.out.println(ans);
		}
	}
}

Related:

• Subscriptions Solution Codechef
• Alternate Additions Solution Codechef
• Equal Strings Solution Codechef
• Divisible by i Solution Codechef
• Possible GCD Solution Codechef
• Expected move Solution Codechef
• Reduce to zero Solution Codechef
• Full Path Eraser Solution Codechef