Hackonacci Matrix Rotations

By | December 21, 2016

Hackonacci Matrix Rotations

We define a Hackonacci  series as follows:

hackonacci (n) = 1. hackonacci (n-1) + 2. hackonacci (n-2) + 3. hackonacci(n-3)

hackonacci(1)= 1

hackonacci(2)=2

hackonacci(3)=3

We define a Hackonacci Matrix to be an n X n matrix where the rows and columns are indexed from 1 to n , and the top-left cell is (1,1) . Each cell (i,j) must contains either the character X or the character Y. If hackonacci ((i.j)^2)  is even, it’s X; otherwise, it’s Y.

Next, we want to performqueries where each queryconsists of an integer, angle-i. Each angle-i is a multiple of 90 degrees and describes the angle by which you must rotate the matrix in the clockwise direction. For each angle-i , we want to count the number of cells that are different after the rotation. For example, the diagram below depicts the 270  rotation of a Hackonacci Matrix when n=2:

image

As you can see, there are two cells whose values change after the rotation. Note that we filled each initial cell using the Hackonacci formula given above:

 

Given the value of and queries, construct a Hackonacci Matrix and answer the queries. For each query , print an integer on a new line denoting the number of cells whose values differ from the initial Hackonacci Matrix when it’s rotated by degrees in the clockwise direction.

Input Format

The first line contains two space-separated integers describing the respective values of and .
Each line of the subsequent lines contains an integer denoting .

Constraints

  • It is guaranteed that each is multiple of degrees.

Output Format

For each , print a single integer on a new line denoting the number of different cells that differ between the initial matrix and the matrix rotated by degrees.

Sample Input 0

4 3
90
180
270

Sample Output 0

10
6
10

Explanation 0

Because , we must build a Hackonacci matrix and then perform queries, shown below. The following diagrams depict each query rotation, and cells whose values changed after performing a rotation are highlighted in orange:

  1. When we perform a rotation on the matrix, there are cells whose values change:
    imageThus, we print on a new line.
  2. When we perform a rotation on the matrix, there are cells whose values change:image
    Thus, we print on a new line.
  3. When we perform a rotation on the matrix, there are cells whose values change:image
    Thus, we print on a new line.

Source :  Hackerrank

Solution

Working on the solution