2

私はspojの問題を解決しようとしています。ここに問題へのリンクがあります。

http://www.spoj.pl/problems/TAP2012B/

私が解釈したことから、式 xy+yz+xz = N の解の数を見つける必要があります。ここで、n は与えられています。x>=y>=z z はゼロにすることができます。しかし、x と y はできません。3つのforループを実装することでこれを解決しようとしました(悪いアプローチ)。正しい答えを出していますが、遅すぎます。また、他の人がすぐに解決したので (0.00)、この問題には非常に異なるアプローチがあると確信しています。N = 20 の場合、異なる解の数は 5 です: (6,2,1) (5,4,0) (10,2,0) (4,2,2,) (20,1,0)

4

3 に答える 3

2

数論に基づいて構築された素晴らしいソリューションがあるかもしれません。しかし、単にタスクを再考するだけで、アルゴリズムの複雑さも軽減できます。

たとえば、 として計算できるので、3 番目のループは必要ありませzん(N - x*y)/(x+y)。そして、私たちが知っているように、それは否定的ではないので、毎回yずっと実行する必要はありません。xzN >= xy

N = 9747
for x in range(1, N+1):
    max_y = min( N / x, x) 
    for y in range(1, max_y+1):
        if (N - x*y) % (x+y) == 0:
            z = (N - x*y) / (x+y)
            if z <= y:
                print x,y,z
于 2013-07-04T11:33:13.240 に答える