4

SPOJ問題「クリケットトーナメント」を解こうとしています。コードは python と c で書きました。Python では、入力 0.0 0/0 300 に対して約 2 秒かかります。しかし、C では永遠に実行されます。C のコードは、19.5 0/0 1 のような小規模なテスト ケースで実行されています。

C のコード

#include<stdio.h>
float ans[10][120][300]={0};
float recursion(int balls, int reqRuns, int wickets);
int readScore(void);

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        memset(ans,0,sizeof(ans));
        float overs;
        int myruns,wickets,target;
        scanf("%f",&overs);
        myruns=readScore();
        scanf("%d",&wickets);
        //printf("%d %d\n",myruns,wickets );
        scanf("%d",&target);
        //printf("%d %d %d\n",myruns,wickets,target);
        if(myruns>=target)
        {
            printf("%s\n","100.00");
            continue;
        }
        else if(wickets>=10)
        {
            printf("%s\n", "0.00");
            continue;
        }
        printf("overs = %f\n", overs);
        int ov = (int) overs;
        int ball = (int)(overs*10)%10;
        int totballs = 6*ov+ball;
        //printf("%d %d\n",ov,ball );
        //printf("%d %d %d\n",totballs, target- myruns,wickets );
        float finalAns = recursion(totballs,target-myruns, wickets)*100;
        printf("%.2f\n",finalAns);

    }
    return 0;
}

int readScore()
{
    char ch;
    int ans2=0;
    ch = getchar();
    //ch = getchar();
    //ans = ans*10 + ch-'0';
    //printf("sadasdas %d\n",ch );
    while(ch!='/')
    {
        ch=getchar();
        //printf(" ch = %d\n", ch-'0');
        if(ch!='/')
        ans2 = ans2*10 + ch-'0';

    }
    //printf("%d\n",ans );
    return ans2;
}

float recursion(int balls, int reqRuns, int wickets)
{
    if (reqRuns<=0)
        return 1;
    if (balls==120||wickets==10)
        return 0;
    if(ans[wickets][balls][reqRuns]!=0)
        return ans[wickets][balls][reqRuns];

    ans[wickets][balls][reqRuns] = (recursion(balls+1, reqRuns,wickets)+recursion(balls+1, reqRuns-1,wickets)+
    recursion(balls+1, reqRuns-2,wickets)+recursion(balls+1, reqRuns-3,wickets)+
    recursion(balls+1, reqRuns-4,wickets)+recursion(balls+1, reqRuns-5,wickets)+
    recursion(balls+1, reqRuns-6,wickets)+recursion(balls+1, reqRuns,wickets+1)+
    2*recursion(balls, reqRuns-1,wickets))/10;
    return ans[wickets][balls][reqRuns];
}

Python でのコード

from __future__ import division

saved = {}
t = input()

def func(f):
    if f in saved:    return saved[f]
    x,y,z,n = f 
    if z >= n:    return 1
    if x == 120:    return 0 
    if y == 10:    return 0

    saved[f] = (func((x+1,y+1,z,n)) + func((x+1, y,z,n)) + func((x+1,y,z+1,n)) + func((x+1, y, z+2,n)) + func((x+1, y, z+3,n)) + func((x+1, y, z+4,n)) + func((x+1, y, z+5,n))+ func((x+1, y, z+6,n))+ func((x,y,z+1,n)) + func((x,y,z+1,n))) / 10
    return saved[f]

def converter(f):
    v = f.index('.')
    x,y = int(f[:v]), int(f[-1])
    return x*6+(y)

for i in range(t):
    x,y,z = raw_input().split()
    v = y.index('/')
    q = int(y[:v])
    x,y,z = converter(x), int(y[(v+1):]), int(z)
    print  '%.2f' % (100 * func((x,y,q,z)))
4

3 に答える 3

3

あなたの問題は、再帰の結果の多くが0であることです。

if(ans[wickets][balls][reqRuns]!=0)
    return ans[wickets][balls][reqRuns];

多くの場合、キャッシュされた結果を返すことができないため、多くのf in saved結果を再計算していますが、Pythonのチェックは同じ値の再計算を防ぎます。

C コードを変更して、 の初期エントリにans負の数が含まれるように設定し (プラットフォームの浮動小数点表現が IEEE754 であることがわかっている場合は、に変更するだけで十分memset(ans, 0x80, sizeof ans);です)、条件を次のように置き換えました。

if (ans[wickets][balls][reqRuns] >= 0)

そしてすぐに結果を得ました：

$ time ./a.out  < spoj_inp.txt 
overs = 0.000000
18.03

real    0m0.023s
user    0m0.020s
sys     0m0.002s
于 2012-10-01T21:19:28.223 に答える
0

問題は、scanfの使用にあります。スペースまたは改行を入力のターミネータとして扱います。ほとんどの場合、各入力の後にEnterと入力しています。ただし、問題は、\ nがバッファに残り、それが次の入力に渡されることです。

strict cを使用していない場合は、

cin.ignore()

各scanf呼び出しの後。私はあなたのコードでそれを試し、成功した出力を得ることができました。

または、

fflush(stdin);

これも役立つかもしれません

stackoverflowでのscanf

于 2012-10-01T19:06:52.297 に答える
0

ここで再帰が非難されるべきだと思います。コードは、より小さなターゲットに対して機能します。可能であれば、再帰を取り除きます。

ターゲットが小さい場合:

入力

2
0.0 0/1 10
0.0 2/2 20

出力

100.00
99.99
于 2012-10-01T19:20:24.237 に答える