Problem Link: http://www.spoj.com/problems/YELBRICK/
SUMMARY:
Each test case is given using several lines. The first line contains an integer N representing the number of different suppliers of yellow stone (2 ≤ N ≤ 1000). For simplicity, we assume that the engineers will buy exactly one stone from each supplier. Each of the next N lines contains three integers Ai, Bi, Ci (0 < Ai, Bi, Ci ≤ 1000, 1 ≤ i ≤ N) that describe, respectively, the width, height and depth of each stone provided by the i-th supplier. The last test case is followed by a line containing one zero.
For each test case, print one line containing the minimum number of identical cubes that can be cut from the given stones.
Logic
SUMMARY:
Each test case is given using several lines. The first line contains an integer N representing the number of different suppliers of yellow stone (2 ≤ N ≤ 1000). For simplicity, we assume that the engineers will buy exactly one stone from each supplier. Each of the next N lines contains three integers Ai, Bi, Ci (0 < Ai, Bi, Ci ≤ 1000, 1 ≤ i ≤ N) that describe, respectively, the width, height and depth of each stone provided by the i-th supplier. The last test case is followed by a line containing one zero.
For each test case, print one line containing the minimum number of identical cubes that can be cut from the given stones.
Logic
Cubes could be formed when all sides of individual cuboids are divisible by same no. or the volume is perfect cube.
So we have to maximize the volume with minimum number of cubes. So we must divide all sides with a number (a smallest number that divides all the sides).
To View My Solution:
No comments:
Post a Comment