CUBELCM - SUBCUBE EDGE LCM
My Friend Deepan Gupta gave me a problem on 3-D and said put it on SPOJ to have some peop fun. You are given a Cube M with size N*N*N, find the subcube S of M, having dimention E*E*E such that E is minimum and sum of all the elements of this subcube is greater than or equal to W. But i found this problem easy and also there are similar problems that already exists on SPOJ. So i made it twist. Now If no such cube exists, print -1. Else if exists with size E, then find the smallest k such that - n divides lcm (m,k) ; m divides lcm (n,k), where n = E^4, m = E^4+1.
Constraints : 0<=M[i][j][k]<=10^9, 1<=i,j,k<=N, 0<=W<=10^15, 1<=N<=100.
Input :
First line contains N,W, size of Cube and Cut-off weight respectively. Next lines contains N matrix. First N lines contains 1st bottom layer of Cube M, next N lines 2nd bottom layer of cube M and so on. Each layer has dimention N*N.
Output :
Print output as stated Above.
Examples :
Input :
3 15
1 2 3
2 3 4
3 4 5
2 3 4
3 4 5
4 5 6
5 6 7
6 7 8
7 8 9
Output :
272
Input :
3 1000
1 2 3
2 3 4
3 4 5
2 3 4
3 4 5
4 5 6
5 6 7
6 7 8
7 8 9
Output :
-1
Added by: | Rishav Goyal |
Date: | 2014-05-10 |
Time limit: | 0.100s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |
Resource: | Own |