[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.
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
Read full article from [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.
时间复杂度O(n ^ 2)
1. 使用字典divDict统计d / c的个数（需要保证可以整除）
2. 计算d / c的值与a * b相互匹配，并且下标符合要求的a, b, c, d的个数
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
Read full article from [TopCoder]SRM 671 Div2 BearDartsDiv2 | 书影博客
