Random OR Solution|Codesheff February long 2022- Division 3(Rated)

 Chef is playing a game, which he starts with a score of S=0. He also has an integer N.

In one move, Chef does the following:

• Uniformly randomly pick an integer X between 0 and 2N−1 (inclusive of both ends)
• Update his score as S→S∣X, where ∣ denotes the bitwise OR operation

For example, if Chef's current score is S=6 and he picks X=10, his new score is 6∣10=14.

Chef stops when his score S becomes equal to 2N−1. What is the expected number of moves Chef performs?

Output the answer modulo 109+7. That is, the answer can be expressed as a fraction P/Q, where gcd(Q,109+7)=1. Print P\cdot Q^{-1} \pmod{\ 10^9 + 7}, where Q^{-1} denotes the modular multiplicative inverse of Q with respect to 10^9 + 7.

Input Format

• The first line of input contains an integer T, denoting the number of test cases. The description of T test cases follows.
• Each test case contains a single integer N.

Output Format

For each test case, output on a new line the expected number of moves Chef performs, modulo 10^9 + 7.

Constraints

• 1 \leq T \leq 100
• 1 \leq N \leq 3 \cdot 10^5
• Sum of N over all test cases do not exceed 3 \cdot 10^5

Subtasks

Subtask 1 (30 points):

• 1 \leq N \leq 10^3
• Sum of N over all test cases doesn't exceed 10^3

Subtask 2 (70 points):

• Original constraints

Sample Input 1 

3
1
2
100

Sample Output 1 

2
666666674
328238032

Explanation

Test case 1: In each move, Chef chooses either 0 or 1, each with a probability of 1/2. The game ends as soon as Chef chooses 1. Thus, the probability that the game takes exactly k moves is 2^{-k}.

The required expected value is then \displaystyle\sum_{k=1}^\infty k\cdot 2^{-k}, which equals 2.

Test case 2: In each move, Chef chooses an integer in [0, 3]. The answer is 8/3.

Solution:

N queen puzzle solved solution|

 , being a Chess fan, was thrilled after he read the following news:

Michael Simkin, a postdoctoral fellow at Harvard University’s Center of Mathematical Sciences and Applications proved that for a large value of N, there are approximately (0.143⋅N)N configurations in which N queens can be placed on a N×N chessboard so that none attack each other.

Although the formula is valid for large N, Chef is interested in finding the value of function f(N) = (0.143⋅N)N for a given small value of N. Since Chef is busy understanding the proof of the formula, please help him calculate this value.

Print the answer rounded to the nearest integer. That is, if the actual value of f(N) is x,

Print ⌊x⌋ if x−⌊x⌋<0.5

Otherwise, print ⌊x⌋+1

where ⌊x⌋ denotes the floor of x.

Input Format

The first line of input contains a single integer T, denoting the number of test cases. The description of T test cases follows.

Each test case consists of a single line of input containing one integer N.

Output Format

For each test case, output in a single line the value of f(N) rounded to the nearest integer.

Constraints

1≤T≤12

4≤N≤15

Subtasks

Subtask #1 (100 points): Original constraints

Sample Input 1 

2

4

10

Sample Output 1 

0

36

Explanation

Test case 1: f(N)=(0.143⋅4)4=0.107, which when rounded to nearest integer gives 0.

Test case 2: f(N)=(0.143⋅10)10=35.7569, which when rounded to nearest integer gives 36 

Solution:

#include <bits/stdc++.h>

using namespace std;

int main()

{

    int t;

    cin>>t;

    while(t--){

        int n;cin>>n;

     float x=pow(0.143*n,n);

     if(x-floor(x)<0.5){

         cout<<floor(x)<<endl;

     }else{

         cout<<floor(x)+1<<endl;

     }

    }

}

    

Chef and the Hair Salon solution|February long 2022 (div 3)(rated)

Chef recently realized that he needs a haircut, and went to his favorite hair salon. At the salon, he found $N$ customers waiting for their haircuts. From his past experience, Chef knows that the salon takes $M$ minutes per customer. Only one person can get their haircut at a time.

For how many minutes will Chef have to wait before he can get his haircut?

Input Format

• The first line of input contains a single integer $T$, denoting the number of test cases. The description of $T$ test cases follows.
• The first and only line of each test case contains two space-separated integers $N$ and $M$, as described in the problem.

Output Format

For each test case, print a single line containing one integer — the number of minutes that Chef will have to wait before he can get his haircut.

Constraints

• $1 \leq T \leq 1000$
• $0 \leq N \leq 1000$
• $1 \leq M \leq 1000$

Subtasks

Subtask #1 (100 points): Original constraints

Sample Input 1 

2
2 15
0 15

Sample Output 1 

30
0

Explanation

Test case $1$: There are $2$ customers waiting for the haircut and the salon will take $15$ minutes for each customer, hence Chef will have to wait for $30$ minutes before he can get his haircut.

Test case $2$: There are $0$ customers waiting for the haircut, therefore the Chef will not have wait to get the haircut.

Solution: