N Queens Puzzle Solved ! Solution Codechef

N Queens Puzzle Solved ! Solution Codechef

Chef, 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 NN, there are approximately (0.143⋅N)N(0.143⋅N)N configurations in which NN queens can be placed on a N×NN×N chessboard so that none attack each other.

Although the formula is valid for large NN, Chef is interested in finding the value of function f(N)f(N) = (0.143⋅N)N(0.143⋅N)N for a given small value of NN. 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)f(N) is xx,

  • Print ⌊x⌋⌊x⌋ if x−⌊x⌋<0.5x−⌊x⌋<0.5
  • Otherwise, print ⌊x⌋+1⌊x⌋+1

where ⌊x⌋⌊x⌋ denotes the floor of xx.

Input Format

  • The first line of input contains a single integer TT, denoting the number of test cases. The description of TT test cases follows.
  • Each test case consists of a single line of input containing one integer NN.

Output Format

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

Constraints

  • 1≤T≤121≤T≤12
  • 4≤N≤154≤N≤15

Subtasks

Subtask #1 (100 points): Original constraints

Sample Input 1 

2
4
10

Sample Output 1 

0
36

Explanation

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

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

N Queens Puzzle Solved Solution Codechef
N Queens Puzzle Solved Solution Codechef

SOLUTION

Program: N Queens Puzzle Solved ! Solution Codechef in Python

for _ in range(int(input())):
    a=int(input())
    a=pow((0.143*a),a)
    print(round(a))

Program: N Queens Puzzle Solved ! Solution in C++

#include <iostream>
using namespace std;
#include<math.h>
int main() {
	int t;
	cin>>t;
	while(t--)
	{
	    int n;
	    cin>>n;
	    float m;
	    m=pow(0.143*n,n);
	    long int v=m;
	    if((m-v)<0.5)
	    cout<<v<<"\n";
	    else
	    cout<<v+1<<"\n";
	}
	return 0;
}

Program: N Queens Puzzle Solved ! 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 test = sc.nextInt();
		 while(test-- > 0){
		     int n =sc.nextInt();
		     double result = Math.pow((0.143*n),n);
		     System.out.println(Math.round(result));
		 }
	}
}

February Long Challenge 2022 Solution

January Long Challenge 2022 Solution

Leave a Comment

7 − two =