失われたカードを見つける（より速い解決策）

Question

1からNまでのユニークな番号を持つN（3 < = N < = 50000）カードが与えられます。 カードを3枚失ってしまいました。

入力は：自分のキューブの我々が持っているすべての左のカードの合計、彼らの二乗の和と合計：最初の行は セカンドラインは、3つの数字が含まれているカードNの数が含まれています。

出力：任意の順序で3枚のカードが失われました。

ここで私が試したことは：紛失したカードについて同じ3つの合計を見つけ、そのうち3つが合計を満たすまで、可能な数をチェックします。

高速なソリューションはありますか？私は、最大NとPythonで2秒の制限時間を通過しなければならない= 50000

N = int(input()) 
lst = list(range(1, N+1)) 
s_rest, s2_rest, s3_rest = list(map(int, input().split())) 

s = sum(lst) 
s2 = sum([x**2 for x in lst]) 
s3 = sum([x**3 for x in lst]) 
# sums of 3 lost numbers 
s_lost = s - s_rest 
s2_lost = s2 - s2_rest 
s3_lost = s3 - s3_rest 


def find_numbers(): 
    """Find first appropriate option""" 
    for num1 in range(s_lost): 
     for num2 in range(s_lost): 
      for num3 in range(s_lost): 
       if (num1 + num2 + num3 == s_lost) and (num1**2 + num2**2 + num3**2 == s2_lost)\ 
         and (num1**3 + num2**3 + num3**3 == s3_lost): 
        return (num1, num2, num3) 

answer = find_numbers() 
print(answer[0], answer[1], answer[2]) 

例

入力：

出力：

---

入力：

出力：

Answer 1

ご不明な数字はX、Y、Z、ある場合、あなたは、このシステムの直接的な解決策は複雑すぎるようだが、我々は、未知のものを修正し、シンプルなシステムを解くことができる3つの方程式

x + y + z = a //your s_lost 
x^2 + y^2 + z^2 = b //your s2_lost 
x^3 + y^3 + z^3 = c //your s3_lost 

のシステムを持っています。例えば、zの可能なすべての値をチェックし、xとy

for z in range(s_lost): 
.... 

するためのシステムを解く今度は、新しいシステムに見てみましょう：

x + y = a - z = aa 
x^2 + y^2 = b - z^2 = bb 
substitute 
x = aa - y 
(aa - y)^2 + y^2 = bb 
2 * y^2 - 2 * y * aa - bb + aa^2 = 0 
solve this quadratic equation for y 
D = 4 * aa^2 - 8 * (aa^2 - bb) = 8 * bb -4 * aa^2 
y(1,2) = (2*aa +- Sqrt(D))/4 

だから、すべてのzの値を見つける：
- ソリューションを提供しますかyの整数値
- 次にx
を取得し、キューブサム式が真であるかどうかを確認します。

この手法を使用すると、キュービック複雑度O（N^3）に対して線形複雑度O（N）の解を得ることができます。

P.S.式システムのための幾分単純な数学的解が存在するならば、複雑さO（1））

Answer 2

は確かに速く存在しますアプローチ！

はN = 50,000のためにあなたのブルートフォース機能は

N * N * N = 125,000,000,000,000 

の反復までに行う必要がありますので、これはオプションではありません。

また、あなたが重複番号は（問題が明示的にそれを述べていない避けるためにnum1 == num2などをチェックする必要がありますが、私は「私たちは、いくつかの3枚のカードを失った」理解し、あなたが与えられた条件を満たした3つの異なる番号を検索する必要があることを意味）。

Answer 3

リストを並べ替えて、a[i+1] =/= a[i]+1のようなペアを見つけることができます。そのようなすべてのペア番号のために[a[i]+1;a[i+1])がありません。これはあなたにO（n log n）の実行時間を与えます。

Answer 4

これは、数学的手法によって簡略化することができます。 3つの方程式が与えられ、3つの未知数があります。

sum(1+2+..+N) - x1 - x2 - x3 = a 
sum(1^2+2^2+..+N^2) - x1^2 - x2^2 - x3^3 = b 
sum(1^3+2^3+..+N^3) - x1^3 - x2^3 - x3^3 = c 

明らか

sum(1..N)sum(1^2+2^2+3^2+..+N^2)が1/6 *N*(N+1)*(2N+1)で、sum(1^3+2^3+..+N^3)が1/4 *N^2 *(N+1)^2のように記述することができる一方で、1/2 *N(N+1)です。 ∑k、∑k^2、∑k^3

この時点で残された唯一の事は、方程式の特定のシステムを解く（3つの未知数を有する3が完全に解けるある）、これを実施している。ここでwolframalpha出力です。あなたはそれをより簡単にする1つの解決策を見つける必要があります。実行時間はO（1）です。私はあなたのアイデアを与えることができ

Answer 5

、

sum1 = 1+2+3...n

を聞かせてはsum2 = 1^2+2^2+3^2...n

とp, q, rが連続して入力することによって与えられた3つの数字でみましょう。

a, b, cを検索する必要があります。

がx = sum1 - (p+c)

を聞かせて、各反復についてfor c = 1 to N.

を反復処理はy = sum2 - (q+c*c)

のでa+b = xとa^2+b^2 = yをしましょう。

a^2+b^2 = (a+b)^2 - 2ab以降、式a^2+b^2 = yから2abを見つけることができます。

a+bが知られており、abが知られており、少し数学計算によって、あなたはaとbのためのソリューションが存在する場合（これは二次方程式を形成する）見つけることができます。存在する場合は、ソリューションを印刷して繰り返しを中断します。

これはO(N)ソリューションです。