1. Implementing nCk
Implement the Combinations by the formula of
nCkn1Ck1n1Ck
where
nC0nCn1
using recursive function calls. Assume that user input n and k in the first 2 lines, report all combinations calculated in the process. For example, if user input n3 and k1, output:
3C12C02C12C012C11C01C11C011C112C123C13
Test cases.
Input:
42
Output:
4C23C13C23C12C02C1 2C012C11C01C11C011C112C123C133C22C12C22C11C01C11C011C112C122C213C234C26
Input:
55
Output:
5C51
2. Queens cant attack me!
Consider a square chessboard with NN cells and M queens on the chessboard Note: there are no other chesses besides the queens.A queen can move vertically, horizontally or diagonally. As an example, consider the square chessboard with 66 cells with one queen denoted by thenotation in Figure 1 below. The cellsthat can be reached by the queen are marked with the O notation. There are 16 cells cannot be reached by the queen.
Your task is to calculate the number of cells that are NOT reachable by any queens.
Input specification:
The first line contains two integers, N and M. 1N100, 1M10.
Following are M lines. Each line contains two integers x and y, representing the location of a queen, i.e., the queen is at xth row and yth column 1x, yN.
Output specification:
The number of cells that are not reachable by any queens.
Testcase 1 Including user input bolded
6 14 316
Testcase 2 Including user input bolded
6 24 36 49
3. Where is my treasure?
In a game there is a map showing the location of various treasures featured in the gameplay.
Each treasure is depicted by a square blackandwhite pictogram represented as a grid of pixel values.
Each pixel value is either 0 representing a black pixel, or 1 representing a white pixel.
The treasures are of various dimensions. For example, the following 16×16 pixel grid represents a sword in the game:
The map is also represented as a square grid of blackandwhite pixels. As above, the cell in the top left corner of the grid has x,y coordinates 0,0.
A treasure may appear in one of four possible orientations in the map: rotated clockwise through 0, 90, 180 or 270 degrees from the orientation of its stored representation.
It is guaranteed that the given treasure appears exactly once in the map, however it may be in any one of the four orientations described above.
Write a program to find the map coordinates of the treasures location. Report the map coordinates of the top left corner cell of the treasure as it appears on the map. Note that the coordinates of the location are not affected by the orientation of the treasure. Assumptions:
Treasures do not overlap with other treasures or with other features in the map.
No treasure appears as part of the representation of any other treasure.
Example:
You are searching for the sword in a 100×100 pixel map. If you find its pictogram
Rotated through 90 degrees, in the top left corner of the map, output 0 0
Not rotated, in the top left corner of the map, output 0 0
Rotated through 180 degrees, in the bottom left corner of the map, output 0 84
Input specification:
The first M lines contain the representation of the treasure.
Each line contains M digits 0 or 1 only representing pixel values. The ith digit of the jth line gives the value of the pixel at x,y coordinate i,j in the representation.
The remaining N lines contain the representation of the map in the same form as described above for the treasure.
In all test cases, 1MN100.
Output specification:
The x, y coordinates of the top left corner cell of the treasures location in the map. The coordinates should be separated by a single space.
Sample input:
0001011011111111111110111101110001
Sample output:
1 2
Explanation:
The input represents the following treasure and map:
The treasure, rotated through 180 degrees, appears in the bottom centre of the map.
The topleft pixel of the treasure, as it appears in the map, is at map location 1,2.
Reviews
There are no reviews yet.