Soluție HackerRank pentru Hackonacci Matrix Rotations, subdomeniul Algebra, în Python 3. Include cerința formatată, exemple, explicația pașilor și cod…
- Problemă: Hackonacci Matrix Rotations
- Domeniu: Algebra
- Limbaj: Python 3
Challenge: Hackonacci Matrix Rotations
Subdomeniu: Algebra (algebra)
Scor cont: 35.0 / 35
Submission status: Accepted
Submission score: 1.0
Submission ID: 464740734
Limbaj: python3
Link challenge: https://www.hackerrank.com/challenges/hackonacci-matrix-rotations/problem
Cerință
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 × 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 perform q queries where each query i consists 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:
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:
- (1, 1): hackonacci((1 · 1)^2) = hackonacci(1) = 1
Because this is an odd number, we mark this cell with a `Y`.
- (1, 2): hackonacci((1 · 2)^2) = hackonacci(4) Rightarrow 1 · hackonacci(3) + 2 · hackonacci(2) + 3 · hackonacci(1) Rightarrow 1 · 3 + 2 · 2 + 3 · 1 = 3 + 4 + 3 = 10
Because this is an even number, we mark this cell with an `X`.
- (2, 1): hackonacci((2 · 1)^2) = hackonacci(4) Rightarrow 10
Because this is an even number, we mark this cell with an `X`.
- (2, 2): hackonacci((2 · 2)^2) = hackonacci(16) Rightarrow 296578
Because this is an even number, we mark this cell with an `X`.
Given the value of n and q queries, construct a Hackonacci Matrix and answer the queries. For each query i, 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 angle_i degrees in the clockwise direction.
Input Format
The first line contains two space-separated integers describing the respective values of n and q.
Each line i of the q subsequent lines contains an integer denoting angle_i.
Output Format
For each angle_i, 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 angle_i degrees.
Constraints
+ 1 ≤ n ≤ 2000
+ 1 ≤ q ≤ 10^4
+ 0 ≤ angle_i ≤ 10^5
+ It is guaranteed that each angle_i is multiple of 90 degrees.
Cod sursă
import sys
# hackonacci(n) parity is periodic with period 7 and odd for n % 7 in {0,1,3,6}.
ODD_MOD = {0, 1, 3, 6}
SQ_MOD = [(i * i) % 7 for i in range(7)]
def build_matrix(n):
mat = [bytearray(n) for _ in range(n)]
jmods = [j % 7 for j in range(1, n + 1)]
for i in range(1, n + 1):
im = i % 7
row = mat[i - 1]
for j in range(n):
m = (im * jmods[j]) % 7
k = SQ_MOD[m]
# 1 for X (even), 0 for Y (odd)
row[j] = 0 if k in ODD_MOD else 1
return mat
def diffs(mat):
n = len(mat)
d90 = d180 = d270 = 0
for i in range(n):
row_i = mat[i]
ni = n - 1 - i
row_ni = mat[ni]
for j in range(n):
v = row_i[j]
nj = n - 1 - j
if v != mat[nj][i]:
d90 += 1
if v != row_ni[nj]:
d180 += 1
if v != mat[j][ni]:
d270 += 1
return d90, d180, d270
def main():
data = sys.stdin.buffer.read().split()
if not data:
return
n = int(data[0])
q = int(data[1])
mat = build_matrix(n)
d90, d180, d270 = diffs(mat)
out = []
idx = 2
for _ in range(q):
a = int(data[idx]) % 360
idx += 1
if a == 0:
out.append('0')
elif a == 90:
out.append(str(d90))
elif a == 180:
out.append(str(d180))
else: # 270
out.append(str(d270))
sys.stdout.write('\n'.join(out))
if __name__ == '__main__':
main()