← 返回题目列表

Codeforces · 215/C

C. 十字架

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

有一个棋盘,其网格由 n 行 m 列组成,行从上到下从 1 编号,列从左到右从 1 编号。在此网格中,我们将位于第 i 行和第 j 列的单元格表示为 (i, j)。

一组六个数字 (a, b, c, d, x0, y0),其中 0 ≤ a, b, c, d,是一个十字,并且有一组分配给它的单元格。如果至少满足两个条件之一,则单元格 (x, y) 属于该集合:

- |x0 - x| ≤ a 和 |y0 - y| ≤ b
- |x0 - x| ≤ c 和 |y0 - y| ≤ d

图为3×4格子上的十字(0,1,1,0,2,3)。

您的任务是找出六个数字(a、b、c、d、x0、y0)的不同组的数量,这些数字确定等于 s 的区域的十字,这些十字完全放置在网格上。如果十字的任何单元格在网格范围内(即对于十字的每个单元格 (x, y) 1 ≤ x ≤ n;1 ≤ y ≤ m 成立),则该十字完全放置在网格上。十字的面积是它所具有的单元数。

请注意,如果表示两个十字的六个数字的有序组不同,则认为两个十字是不同的,即使这些十字作为点集重合。

输入

输入由一行组成,其中包含三个整数 n、m 和 s (1 ≤ n, m ≤ 500, 1 ≤ s ≤ n·m)。整数之间用空格分隔。

输出

打印单个整数 — 六个整数组成的不同组的数量,这些整数表示与面积 s 的交叉,并且完全放置在 n × m 网格上。

请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。

示例

输入 #1

2 2 1

输出 #1

4

输入 #2

3 4 5

输出 #2

4

注意

在第一个样本中,查找的六个数字组为:(0, 0, 0, 0, 1, 1)、(0, 0, 0, 0, 1, 2)、(0, 0, 0, 0, 2, 1)、(0, 0, 0, 0, 2, 2)。

在第二个样本中,查找的六个数字组为:(0, 1, 1, 0, 2, 2),(0, 1, 1, 0, 2, 3),(1, 0, 0, 1, 2, 2),(1, 0, 0, 1, 2, 3)。