बड़े पूर्णांक गुणांक (पूर्णांक पर) के साथ वर्गबद्ध समीकरणों को वास्तव में कैसे हल करें?

Question

मैंने Google Code Jam में a problem about bullseyes पढ़ा। (प्रतियोगिता अब खत्म हो गया है, तो यह इस बारे में बात करने के लिए ठीक है)

मारिया काले रंग की टी मिलीलीटर, जो वह मोटाई 1 सेमी (एक सेंटीमीटर) के छल्ले आकर्षित करने के लिए प्रयोग करेंगे के साथ शुरू होता है। मोटाई 1 सेमी की एक अंगूठी दो सांद्रिक सर्कल के बीच की जगह है जिसका त्रिज्या 1 सेमी से भिन्न होता है।

मारिया त्रिज्या आर सेमी के एक सफेद सर्कल के चारों ओर पहली काली अंगूठी खींचती है।

त्रिज्या 1 सेमी के साथ डिस्क का क्षेत्र π सेमी 2 है। क्षेत्र π सेमी 2 को कवर करने के लिए पेंट का एक मिलीलीटर आवश्यक है। मारिया आकर्षित कर सकते हैं कि काले रंग के छल्ले की अधिकतम संख्या क्या है?

कागज पर मेरी गणना करके, रंग के क्षेत्र, एन के छल्ले, भीतरी r त्रिज्या के साथ एक बुल्सआई आकर्षित करने के लिए के रूप में पाई की एक बहु 2*n**2 + n*(2*r-1)

तो पेंट की समस्या को मिल रहा है t*pi millitres दिया

है सबसे बड़ा एन जैसे f(n,r) <= t।

आज सुबह मैं हल है कि द्विआधारी खोज https://github.com/hickford/codejam/blob/master/2013/1A/bullseye/bullseye.py

साथ मैं द्विघात समीकरण से अधिक द्विआधारी खोज को इसलिए चुना क्योंकि मैं चल बिन्दु अस्पष्टता की बहुत सावधान कर रहा हूँ - इस समस्या को टी में और आर 10 के रूप में के रूप में बड़ा पूर्णांक हैं ** 18)। पिछले कोड जाम में अंकगणित अपर्याप्त मुझे थोड़ा सा।

लेकिन मैं उत्सुक हूँ। क्या आप बड़े पूर्णांक गुणांक के साथ समीकरणों के सही उत्तर देने के लिए वर्गबद्ध समीकरण को किनारे लगा सकते हैं? क्या सिथी या न्यूम्पी जैसे गणित पुस्तकालयों में मुझे कुछ देने की ज़रूरत है?

---

प्रदर्शन यह है कि वर्गबद्ध समीकरण बड़े इनपुट के लिए गलत जवाब देता है। उदाहरण के लिए, r=308436464205151562 और t=1850618785230909388 के साथ। हल करने के लिए वर्गबद्ध समीकरण

2*n**2 + 616872928410303123*n -1850618785230909388 <= 0 

यानी। गुणांक

a = 2 
b = 616872928410303123 
c = -1850618785230909388 

कम्प्यूटिंग अजगर

> int((-b + math.sqrt(b**2 - 4*a*c))/(2*a)) 
    0 

में यह गलत जवाब है कर रहे हैं! सही जवाब (बाइनरी खोज के द्वारा पाया) 3

>>> n = 3 
>>> 2*n**2 + 616872928410303123*n -1850618785230909388 <= 0 
True 

Answer 1

प्रतीकात्मक सटीक जोड़तोड़ के लिए है, वहाँ sympy है।

आप निम्नलिखित पेस्ट:

a, b, c = 2, 616872928410303123, -1850618785230909388 
x = Symbol('x') 
int(max(solve(a*x**2 + b*x + c, x))) 

here, आप 3.

मिल [ओपी टिप्पणी निम्नलिखित संपादित]।

Answer 2

यदि (t/r^2) > 10000sqrt के माध्यम से गणना करें।
तो (t/r^2) < 10000 हर n 0 से शुरू करके 1.

Answer 3

पूर्णांक वर्ग जड़ों का उपयोग कर समाधान में वृद्धि के रूप में @Vaughn

def solve2(r,t): 
    """Maximum number of black rings that Maria can draw, with inner radius r, given pi*t of paint. Solve using quadratic equation""" 
    import gmpy 
    from gmpy import mpz 

    a = 2 
    b = 2*r - 1 
    c = -t 

    x = (-b + mpz(b**2 - 4*a*c).sqrt()) // (2*a) 
    return int(x) 

Answer 4

roundoff परिशुद्धता इस समस्या पर मुझे मरवा ने सुझाव दिया है ... लेकिन आप रख सकता है की कोशिश सब कुछ 64 बिट पूर्णांक परिशुद्धता पर, और परिणामी वर्गबद्ध समीकरण पर एक बाइनरी खोज करते हैं। मैंने अपना दृष्टिकोण here रेखांकित किया।