查看: 656|回復: 0

[提問] codechef WALL

[複製鏈接]
  • TA的每日心情
    開心
    2015-4-12 10:09
  • 簽到天數: 137 天

    [LV.7]常住居民III

    142

    主題

    686

    帖子

    3559

    積分

    邁向天堂

    蘇多門

    Rank: 8Rank: 8

    積分
    3559

    新手達陣台南一中資訊社程式設計達人 - 2014

    發表於 2014-9-2 22:52:56 | 顯示全部樓層 |閱讀模式

    趕快加入我們來參與討論吧!

    您需要 登錄 才可以下載或查看,沒有帳號?加入我們

    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);
            }
    }
    
    蘇多門 domen111
    My Web: https://sites.google.com/site/domenprg/
    回復

    使用道具 檢舉

    您需要登錄後才可以回帖 登入 | 加入我們

    本版積分規則

    快速回覆 返回頂部 返回列表