Question 1
Colour the objects
You are given N objects, an integer K, and two types of
colors (color 0 , color 1). The objects are labelled from 1 to N.
Task
Determine the number of ways to color all the objects such
that the distance between any two objects of the same colour is at most k.
Note: the distance between two objects is defined as the
absolute difference between the labels of the two objects.
You have to print the number of ways modulo 109 +
7.
Example
Assumptions
·
N = 1
·
K = 1
Approach
You must determine the number of ways to color all the
objects such that the distance between any two objects of the same colour is at
most K:
·
You have only 4 ways that satisfy the given
condition:
o
010
o
101
o
001
o
110
Function description
Complete the solution function in the editor. This function
takes the following 2 parameters and the returns the number of ways to the
first line contains T denoting the number of test cases. colour all the objects such that the distance
between any two objects of the same colour is at most K:
o
N: represent the number of objects
o
K: represents an integer as given in the problem
Input format
Note: this is the input format that you must use to
provide custom input (available above the Compile and Test button).
·
The first line contains T denoting the number of
test cases. T also specifies the number of times you have to run the solution
function on a different setoff inputs.
·
For the first case:
o
The first line contains two space – separated
integers N and K.
Output format
For each test case in a new line, print the answer. If there
is no way to colour the objects, print 0.
Constraints
1 ≤T≤10
1≤N≤1012
0≤K≤1012
Code snippets (also called starter code/boilerplate code)
This question has code for C, CPP, Java, and Python
Explanation
The number of ways in which the given 5 objects can be
coloured that the distance between any two objects of the same colour is at
most 2 is :
00011
00111
11000
11100
No comments:
Post a Comment