#P1585. 魔法阵
魔法阵
题目描述
魔法阵是一个 的格子(高 ,宽 ), 为偶数。Smart 手中有 个宝石(以 编号)。Smart 从最右上角的格子开始走,从一个格子可以走到上、下、左、右 个相邻的格子,但不能走出边界。每个格子必须且仅能到过 次,这样 Smart 一共走了 个格子停止(随便停哪里)。Smart 每进入一个格子,就在该格子里放入一颗宝石。他是按顺序放的,也就是说——第 个进入的格子放入 号宝石。
如果两颗宝石的编号对 取模的值相同,则认为这两颗宝石相互之间有微妙的影响。也就是说,我们按照宝石的编号对 取模的值,将宝石分成 对,其中每对都恰有两颗宝石。对于每一对宝石,设第一颗宝石在第 行第 列,另一颗宝石在第 行第 列,那么定义这 个宝石的魔力影响值为 $k_1 \times \lvert a - c \rvert + k_2 \times \lvert b - d \rvert$。
需要你求出的是,在所有合乎题意的宝石摆放方案中,所有成对的宝石间的最大魔力影响值的最小值为多少。换句话说,如果我们定义对 取模的值为 的一对宝石的魔力影响值为 。你需要求出的就是 的最小值。
输入格式
只有一行用空格隔开的四个整数,分别是 。
输出格式
只需输出一个整数,即题目所要求的“所有成对的宝石间的最大魔力影响值的最小值”。
2 2 2 2
4
提示
对于 的数据,,。