grid-count-1

The fight between Batman and Superman just got dirty. Superman tried to trick Batman and locked him inside an N x N grid. This gird is really special. It has values at each of its cell which is some positive integer.

Superman gave Batman a serious headache inside the grid. He gave him an integer K and ordered him to tell count of such K x K matrix which when summed equals a perfect cube. Only if Batman gives the correct answer will the grid open and let Batman out.

Batman being not so good at coding turns to you for help. Its time for you to prove that you are a real Batman Fan by helping him out.

Input:

The first line contains 2 integers N and K . This is followed up by an N x N matrix.

Output:

Print number of such K X K matrix whose sum is a perfect cube.

Constraints :

 N  ≤ 1000

 K  ≤ N

All values in matrix  ≤ 10^9

SAMPLE INPUT
3 2
5 69 2 
42 9 9 
5 8 1 

SAMPLE OUTPUT
3

Explanation

The 3:  2x2 matrices whose sum equals a perfect cube are:

(1,1) to (2,2)

(2,1) to (3,2)

(2,2) to (3,3)

Source: hackerearth | Difficulty: EASY
Tags: Dynamic programming

Mathematics


Solutions:
n, k = list(map(int, input().split()))
mat= []
def is_perfect_cube(x):
	x = abs(x)
	return int(round(x ** (1. / 3))) ** 3 == x
for i in range(n):
	l = list(map(int, input().split()))
	sum = 0
	prev = l[0]
	for x in l[0:k]:
		sum += x
	l[0]=sum
	for j in range(1, n-k+1):
		sum = sum-prev + l[j+k-1]
		prev = l[j]
		l[j]=sum
	mat.append(l)
count=0
#print mat
for i in range(n-k+1):
	c = 0
	for z in range(0, k):
		c+=mat[z][i]
		if is_perfect_cube(c):
			count+=1
	for j in range(1, n-k+1):
		c = c - mat[j-1][i]+mat[j+k-1][i]
		if is_perfect_cube(c):
			count+=1
print(count)


ptr=input()
n,k=ptr.split(' ')
n=int(n)
k=int(k)
arr = []
sum = []
cnt=0
for i in range(0,n):
	arr.append([])
	sum.append([])
	str = input().split()
	for num in str:
		arr[i].append(int(num))
		sum[i].append(0)
for j in range(0,n):
	m=0
	for i in range (0,k):
		m=m+arr[i][j]
	sum[0][j]=m
	for i in range(1,n-k+1):
		m=m+arr[i+k-1][j]-arr[i-1][j]
		sum[i][j]=m
for i in range(0,n-k+1):
	sm=0
	for j in range(0,k):
		sm=sm+sum[i][j]
		if int(round(sm ** (1. / 3))) ** 3 == sm:
			cnt=cnt+1
	for j in range(1,n-k+1):
		sm = sm+(sum[i][j+k-1] - sum[i][j-1]);
		if int(round(sm ** (1. / 3))) ** 3 == sm:
			cnt=cnt+1
print(cnt)


def is_perfect_cube(x):
	x = abs(x)
	return int(round(x ** (1. / 3))) ** 3 == x


def main():
	N,K=list(map(int,input().split()))
	grid=[]
	for i in range(N):
		grid.append(list(map(int,input().split())))

	precomput=[]
	for i in range(N):
		summ=0
		#segment addition
		for j in range(K):
			summ+=grid[i][j]
		lst=[]
		lst.append(summ)
		for j in range(1,N-K+1):
			lst.append(lst[j-1]-grid[i][j-1]+grid[i][j+K-1])

		precomput.append(lst)

	#print precomput

	cnt=0
	for i in range(N-K+1):
		summ=0
		#segment addition
		for j in range(K):
			summ+=precomput[j][i]
		prev_sum=summ
		if is_perfect_cube(prev_sum):
			cnt=cnt+1
		for j in range(1,N-K+1):
			prev_sum=(prev_sum-precomput[j-1][i]+precomput[j+K-1][i])
			if is_perfect_cube(prev_sum):
				cnt=cnt+1

	print(cnt)


main()


n,k=list(map(int,input().split()))
mat=[[0 for i in range(n)] for j in range(n)]
splitup=[[0 for i in range(n)] for j in range(n)]
for i in range(n):
	mat[i]=list(map(int,input().split()))
#print mat
for j in range(n):
	sum = 0
	for i in range(k):
		sum += mat[i][j];
       		splitup[0][j] = sum;
	for i in range(1,n-k+1):
		sum += (mat[i+k-1][j] - mat[i-1][j]);
	        splitup[i][j] = sum
ans=0
for i in range(n-k+1):
   	sum = 0
      	for j in range(k):
        	sum += splitup[i][j]
	a = round(sum ** (1/3.0))
	b = a+1
	c = a-1
	if a*a*a==sum or b*b*b==sum or c*c*c==sum:
		ans+=1
      	for j in range(1,n-k+1):
		sum += (splitup[i][j+k-1] - splitup[i][j-1])
		a = round(sum ** (1/3.0))
		b = a+1
		c = a-1
		if a*a*a==sum or b*b*b==sum or c*c*c==sum:
			ans+=1
#print splitup
print(ans)


def is_perfect_cube(x):
	x = abs(x)
	return int(round(x ** (1. / 3))) ** 3 == x


def main():
	N,K=list(map(int,input().split()))
	grid=[]
	for i in range(N):
		grid.append(list(map(int,input().split())))

	precomput=[]
	for i in range(N):
		summ=0
		#segment addition
		for j in range(K):
			summ+=grid[i][j]
		lst=[]
		lst.append(summ)
		for j in range(1,N-K+1):
			lst.append(lst[j-1]-grid[i][j-1]+grid[i][j+K-1])

		precomput.append(lst)

	#print precomput

	cnt=0
	for i in range(N-K+1):
		summ=0
		#segment addition
		for j in range(K):
			summ+=precomput[j][i]
		prev_sum=summ
		if is_perfect_cube(prev_sum):
			cnt=cnt+1
		for j in range(1,N-K+1):
			prev_sum=(prev_sum-precomput[j-1][i]+precomput[j+K-1][i])
			if is_perfect_cube(prev_sum):
				cnt=cnt+1

	print(cnt)


main()


def is_perfect_cube(x):
	x = abs(x)
	return int(round(x ** (1. / 3))) ** 3 == x


def main():
	N,K=list(map(int,input().split()))
	grid=[]
	for i in range(N):
		grid.append(list(map(int,input().split())))

	precomput=[]
	for i in range(N):
		summ=0
		#segment addition
		for j in range(K):
			summ+=grid[i][j]
		lst=[]
		lst.append(summ)
		for j in range(1,N-K+1):
			lst.append(lst[j-1]-grid[i][j-1]+grid[i][j+K-1])

		precomput.append(lst)

	#print precomput

	cnt=0
	for i in range(N-K+1):
		summ=0
		#segment addition
		for j in range(K):
			summ+=precomput[j][i]
		prev_sum=summ
		if is_perfect_cube(prev_sum):
			cnt=cnt+1
		for j in range(1,N-K+1):
			prev_sum=(prev_sum-precomput[j-1][i]+precomput[j+K-1][i])
			if is_perfect_cube(prev_sum):
				cnt=cnt+1

	print(cnt)


main()