無限序列。無法在1秒內處理答案

我想查找無限序列的數字[i]，但在以下輸入中需要很長時間。無限序列。無法在1秒內處理答案

讓我們考慮一個接一個地寫上10的上升冪構成的數字的無限序列。這裏是序列的開始：110100100010000...你要找出序列的確定位置處的數字。

輸入第一行只有一個整數N（1≤N≤65535）。左N行中的第i行包含整數K [i] - 序列中的位置數（1≤K [i]≤231 - 1）。

輸出您將輸出以空格分隔的N位數字0或1。更確切地說，輸出的第i個數字等於上述序列的第Ki個數字。

INPUT
4 
3 
14 
7 
6 
輸出
0 0 1 0 

這裏是我的代碼

x = input() 
a = [] 
for i in range(x): 
    y = input() 
    a.append(y) 

b = '1' 
c = 1 
for i in range(100): 
    c *= 10 
    b += str(c) 

for i in range(x): 
    print b[a[i]-1],

來源

2014-12-08 Clt Complainers

問題是？ – 2014-12-08 08:22:32

@jonrsharpe我想這裏的問題是'K [i]'可以大得多（'1≤K [i]≤231 - 1'，我假設「231」是一個複製粘貼錯誤，意味着2^31）並且這個程序的方法不成立。 – Carsten 2014-12-08 08:30:47

這裏的訣竅是注意到並不是很多，你可以根據模式確切地確定它們的位置;其他任何東西都必須是零。您可以編寫一個函數來確定，對於給定的'i'，無需構建字符串*，必須* K [i]'*。 – jonrsharpe 2014-12-08 08:34:50

你需要超越對問題的基本描述。如果你生成整個字符串，那將是2^31個字符長（你需要上升到65536，而不是100）。幸運的是，有一個更好的方法。你並不需要這個字符串。您只需要一種方法來檢查給定索引K[i]上的字符是否爲1.

字符串中所有「1」的位置對應於triangular numbers。該n個三角形的數量可以通過

x = n * (n + 1)/2

計算通過求解n，我們得到

n = sqrt(2 * x + 0.25) - 0.5

如果x是三角形的數字，然後n將是一個整數，字符串將有該位置上的「1」。否則，一個「0」。此外，我們必須使用K[i] - 1，因爲問題中的索引是基於1的。

import math 
import sys 

f = lambda x: math.sqrt(2.0 * x + 0.25) - 0.5 
g = lambda x: f(x) % 1 == 0 

inp = map(int, sys.stdin.read().split()[1:]) 

print(" ".join("1" if g(x-1) else "0" for x in inp))

來源

2014-12-08 08:46:42 Carsten

你不應該在這裏生成一個完整的字符串，而不是使用一些數學。這裏的數字是：

如果你看一下該系列你會發現1點的所在的位置1，2，4，7，11，... 我們可以概括這一系列使用這個公式(n^2 - n + 2)/2。因此，二次方程式將變爲：

(n^2 - n + 2)/2 = i 
#or n^2 - n + 2 - 2i

哪裏i從輸入來的當前索引。

現在，如果任何i的b^2 - 4ac輸出是一個完美的正方形那就意味着數肯定是1，否則則爲0（這裏的a值是1，b爲-1，我們可以使用2 - 2*i計算c ）

from math import sqrt 

def solve(i): 
    b = -1 
    a = 1 
    c = 2 - 2 * i 
    val = (b**2) - (4*a*c) 
    sq = sqrt(val) 
    if int(sq) == sq: 
     return 1 
    return 0 

for _ in xrange(input()): 
    print solve(input()),

演示：

$ python so.py < foo.txt 
0 0 1 0

來源

2014-12-08 08:47:33

它，因爲你正在構建的C可能花費大量時間完成10個上升冪的數字序列。如果你分析序列的結構，你可以注意到一些模式。

該模式結合事實sum_ {i = 1}^n =（n + 1）* n/2給出下一個解，其中digit_pow_10函數可以直接確定，如果位置y的數字是1或0，而無需構建完整的序列。如果您需要更多的細節請聯繫我

import math 

def digit_pow_10(y): 
    n = int(math.sqrt(0.25+2*y)-0.5) 
    diff = y - int(n*(n+1)/2.0) 
    if diff == 1 or y == 1: 
     return 1 
    else: 
     return 0 

x = input() 
for i in range(x): 
    y = input() 
    a.append(y) 

for y in a: 
    print digit_pow_10(y),

來源

2014-12-08 08:48:34 jorgeluisrmx

無限序列。無法在1秒內處理答案

回答

相關問題