#P3664. 乾坤大挪移

    ID: 2859 传统题 1000ms 512MiB 尝试: 17 已通过: 10 难度: 8 上传者: 标签>难度分类提高+/省选-模拟与实现技巧坐标变换构造与建模奇偶性分析对称性分析动态规划有限候选集缩减数论向下取整与向上取整高精度除法排序与序列处理二分查找CF2500

乾坤大挪移

乾坤大挪移

题目描述

邪恶的 DBJ 抓走了 XYF,把她关在吉萨金字塔群地下(北纬 29∘58′43.41′′29^\circ 58'43.41''、东经 31∘8′5.06′′31^\circ 8'5.06'')。目录哥带上神犬扎昆和军需官巨胖,搭乘猴猴猴家开的泛埃及航空公司的飞机前来救援。

塔共有 TT 层棋盘。每到一层,目录哥都把自己所在的格子当作原点 (0,0)(0,0),下一层的钥匙在 (X,Y)(X,Y)。必须把钥匙移到原点才能下楼。

每次可以任选一个格子作为中心,画一个臂长为 LL 的十字或 X 形,再绕中心顺时针或逆时针旋转 90∘90^\circ。十字沿水平和竖直方向伸展,X 形沿四条对角线伸展。每条臂上的格子数都为 LL,其中包含中心格。形状内每个格子里的物品都跟随格子转到新位置。

左图是逆时针旋转的长度为 3 的 X 形,右图是顺时针旋转的长度为 2 的十字形

对每层分别求取钥匙所需的最少咒语次数。

输入格式

第一行一个正整数 TT。

接下来 TT 行,每行三个整数 X,Y,LX,Y,L,分别表示一层上钥匙的坐标 (X,Y)(X,Y) 和咒语的臂长。

输出格式

每层输出一行。若能把钥匙移到原点,输出最少的咒语次数。若无法取得钥匙,输出 Poor MLG!。

样例

3
12 20 5
14 22 5
0 1 2
4
5
Poor MLG!

数据范围

1≤T≤10001\le T\le 1000,∣X∣,∣Y∣≤10500|X|,|Y|\le 10^{500},2≤L≤105002\le L\le 10^{500}。