Hi, I think I test all the cases but I still get WA in set1. I really wish to
know why.
My idea is to use an array from 0~N to represent the number of language with i
votes
Ex, [ 1, 1, 3] => [0, 2, 0, 1] where there are two 1 vote language and a 3
votes language
And use backtracking algorithm to solve it.
---------
import math
class Solution:
def __init__(self, N, nums):
self.N = N
self.best = 0
self.records = {}
self.nums = [0] * (N + 1)
# use array to track the number of language with n votes
count = 0
for n in nums:
count += n
self.nums[n] += 1
self.chosen(self.nums, count)
def cal(self, nums):
total = 0
for i in range(1, self.N + 1):
if nums[i] == 0:
continue
total += nums[i] * round((100 * i) / self.N)
return total
def chosen(self, nums, count):
tp = tuple(nums)
if tp in self.records:
return
else:
self.records[tp] = True
# stop when count is N
if count >= self.N:
total = self.cal(nums)
if total > self.best:
self.best = total
return
for k in range(1, self.N + 1):
if nums[k] == 0:
continue
# add one to a language with k votes
nums[k + 1] += 1
nums[k] -= 1
self.chosen(nums, count + 1)
nums[k + 1] -= 1
nums[k] += 1
# add a new language
nums[1] += 1
self.chosen(nums, count + 1)
nums[1] -= 1
cases = int(input())
for T in range(1, cases + 1):
N, X = [int(s) for s in input().split(' ')]
nums = [int(s) for s in input().split(' ')]
solution = Solution(N, nums)
print('Case #%d: %d' % (T, solution.best))
--------------------
--
You received this message because you are subscribed to the Google Groups
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/google-code/66eb6217-cc8d-43d1-a5a3-70627bca70eb%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
