爲什麼我得到一個也不能少算總是

我解決Codeforce一個problem，這是我以前提交爲什麼我得到一個也不能少算總是

#!/usr/local/bin/python 

limit = 10**18 
string = raw_input() 
year1, year2 = string.split() 
year1 = int(year1) 
year2 = int(year2) 
x = 1 
count = 0 
a = [] 
while True: 
    k = 2**x - 1 

    if k > limit: 
     break 
    else: 
     for i in xrange(len(bin(k)[2:])): 
      if year1 <= k - (1 << i) <= year2 and len(bin(k - (1 << i))[2:].split('0')) == 2: 
       count += 1 
    x += 1 
print count

它爲所有給定值，但它給了一個更小的計數值的範圍1到1000000000000000000。這是很難調試，因此我把破解了代碼的最後print之前這樣

if year2 - year1 + 1 == limit: 
    count += 1

和它的工作該值，但再次給了一個價值較低值另一個範圍，1到935829385028502935。

難怪無邏輯黑客無法正常工作，但我想知道爲什麼以前計數值爲？

來源

2016-01-07 Mayukh Sarkar

我不知道我正確理解你的問題，但你知道，'範圍（B）'將通過'B-1'正確產生值'0'？ –

是的，我知道這一點，那就是意圖。比特位置從0開始，並且運行一個小於最大值......一個小於一個計數意味着比實際回答少一個計數值。 –

我試圖簡化代碼（現在的工作，接受）：

limit = 10**19 # this change is important because otherwise you will loose 1 solution 
# k > limit and exists such i that k - (1 << i) < limit 

string = raw_input() 
year1, year2 = string.split() 
year1 = int(year1) 
year2 = int(year2) 
x = 1 
count = 0 
a = [] 
while True: 
    k = 2**x - 1 
    if k > limit: 
     break 

    for i in xrange(x - 1): # k has exactly x bits. So we have only x-1 chances to set zero bit 
     if year1 <= k - (1 << i) <= year2: 
      count += 1 
    x += 1 

print count

提交：http://codeforces.com/contest/611/submission/15230069

來源

2016-01-07 20:37:28 SashaMN

這項工作？如果是這樣，在你的回答中這樣說。如果沒有，請刪除它。 – ppperry

您需要通過另一個量級增加limit：

limit = 10**19

否則，你會錯過864691128455135231，從1152921504606846975 - (1 << 58)獲得。

（觀察到1152921504606846975 > 10**18。）

來源

2016-01-07 21:18:14 dejvuth

不錯的觀察..謝謝..爲什麼我不能這樣做.. –

爲什麼我得到一個也不能少算總是

回答

相關問題