#2948. 挑战怪物【2024.9 GESP五级】
挑战怪物【2024.9 GESP五级】
挑战怪物【2024.9 GESP五级】
题目描述
⼩杨正在和⼀个怪物战⽃ ,怪物的⾎量为 h ,只有当怪物的⾎量恰好为 。时⼩杨才能够成功击败怪物。 ⼩杨有两种攻击怪物的⽅式: 物理攻击 。假设当前为⼩杨第 i 次使⽤物理攻击 ,则会对怪物造成 2i 1 点伤害。 魔法攻击 。⼩杨选择任意⼀个质数 ( 不能超过怪物当前⾎量) ,对怪物造成 点伤害 。 由于⼩杨并不擅长魔 法 ,他只能使⽤⾄多⼀次魔法攻击。 ⼩杨想知道⾃⼰能否击败怪物 ,如果能 ,⼩杨想知道⾃⼰最少需要多少次攻击。
输入格式
第⼀⾏包含⼀个正整数 ,代表测试⽤例组数。 接下来是 组测试⽤例 。对于每组测试⽤例 ,第⼀⾏包含⼀个正整数 ,代表怪物⾎量。
输出格式
对于每组测试⽤例 ,如果⼩杨能够击败怪物 ,输出⼀个整数 ,代表⼩杨需要的最少攻击次数 ,如果不能击败怪物, 输出 1。
输入输出样例 #1
输入 #1
3
6
188
输出 #1
2
4
-1
说明/提示
对于第⼀组测试⽤例 ,⼀种可能的最优⽅案为 ,⼩杨先对怪物使⽤魔法攻击 ,选择质数 5 造成 5 点伤害 ,之后对怪 物使⽤第 1 次物理攻击 ,造成 21 1 = 1 点伤害 ,怪物⾎量恰好为 ,⼩杨成功击败怪物。
数据范围
子任务编号 数据点占比 t h 1 20% 5 ≤ 10 2 20% ≤ 10 ≤ 100 3 60% ≤ 10 ≤ 105 对于全部数据 ,保证有 1 ≤ t ≤ 1 , 1 ≤ h 105 。