趕快加入我們來參與討論吧!
您需要 登錄 才可以下載或查看,沒有帳號?加入我們
x
http://www.codechef.com/problems/WALL/
這題輸出會有浮點誤差的問題,不過明明就只是除以2而已,為什麼這樣也會有問題?
就因此損失了好幾分,寫了一個正確的解法結果只拿到和暴力解一樣的分數(好像和當時排名賽的狀況有點像)
[C++] 純文本查看 復制代碼 #include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
ll x[524298];
ll d[524298];
int p[524298];
ll h,n,m,a,b,ind;
ll recb,rece;
ll cal()
{
x[0]=0;
for(ll i=1;1;i++)
{
if(i>=n) return x[n-1];
if(p[ind]!=-1)
{
recb=p[ind]-1;
rece=i-1;
break;
}
x[i]=x[i-1]+d[ind];
p[ind]=i;
ind=(a*ind+b)%m;
}
ll dif=n-1-rece;
ll rec=rece-recb;
return x[rece] + dif/rec*(x[rece]-x[recb]) + (x[recb+dif%rec]-x[recb]);
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
memset(p,-1,sizeof p);
scanf("%lld %lld %lld %lld %lld %lld",&h,&n,&m,&a,&b,&ind);
for(ll i=0;i<m;i++)
scanf("%lld",&d[i]);
ll ans=cal()*h;
printf("%lld.%lld\n",ans/2,ans%2*5);
// printf("%.1lf\n",double(cal()*h)/2);
}
}
|