The "Rounding Error" problem of Round 1B of Google Code Jam 2018 is as follows:

The "Rounding Error" problem of Round 1B of Google Code Jam 2018 is as follows:

My Python code for the problem in as follows:

However, I get the 'Time Limit Exceeded' result event for the smallest test case. How can I speed up this solution?

The "Rounding Error" problem of Round 1B of Google Code Jam 2018 is as follows:

Problem

To finally settle the age-old question of which programming language is the best, you are asking a total of N people to tell you their favorite language. This is an open-ended question: each person is free to name any language, and there are infinitely many languages in the world.

Some people have already responded, and you have gathered this information as a list of counts. For example, 1 2 means that you have asked 3 people so far, and one picked a particular language, and the other two picked some other language.

You plan to publish the results in a table listing each language and the percentage of people who picked it. You will round each percentage to the nearest integer, rounding up any percentage with a decimal part equal to or greater than 0.5. So, for example, 12.5% would round up to 13%, 99.5% would round up to 100%, and 12.4999% would round down to 12%.

In surveys like this, sometimes the rounded percentages do not add up to exactly 100. After you are done surveying the remaining people, what is the largest value that the rounded percentages could possibly add up to?

Input

The first line of the input gives the number of test cases, T. T test cases follow; each consists of two lines. The first line consists of two integers N and L: the total number of people in the survey, and the total number of different languages represented among the people who have already responded. The second line consists of L integers C_i; the i^th of these is the number of people who said that the i^th of the represented languages was their favorite.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the largest value that the percentages could possibly add up to, as described above.

Limits

1 ≤ T ≤ 100.
1 ≤ L < N.
1 ≤ C_i, for all i.
The sum of all C_i values < N.
Time limit: 10 seconds per test set.
Memory limit: 1GB.

This is my Python solution. However, I get the 'Time Limit Exceeded' result even for the smallest test case. How can I speed up this solution?

My Python code for the problem in as follows:

from functools import reduce


def main():
    def gen_sums(total, freq, remaining):
        """Generate percentages' sums"""
        if not remaining:
            yield reduce(lambda x, y: x + (y*100+total//2)//total, freq, 0)
        else:
            seen = set()

            for i in range(len(freq)):
                if not freq[i] in seen:
                    yield from gen_sums(total,
                                        freq[:i] + [freq[i]+1] + freq[i+1:],
                                        remaining-1)
                    seen.add(freq[i])

            yield from gen_sums(total, freq+[1], remaining-1)

    T = int(input())

    for i in range(1, T+1):
        total_people, num_languages = map(int, input().split())
        languages_frequency = [int(x) for x in input().split()]

        if not 100 % total_people:
            print('Case #{}: {}'.format(i, 100))
            continue

        not_responded = total_people - sum(languages_frequency)

        max_percentage = max(gen_sums(total_people, languages_frequency,
                                      not_responded))

        print('Case #{}: {}'.format(i, max_percentage))

main()

However, I get the 'Time Limit Exceeded' result event for the smallest test case. How can I speed up this solution?

My Python code for the problem in as follows:

from functools import reduce


def main():
    def gen_sums(total, freq, remaining):
        """Generate percentages' sums"""
        if not remaining:
            yield reduce(lambda x, y: x + (y*100+total//2)//total, freq, 0)
        else:
            seen = set()

            for i in range(len(freq)):
                if not freq[i] in seen:
                    yield from gen_sums(total,
                                        freq[:i] + [freq[i]+1] + freq[i+1:],
                                        remaining-1)
                    seen.add(freq[i])

            yield from gen_sums(total, freq+[1], remaining-1)

    T = int(input())

    for i in range(1, T+1):
        total_people, num_languages = map(int, input().split())
        languages_frequency = [int(x) for x in input().split()]

        if not 100 % total_people:
            print('Case #{}: {}'.format(i, 100))
            continue

        not_responded = total_people - sum(languages_frequency)

        max_percentage = max(gen_sums(total_people, languages_frequency,
                                      not_responded))

        print('Case #{}: {}'.format(i, max_percentage))

main()

However, I get the 'Time Limit Exceeded' result event for the smallest test case. How can I speed up this solution?