#6351. 「CodePlus 2018 4 月赛」喵呜

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Snakes

题目描述

在马路边有一排整齐的 nn 棵樱花树,每棵树的高度都恰好为 hh。某天,一只可爱的小猫偶然跑到树上来玩,但是这只小猫有些对樱花过敏,所以她现在想赶快离开这些樱花树。

具体来说,现在小猫位于第 xx 棵樱花树上高度为 yy 的位置,她可以通过两种跳跃来离开樱花树:

轻轻跳:向左或向右移动 aa 棵樱花树的同时,所在高度下降 bb,即一次轻轻跳可以从起点移动到第 x+ax+axax−a 棵树上高度为 yby−b 的位置,注意当小猫所在高度不大于 bb 时不可以使用轻轻跳。

使劲跳:向左或向右移动 aa 棵樱花树的同时,所在高度上升 bb,即一次使劲跳可以从起点移动到第 x+ax+axax−a 棵树上高度为 y+by+b 的位置,注意当小猫所在高度大于 hbh−b 时不可以使用使劲跳。

为了离开这片樱花树,小猫需要移动到第 11 或第 nn 棵树上,高度为 hh11 的位置(这样她可以呼吸新鲜空气或者直接走开樱花树)。现在小猫想知道,自己最少需要多少次跳跃才能达成目标。由于她是一只可爱的小猫,所以希望由你来告诉她。

输入格式

从标准输入读入数据。

输入数据第一行包含一个正整数 TT,表示测试数据的组数,各组数据之间没有空行。

接下来 TT 行,依次描述每组数据:

每组数据包含一行,包含六个正整数 n,h,x,y,a,bn,h,x,y,a,b,其含义见题目描述。

输出格式

输出到标准输出。

输出由 TT 组数据组成,各组数据之间没有空行。对于每一组数据:

若小猫可以成功离开樱花树,请输出她需要的最少跳跃次数。

若小猫无法通过给定的跳跃方法离开樱花树,请输出-1

样例

样例输入 1

3
5 5 3 3 2 2
5 7 3 5 2 2
5 7 4 6 1 1

样例输出 1

1
1
1

样例输入 2

3
5 5 3 3 3 2
5 7 1 4 2 2
5 7 1 2 1 2

样例输出 2

-1
-1
-1

样例输入 3

4
999999999999 999999999999 454545454545 454545454545 1 1
777777777777 777777777777 343434343434 343434343434 1 1
777777777777 999999999999 343434343434 454545454545 1 1
999999999999 777777777777 454545454545 343434343434 1 1

样例输出 3

454545454544
343434343433
-1
-1

数据范围与提示

对于所有的数据,保证 1T1001\leq T\leq 1001x,an1\leq x,a\leq n1y,bh1\leq y,b\leq h,其它数据规模与约定请见下表。

测试点编号n,hn,h 的范围特殊约定
110\leq 10 b=1b=1
2
3a=b=1a=b=1
4
5
6
7
8
9500\leq 500 b=1b=1
10
11a=b=1a=b=1
12
13
14
15
16105\leq 10^5 h10h \leq 10
17
18
19
20
211015\leq 10^{15} h10h \leq 10
22
23
24
25

来自 CodePlus 第 4 次月赛,清华大学计算机科学与技术系学生算法与竞赛协会 荣誉出品。
Credit:idea 与命题/何昊天 验题/钟皓曦
Git Repo:https://git.thusaac.org/publish/CodePlus4
感谢腾讯公司对此次比赛的支持。