C. Sasha and the Casino
当 \(k<x\) 时,显然我们只需要每次下注一个硬币就好了.
当 \(k>x\) 时.
考虑先一个一个的下硬币,那么为了保证不亏本,最多输 \(k-2\) 局,然后在第 \(k-1\) 局赢,这样才能盈利 \(1\) 个硬币.
那么在第 \(k\) 局之后呢? 此时我们最少也需要下注两个硬币,这样赢了就能获得 \(2k\) 个硬币, (错误结论:直到第 2*k局之前我们都是可以有机会把之前亏的都赢回来的.)
思考一下,假设硬币数量充足,这时候两个两个的投最多进行几局才能保证不亏本?
为什么会亏本?
你投的数量越多,就可能导致即使你在之后的某一局中赢得 \(2k\) 个硬币也不能弥补之前的亏损,这样你就亏本了,庄家就可以靠这种策略坑你的钱.因此你要保证你的下注赢了以后要稳稳当当地盈利.
假设当前进行的是第 \(i\) 局,下注为 \(now\) ,那么如果赢了,就获得 \(k*now\) 个硬币.假设我们之前投了 \(all\) 个硬币,那么只有满足 \(k*now \geq all+k\),才能保证不亏本. 化简得 \(now\geq all/(k-1)\),此处是上取整.这样我们就得到了为了防止亏本,每次下注的最低金额
这样就很简单了,算出来 1~x 局,以及最后稳赢1局总共x+1局的最低下注金额的和就可以了.
WA7是因为没开longlong或者 当花费钱数大于a时没有break,如果不break就要用__int128存.
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int __int128
void solve()
{
long long k,x,a;
cin>>k>>x>>a;
__int128 l = 0;
for(int i=1;i<=x+1;i++)
{
__int128 now=0;
if(l%(k-1)==0)
{
now = l/(k-1)+1;
}
else
{
now = (l+k-2)/(k-1);
}
l+=now;
// now*k>l+now
// now*(k-1)>l
// now>l/(k-1)
// if((l+1+k-1)%k==0)
// {
// l+=(l+1+k-1)/k+1;
// }
// else l+=(l+1+k-1)/k;
// cout<<' '<<l<<'\n';
// all+=(all+1+k-1)/k;
}
if(l<=a)
{
cout<<"YES\n";
}
else cout<<"NO\n";
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
long long T;
cin>>T;
while(T--)
solve();
}