[TopCoder]SRM 671 Div2 BearDartsDiv2

题目描述:

Limak is an old brown bear who likes to play darts.

Limak just picked up an empty scorecard. He then threw a sequence of darts into a dartboard and for each dart he recorded the point value of the area it hit. You are given a int[] w containing the contents of Limak's scorecard: a sequence of point values.

Today there is a special jackpot. In order to win the jackpot, the player must present a scorecard with exactly four scores: (a, b, c, d). Additionally, these scores must be such that a*b*c = d. Note that order matters: the scores a, b, c, d must have been obtained in this particular order.

Limak wants to erase all but four scores from his scorecard in such a way that he will win the jackpot. Compute and return the number of different ways in which he can do that.

题目大意:

Limak是一只喜欢玩飞镖的老棕熊。

Limak拿了一个空的记分卡,然后向记分卡投掷一组飞镖,并记录每次投掷的得分。给定一个int[]数组w,包含Limak的记分卡的内容:一组得分值。

今天设置了一个特别大奖。要赢得特别大奖,玩家必须提供一个包含4个得分(a, b, c, d)的记分卡。此外,这些得分必须满足a*b*c = d。注意需要考虑顺序:得分a, b, c, d必须以这个特定的顺序获取。

Limak想要从记分卡上擦去多余的得分只留下4个,来赢取大奖。计算并返回满足条件得分的可能方式。

解题思路:

时间复杂度O(n ^ 2)

1. 使用字典divDict统计d / c的个数(需要保证可以整除)

2. 计算d / c的值与a * b相互匹配,并且下标符合要求的a, b, c, d的个数

Python代码:

class BearDartsDiv2(object): 
    def count(self, w): 
        import collections 
        divDict = collections.defaultdict(int) 
        size = len(w) 
        for x in range(size): 
            for y in range(x + 1, size):
                if w[y] % w[x] == 0:
                    divDict[w[y] / w[x]] += 1 
        ans = 0 
        for x in range(size): 
            for y in range(x + 1, size): 
                if w[y] % w[x] == 0: 
                    divDict[w[y] / w[x]] -= 1
            for y in range(x):
                ans += divDict[w[x] * w[y]]
        return ans

 

本文链接:http://bookshadow.com/weblog/2015/10/15/topcoder-srm-671-div2-bear-darts-div2/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

如果您喜欢这篇博文,欢迎您捐赠书影博客: ,查看支付宝二维码