🐷大肚肚
CF-32C普及+/提高

跳跃游戏

2.0s💾 256MB

📋 题目描述

有一只跳蚤在 n×mn \times m 的网格棋盘上进行跳跃游戏,每一次跳跃的距离为定值 ss,而且不能跳出棋盘的边界。定义函数 f(x,y)f(x,y) 表示从 (x,y)(x,y) 开始跳能达到的点的个数,如果 f(x,y)f(x,y) 的最大值为 kk ,那么在保证跳蚤能够到达 kk 个格子的起始位置方案数。

📥 输入格式

仅有一行包含三个整数 nn, mm, ss ( 1n,m,s1061 ≤ n, m, s ≤ 10^6 ) 分别表示棋盘的长度,棋盘的宽度和跳蚤每次的跳跃长度。

📤 输出格式

仅有一个整数,表示题目要求的答案。

📝 样例 1

输入
2 3 1000000
输出
6

📝 样例 2

输入
3 3 2
输出
4

💡 题目讲解

1

理解题意

有一只跳蚤在 n×mn \times m 的网格棋盘上跳。规则很简单:

🦗 每次跳恰好 ss,只能水平或垂直方向(上下左右),不能斜着跳。 🚫 不能跳出棋盘边界。 🎯 f(x,y)f(x,y) = 从格子 (x,y)(x,y) 出发能到达的不同格子的个数。

你需要算出:有多少个起点 (x,y)(x,y),使得 f(x,y)f(x,y) 达到最大值

1s=3 →2↓ s=3n=5, m=4, s=3从"起"出发水平跳到 格子 1垂直跳到 格子 2f(起) = 3
1 / 5