简答题 偏难
#20916

挑战怪物 时间限制:1.0 s 内存限制:512.0 MB 题面描述 小杨正在和一个怪物战斗,怪物的血量为 h ,只有当怪物的血量恰好为 0 时小杨才能够成功击…

挑战怪物

时间限制:1.0 s

内存限制:512.0 MB

题面描述

小杨正在和一个怪物战斗,怪物的血量为 h ,只有当怪物的血量恰好为 0 时小杨才能够成功击败怪物。

小杨有两种攻击怪物的方式:

物理攻击。假设当前为小杨第 i 次使用物理攻击,则会对怪物造成 2i−1点伤害。

魔法攻击。小杨选择任意一个质数 x (x 不能超过怪物当前血量),对怪物造成 x 点伤害。由于小杨并不擅长魔法,他只能使用至多一次魔法攻击。

小杨想知道自己能否击败怪物,如果能,小杨想知道自己最少需要多少次攻击。

输入格式

第一行包含一个正整数 t ,代表测试用例组数。

接下来是 t 组测试用例。对于每组测试用例,第一行包含一个正整数 h ,代表怪物血量。

输出格式

对于每组测试用例,如果小杨能够击败怪物,输出一个整数,代表小杨需要的最少攻击次数,如果不能击败怪物,输出−1。


输入样例

3
6
188
9999

输出样例

2
4
-1

对于第一组测试用例,一种可能的最优方案为,小杨先对怪物使用魔法攻击,选择质数 5 造成 5 点伤害,之后对怪物使用第 1 次物理攻击,造成21−1=1 点伤害,怪物血量恰好为 0 ,小杨成功击败怪物。

对于全部数据,保证有 1≤t≤10,1≤h≤105。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;bits/stdc++.h&gt; using namespace std; vector&lt;int&gt; prime; bool is_prime[100010]; void Eratosthenes(int n) { is_prime[0] = is_prime[1] = false; for (int i = 2; i &lt;= n; ++i) is_prime[i] = true; for (int i = 2; i &lt;= n; ++i) { if (is_prime[i]) { prime.push_back(i); if ((long long)i * i &gt; n) continue; for (int j = i * i; j &lt;= n; j += i) is_prime[j] = false; } } } int main() { Eratosthenes(100000); int t; cin&gt;&gt;t; while(t--){ int tmp=1; int x; cin&gt;&gt;x; int ans=0; while(1){ if(is_prime[x]){ ans++; break; } x-=tmp; ans++; if(x&lt;=0){ if(x&lt;0)ans=-1; break; } tmp*=2; } cout&lt;&lt;ans&lt;&lt;"\n"; } }</pre>
这道题暂未补解析。