Hello Sir,
Rounding Error:-
My understanding is we need to maximize the sum of n values of 100/n,if it
is below 100%
please let me know ,my understanding is correct or not
Regards
Samuel
On Mon, Apr 30, 2018 at 8:33 AM, Si <sinze1...@gmail.com> wrote:
> 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 google-code+unsubscr...@googlegroups.com.
> To post to this group, send email to google-code@googlegroups.com.
> 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.
>
--
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 google-code+unsubscr...@googlegroups.com.
To post to this group, send email to google-code@googlegroups.com.
To view this discussion on the web visit
https://groups.google.com/d/msgid/google-code/CAH5vfnPCGD6YTXxPO5hKQs5QcaW-gkcZ8bNE5ALPoOZ2Vgcg%2Bw%40mail.gmail.com.
For more options, visit https://groups.google.com/d/optout.
