← 返回题目列表

AtCoder · arc013_4

D. 你能把它分开吗?

中文机器翻译题面 查看原题

問題文

高桥先生想通过切割路边发现的铁块来制作砝码。
这个铁块很特别, 在 1cm^3 我们知道 1g 并用它来制作权重。
高桥君是个心地善良的年轻人,所以他也给青木君做举重。
另外,高桥的手不太好,所以我想将他切割一块铁的次数限制为一次,并制作尽可能多种类型的重量。
如何切割铁锭如下。
  • 切割铁锭,使一侧的长度始终为整数。
  • 水平剪切 您可以从 3 方向剪切。也就是说,你不能对角切割。
  • 然而,这一次,某个铁块可以被切割的次数是 仅 1 度。
  • 换句话说,铁块 切割 A 来制作铁锭 B 和铁块 如果你得到 C ,那么铁块 B 和铁块 如果你得到 C 无法断开连接。
考虑到路边发现的铁锭的种类和尺寸,需要多少铁锭才能产生高桥君的重量和青木君的重量?

入力

输入将以以下格式从标准输入给出。
N
X_{1} Y_{1} Z_{1}
X_{2} Y_{2} Z_{2}
:
X_{N} Y_{N} Z_{N}
  1. 1 行是一个整数,表示铁锭的类型。 直到 N(1≦N≦100) 给出。
  2. 2 在 N+1 行 在 N 行中,铁锭的尺寸以半角空格分隔。
    • X_{i} 为 i 铁锭的垂直长度。 第
    • Y_{i} 为 i 铁锭的水平长度。 第
    • Z_{i} 为 i 铁锭的高度。
    • X_{i},Y_{i},Z_{i} 均为整数, 1≦X_{i},Y_{i},Z_{i}≦20 有保证。 如果仅对满足

部分点

  • N = 1 的输入给出正确答案,则部分点为 20 点。 如果正确答案是满足

出力

计算制作所有砝码所需的铁锭数量。 它应该输出为 1 行。
另外,在输出末尾放置一个换行符。

入力例 1

2
3 4 5
2 3 4

出力例 1

13
  • 从一个3*4*5的铁锭,如果在3*4的平面上水平切割的话,会是12,24,36,48
    如果在3*5的表面上水平切割,则会是15,30,45
    如果在 4*5 的表面上水平切割,则会是 20,40
    您可以制作 9 种类型的权重。
  • 由2*3*4铁锭,
    如果在2*3的面上水平切割,则会是6,12,18
    如果在 2*4 的表面上水平切割,则会是 8,16
    在 3*4 表面上水平切割时,12 您可以制作 5 种类型的权重:
    。
  • 总共有 13 种重量,所以我想为两个人准备所有的重量。
  • 这将九个3*4*5铁锭分为(12-48)(24-36)(36-24)(48-12)(15-45)(45-15)(30-30)(20-40)(40-20),
    将四块2*3*4铁锭切割成四块(6-18)(18-6)(8-16)(16-8),
    你可以为两个人制作各种重量。

入力例 2

1
3 1 1

出力例 2

2

入力例 3

2
2 2 1
6 2 1

出力例 3

5

入力例 4

3
1 1 1
1 1 1
1 1 1

出力例 4

0