| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 12935 | Greatest Common Divisor |
|
| 13291 | KONODIODA |
|
| 13297 | Learning Matrix |
|
Description
Dio, an evil vampire, does all kinds of evil and nobody can fight against him.
However, there's a brave man, JoJo, standing out and using all his ability to defeat him.
Everyone appreciate JoJo's great achievement and the world becomes safe and peace again.
Unfortunately, since Dio is a vampire, he revives himself again and tries to make more chaos......
We have known that there is a star-shaped birthmark on Dio's neck. To make sure that Dio is not able to enter our country, in the airport, we will use a special technique to scan a part of the visitors' skin and transfer the raw image to gray scale (0-255, 0 means black and 255 means white).
Given an image (square matrix) A[N,N], if point P(X,Y) is the center of a star, the following condition will be satisfied:
(1) A[X][j]=255, for all 0<=j<N (The values in the Xth row are all 255)
(2) A[i][Y]=255, for all 0<=i<N (The values in the Yth column are all 255)
(3)
A[X+i][Y+i]=255, for all -N<=i<N if 0<=(X+i)<N and 0<=(Y+i)<N
A[X+i][Y-i]=255, for all -N<=i<N if 0<=(X+i)<N and 0<=(Y-i)<N
(The values of two diagonals from the centers are all 255)
For example, a star looks like:
In this problem, given T square matrices wth size N, you are asked to find out how many stars in each matrix respectively.
Hint.
If you cannot pass all the testcases, you can try to use extra arrays to record some infomation when you read the input data.
By doing so, you can immediately determine whether a point is a star.
Input
There are three parts of the input:
(1) The number of testcases, T. 1<=T<=1000
(2) The size of the square matrices, N. 1<=N<=2048
(3) T N*N matrices separated by a newline character. 0<=The values in the matrices<=255.
Output
The number of stars in each matrix.
Note that you need to print "\n" in the end of each answer.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
"We're no strangers to love
You know the rules and so do I
A full commitment's what I'm thinking of
You wouldn't get this from any other guy
~ 《Never Gonna Give You Up》
In this problem, given 2 matrix, A[N, M] and B[M, N]. You are asked to calculate C = (A x B)T (the transpoed matrix of A multiplies B).
How to calculate A x B:
How to transpose a matrix:
Note that every elements in A, B, and C can be represented by datatype int.
Input
There are three parts of the input:
(1)1<=N<=2100
(2)1<=M<=2100
(3)A[N,M] and B[M,N] separated by a newline charcter. -100<=The values in the matrix<=100.
Output
C = (A x B)T (the transpoed matrix of A multiplies B).
Note that you have to print whitespaces between each elements and a newline character in the end of each rows.