2012 Canadian Computing Competition, Stage 2

Day 2, Problem 2: Sample Size

Someone whose name I don't want to remember was reading an article in the newspaper that mentioned the results of a poll. Upon seeing that the percentages that appeared in the article were all 25%, 50% and 75%, they thought that maybe the poll only included 4 people, and was then not very good.

In this problem, your task is to come up with a program that would make a similar analysis. In particular, given the percentages that appear in a newspaper article, it is your task to determine the minimum number of people that must have been interviewed in order for those percentages to be possible, assuming that percentages are rounded to the closest integer, with .5 rounded up (so, 1 of 3 people corresponds to 33%, 2 of 3 people corresponds to 67%, and 155 of 1000 people corresponds to 16%).

Input Format

The first line of the input file will contain an integer M between 1 and 100000 (inclusive). This represents the number of percentages that appear in the newspaper article you are analyzing.

M lines will follow, each of them containing an integer percentage P, 0 ≤ P ≤ 100.

Output Format

An integer N ≥ 1, the minimum number of people that must be interviewed for all of the percentages in the input to correspond to a fraction of those people.

Sample Input 1

3
25
50
75

Sample Output 1

4

Sample Input 2

2
33
67

Sample Output 2

3

All Submissions
Best Solutions


Point Value: 10
Time Limit: 2.00s
Memory Limit: 64M
Added: Jun 20, 2012

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, TEXT, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

EDIT: NVM it's probably a version thing.

Indeed. {} syntax for sets was introduced in Python 3.