1

我正在尝试解决此处描述的设备问题。我有一个解决方案，但它需要超过 2 秒的时间限制。我试图优化我的代码以提高速度，但无法在 2 秒的限制内完成。

import sys
import math

for line in sys.stdin:

    line = line.strip("\n").split(" ")
    numSwitches = int(line[0])
    numPics = int(line[1])

    wiring = {}
    inValid = False
    for i in range(numPics):
        if (inValid):
            break
        x = sys.stdin.readline().strip("\n")
        f_x = sys.stdin.readline().strip("\n")

        x_ones = 0
        f_x_ones = 0

        digit = 0
        for i in range(numSwitches):
            if f_x[i]=='1':
                digit += 2**(numSwitches-i-1)
                f_x_ones += 1

        for switch in range(numSwitches):
            if (x[switch]=='1'):
                x_ones += 1
                if not (switch in wiring.keys()):
                    wiring[switch] = digit
                else:
                    wiring[switch] &= digit

        if x_ones != f_x_ones:
            inValid = True
            break

    if not inValid:
        for i in wiring.values():
            if i==0:
                inValid = True
                break

    for possibilities in set(wiring.values()):
        frequency = wiring.values().count(possibilities)
        if frequency>1:
            oneBits = 0
            while (possibilities>0):
                oneBits += (possibilities%2==1)
                possibilities /= 2
            if oneBits < frequency:
                inValid = True
                break

    if not inValid:
        print math.factorial(numSwitches-numPics)%1000003
    else:
        print 0

我正在寻找有关我应该解决问题的方法的建议或关于如何优化当前代码的输入。

注意： 考虑以下测试用例：

3 2
110
011
011
011

我的代码发现以下方式无效。首先，在遇到第一张照片（110、011）时。接线字典被分配了以下键和值：

wiring[0] = 011
wiring[1] = 011

这意味着第一个和第二个开关可以点亮第二个或第三个灯。在遇到第二张照片（011、011）时。接线更新如下：

wiring[1] = 011 & 011 = 011
wiring[2] = 011

现在观察接线状态表明所有三个开关都可以点亮第二个和第三个灯。这是不一致的，因为 3 个开关必须点亮 3 个灯，这里我们有 3 个开关点亮 2 个灯。

4

1 回答 1

0

我认为这可能是一个解决方案，但我不确定，我明天可以解释更多

import numpy as np
from operator import mul

def apparatus(n, m, x, y):
    if not m:
        return np.math.factorial(n) % 1000003
    result = 1
    tmp = np.matrix([False] * x.shape[1])

    for i in xrange(x.shape[1]):
        if tmp[0, i]:
            continue
        tmp0 = np.prod(x[:, i] == x, 0)
        tmp1 = np.prod(x[:, i] == y, 0)
        if np.sum(tmp1) != np.sum(tmp0):
            return 0
        result *= np.math.factorial(np.sum(tmp1))
        result %= 1000003
        tmp += tmp1

    return result

x = np.matrix([[True, True, False]])
y = np.matrix([[False, True, True]])
print apparatus(3, 1, x, y)

x = np.matrix([[True, False, False, False], [False, False, False, False]])
y = np.matrix([[True, False, False, False], [False, False, True, False]])
print apparatus(4, 2, x, y)

print apparatus(1000, 0, [], [])
于 2015-11-22T23:21:35.700 回答