If 5*round(100/6) was the way to compute the result, then the entire
problem would be trivial, since the answer would always be n*round(100/n),
regardless of how the voters chose results.
You want round(5*100/6). Compute the percentage 5*100/6 = 83.333...% and
then round it to an integer number of percent: 83%.
This problem is asking about the rounded results shown in polls, such as:
What is your favorite color?
Red: 50%
Blue: 17%
Green: 17%
Yellow: 17%
These percentages add to 101%, because the percentage of those who selected
each response is rounded separately. The last three (assuming the 3-1-1-1
totals from the example) are each 16.666...% and they each round up to 17%.
The 50% from 3 voters out of 6 is exact, and nothing rounds down, so this
imbalance in rounding leads to results summing to 50+17+17+17 = 101 instead
of 100.
And the question is, what is the largest sum possible, given the total
number of voters and the votes cast by a portion of them.
On Wed, May 2, 2018 at 9:27 AM Samuel Jawahar <insidej...@gmail.com> wrote:
> Thanks a lot sir,5*round(100/6) is not valid?,in case1 it is
>
> On Wed, May 2, 2018, 17:39 Joseph DeVincentis <dev...@gmail.com> wrote:
>
>> No. If five people choose one language and one chooses another, than the
>> language with 5 people represents 5/6 = 83.33...% and you get 83 + 17 = 100.
>> If six people all chose different languages then each of six languages
>> would have 17% and the total would be 102, but that option is not available
>> due to the initial condition indicating three people chose the same
>> language.
>>
>> On Wed, May 2, 2018 at 7:14 AM Samuel Jawahar <insidej...@gmail.com>
>> wrote:
>>
>>> In Sample Case #3, one optimal scenario is as follows: each of the
>>> remaining two people chooses an unchosen language, so the rounded
>>> percentages add up to 50 + 17 + 17 + 17 = 101.
>>>
>>> if 5 people chooses same language and one person chooses different one
>>> then the result=102
>>> 5*17+17=102
>>> Regards
>>> Samuel
>>>
>>>
>>> On Wed, May 2, 2018 at 4:43 PM, Samuel Jawahar <insidej...@gmail.com>
>>> wrote:
>>>
>>>> In Sample Case #3, one optimal scenario is as follows: each of the
>>>> remaining two people chooses an unchosen language, so the rounded
>>>> percentages add up to 50 + 17 + 17 + 17 = 101.
>>>>
>>>> if 5 people chooses same language and one person chooses different one
>>>> then the result=102
>>>>
>>>> Regards
>>>> Samuel
>>>>
>>>> On Wed, May 2, 2018 at 3:23 PM, Samuel Jawahar <insidej...@gmail.com>
>>>> wrote:
>>>>
>>>>> 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/CAH5vfnNi4RKPFxrR9EhbE7tDEfmuO%2BJMP3S7WGj6jMvyaiMF%2BQ%40mail.gmail.com
>>> <https://groups.google.com/d/msgid/google-code/CAH5vfnNi4RKPFxrR9EhbE7tDEfmuO%2BJMP3S7WGj6jMvyaiMF%2BQ%40mail.gmail.com?utm_medium=email&utm_source=footer>
>>> .
>>> 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/CAMAzhziv5HeJLrUGz2MXQzwkSxi5Ngg646R%3D5xVX1sQGpB6BMQ%40mail.gmail.com
>> <https://groups.google.com/d/msgid/google-code/CAMAzhziv5HeJLrUGz2MXQzwkSxi5Ngg646R%3D5xVX1sQGpB6BMQ%40mail.gmail.com?utm_medium=email&utm_source=footer>
>> .
>> 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/CAH5vfnP-a3JajsdFPUtp00uusBdwhjnhbP4-UgoPDqM6X4_jRA%40mail.gmail.com
> <https://groups.google.com/d/msgid/google-code/CAH5vfnP-a3JajsdFPUtp00uusBdwhjnhbP4-UgoPDqM6X4_jRA%40mail.gmail.com?utm_medium=email&utm_source=footer>
> .
> 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/CAMAzhzj9_6ykQxiB1txVtG0iGe83hQknWdjDLScnT%3DX2i7voBw%40mail.gmail.com.
For more options, visit https://groups.google.com/d/optout.
