思路与方法

核心观察

• 设对三根木头累计切去的总长度分别为 $(s_1,s_2,s_3)$。初始 $(0,0,0)$。

• 第 $i$ 次若给第 1 根切，则需 $a-s_1>i \iff s_1+i < a$；切完后 $s_1\leftarrow s_1+i$（另外两根不变）。对第 2、3 根同理。

• 只需记录所有可达的累计切除三元组集合 $R$（含初始）。最终把每个可达状态映射为长度 $(x,y,z)=(a-s_1,b-s_2,c-s_3)$，统计满足

  $$x+y > z,\quad y+z>x,\quad z+x>y$$

题目描述

小红是一家木材厂的厂主，他收到了一项加工任务：

有三根长度分别为 $a,b,c$ 的木头，需要进行最多 $n$ 次加工，其中第 $i$ 次加工需要将其中一根长度大于 $i$ 的木头切割，使其长度减小 $i$。被切下的部分将会丢弃不能重复使用。

定义一个三元组 $(a,b,c)$ 是“美丽的”当且仅当 $a,b,c$ 可以组成一个面积不为 $0$ 的三角形。

该任务的目标是计算 通过不超过 $n$ 次加工，三根木头的长度可以组成美丽的三元组 的数量。

输入格式

输入四个整数 $n,a,b,c$，满足 $1 \le n,a,b,c \le 100$。

输出格式

输出可以得到的美丽的三元组的数量。

7 5 8 9

37

5 3 4 5

10